cracking codes

This is very probably a totally simplistic way of looking at the problem we have of secure communications - sending messages without some government snooping into our private mail. However, I know there are some super clever folk on here so I thought I would describe what I have been thinking about and see if there is some way which is simple yet NSA-proof (even if they are monitoring our every move).

You remember the WWII secret codes which were based on a book? You made up your message from words in a book - page x, word y for each of the words in your message. Was this a good cypher? Could the NSA or whoever with their supercomputers crack these types of codes now? Maybe if they had the same book and they knew which book was being used.

It seems to me that mathematically-based codes and methods of encoding mass-communications like https:// encoded web communications are now relatively simple to crack because you just have to throw masses of computing power at the problem and eventually it will be cracked. What we need is something which is not maths-based and relies on two parties knowing the same information which is used to encode the messages.

So, say we had a large block of text which consisted of random words, the characters were mapped and placed in a list.

A appears at positions 1,3,6,19
B appears at positions 5,9,26
T appears at positions 7

the message could be encoded as 005,006,007 as the word BAT
but later in the same message it could equally be coded as 026, 001, 007 which would also be the word BAT

Any character could be in any position in the block of text you and your partner decided to use.
How could the supercomputer know or find out where the characters were in the text block and what numbers referred to which letters?

a reply to: qmantoo

When I was in college, people majoring dual majoring in computer science and math would take Cryptology which talked about all of this stuff. Unfortunately I didn't dual major in Comp Sci and math (though I probably should have, I took enough math courses to not make it a huge stretch).

a reply to: qmantoo

Is your conversation about Starbucks today important enough to code and send to your friend? I would say this would be sufficient if you had secret conversations but the NSA doesn't care about what you bought at the store....

During World War I, families used to do something similar with wartime newspapers (the post office would deliver them free to their relatives on the front line). Each sender would create secret message by using a needle to mark little holes beside the pre-existing letters of an article in order to compose their message. The wartime censor would only have time to check that it was an official newspaper and had no written text. So that system definitely worked.

With modern digital files, you could use something like a Linux DVD ISO files as the reference block and simply mark the byte offset and length for each part of your message. Maybe even a skip number where you skip every fixed number of bytes.

There's another way where you could convert your message into a large number and try and find which prime number could be used to represent those bytes. Like the "illegal prime number" used to encode DeCSS

en.wikipedia.org...

a reply to: Chrisfishenstein

So the fact that you dont consider my coffee review to be secret enough means that we should not have the ability to make it secret if we want to?

originally posted by: qmantoo

This is very probably a totally simplistic way of looking at the problem we have of secure communications - sending messages without some government snooping into our private mail. However, I know there are some super clever folk on here so I thought I would describe what I have been thinking about and see if there is some way which is simple yet NSA-proof (even if they are monitoring our every move).

You remember the WWII secret codes which were based on a book? You made up your message from words in a book - page x, word y for each of the words in your message. Was this a good cypher? Could the NSA or whoever with their supercomputers crack these types of codes now? Maybe if they had the same book and they knew which book was being used.

It seems to me that mathematically-based codes and methods of encoding mass-communications like https:// encoded web communications are now relatively simple to crack because you just have to throw masses of computing power at the problem and eventually it will be cracked. What we need is something which is not maths-based and relies on two parties knowing the same information which is used to encode the messages.

So, say we had a large block of text which consisted of random words, the characters were mapped and placed in a list.

A appears at positions 1,3,6,19
B appears at positions 5,9,26
T appears at positions 7

the message could be encoded as 005,006,007 as the word BAT
but later in the same message it could equally be coded as 026, 001, 007 which would also be the word BAT

Any character could be in any position in the block of text you and your partner decided to use.
How could the supercomputer know or find out where the characters were in the text block and what numbers referred to which letters?

If the keys are large enough, the encoding of the word Bat would be as you said anyway. Let's say the key is a 1000 characters and the text being sent is 1000 characters, chances are any letter will not show up as the same encrypted letter twice. Problem is that using keys the size of the message take a little over twice the time to send.

Randomized key seeding is where it's at!

Cheers - Dave

a reply to: bobs_uruncle

Time is not that important if one is more concerned with secrecy and megabytes take only a few minutes to send. In the search for perfection, then yes itwould be nice to have fast and secure comms. I dont see how the supercomputers could determine the message if it is not mathematically encoded.

a reply to: qmantoo

What we need is something which is not maths-based and relies on two parties knowing the same information which is used to encode the messages.

Where both parties share a common secret to encrypt/decrypt the message it's called symmetric encryption. Protocols such as https use asymmetric encryption, which means that messages can be encrypted with a private key and decrypted with the corresponding public key, or encrypted with the public key and decrypted with the private key. The server keeps the private key secret and their public key is spread widely by attaching it to their ssl certificate. Think of it like a key and padlock. The server keeps the key but anyone can get a copy of the padlock and lock their data using it, then send it back to the server, who can unlock the data with their secret private key. So in this way the server doesn't have to share a unique secret with every person and keep track of all the encryption keys. Even though anyone can encrypt data using the public key, it's very hard to decrypt data using the same key it was encrypted with, which is why it's called asymmetric.

Symmetric encryption is typically used on top of asymmetric encryption to make it stronger. There are in fact many good symmetric encryption algorithms which even the best supercomputers cannot crack. If you're using a cryptographically secure algorithm such as AES256 and you use a very long and complicated password you can be pretty sure it wont be cracked any time this decade. Just look at the encrypted Wikileaks insurance files which have been floating in wild for many years now and still haven't been cracked. Usually it all comes down to the strength of your password. However, having said that, there is a not so well known and not widely used type of symmetric encryption algorithm which is capable of offering so called "perfect secrecy". It is the algorithm I would personally use to encrypt something if I wanted to ensure absolutely no one would ever crack it. It is called the one-time pad technique:

In cryptography, a one-time pad (OTP) is an encryption technique that cannot be cracked if used correctly. In this technique, a plaintext is paired with a random secret key (or pad). Then, each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition. If the key is truly random, is at least as long as the plaintext, is never reused in whole or in part, and is kept completely secret, then the resulting ciphertext will be impossible to decrypt or break.[1][2][3]

In other words you just generate a random string (called the pad) of equal length as the data you want to encrypt and then combine both strings with the xor operation or modular addition as Wikipedia suggests. The result is a completely random encrypted string which can only be decrypted using the original random string. If you tried to guess every possible random string you would discover that you could make the decrypted message say anything because the random string is as long as the original message. In this way it offers plausible deniability in the case anyone does manage to decrypt it, there's no proof they actually decrypted it using the right key.

The main issue with the one-time pad technique seems to be that it's inconvenient to have an encryption key which is the same length as your message. However in my opinion that is easily solved by using a short seed key which is then used by a PRNG to generate a random string of length equal to the message being encrypted. As long as the seed key is long enough the encryption will be virtually impossible to break, so it would act like a normal encryption password. The other issue with the one-time pad is the fact that the same encryption key can only be used once. However this is also be solved by concatenating a random salt string with the seed key before generating the pad. Then the salt string is appended to the resulting pad so that it can be used for decrypting the file.

PS - I have implemented the algorithm I just explained in PHP. Anyone interested can PM me for a link.

originally posted by: qmantoo
Any character could be in any position in the block of text you and your partner decided to use.
How could the supercomputer know or find out where the characters were in the text block and what numbers referred to which letters?

You couldn't decrypt a three letter message like "bat" very easily.

But if they knew the language was English and the message was long enough, you just apply letter frequency statistics like the savvy participants on Wheel of Fortune used.

Some letters appear more frequently than others, so you just do a statistical analysis, and if the frequency order doesn't match exactly it doesn't matter because you're using computers so it's fast to check similar but different orders:

Letter frequency

Herbert S. Zim, in his classic introductory cryptography text "Codes and Secret Writing", gives the English letter frequency sequence as "ETAON RISHD LFCMU GYPWB VKJXQ Z", the most common letter pairs as "TH HE AN RE ER IN ON AT ND ST ES EN OF TE ED OR TI HI AS TO", and the most common doubled letters as "LL EE SS OO TT FF RR NN PP CC".[2]

The "top twelve" letters comprise about 80% of the total usage. The "top eight" letters comprise about 65% of the total usage.

Now if you could figure out a way to make "Q" the most common letter in the message instead of "E" then this method wouldn't work. For that you might need to use more than one encryption algorithm.

Sounds like Herbert S. Zim's book might be an interesting read but I haven't read it.

originally posted by: qmantoo
You remember the WWII secret codes which were based on a book? You made up your message from words in a book - page x, word y for each of the words in your message. Was this a good cypher?

Yes. SOE agents would memorise a sentence and that would provide the key, so only they could decode message. It may have been why agents were so aggressively tortured by the Gestapo because to discover the key enabled them to uncover past messages.

en.wikipedia.org...

originally posted by: qmantoo
a reply to: Chrisfishenstein

So the fact that you dont consider my coffee review to be secret enough means that we should not have the ability to make it secret if we want to?

Not at all! If you would like, go for it...I am just saying are your conversations important enough to be secretive by sending a book to your friend to decipher your codes through email...That's all I am saying...Don't know too many people who would be willing to decipher a code over telling someone about your trip to Mickey D's today....

There is one code that I know of that was never cracked during WW2. It was used by the Navajo code talkers.

Code talkers

originally posted by: qmantoo

This is very probably a totally simplistic way of looking at the problem we have of secure communications - sending messages without some government snooping into our private mail. However, I know there are some super clever folk on here so I thought I would describe what I have been thinking about and see if there is some way which is simple yet NSA-proof (even if they are monitoring our every move).

You remember the WWII secret codes which were based on a book? You made up your message from words in a book - page x, word y for each of the words in your message. Was this a good cypher? Could the NSA or whoever with their supercomputers crack these types of codes now? Maybe if they had the same book and they knew which book was being used.

If it's a fully random one-time pad then no. The problem is the 'one-time' pad business. Book codes which get re-used can be analyzed by recognizing patterns from repeated messages, or from different parts of very long messages.

Since now people & machines need to transmit terabytes of data you can only get this by having 'books' which are effectively cryptographically generated mathematically and not fixed.

there a one time pad generator at:

One-time Pad Generator

you can give it specific information to make it gen the same numbers, so you can give a friend a password and word length to input and it will gen the same numbers. so as long as the password is kept secret. the one time pad is secret and your msg for the long run will be secret.

When you spend a bit of time looking at cryptography you realise that nothings impossible to crack its just the time and effort needed, even 1 time pads can be done but its the verification thats the problem

originally posted by: Maxatoria
When you spend a bit of time looking at cryptography you realise that nothings impossible to crack its just the time and effort needed, even 1 time pads can be done but its the verification thats the problem

When something requires the energy of a thousand suns and a billion years to crack, it may not be impossible, but it's close enough to impossible that people can safely rely on it. When you study cryptography long enough you realize that it's not like in the movies where they can crack every possible code in a matter of hours or minutes. Also, there's absolutely no way to crack the one-time pad technique if it's done properly. If the pad is a few hundred characters long you know it's going to take longer than the age of the universe to even try all the possible combinations. But there is absolutely no point to trying out all the combinations because you can't verify which one is correct.

a reply to: qmantoo

You remember the WWII secret codes which were based on a book? You made up your message from words in a book - page x, word y for each of the words in your message. Was this a good cypher? Could the NSA or whoever with their supercomputers crack these types of codes now?

You have to remember that encryption has progressed by 70 years since then.
Codes using words from a book would be cracked in a few seconds by their computers.
Codes like 'true crypt' are still thought to be safe against the NSA since the time and computing power needed brings the result in thousands of years. To late to be of any use.

There was a case a couple of years back where a judge jailed a man because he would not give up the password to his encrypted hard drive.
They had him for kiddy porn and suspected the drive contained more of the same.
His stand was based on the right to not self incriminate.