Schneier on Security

Justin • September 19, 2014 12:48 PM

pnobody@localhost

Sorry, I don’t think you understood the point I was making.

I was making a few very simple points:

1) If you take something RANDOM and run it though one trillion encryptions with a block cipher it’s STILL RANDOM … and contrary to the point you seem to be trying to make – IT DOESN’T MATTER IF YOU XOR IN MORE PLAIN TEXT.

2) So, if you take a 128 block of plain text then XOR it with a 128 bit secret key derived from a truly random source, then the result is unconditionally secure – doesn’t matter if you then XOR the result with 10 BILLION bytes of plain text IT IS STILL SECURE. Got that? Otherwise any idiot could break an unbreakable one time pad just by adding more XOR’s which doesn’t any sense whatsoever.

3) It’s also true that if you take the above XOR’ed ciphertext, and throw away the original copy of the random pad key, and throw away the original plaintext, and just consider the cipher-text as a NEW random pad- IT’S STILL JUSTS AS RANDOM AS IT EVER WAS (just as long as the original first random pad was truly random).

Where you DO get in trouble re-using key material is in the case where an attacker can gather multiple copies of cipher-texts XOR’d with the same keystream, which would allow the streams to be XOR combined to cancel out the encryption.

This does NOT happen in the CBC mode I proposed, because the intervening AES-CBC block encryptions in the first layer prevents simple bit wise correlations between blocks.

Theoretically, to the extent that the block cipher is not perfect in obfuscating the relationship between blocks, the IV could leak information between blocks, but if you are just talking about ANY SINGLE BLOCK, then the question breaks down to two simple points:

1) Is the IV to THIS block derived from a truly random value (answer: Yes, if the first block IV was RANDOM all other blocks inherit that randomness).

2) Can the attacking cryptanalyst gain access to the IV (answer: No, ALL block IV’s are obfuscated by the second encryption layer)

So, block by block, the attacker must deal with the fact that each blocks plain text is first XOR’d with an unknown cryptographically strong random value that is hidden, so barring side channel attacks, there should be no way short of brute-forcing the key and original blocks secret IV.

This is true because as stated above in Lemma 1, 2, and 3 above, if the original IV is RANDOM, mixing it with plain text and then re-encrypting, even multiple times, will not make it any less random, so all the following blocks inherit an apperently RANDOM IV value from the first block, and this should remain true so long as the attacker can’t gather and compare all those IV’s (which is prevented by the second layer of encryption).

As you your mincing words about the ‘true’ definition of a One Time Pad, sorry being ‘unconditionally secure’ isn’t part of it. Actually THAT KIND OF DUMB STATEMENT is probably the WORST example of silly snake-oil claims surrounding One Time Pads. Though secure in an information-theoretic sense, there are a hundred practical reasons why a On Time Pad might be anything but secure in practice. The ‘real world’ a One-Time-Pad will NEVER be ‘unconditionally secure’ because of these other factors (implementation errors, stolen keys, etc.)

The sole point I was making was, that the super-encryption scheme proposed does have ‘unconditionally secure’ elements, which combine with the properties of the underlying CBC block cipher to strengthen the composite cipher against cryptanalytic methods short of brute-force.

I wasn’t claiming ‘unconditional security’ or that the composite cipher was ‘exactly like a One Time Pad’ or I wouldn’t have mentioned a ‘brute force’ attacks on the keys and IV (you can’t brute-force a one time pad).

Justin • September 19, 2014 11:34 PM

nobody@localhost

(a) there exists exactly one cipher which is proved unbreakable, and (b) you are usually better off using a good block cipher etc. …

Correct on point (b), not so much on (a).

Like Bruce has always said, bad crypto is simple and easy, but good crypto is complicated and difficult. So no one is served by oversimplifications.

Quoting Wikipedia:

“Several secret sharing schemes are said to be information theoretically secure and can be proven to be so.”

Such a scheme can be turned into a an unconditionally secure cipher by dispatching multiple couriers, each with only a piece of the message.

This has the disadvantage over a One Time Pad that the key can not be pre-shared, but has the HUGE advantage that the scheme can be arranged such that an arbitrary number of intercepted messages will NOT compromise the theoretical unconditional security of the scheme.

And there are several other cryptographic constructions with information-theoretic perfect security, but they don’t appeal to the snake-oil folks who focus like a laser on One-Time-Pads.

They like One-Time-Pads because the logic and math is really simple:

Take any set of arbitrary messages of equivalent length:

Humpty Dumpty sat on a…

Mary had a little lamb…

… and you can transform the first message into the second by flipping selected bits. This gives the OTP it’s absolute security, since absent the key, we don’t know which bits were inverted by the XOR operation, so depending on the XOR key the message could be literally ANYTHING.

It also shows a HUGE weakness in the supposedly ‘perfect security’ of a One Time Pad – Malleability.

Malleability means that if we can guess some plain text, then we can trivially manipulate a few bits to modify the cipher-text to substitute an alternate message of equivalent length.

So we could alter the cipher text of a message reading:

“Lets attack at sunrise”

So that it instead reads something like:

“Lets not attack rashly”

Given the malleability issue, and the huge key transfer and key storage issues, and given that there are other information-theoretic ‘unconditionally secure’ constructions, one might wonder, just what is the fascination with One Time Pads?

… could it be, because people who don’t have the sophistication to understand the complex mathematical proofs for some of the more complex provably secure cryptographic constructions, CAN understand a simple XOR operation and the above “Mary had a little lamb”, and “Humpty Dumpty” examples – then feel like big shots by saying, “All you cryptographers doun kno nuthin, because yuh’all is always guess’n about this crypto or that crypto, but I DO KNOW! Ha, ha, ha, I KNOW A CIPHER THAT IS THE ‘ONLY’ CIPHER THAT IS REALLY SECURE!!!”

Yeh, right.

For local files, OTP key storage is a significant problem (but gee, I put my key files in a folder labled “just random stuff, don’t look here!” so I don’t understand how my ‘perfect cipher’ got broken!) … and for exchange of messages over a distance, key exchange is just as big of problem (gee I can’t understand how my courier could sell me out like that!)

Again, my advise is to use something like AES-128-CBC or AES-256-CBC with a secret IV, then super-encrypt with RC4, Twofish, or Serpent and, baring side channel attacks or key compromises, you should be secure in a practical sense.

Justin • September 21, 2014 8:46 PM

Contrary to several comments here, the Vernam cipher was understood to be secure prior to Shannon’s work, based on the trivial proof that, by selecting the appropriate key, any message can be transformed into any other message, which means that, absent that key, the attacker can’t possibly guess which of the possible plain texts is correct.

Claude Shannon did do groundbreaking pioneering work in the field of information theory — but the formal proof of the unconditional information-theoretic security of a fully random Vernam cipher one-time-pad was only a very minor incidental part of his work, which was only important because he formalized this proof in relation to other fundamental precepts of information theory, which he then went on to generalize to the whole field of digital communications in the presence of perturbing influences (i.e. how much data can we push through a channel in the presence of noise).

Shannon’s contribution was to generalize the idea, and put it in the larger context of the underlying information theory, as a limiting case on the upper bounds on how much information will flow through a channel perturbed by noise (Eb/No vs. channel capacity). When the channel noise reaches the point were the error probability reaches 50/50 you are effectively reduced to guessing and no information transfer is possible. This is effectively what happens when you XOR plain-text with random data. For more information, look up Eb/No on Wikipedia and you will find all the math related to the Shannon–Hartley theorem.

This formula is at the core of all modern digital modulation systems, so there is no doubt that Shannon is indeed one of the unsung heroes of the information age, along with others like Alan Turing, and John von Neumann.

Please don’t trivialize his work with all this silly name-dropping like his main contribution humanity was nothing more that being some kind of early disciple of your holy church of the One-Time-Pad.

As to the ‘for all time’ security of a One-Time-Pad encrypted message – Yes, this is perfectly true in the context of ephemeral information transfer. For ephemeral information transfer, it’s great – if party “A” sends party “B” message “Z” and assuming that after decryption both parties then destroy all copies in existence of the key (and assuming there are no side-channel key compromises) – then any intercepted cipher-text would indeed be secure against decryption by an adversary ‘for all time’ (We still can’t decode some messages encrypted this way in WW2, and never will unless the pad keys are found somewhere).

… On the other hand, ciphers are not just used for secure transmission, they are also frequently used for secure storage in persistent data storage, and in that scenario the ‘for all time’ security of a One-Time-Pad becomes a ‘for all time’ vulnerability. Because if anyone, anytime, EVER ‘for all time’ gets access to your massive store of key material then the encryption is worthless.

So, let’s examine another scenario – let’s suppose that someone has a top secret new invention worth billions, and reading all the posts here on this forum from friendly helpful self-appointed-expert-OTP-groupies, he (or she) decides that they will protect the information using the “only proven unbreakable cipher”. So buying a second hard drive, they carefully fill it full of random bytes, and use those bytes to XOR encrypt their sensitive data. Then, realizing that the key data is also somewhat sensitive, they hide the key hard drive in the attic…

…What’s wrong with this picture? What happens to his (or her) ‘perfect security’ when someone breaks in and steals both her encrypted drive AND to his (or her) horror finds the secret key drive hidden in her attic? How is this even the least tiny bit more secure that just hiding the drive with the private data in the attic in the first place?

On the other hand, if they had simply encrypted the data with AES-CBC-256, then Twofish-CBC-256, then RC4 and simply REMEMBERED the 60 character pass phrase (With mixed case alpha, digits, and funny punctuation) – and used a multi-round strong KDF with SHA512 to independently key all those ciphers – then how secure would that be?

With each of the first two ciphers using 256 bits of key, and secret 128 bit IV, followed by another 128 bits of RC4 key, then who ever stole her information would be looking at about 896 bits of keys that they would have to break.

Even if the wheels flew off one of the ciphers due to an internal vulnerability, and it was completely broken, the other ciphers in the chain would still protect the data, and you would still be looking at more than 512 bits of key to be brute forced.

To put that into perspective, let’s get real creative and assume that someone could magically turn every atom in the entire earth into a quantum super computer that could examine a trillion keys a second – Got that? – Then we would be looking at cracking 1.33E50 (mass of earth in atoms) * 1E12 (keys/sec) or pretty close to 1.33E62 keys/second … coincidentally, 2^512 is also equal to 1.3E something-or-other – in fact pretty close to 1.34E154.

The difference in the mantissa between 1.33 and 1.34 is pretty small, but that difference in exponents, well that does tend to make a difference. Enough difference that it will take roughly 1E104 seconds to try all those keys. Call it 10000 Google-Seconds. That’s so many trillion trillion trillion of years you can’t even represent it within the timeframe of the known age of the universe!

So let’s see – I can ether OTP encrypt my data, bury the key hard drive in the back yard (or hide it in the attic) – and hope like hell that no one finds it – or use encryption that will almost certainly remain unbroken when our Sun has burned down to the size of a charcoal briquette – and just remember the key.

Not trying to belabor this folks, my point is simply that, though the One-Time-Pad can indeed be proven unconditionally secure under specific conditions, and may be a good choice under those conditions, this does NOT make it the right solution for most other cryptographic applications where it’s practical limitations and vulnerabilities far outweigh it’s advantages.