OSDev.org

Guessing whether you got the correct plaintext out of a brute-force attack is much easier than you think. Most documents have a very non-random distribution of values. (Text, for example, uses only ~60 out of 256 possible byte values.) If you have the wrong key, the outcome is random...

Solar wrote: Guessing whether you got the correct plaintext out of a brute-force attack is much easier than you think. Most documents have a very non-random distribution of values. (Text, for example, uses only ~60 out of 256 possible byte values.) If you have the wrong key, the outcome is random...

I was thinking about this a few weeks ago. Even if the sample text itself is non-random, the encrypted ouput of that text seems like it would be pretty random (if you don't try to Base64 encode it or anything, and just take the straight-up byte values you get as output).

So what would happen if you encrypt the encrypted output, either with the same or different key. Anybody who didn't know that you did that who was trying to brute-force would assume that there was only one level of encryption, and would never get ay plaintext out and it seems like that would make it hard to guess when the brute-force was successful.

Even if they did know that you encrypted it twice and that they would have to apply brute force twice, if the data they're looking for is random in distribution, I still don't see how they'd know that they hit on the right one.

On the other hand, I know that the math involved in the equations deals with very large exponential and modular math, so maybe it's as simple as seeing if the output from the equation gives you somthing between 0 and 255, instead of some number with 10 digits in it...

So what would happen if you encrypt the encrypted output, either with the same or different key.

Let me tell you a story.

In 1928, Germany started using a strange new cipher that no-one seemed to be able to de-cipher. It was the Enigma engine, which used a so-called "substitution cipher". Three rotors resulted in 26 x 26 = 676 possible substitution "alphabets".

Then some guy named Willi Korn came up with the idea of increasing complexity by adding a "reflector" - effectively running the enciphered letter and run it through the machine again.

On the upsite, you now hat 26 x 26 x 26 = 17576 possible substitution alphabets.

On the downside, this meant that "A" as input could never be encrypted to an "A" in output, and that if "A" resulted in "X", then "X" would result in "A".

Enigma was broken eventually, in no small part because of this weakness.

Another point:

Anybody who didn't know that you did that...

This is called "security through obscurity", and it wouldn't work. If your cypher software is available to the public, you just had to disassemble it to find out. If your cypher software is not available to the public, your security depends on every single person who has access to your cyper software, the security of that person's computer, communication lines, physical security of the house where the software is kept.

What am I trying to say? Easy: Do not approach cryptography with a "this should work" mindset. It is a highly sophisticated science. Do not use homebrewed algorithms.

Solar wrote: This is called "security through obscurity", and it wouldn't work.

What am I trying to say? Easy: Do not approach cryptography with a "this should work" mindset. It is a highly sophisticated science. Do not use homebrewed algorithms.

I'm not talking about a "homebrew" software approach. I'm talking about using existing algorithms and software and just running them through a second time, the idea being that it would be harder to detech the correct decryption because they would still be getting "garbage" out instead of readable text. And you left out the part where I referred to "even if they did know that you encrypted it twice," the point of that being that it wasn't dependent on keeping the method obscure.

As far as the "this should work" mindset, I don't see how doing this would make it worse. I haven't read anything about any of the current public key cryptosystems having any weakness related to the re-encryption of encrypted data. So even if it doesn't "work", all I've done is wasted a few seconds doing an extra encryption step, and even if it only makes it a little harder to determine when the plaintext of the first decryption step has been reached, one might consider that worthwhile.

bkilgore wrote:

Solar wrote: This is called "security through obscurity", and it wouldn't work.

What am I trying to say? Easy: Do not approach cryptography with a "this should work" mindset. It is a highly sophisticated science. Do not use homebrewed algorithms.

I'm not talking about a "homebrew" software approach. I'm talking about using existing algorithms and software and just running them through a second time, the idea being that it would be harder to detech the correct decryption because they would still be getting "garbage" out instead of readable text. And you left out the part where I referred to "even if they did know that you encrypted it twice," the point of that being that it wasn't dependent on keeping the method obscure.

What's the difference between running it once or twice? A different mapping. Running it twice is equal to running a different algorithm once.

About rounds:

Encryption basically is a transformation from some codespace C(p) to another codespace C(e), possibly (and probably) equal. C(e) needs to contain at least as many codewords as C(p) to make it possible to encrypt any text and decrypt it again without loss, while C(p) needs to contain as many as C(e) to make the inverse possible.

Making a translation table is possible for short keylengths. Everytime the keylength increases by 1 bit, the translation table more than doubles in size. You can make a 8-bit translation table in .25 KiB, a 16-bit one in 128KiB, but where a 32-bit one already takes 16GiB a 64-bit one couldn't be stored on any home computer. This implementation method is the fastest possible however, it allows you to just lookup any value, making each N-bit encryption a mere table lookup, usually about a single cycle in length (not counting memory access times).

Since it's not possible for larger keylengths, structures need to be thought up to make it possible to use a technique on a small bit of the table, then distribute the diffusity, then repeat that.

The simplest form of course is just repetition. You take some reversible operation that operates on all bits but is pretty simple (shift-left, xor with some value if the shifted bit was 1) and repeat it a number of times. The number of repetitions is the number of "rounds". This gives pretty good results for fairly simple algorithms, but is pretty slow. I've heard somebody even state that given enough rounds, the simplest algorithm would be uncrackable. The problem is therefore not how to make the algorithm very hard to crack by adding rounds.

There are other forms of repetition, such as a structure called a Feistel cipher. This consists of dividing the current text into two halves, performing an operation on half of it, swapping the halves and xor-ing the just operated on half onto the newer half. Effectively, this means that the next operation is on half the bit length, while the entire cipher works on all bits. This does pose the problem that, since each round only works on half the bits directly, for the same amount of strength the encryption needs to be around double the amount of rounds.

A third is performing a small operation a number of times, each time on a part of the full state. This doesn't mix the bits quite as well but does reduce the size of the problem. More than one way of dividing combined with different combination methods gives a proper distribution.

Adding rounds causes the algorithm to take linearly longer. Each algorithm has a given point at which the algorithm isn't going to be broken sooner than by brute force, but when adding more rounds will mainly add time. At the time when every combination of input bits affects every combination of output bits with equal chance, this point has been reached. This point is, incidentally, for most algorithms, twice the amount of rounds it takes for a single bit to be diffused among all output bits. For an example, read the AES spec (also called Rijndael) which contains an interesting bit on the why and how of their algorithm. They have (for the 128-bit version) a full diffusion in 4 rounds. Take twice that, plus two to decrease the odds of a small break to actually reduce the strength, and you end up with 10.

There goes another rant... Hope you're enjoying it a bit and not just skipping over it...

bkilgore wrote: As far as the "this should work" mindset, I don't see how doing this would make it worse.

Then my Enigma example wasn't good enough. Running the same algorithm twice can introduce patterns, redundancies, weaknesses. Unless you have studied the subject of ciphers, you probably cannot really tell, and should leave stuff like that to people who spend their whole lifes researching the subject.

Hi,

well its clear i shouldnt use a "homegrone" thingie since i wont be able to build/test it in a couple of weeks. now i just gotta look at well documented and proven encryptions and find out which is best for my os since i still got the problem whit a finith amount of time so cant just pick the best encryption which would probely take way to long to en-/de-code. and offcourse also a good way to store the key's.

one other small thing, should i make a difference between for example encoding text and enconding simple data (not ASCII), since the data is or should be a lot more random then ascii-text.

So, would it be usefull to use a special encryption for ascii files. or is it so that you shouldnt be able to see the difference (between ascii and random data), assuming the encryption does its job propperly.

Regards
PyroMathic

I suppose you could compress the ASCII text before encryption to increase the randomness, at least have an option for it, and not just limited to ASCII text files of course. Everything I can think of to increase the randomness of the text seems to end up compressing it anyway.

blip wrote: I suppose you could compress the ASCII text before encryption to increase the randomness, at least have an option for it, and not just limited to ASCII text files of course. Everything I can think of to increase the randomness of the text seems to end up compressing it anyway.

Maybe that will make Solar happy (although he'll probably find some problem with it too). That satisfies the basic concept I was going for (make the data *look* as random as possible so that it's harder to tell when you've found the correct key). It can even be well-known that you're using this method, if you can find a compression method where it is unnecessary to embed easily detectable headers.

And I seriously hope that there's not some hidden weakness inherent in encrypting compressed data with all current cryptosystems, or people might be in for some big surprises regardless of whether or not they're using it for the purposes of making decryption harder.

It's easy to shoot down an idea with a simple "leave it to the experts" but a) you'll probably miss out on a lot of good ideas, and b) i'm going back to school for my masters soon in what will most likely be cryptography or a related field, so soon I may be one of those experts you like to leave everything to. Why wait to start thinking about interesting ideas?

DISCLAIMER: None of the ideas, concepts, techniques or algorithms mentioned in this post have been verified by professional cryptographers to be mathematically sound or cryptographically safe. Use of any such ideas, concepts, techniques or algorithms is strongly discouraged unless you want your wife to find out about your mistress, the police to find out about your racketeering, and the government of Russia to learn all of our state secrets. You have been warned.

With all the rants (including the mine one) about classic cryptosystems, we have forgot some very important "details".

I firmly believe that 99.99% of all information ever encrypted today and that someone (NSA, whoever...) stored will be decrypted very soon. Key word: QUANTUM COMPUTATION

Look at this article http://en.wikipedia.org/wiki/Timeline_of_quantum_computing and you'll notice that the fiels has suffered such a huge amount of advances alone the two past years that we must fear for all our data.

Nevertheless, I don't want my foresayings sound like the prophecies of Nostradamus (although, imagine you were able to read ALL executive orders from the US president by 2016... *evil grin*)

The only cryptosystem that is really, really, really safe and sound is a modified Vigenere algorithm known as the One Time Pad (OTP). While I can't remember any real use of the OTP, it has been mathematically proven to be SAFE. What stands against its practical, real-world application are its secondary conditions, i.e., the key synchronization between the sending and the receiving part.

It seems that we'll soon be forced to use the OTP (or some of its variants; the traditional OTP is based on the Vigenere cypher, but it could also be done with an XOR-substitution algorithm...). While we were all discussing about using some thoroughly tested open-source encryption package, OTP is surprisingly easy to implement; the only reason why you'd use some third-party piece of software is performance (although the algorithm is very fast compared with other crypto-algorithms).

Thus, the tough part of the task is the key exchanging method, which can't be done with RSA or DH or El Gamal or any of these, just remember: Quantum computation.

Nevertheless, whilst Quantum physics is the stuff cryptoanalyser's dreams are made, it's also their worst nightmare: QUANTUM CRYPTOGRAPHY

Without explaining all the details, Quantum Cryptography allows two parts to exchange a key which can be used for the OTP. Again, Quantum Cryptography is mathematically proven to be safe. Really safe. The only argument against it are physical limitations, because we need some kind of advanced technology to transport photons without altering their state, but that's mainly a material science topic and I'm confident it'll be solved within the next decade.

Of course, we could also discuss the possibility that governments won't ever let us use these technologies, but that's a whole new can of worms which certainly does not belong into an OS-devers forum. That particular subject, also an interesting one (never said it wasn't), can be discussed at the Electronic Frontier Foundation (EFF).

While I'm writing this, I'm really hoping the forum software will allow me to post such a long rant, but anyway, just forgive me for being so long...

Hoping that this post will interest at least one person,

Candamir a.k.a. Robin Hollenstein

BTW: Most, if not all of this information is from Simon Singh's book, although I don't remember its name in English... => Very cool book. I'd also like to recommend you the Wikipedia articles on the subject, they're also nice to read

Candamir wrote: While we were all discussing about using some thoroughly tested open-source encryption package, OTP is surprisingly easy to implement; the only reason why you'd use some third-party piece of software is performance (although the algorithm is very fast compared with other crypto-algorithms).

A one-time-pad (OTP) has the disadvantage that sender and receiver must both have access to a really random (not pseudo-random) secret key of at least the same length as the original message.

The thing is, how do you manage to exchange that key securely... ;D

Solar wrote:

Candamir wrote: While we were all discussing about using some thoroughly tested open-source encryption package, OTP is surprisingly easy to implement; the only reason why you'd use some third-party piece of software is performance (although the algorithm is very fast compared with other crypto-algorithms).

A one-time-pad (OTP) has the disadvantage that sender and receiver must both have access to a really random (not pseudo-random) secret key of at least the same length as the original message.

The thing is, how do you manage to exchange that key securely... ;D

ehm, but then otp is nice but i would require a second hdd to store the key, since if the data is 200 gig's the key also needs to be 200 gig's...

if i am right this method was used by the russians or germans not sure in WO2, but they used re-used the key's which made it not random, and gave the US the oppertunity to decrypt it...

to get back to packing ASCII or other data, wont i first need to use the key in some way, since otherwise it could "simply" be peeled of? still using the key before, wont be that hard to implement, so still good idea.

Regards
PyroMathic

There are two problems with One-Time-Pad:

1. Your key is as long as your data, and may not be used several times, even for different data. If you try to reuse the key, it's not OTP anymore.

2. The pad has to be random for this to work. Almost all pseudorandom number generators have some properties which make then useless for OTP.

So while the OTP encryption itself is trivial to implement (say, as a xor), the real problem with OTP is generating/storing/transmitting the keys, and that's just as hard if not harder than simply using a different encryption algorithm.

Pyr0Mathic wrote:

Solar wrote:

Candamir wrote: While we were all discussing about using some thoroughly tested open-source encryption package, OTP is surprisingly easy to implement; the only reason why you'd use some third-party piece of software is performance (although the algorithm is very fast compared with other crypto-algorithms).

A one-time-pad (OTP) has the disadvantage that sender and receiver must both have access to a really random (not pseudo-random) secret key of at least the same length as the original message.

The thing is, how do you manage to exchange that key securely... ;D

ehm, but then otp is nice but i would require a second hdd to store the key, since if the data is 200 gig's the key also needs to be 200 gig's...

if i am right this method was used by the russians or germans not sure in WO2, but they used re-used the key's which made it not random, and gave the US the oppertunity to decrypt it...

to get back to packing ASCII or other data, wont i first need to use the key in some way, since otherwise it could "simply" be peeled of? still using the key before, wont be that hard to implement, so still good idea.

Regards
PyroMathic

IIRC both did, the russians in all communication (reusing keys up to 4-5 times) and the germans in U-boat communications until '43 or so. The german one wasn't cracked (still iirc) but they changed to an enigma for all, which was subsequently captured and cracked. The russian communication was "cracked" by methods of the reuse, which gives you two texts xor'ed on each other (p1 xor key xor key xor p2 => p1 xor p2), and with those you can search for equal characters if the outcome is 0.

On the subject of quantum cryptography - all very nice, but you cannot avoid man-in-the-middle attacks that way. You will have certainty that there are two systems that know the key, but you won't know who the other one is. That makes it about as useful as a pretty good normal encryption algorithm - it's great, but it does have its weaknesses.