23

Say Alice and Peter each have a 4GB USB flash memory stick. They meet and save on both sticks two files named alice_to_peter.key (2GB) and peter_to_alice.key (2GB) which contain randomly generated bits. They never meet again, but communicate electronically. Alice also maintains a variable called alice_pointer and Peter maintains variable called peter_pointer, both of which are initially set to zero.

When Alice needs to send a message to Peter, she does (where n is the nth byte of the message):

encrypted_message_to_peter[n] = message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]
encrypted_payload_to_peter = alice_pointer + encrypted_message_to_peter
alice_pointer += length(encrypted_message_to_peter)

(and for maximum security, the used part of the key can be erased)

Peter receives encrypted_payload_to_peter, reads alice_pointer stored at the beginning of message and does:

message_to_peter[n] = encrypted_message_to_peter[n] XOR alice_to_peter.key[alice_pointer + n]

And for maximum security, after reading of message also erase the used part of the key. - EDIT: In fact this step with this simple algorithm (without integrity check and authentication) decreases security, see Paŭlo Ebermann post below.

When Peter needs to send a message to Alice they do the reverse, this time with peter_to_alice.key and peter_pointer.

With this trivial schema they can send each day for the next 50 years 2GB / (50 * 365) = ~115kB of encrypted data in both directions. If they need more data to send, they could use larger keys, for example with today's 2TB HDs (1TB keys) it would be possible to exchange 60MB/day for the next 50 years! That's a lot of data in practice; for example, using compression it's more than hour of high quality voice communication.

It seems to me that there is no way for an attacker to read the encrypted messages without the keys, because even if they have an infinitely fast computer, with brute force they can get every possible message under the limit, but this is an astronomical number of messages and the attacker doesn't know which of them is the actual message.

Am I right? Is this communication scheme really absolutely secure? And if it is secure, does it have its own name? XOR encryption is well-known, but I'm looking for the name of this concrete practical application using large keys on both sides? I am humbly expecting that this application has been invented someone before me. :-)

Note: If it's absolutely secure then it's amazing, because with today's low cost large storage devices, it would be much cheaper to do secure communication than with expensive quantum cryptography, and this has equivalent security!

EDIT: I think this will be more practical in the future as storage costs decrease. It can solve secure communication forever. Today you have no certainty if someone successfully attacks existing ciphers even a year later and makes its often expensive implementations insecure. In many cases before communication occurs, when both sides meet personally, that's the time to generate the keys. I think it's perfect for military communication, for example between submarines which can have HDs with large keys, and military central can have a HD for each submarine. It could also be practical in everyday life, for example to control your bank account, because when you create your account you meet with the bank etc.

  • 4
    Other than the specific scheme to coordinate which part of the key to use, this is just a one-time pad. But under closer inspection it turns out to not actually be useful for 99% of use cases. – user7043 Jun 1 '14 at 14:57
  • 10
    As this question is about the strength of a particular crypto algorithm, it might be more suited for crypto.stackexchange.com. To move your question there, you can flag for moderator attention and ask for migration. – Bart van Ingen Schenau Jun 1 '14 at 15:02
  • 12
    OTPs were invented over a century ago, and were used, as actual physical pads of paper, in both World Wars. (en.wikipedia.org/wiki/One-time_pad) The problem in cryptography then as now is key exchange. – Steven Burnap Jun 1 '14 at 15:46
  • 6
    Note that this still leaves you to resolve the problem of generating enough unique keys for all expected data until the two parties meet again, and that the keys must be generated via a GENUINELY random process -- pseudorandom number generators are vulnerable to analysis, increasingly so as more samples using the same PRNG become available. – keshlam Jun 1 '14 at 17:58
  • 1
    @keshlam. Generating true quantum-random numbers are becoming very cheap. Interesting article at arxiv: Quantum random number generation on a mobile phone: arxiv.org/abs/1405.0435 – user3123061 Jun 1 '14 at 18:19
50

Yes, this is a One-time pad. If the key material is never re-used, it is theoretically secure.

The downsides are that you would need one key per communicating pair of principals and you would need a secure way of exchanging the key material in advance of communicating.

  • 52
    I think it's worth stressing that "theoretically secure" means that it's mathematically proven to be unbreakable, provided that the keys are truly random and not reused. That's pretty much the strongest guarantee you can get anywhere in cryptography. – Michael Borgwardt Jun 1 '14 at 15:27
  • 1
    @MichaelBorgwardt huge point there. In this case "theoretically secure" actually is better than "practically secure". – Mark Jun 2 '14 at 12:16
  • 2
    case in point: i've got a 2GB random key which happens to have 16 sequential bytes of 0. – Michael Jun 2 '14 at 16:21
  • @Michael The chances of that happening are around 1 in 10^27. – this Jun 2 '14 at 20:58
  • 1
    @Floris My "calculation": A byte has 256 possible values. That is one in 256 that all will be zero. 256^16 to get the chance for 16 bytes. And then divide the number of bytes in 2GB by that chance. I think I missed a division by 16, anyway here (1024*1024*1024*1024*2 * ( 1/16 ) ) / (256^16 ) Your last point makes this calculation irrelevant anyway. – this Jun 2 '14 at 21:29
32

As Vatine's answer indicates, your algorithm is basically a one-time-pad.

However, to comment on one of your notes:

Note: If its absolutely secure then its amazing because with today low cost large memories it is practicaly much cheeper way of secure communication than expensive quantum cryptography and with equivalent security!

My response is no, it is not amazing. The devil is always in the details, and the devil here is in the exchange of keys. Your method depends on a flawless, face-to-face key exchange. I can't afford to send James Bond carrying a 4GB flash disk for me to every merchant on the internet every time I want to buy something or have other secure connections.

And lastly, the XOR aspect of your algorithm is not important. A simple substitution cipher is just fine with a OTP. The strength of the OTP is that the key is never reused, and it assumes James Bond is flawlessly exchanging the keys for both parties (i.e. prior secure key exchange)

  • 13
    The other thing about an OTP is that the key is (at least) as long as the message to encrypt, and needs a very high quality random number source. – Donal Fellows Jun 1 '14 at 20:04
  • Many encryption algorithms work by somehow converting a key into a stream of data which is indistinguishable from random data, then using that data as a one time pad. From an attacker's perspective, there is no difference between data that is truly random and data which is indistinguishable from random data (by definition; if you found a difference, it wasn't indistinguishable), so in theory this is just as safe as OTP. Of course, when we say data is indistinguishable from true random data, there's usually a bunch of caveats. This explanation is of course a gross over-simplification. – Brian Jun 2 '14 at 20:36
21

While the one-time-pad has an unconditional (mathematically proven) privacy guarantee against an attacker who only can read messages, it has some weaknesses.

  • An intercepting attacker who guesses correctly the plain text can manipulate the ciphertext to whatever she wants (with the same length).

  • If an attacker inserts or deletes some message (or part thereof), Alice's and Bob's pointers get out-of-sync and every future communication is broken.

    Update: This assumed that both parties keep track of both pointers. If you send the current pointer value, you are vulnerable to two-time-pad attacks (if you allow the same range of key to be used more than once) or DOS-attacks (if you don't allow the same range of key to be used more than once, e.g. by deleting them).

Both of those problems are caused by missing integrity and authentication protection – you have a perfect cipher, but no MAC.

Add a MAC to your one-time-pad protocol to make it actually secure. Each message should get a "checksum" which ensures that it was actually sent by the supposed sender, and was not modified in between. Also, you should sent some sequence number so the receiver knows which part of the key to use when a previous message got lost (or to reject the message if it is duplicated) – include this in the checksum calculation.

A usual MAC algorithm would do here, but I suppose you might want to use some one-time polynomial MAC to have matching security to your one-time pad. (Take the MAC key from the bits before or after your encryption key, i.e. don't reuse one key for both goals.)

  • If an attacker inserts or deletes some message (or part thereof), Alice's and Bob's pointers get out-of-sync and every future communication is broken. Pointers are independent and not need to be in sync so no future comunication is broken if message is lost (actual offset of key used to encrypt message is sended with that message). But you are partly right: Out-of-sync is used part of key at receiving side which is not erased because deleted message is not received (used part will be erased with next received message). – user3123061 Jun 1 '14 at 20:12
  • But, you are right. Presented simple algoritm miss integrity and authentication. Practical implementation will need be more robust. – user3123061 Jun 1 '14 at 20:22
  • @user3123061 I wouldn't just shrug off integrity and authentication if I were you. The technique of adaptive chosen ciphertext attack exploits an absence of integrity protection to break confidentiality. I would go so far as to say that the classical one-time pad (which is what you have reinvented) is flat-out insecure, despite its apparent mathematical solidity, just because of this attack. – zwol Jun 1 '14 at 21:05
  • 2
    Adaptive chosen cipertext attack is a pretty poor choice of attack against a human-checked OTP. OOS is going to be noticed and your attacker gets punted pretty fast. Only if the receiver is machine-processed and yielding a response is this attack any good at all. – Joshua Jun 2 '14 at 1:01
  • @Zack There are many problems with OTPs, but none threatens confidentiality. Note that even if you perfectly guess the previous message's plantext+key, the next message is encrypted with an entirely new, independent key (of considerable size too). There is nothing to adapt to over multiple interactions. – user7043 Jun 2 '14 at 6:00
4

Actually it's not entirely safe. What your protocol leaks is the LENGTH of the communicated message.

For example, if the spy knows you will reply with "yes" or "no" and sees the length =2 he can deduce it's "no".

It actually is amazing how much can be deduced only from known lengths if one can guess the context.

  • 3
    That's quite easy to fix though, to a reasonable level of security, since you can pad the message with random junk, so message length are multiples of a fixed block size - say 256 chars. That would defeat a simple yes v no analysis, at a cost of using up the OTP faster. – Peter Bagnall Jun 2 '14 at 12:44
  • Indeed--since you can send ~115kB every day for the next 50 years, you may expect that each block would be at least 20kb, which means length isn't as important. – apnorton Jun 2 '14 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.