semi-preditcable OTPs

[leichter_jerrold at emc.com]

| I recall reading somewhere that the NSA got ahold of some KGB numeric
| OTPs (in the standard five-digit groups).  They found that they
| contained corrections, typos, and showed definite non-random
| characteristics.  Specifically, they had a definite left-hand
| right-hand alternation, and tended to not have enough repeated digits,
| as though typists had been told to type random numbers.  Despite this,
| the NSA wasn't able to crack any messages.
| 
| My question is, why?   I think I know the reason, and that is that any
| predictability in a symbol of the OTP correlated to a predictability
| in only one plaintext symbol.  In other words, there was no "leverage"
| whereby that plaintext could then be used to derive other symbols. 
| Can anyone explain this better (or more accurately)?  Is this lack of
| diffusion?  Or does it have something to do with the unicity distance?
To get perfect security in a OTP system, you need to add as much
equivocation 
from the keystream as is being removed by the plaintext.  It's generally 
calculated that each letter in English text adds between 2 and 3 bits of 
information.  Hence you only need to add 3 or so bits of randomness from
each 
key input to make the system secure.  Even with the biases, there was
probably 
easily enough randomness in the OTP's to make recovery at least impractical
(e.g., information leaks but so slowly that you never see enough input to
get 
any useful decryptions) and perhaps even be theoretically impossible.

							-- Jerry


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com