Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I have a Raspberry Pi single-board computer that happened to have an hardware true random number generator, based on some quantum effects on the processor silicon, baked into its BCM2835 chip and I can pump its randomness by dumping bits from /dev/hwrng device in Raspbian, its Debian-based Linux operating system.

Now let's say I want to implement some sort of one-time pad scheme using this little piece of hardware as a randomness generator. How?

share|improve this question
3  
It's explained in more detail than you could possibly hope for in wikipedia. –  hunter Sep 21 '13 at 19:18
3  
You output the pad, transfer it through some secure channel (out of scope), and then simply xor it with the message to encrypt/decrypt. With which part do you have a problem? –  CodesInChaos Sep 21 '13 at 20:06
1  
@AlexandreYamajako Q1: flash memory Q2: yes, but personally I still have a few TB lying around doing nothing squared –  owlstead Sep 22 '13 at 15:13
1  
@AlexandreYamajako I can toss SD cards around without raising suspicion and all machines in my team have built-in SD card readers. Also, I have written a program on it to allow anyone obtain 1KB of fresh randomness in a contained network. –  Maxthon Chan Sep 22 '13 at 16:12
2  
OTP is a theoretical tool, it is not practical, and you should not use it. The challenging part in larger systems is not the encryption (well understood) but the key exchange (saying it is out of scope deals with this nicely in theory). –  tylo Sep 23 '13 at 10:05

2 Answers 2

up vote 5 down vote accepted

There are four concerns here:

  1. Pad generation
  2. Pad transmission
  3. Message privacy
  4. Message authenticity

Pad generation

The security of the one-time pad depends on the assumption that the pads are generated from a truly random source.

This is actually quite a big ask. Suppose for a moment that you want to exchange a 4 gigabyte pad. Let's say your RNG does that one byte at a time. What you're basically asking is for billions of iterations of the RNG without any kind of generation failure.

Worse, the RNG can fail in a way that is not immediately obvious or detectable. The Debian bug springs to mind here.

Or, more directly, a nation state could deliberately weaken your RNG.

Pad Transmission

The next problem is finding a secure way to transfer the pad. The pad will be longer than the message you wish to transmit, at least if you want to be able to detect alterations to your message. See below.

This immediately raises the question of what one hopes to gain by using the OTP. If you have a secure channel capable of transmitting a pad longer than the original message, why not just use this channel to transmit the message?

Given this logic, there is only really one use for the OTP, which is to time-shift a secure channel. For example, I might be able to meet my friend in the pub and give him a terabyte of pad but afterwards he might be abroad for two years.

Message Privacy

Assuming you've solved the problems of generation and transmission, next comes actually encrypting your message. This is the most straightforward piece of the whole exercise.

You just work through your message a word at a time and logically XOR that word with a corresponding one from the pad. No part of the pad may be re-used under any circumstances. It's best to have your program destroy the read section of the pad after completing the encryption operation.

Decryption on the other end is exactly the same process. Simply logically XOR the cipher-text with the pad to recover the plain-text. This works because XOR is its own inverse:

A XOR B XOR B = A

Message authenticity

One of the things that trips up amateurs is that encrypting your data doesn't means that nobody can undetectably alter the message in transit.

Suppose that an ATM used the OTP to encrypt its communications but no authentication. I have £0 in my bank account but I ask the ATM to give me £500. The bank replies with a single bit message which indicates whether the withdrawal is authorised or not: 1 for yes, 0 for no.

I know the bank is going to decline me so at precisely the right moment, I flip the bit before it gets to the machine. The machine spits out the £500.

You get around this problem by having a message authentication code (MAC). This is an authentication code you tack on the end of the message which acts as a secure checksum.

If I tried to flip the bit on a message with a MAC protecting it, the checksum would not longer verify and the system would know something funny is going on.

To authenticate OTP messages, you probably want to use a universal hash. This allows you to retain the security proof on both the hash and the cipher-text.

Universal hashes are a whole series of questions and answer in their own right so I'm just going to say that you should read around the subject.

Conclusion

The OTP is one of these ciphers that lot of amateurs gravitate towards because it's "perfectly" secure.

However, in reality we don't deal with perfection. We often don't have a secure channel with which to communicate a pad. We often don't have an RNG that has a failure rate of fractions of a billion or trillion. There are often cockups that result in pad being re-used.

For all of these reasons, competent cryptographers never recommend an OTP.

share|improve this answer
1  
"No part of the pad may be re-used under any circumstances." I think that's a bit misleading as written. It seems to imply that if you have two pads, P1 and P2, P2 can not contain any sub-sequences that appear in P1! That is clearly not correct. P2 will certainly contain subsequences that occur in P1 (if you define "subsequence" short enough). Am I being too pedantic? –  user7576 Sep 26 '13 at 11:59

As well as Simon Johnson's suggestions you should think about the following:

  • When collecting the entropy you'll need to ascertain the speed at which the hardware random number generator provides entropy. The collection program may need to be in a loop so waits for more entropy to become available (similar to /dev/random).

  • Think about other sources of entropy you could mix in (don't have all your eggs in one basket).

  • Use a randomness extractor on the generated entropy to get a uniform distribution.

  • Depending on what kind of data you are sending you could use fixed size data blocks and use padding to disguise the true length of the plaintext.

  • You need a protocol. Think about which key gets used and when. How do you communicate which key to use for decrypting to the recipient. What do you do in failure. How do you compute the MAC, etc. Look up the SSH protocol for ideas.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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