0

We all know the two most important problems related to a “one-time-pad”:

  1. The one-time-pad needs to be truly random (which I think is logic, as pseudo random generators are quick but predictable).

  2. The practicability of being able to transmit the number of keys securely to the receiver.

When only having a numbers station available to transmit the keys to the receiver, my common sense says security is practically rendered near to void because the keys are broadcasted to whoever-listenes-to-the-numbers-station.

When someone has access to encrypted messages and can listen/intercept the public broadcast by the numbers station, isn't using a numbers station to transmit a one-time-pad actually insecure? And — if I'm correct that it is insecure — is there a way around this security problem under the described conditions?

e-sushi
  • 1,296
  • 2
  • 14
  • 41
  • Why do you assume that numbers stations transmit one-time pads, rather than ciphertexts (with a pre-agreed key)? – Gilles 'SO- stop being evil' Jul 19 '13 at 15:16
  • @Gilles Because they could be transmitting either. During my military time, I have *"met"* ample number stations that transmitted keys instead of encrypted messages, or even both at separate intervals. – e-sushi Jul 19 '13 at 16:17

3 Answers3

7

"Pseudo random generators are quick but predictable": well, that's true only in an ethereal, mathematical sense. In practice, if your PRNG is cryptographically secure and seeded with some initial randomness of large enough entropy (128 bits are enough), then it won't be predictable. However, if a PRNG is involved, this is not true "One-Time Pad" but a mere "stream cipher".

OTP is a nice theoretical toy but it has no practical advantage over a properly used stream cipher. For some reason, a lot of people have fantasies of OTP being the ultimate answer for the Real World, and this leads to many misguided designs.

The main practical issue of OTP is that the key must be as large as the message, which is inconvenient: usually, we use cryptography to reduce problems: we apply encryption to reduce the problem of ensuring the confidentiality of a 10 GB file to the problem of ensuring the confidentiality of a 16-byte key, which can be managed much more easily (it can even be remembered and typed in by a human). If the key is as large as the data, then no reduction has occurred. At best, OTP can bring a time-based advantage: exchange the key in advance, when conditions allow for that, allowing for secure transmission later on. That's how the red phone worked: tapes full of random bits exchanged on a weekly basis (by special planes), so that immediate secure communication can be done at any time with no latency.

Of course, OTP relies on the key stream to be secret. There is no point in using public data as key stream. The whole security of OTP relies on secrecy of the key.

There is, however, a generic key exchange protocol which works with a public source of data similar to your "number stations".

It works like this:

  1. Alice and Bob listen to the number stations, and write down, at random intervals, some of the numbers and the "index" of these numbers. For instance, Alice remembers "171th number was 40; 236th number was 91; 406th number was 38;..." while Bob does the same with some other randomly chosen numbers in the public sequence.
  2. At the end of the day, Alice sends to Bob the list of indices that she remembered ("I have numbers 171, 236, 406...") and Bob responds with his own list of indices. With high probability, they have a few indices in common, so they will use the corresponding numbers as shared key.

An eavesdropper, however, would have to remember all, or at least most of the numbers, in order to also remember the same numbers. If the "number station" is sufficiently high-speed (say, it outputs 1 terabyte worth of data per second, and Alice and Bob gather randomly picked numbers during one whole day), then the storage requirement for the attacker can become prohibitive.

The Cachin-Maurer protocol is a fine example of a theoretically secure but grossly impractical cryptographic algorithm. Just like OTP.

e-sushi
  • 1,296
  • 2
  • 14
  • 41
Tom Leek
  • 168,808
  • 28
  • 337
  • 475
  • From a practical standpoint, the mathematical "non-random" matters. It reduces the bits of complexity from infinite to the number of possible initialization values for the random number generator. That's a very large reduction in complexity. OTP is also the only thing perfectly forward secure, though it does rely on physical security of the keys so in some ways it can be practically less secure, which is worth mentioning, but as far as security of the data transmitted, it is the most verifiable security out there. – AJ Henderson Jul 19 '13 at 14:15
  • 1
    As for randomness, remember that we don't have access to "guaranteed random numbers". What we have are physical process which are, _to the best of our knowledge_, unpredictable. Radioactive decay is random _unless our finest physicists got it wrong_. Similarly, a properly seeded PRNG is indistinguishable from randomness until (at least) the Sun goes out _unless our finest cryptographers got it wrong_. Claiming that one is "perfectly forward secure" while the other is not, is like claiming that Niels Bohr is _obviously_ much smarter than Adi Shamir, which is, at best, subjective. – Tom Leek Jul 19 '13 at 15:50
  • A number station that outputs 1 terabyte worth of data per second is — how should I put it without stepping on any toes — not exactly what I was talking about. A data rate of 1 TB/Sec clearly identifies a digital number station, but I was rather thinking and talking about the classical, more commonly known kind of number stations which use "voice" to transmit numbers via shortwave radio frequencies. Nevertheless, some points you made are interesting. – e-sushi Jul 19 '13 at 15:50
  • 1
    If the source produces 2^36 words of 128 bits per second (that's 1 TB/s) and does so for 2^16 seconds (that's a bit more than 18 hours), then we end up with 2^52 words, and Alice and Bob only have to record about 2^27 such words (with index) or so to have a good chance of a match -- that's about 3 GB worth of data, perfectly doable with today's technology. On the other hand, the attacker has to record about 64 PB (that's 2^16 TB) to succeed, which is substantially harder. Note that I did write "grossly impractical". That's a nifty _theoretical_ algorithm. – Tom Leek Jul 19 '13 at 15:55
  • @TomLeek My bad - forgot the calculations. Thanks for the heads-up! – e-sushi Jul 19 '13 at 15:59
  • @TomLeek - For the pseudo randoms, the sequence of numbers is apparently random, but you still only get the security of the complexity of the initialization value. The problem isn't attacking the sequence of numbers, it is attacking the initialization of the sequence of numbers, which is a great deal less complex than apparently random phenomena. I guess if you can feed a very long initialization in, it may be practically indistinguishable since the foreseeable future will lack the processing power to test the entire space of initialization values, but it is still the key weakness. – AJ Henderson Jul 19 '13 at 16:15
  • The usual argument is that "testing the entire space" is a computationally bounded problem -- for instance, there are strong energy-related arguments that there cannot be enough energy available, even converting the whole mass of the Sun to energy, to explore a 230-bit space exhaustively. Assuming we can will go beyond implies great advances in physics (e.g. "reversable computing"), which themselves would be likely to weaken assertions about the randomness of the physical events which we use in the first place to obtain "true randomness". – Tom Leek Jul 19 '13 at 16:35
  • @TomLeek - ok, that's fair I suppose, thanks for the further explanation. – AJ Henderson Jul 19 '13 at 19:41
3

Yes, it is hugely insecure. It's secure like putting a bright flashing neon sign on your front lawn saying "My hide-a-key is under the mailbox in the white rock, and $100,000 of jewelry are hidden under the TV. Please come in and have a look. Nobody is home from 1pm to 3pm. Have a wonderful day."

For a one-time pad to be secure, it has to be delivered in a secure manner that is free from eavesdropping (ie, normally by trusted courier). While you could technically transmit a one-time pad securely with a one-time pad, you'd use up as much of the previous pad as you gained, so it wouldn't have any benefit.

If any part of a pad becomes publicly visible, that part of the pad is ineffective because it has been disclosed. The entire point of a one time pad is that it makes any data well and truly random, but if the key is shared, then it's no longer random.

AJ Henderson
  • 41,816
  • 5
  • 63
  • 110
3

One-time pads are secure only if the key material is kept secret to the people who should be able to decrypt messages. Broadcasting a one-time pad would be exactly as bad as publicly broadcasting a secret symmetric key or secret private key in any other cryptographic system.

However, you could use a numbers station to broadcast secret encrypted messages, when the key is already known by the intended recipient. In that case, you're relying on the strength of the cryptographic system to ensure that other recipients of the encrypted message (who do not hold the key) cannot decrypt it.

Such an encrypted message could include further key material. However, you could not use a one-time pad to transmit additional one-time pad data, since it consumes one bit of shared one-time key to transmit one bit of a new one-time key. You could transmit an encrypted one-time pad using a different crypto system, e.g., a one-time pad encrypted with a shared AES key -- but then the problem of decrypting your messages encrypted with the new one-time pad (which ought to be a theoretical impossibility) reduces to the problem of breaking the AES encryption on the one-time key transmission (which is very hard, but not a theoretic impossibility).

apsillers
  • 5,780
  • 27
  • 33