ciphergoth | No it bloody doesn't.

No it bloody doesn't.

Mathematicians who know fuck all about crypto are fond of saying that their latest discovery might have crypto applications.

http://news.bbc.co.uk/1/hi/sci/tech/2146295.stm

In this case, as usual, it doesn't.

Why is it crypto, of all fields, that attracts this idea that you don't have to know a damn thing about it to innovate in it? All fields get crackpots, but even crackpots have a vision that there are people employed to do some research in this field already, whereas there seem to be an endless supply of people who act as if they are the first to think really hard about encryption.

Update: Whoops, I spoke too soon. It turns out that Carl Pomerance among others is involved in this research, so I guess it is legit. I'm surprised.

Flat | Top-Level Comments Only

OK Paul, why are random series of numbers not applicable?

I guess the answer goes like this: Let's say the cryptosystem involves choosing a normal number, like the root of a large prime, as key and xoring the plaintext with its bits. Then, if I assume the input contains a large block of zeros, which it often does, how easily can I determine the key from an arbitrary sequence of its bits?

Pavlos

That approach (which I'm sure Paul can remind us of the technical name for) has another defect - you can never use the same key twice! If the key is X, and the messages are A and B, your attacker has X xor A and X xor B.

(X xor A) xor (X xor B) = X xor A xor X xor B = X xor X xor A xor B = A xor B.

A xor B is usually pretty easy to decipher with a little guesswork.

Vernam cipher. This isn't really a defect - you should never use the same (key, nonce) pair twice with any stream cipher. CTR and OFB modes turn a block cipher into a Vernam stream cipher, and they're perfectly secure if the block cipher is secure.

Yeah, but I have to flaunt the tiny bits of crypto that I do know.

It's the distinction between random and pseudo-random. Unless you are very careful, any pseudorandom number generating function you design can be reversed easily to derive the seed/key from a sequence of pseudorandom numbers generated from it.

Of course, a truly random sequence would be useless for crypto as you could not reconstruct it at the other end. So you need a pseudorandom generator function which is also a one-way function. This is a hard problem.

Of course, IANAC.

This is basically correct. This "normality" property they've proven is not enough for a generator to be useful - it must be "computationally indistinguishable" from a true random number generator to someone who hasn't got the seed. We've got lots of generators that we believe are indistinguishable, most of which are *far* faster than fetching digits of Pi with the Bailey-Plouffe algorithm, and plenty that have much better theoretical properties than BP.

A quick email exchange with David Bailey has done nothing to allay my suspicions and everything to confirm them...

They are, it's just that the digits of pi aren't random in any way that's useful for cryptography. They may be statistically random, but that's not enough. Since the sequence is always the same, digits of pi are basically yet another pseudo-random number algorithm, and not a particularly efficient one.

Suppose you take the unbreakable one time pad, and use digits from pi as the random numbers for the key. Problem is, in cryptography you have to assume that the enemy knows your algorithm. So you've just reduced your keyspace to the maximum size of offset into pi that you're prepared to use. Worse, you haven't actually made one-time-pad fundamentally more convenient--you still need some secure channel to communicate the offset to the person who's supposed to be decrypting the message. Worse still, because there's an algorithmic connection between adjacent digits of pi, there's probably a boatload of smarter attacks you've just opened yourself up to, just like if you were using any other pseudo-random number generator for your keys. For instance, if the enemy can guess even a fairly short piece of known plaintext, cracking your message becomes trivial--use that known plaintext to compute a set of digits, find the places where those few digits occur in sequence in pi (http://www.angio.net/pi/piquery), and one of those few places is the key. If they know you're talking about a string as long as "Osama Bin Laden", you might as well not bother encrypting...

The dumbest statement in that article has to be:

It may also allow the construction of unbreakable codes based on long sequences of random numbers.

The person writing obviously hasn't heard of one-time pad, so what are they doing writing an article about mathematics and cryptography?

I was thinking about something similar last night. It seems to me that innovation for its own sake should be valued as much in crypto as in medicine, ie. not at all. A merely different encryption algorithm is, like a different antibiotic, good to have as a plan B in case the adversary manages to foil the first one ... pauses briefly to consider similarities between crypto and DNA information warfare, finds only superficial ones ... but unless there is some concrete benefit the risks would never justify deployment of the minority algorithm.

I honestly think you should write a book that explains in lay terms what crypto can and cannot do. One section should say: "There is no objective test that a certain algorithm encrypts effectively. Confidence is gained after a large number of well-motivated experts try in earnest to break the algorithm and fail." I now understand that this is correct, but I didn't a while ago, and I don't think it is widely understood.

Pavlos

I didn't really understand this until I read Cryptonomicon, so maybe the book exists already. And has a plot!

Flat | Top-Level Comments Only

No it bloody doesn't.

no subject

Lay guess

Re: Lay guess

Re: Lay guess

Re: Lay guess

no subject

no subject

An amateur writes

I take it innovation has low value

Re: I take it innovation has low value