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.

Mike Partridge
  • 6,587
  • 1
  • 25
  • 39
user3123061
  • 1,609
  • 1
  • 15
  • 17
  • 4
    Other than the specific scheme to coordinate which part of the key to use, this is just a [one-time pad](http://en.wikipedia.org/wiki/One-time_pad). But under closer inspection it turns out to not actually be useful for 99% of use cases. –  Jun 01 '14 at 14:57
  • 10
    As this question is about the strength of a particular crypto algorithm, it might be more suited for http://crypto.stackexchange.com/. To move your question there, you can flag for moderator attention and ask for migration. – Bart van Ingen Schenau Jun 01 '14 at 15:02
  • "Why aren't OTPs practical" might be another good question (for [security.se]), but it's certainly a separate question. –  Jun 01 '14 at 15:37
  • 12
    OTPs were invented over a century ago, and were used, as actual physical pads of paper, in both World Wars. (http://en.wikipedia.org/wiki/One-time_pad) The problem in cryptography then as now is key exchange. – Gort the Robot Jun 01 '14 at 15:46
  • 2GB for every peer you ever want to communicate with? That doesn't scale well. – Bergi Jun 01 '14 at 17:57
  • 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 01 '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: http://arxiv.org/abs/1405.0435 – user3123061 Jun 01 '14 at 18:19
  • @Bergi: 2GB is chosen a example. It can be lot less or more depending on needed average speed for needed amount of time. Of course this method scales very badly for everyone-to-evereone else communication model. But i think scalability for everyone-to-center model can be depending on application relatively acceptable today. – user3123061 Jun 01 '14 at 18:53
  • @user3123061 - It also depends on what you're sending. If it's just plain text, sure, it won't use that much. But if you're transferring audio or video, you'll burn through the key in no time. – Bobson Jun 02 '14 at 16:26
  • As @StevenBurnap pointed out, the biggest weakness of one-time pads is the difficulty in exchanging the keys. You absolutely must deliver the key physically or over a secure channel, and you absolutely must be certain no one intercepted any part of the key. This is definitely doable, but it's too expensive for many applications. – Kevin Jun 24 '14 at 17:53

4 Answers4

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.

Vatine
  • 4,251
  • 21
  • 20
  • 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 01 '14 at 15:27
  • 1
    @MichaelBorgwardt huge point there. In this case "theoretically secure" actually is better than "practically secure". – Mark Jun 02 '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 02 '14 at 16:21
  • @Michael The chances of that happening are around 1 in 10^27. – this Jun 02 '14 at 20:58
  • @self - are you sure of your math? I make it approximately `pow(2,8*16-31)=1.6e+29`. Which is even smaller. And at any rate - if you have a sequence of 16 characters that _appear_ to be in plain text there is actually no guarantee that they are, in fact, plain. So even if you might send a "genuine looking" message, you will find a (relatively) large number of other "unscrambled" messages that are in fact scrambled - by the same math. – Floris Jun 02 '14 at 21:19
  • 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 02 '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)

Community
  • 1
whatsisname
  • 27,463
  • 14
  • 73
  • 93
  • 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 01 '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 02 '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.)

Paŭlo Ebermann
  • 802
  • 5
  • 11
  • _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 01 '14 at 20:12
  • But, you are right. Presented simple algoritm miss integrity and authentication. Practical implementation will need be more robust. – user3123061 Jun 01 '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*](https://en.wikipedia.org/wiki/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 01 '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 02 '14 at 01: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. –  Jun 02 '14 at 06:00
  • @user3123061 I did miss this "sent the counter" in your protocol, sorry. Though if that counter is not protected, you'll be using the same key block twice if the attacker replays a block (maybe slightly modified). – Paŭlo Ebermann Jun 02 '14 at 09:46
  • "An intercepting attacker who guesses correctly the plain text" assuming no other means than captured data to guess the plain text, replacing the data by other random data has exactly the same effect, since all guesses are equally probable. – PlasmaHH Jun 02 '14 at 09:49
  • @PlasmaHH Often attackers have other means of guessing the plaintext (or sections thereof) by out-of-channel information – e.g. you might now it is one of 100 specific files, and you can guess which one by looking at the file size. (A guess doesn't need to be always correct to be an acceptable attack.) Then you can replace one part of the file by something else, and the user either gets your malicious executable, or non-working stuff. – Paŭlo Ebermann Jun 02 '14 at 09:59
  • Or you know some of the plain text because you know what protocol the user is using. There's plenty of room for evil when editting the standard, predictable headers of an http response. – Brian Jun 02 '14 at 20:42
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.

w.pasman
  • 41
  • 1
  • 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 02 '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 02 '14 at 14:39