🔒 Locked

Basic concepts about encryption/cryptography ?

Started by CosmoKramer Aug 23, 2005 at 11:14 AM 15 replies 2.5k views

Original Post

Aug 23, 2005 at 11:14 AM

Ever since I was about 12 years old, I have tinkered with rudimentary encryption schemes. I remember me and my brother came up with this 'code' that none of our friends could crack - it was something rediculously easy like: A is UT B is RP C is QN ... Z is SK Then we could write messages back and forth like "UTGHGH DSTYEKRKDS" or whatever. Like I said, none of our friends could crack it, but on the other hand: our friends were about 12 years old as well, and plus I dont think they even ever tried to crack it... Anyway, when I got to university, I got my first taste of 'real' encryption, using mathematics. Specifically, we learned about RSA encryption, which works based on the concept that it is easy to multiply 2 huge numbers together to get a double-huge number, but it is hard to factor the double-huge number back into the 2 huge numbers. If Im not mistaken, this is when you get into 40bit encryption, 128 bit encryption, and 1024 bit encryption, an these numbers basically have to do with the size of the numbers you are multiplying around, ie the strength of the encryption. This is the kind of thing that banks, and browsers and top secret government people use to encrypt their important data. What I want to know, is what is the fundamental difference between the kind of enryption I did when I was 12 (lets call it encraption for the sake of argument), and this fancy mathematical encryption? For example, is my encraption equivalent to 4 bit encryption or something? I guess I just dont understand how encryptions can be cracked. Take RSA encryption for example - the problem is 2-fold. For one thing, you have to have a lot of brute force processing power to factor the number and find the right key. Ok sure thats the part I understand, and thats the part that sort of 'guarantees' how strong the encryption is. But before you even get to brute-forcing the code, dont you have to know what kind of encryption it is? For example, if you came accross this piece of data that I was sending to my brother: 3150989050148843490751480392850178423095179048390... If you knew it was RSA encrypted using 128 bit encryption, then you could set your computer to work cracking it, and expect an answer in (what? days? weeks?). But who says its RSA128? It might be another one of my stupid encraptions, like this: A is 3150 B is 5014 C is 1480 ... Z is 0938 Sure, this encraption is naive and I wouldnt trust it to send my credit card info over the net or anything, but how could someone possibly go about cracking it, without knowing what algorithm I used? Someone could have the most powerful computer in the world, and it would never solve this encraption, if they were using the wrong algorithm to crack it, for example if they assumed I was using RSA and I'm not. When I was between 12-years old and university-years old, I came up with slightly more complicated encraptions. For example, Take your input string: "Hey bro this tests my new encraption method" and.. 1) convert it to binary 2) reverse it 3) split it into chunks of 8 bits at a time 4) reverse each 8 bit chunk 5) convert it back to ascii, to get a jumbled (coded) string I can make it arbitrarily complex by just adding more steps between 1 and 5, as long as those steps can be reversed in the decryption process. How would such an encraption as this stack up against a 'real' encryption? Unless I published my algorithm on how to encrypt it, how could anyone possibly crack the code? This encraption doesnt rely on the fact that it takes tons of processing power to do something (eg factor a number), but instead it relys on the fact that no one knows what algorithm i used to encrypt it. Again, you could have the fastest computer in the world, but how would it help you unless you told it what to do?

meh

Aug 23, 2005 at 11:26 AM

There are lots of techniques you can use to break simple substitution ciphers like the one you suggest.

If you have a good idea about the language or contents of the message a study of the frequency of each individual part occuring is generally enough to give you a good idea of what each codeword represents in plaintext. For example e is the most common letter in the english language.

Adding in factors such as more steps, multiple substitutions for each letter and other tricks make it harder to crack. Enigma basically worked as your example does but let the operator change bits depending on a key. It was a fairly strong cipher but it was breakable because it was used by people. For example they used to use a day key and message key and the intial part of any message would be the message key repeated. By studying the messages in sufficent quantity the guys in GCHQ were able to notice this repetition and start breaking the code down. Another example is that the allies would know that a message sent at a certain time of a certain length was likely to be a weather report, in a standard format and as such you know enough about the message to start decrypting it.

I also did a module in Encryption at Uni, probably one of my favourite bits of maths as its very easy but also pretty damn clever.

In the end all that is required to break a code is time. The difference between schemes such as 8-bit RSA, 1024-bit RSA and your 12 year old effort is the amount of time it'll take.

The Code Book - Simon Singh - Great book.

benryves

526

benryves

Aug 23, 2005 at 11:28 AM

Quote:
Original post by meh
The Code Book - Simon Singh - Great book.

Seconded. A very interesting read.

CosmoKramer

Author

CosmoKramer

Aug 23, 2005 at 11:35 AM

Thanks for the info meh. Makes sense but I still have some questions. Ill have to check out that book...

Quote:
Original post by meh
In the end all that is required to break a code is time. The difference between a scheme such as RSA and your 12 year old effort is the amount of time it'll take.

Ok I guess I knew this deep down. With enough time you could do just about anything.

But my theory is that it would take MORE time to break my 12 year old encraption than RSA.
Why?

If its RSA then the crackers can just say 'Ok start the RSA decryption software and lets go to lunch while it runs'.

But for my 12 year old encraption, the crackers have to sit down and try to think what my message could possibly contain, then look for patterns, then try different things, etc etc. In other words it would take actual work.

Is this accurate?

thanks again!

meh

Aug 23, 2005 at 11:37 AM

Well that's where the skill of the person doing the decrypting comes in. Anyone worth their salt given an unknown message encrypted by an unknown algorithm will probably start with the most basic encryption and work towards more exotic methods is their initial probing fails.

If the persons workflow was to start with RSA then yes it would take longer to break (since they'd have to fail with using RSA first!).

xor

Aug 23, 2005 at 11:40 AM

Your initial encraption is easily crackable with pencil and paper.
Statiscally in each language each letter occurs a certain amount of times in a given text. The decryption process can be improved if we have a context(subject of the message, origin of the person writing it, etc).
You basicaly count all the letters 'a', in a book for instance, then all the letters 'b' and so on, and then calculate the percentage of each letter, there are actually online databases of this kind sorted by subject(sci-fi, CS, movies, etc). To decrypt the message you calculate the percentages of each pattern in the encrypted message and subtitute the patterns with the letter with the closest percentage to it.

This method isn't exactly science, several letters will fail it's target and you'll have to guess where they should be instead, and if the message is short enough and with no context, you might not even be able to decrypt it.

RSA 128 is currently deprecated, you might thinking about AES128 or some other symetric encryption scheme or hash. I belive a few years back the advisable encryption sugested for RSA was 256/512 for domestic use, 512/768 for companies, and no less then 1024 for the government(this would be the US government, since the article was directed at US citizens).

CosmoKramer

Author

CosmoKramer

Aug 23, 2005 at 11:42 AM

Oh yea and the main thing I want to know is this:

when you say 128 bit encryption, the 128 basically means the size of the numbers you are dealing with, correct? So in other words, basically means 'how long it will take to crack', or 'how much processing power is needed', or something like that anyway, right? Basically, the bigger the number, the better.

Is there some sort of equivalent measurement for 12-year-old-encraption type schemes? Like some kind of formula that incorporates how many code characters you use per real character, and how many steps you use, and other factors? For example, if I come up with a pretty crazy series of steps to encrypt a string, is there any way you could analyze my algorithm and say 'this is equivalent to 38 bit encryption strength'?

For x-bit encryption, can I write an encraption that is just as strong (strong meaning time to crack it) by adding an arbitrary number of steps to my encraption process?

xor

Aug 23, 2005 at 11:46 AM

The number(128, 256, 512, ...), is usually the size of the key used in the encryption, and the size of the key usually is directly proportional to the security of the cipher.

About your latest encraption, you don't seem to use a key, so it boils down to security through obscurity. Is broken by figuring out the algorithm through study of the messages and their context.

DrSpock

Aug 23, 2005 at 11:47 AM

I think its easier than that.

With your scheme, you would have to communicate the complete key ( or code book ) to your system with anyone that wanted to decrypt it. And if that key was intercepted, your encryption is as good as plain english.

RSA is a public key encryption, where a component of the encryption can be communicated and even if intercepted, decrypting the ciphertext is not simple.

xor

Aug 23, 2005 at 11:55 AM

Quote:
Original post by DrSpock
RSA is a public key encryption, where a component of the encryption can be communicated and even if intercepted, decrypting the ciphertext is not simple.

If key exchange is intercepted, decrypting just RSA encrypted messages is trivial, look into 'man in the middle' attack. Ence the need for digital signatures.

kSquared

192

kSquared

Aug 23, 2005 at 11:57 AM

Quote:
Sure, this encraption is naive and I wouldnt trust it to send my credit card info over the net or anything, but how could someone possibly go about cracking it, without knowing what algorithm I used? Someone could have the most powerful computer in the world, and it would never solve this encraption, if they were using the wrong algorithm to crack it, for example if they assumed I was using RSA and I'm not.

That is correct. However, in practice it's usually very easy to determine if you're using a cipher or not. Additionally, if it is known that the cipher translation is a k-digit number, the code becomes extraordinarily easy to crack. And all substitution ciphers are invariably vulnerable to cracking by frequency analysis.

For instance, if it is observed that you transmitted 401 digits and it is known that you don't use any padding, and that you're using an unknown substitution cipher, you must have transmitted either exactly 1 or 401 symbols. For instance, consider your example below:

Quote:
For example, if you came accross this piece of data that I was sending to my brother:

3150989050148843490751480392850178423095179048390

This sequence is 49 characters long. If that is all that was transmitted, it becomes immediately obvious that you transmitted 1 character, 7 characters, or 49 characters going under the assumption that each cipher encodes characters to the same symbol length. Using so many digits for 1 character seems frivolous; likewise, it is unlikely that you were able to send a meaningful message using only ten different letters. 7 is therefore the obvious choice. I've already uncovered a wealth of information about your cipher using just 7 symbols from it, without knowing anything about what the message is.

Quote:
How would such an encraption as this stack up against a 'real' encryption? Unless I published my algorithm on how to encrypt it, how could anyone possibly crack the code?

An arbitrary letter-substitution cipher can be easily solved by a modern computer with sufficient input. Because there are a finite number of potential substitutions (26, in the case of case-insensitive alphabetic messages), any message of 26 or more characters will contain repeating elements. (This also means that an arbitrary cipher-cracker cannot guarantee a successful result without knowing that at least 27 characters have been transmitted.) You could get around this by never sending more than 27 characters with a given cipher, but this in turn limits how much useful information you can convey.

Cypher19

139

Cypher19

Aug 23, 2005 at 1:26 PM

Quote:
This sequence is 49 characters long. If that is all that was transmitted, it becomes immediately obvious that you transmitted 1 character, 7 characters, or 49 characters going under the assumption that each cipher encodes characters to the same symbol length. Using so many digits for 1 character seems frivolous; likewise, it is unlikely that you were able to send a meaningful message using only ten different letters. 7 is therefore the obvious choice. I've already uncovered a wealth of information about your cipher using just 7 symbols from it, without knowing anything about what the message is.

...with just an assumption. You forgot about the possibility that there may be an introduction character that is basically "Begin message", similar to the 00 in the cipher in Sphere. If, say, 3 by itself is the start of the message, then you've got a 48 character long set, which could be 2, 3, 4, 6, 8, 12, 16, 24 or 48 characters unencrypted.

Anyways, we'd probably have to see multiple messages to try and find consistencies and patterns in what you're sending.

But even really difficult home-made ciphers can be uncovered given enough time. For example, 'alien language 2' in Futurama is actually partially mathematically based, and I don't think anyone was given any clues as to what source messages was (unlike 'alien 1', in which the pilot had 5 alien characters on a slurm advertisement that people could figure out easily, as that same ad appeared elsewhere in the episode with english) but they still figured it out eventually. It took them several months, but they got it!

SamLowry

Aug 23, 2005 at 1:48 PM

And for anyone who's in the mood for a boring read... Download the Handbook of Applied Cryptography (yes legal).

AFAIK, not knowing which algorithm is used should make decryption a lot harder, but how often is this the case?

ApochPiQ

1,378

ApochPiQ

Aug 23, 2005 at 4:30 PM

You've basically got three families of encryption schemes. The first is substitution, where one block of input data is transformed into a corresponding block of output data. Essentially this is a mathematical function. Although sophisticated substitution schemes are capable of non-homogenous mappings (i.e. not one-to-one), they are still highly subject to statistical analysis, and will invariably produce very easily recognizable patterns. I've met a couple of machine-code wizards who could look at a binary file and recognize obfuscated string data and actual machine code, which is a testament to the power of analysis and pattern detection.

The next "level" is deterministic transformation, where you don't necessarily have a table mapping a given input to a given output. Instead, there is an algorithm that does this, usually making decisions based on the input and selecting one of many different sub-transformations. However, the important distinction is that the mapping is still fundamentally linear. The OP's "slightly more complicated algorithms" fit this category. Because the mapping is still linear (although not necessarily homogenous) it is possible, given enough sample data, to reconstruct patterns and arrive at the original algorithm. This is the family of "encryption" methods that most homebrew, security-by-obscurity type solutions use. It is considerably more difficult for an amateur to crack than straight substitution, but it will only add a marginal amount of challenge to a properly educated codebreaker.

The only genuinely strong level is nonlinear encryption. This is actually related to hashing (SHA, MD4/MD5, et. al.). Basically, you have an algorithm that is fundamentally irreversible (hashing) or extremely hard to reverse without all the pieces (public key systems). I would imagine there are some others out there, and for sure there are methods as yet undiscovered, but The Big One is public key.

Comparing bit-strengths across families is meaningless. It's essentially impossible to generalize how "strong" two specific encryption schemes are in relation to each other or in absolute terms. The best you can do is estimate strength primarily by family of algorithm and secondarily by sophistication; for public-key systems, bit-strength tends to be the most useful benchmark of sophistication. However, it has been known to happen that encryption systems are very clever and yet fall apart due to their fist - their unique, subtle fingerprints that leave them open to statistical analysis, or make them far less secure than theoretically possible.

Anyways, I'm not anything close to properly edumacated on encryption, but there's what I know - horribly incorrect terminology and all [smile]

jfclavette

138

jfclavette

Aug 23, 2005 at 4:36 PM

For an interesting novel that offers some insights on cryptography, I heartily suggest Neal Stephenson's Cryptonomicon.

kSquared

192

kSquared

Aug 23, 2005 at 7:33 PM

Quote:
Original post by Cypher19
Quote:
This sequence is 49 characters long. If that is all that was transmitted, it becomes immediately obvious that you transmitted 1 character, 7 characters, or 49 characters going under the assumption that each cipher encodes characters to the same symbol length. Using so many digits for 1 character seems frivolous; likewise, it is unlikely that you were able to send a meaningful message using only ten different letters. 7 is therefore the obvious choice. I've already uncovered a wealth of information about your cipher using just 7 symbols from it, without knowing anything about what the message is.

...with just an assumption. You forgot about the possibility that there may be an introduction character that is basically "Begin message",

No, I didn't. You missed the part above that where I said

Quote:
"... For instance, if it is [...] known that you don't use any padding, ..."

If there is no padding as my assumption states (as would be the case if you didn't have extraneous characters), then indeed the assessment of 7 characters is the reasonable and correct one.

Nemesis2k2

116

Nemesis2k2

Aug 24, 2005 at 3:11 AM

Quote:
I've met a couple of machine-code wizards who could look at a binary file and recognize obfuscated string data and actual machine code, which is a testament to the power of analysis and pattern detection.

If you spend a lot of time doing this kind of stuff, you can get to levels others would percieve as psychic. There's simple stuff like getting an impression of whether or not the data is most likely compressed/encrypted based on the density. As you go on it becomes easy to recognise machine code from regular data extremely quickly, even if you don't know the instruction set or the architecture. Uncompressed graphics in perticular become easy to recognise, as you can notice the patterns of data blending together, and segments carrying on in an orderly fashion, which doesn't occur in purely mathematical data. Sound data can also be easy to recognise due to it's wave-like nature, perticularly in sections where there is little sound being played, such as the beginning and end of a sample commonly.

Eventually it becomes trivial to differentiate between code and different types of data, even when they're packed together in a single block, such as in embedded and cartridge-based systems. Memory dumps in perticular become trivial to parse, and you can find the most probable locations for a given block of data or variable simply by jumping through sections of the file and stopping when you come to it (eg, finding a single integer you're looking for, which you don't know the value or the location of, in an 8MB memory dump of which you know nothing about the structure beforehand, within 5 minutes). If you spend waaaay to long doing this kind of stuff, you can recognise data after it's been through various basic operations (eg, a string after an XOR with a certain value), and you can start to recognise common manipulations of data on sight (eg, data compressed with common compression schemes).

Around the time you start reading basic flow control machine code instructions for certain processors, and decoding compressed/manipulated data in your head is the time you suddenly realise you really need to get out more. When you start figuring out machine code instructions you don't know from others you do, and deriving accurate modified algorithms for data manipulation from the source data alone, you start getting a little bored with most challenges, as it's now just a matter of going through the motions (a lot of them, over a long period of time), or staring at effectively unbreakable encryption expecting the cypher to just jump into your head (which of course it doesn't). At this point, you put hacking on the backburner and immerse yourself entirely in a different but related area, such as games programming.

Or so I've heard.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.