Tuesday, 21 October 2014

What is a OTP ?




A One Time Pad is a sequence of random bits. If used correctly, the one-time pad encryption is unbreakable.  The OTP or key must be random, as large as the plaintext, never reused in whole or part and kept secret.

Pros

  • unbreakable security.
  • Almost all methods for encryption today is based on the assumption that the universe will end long before the decryption can be brute forced using computing power and maths theory available now. This assumption may be wrong with the invention of quantum decryption computers, where all solutions are evaluated at once and the correct solution is resolved when the wave function is collapsed. Post publicly/privately available quantum decryption computers, OTP should still be secure if the source of the randomness is from nature.

Cons

  • High-quality random numbers are not easily generated. Even when generating the random numbers care must be taken to prevent them from being copied.
  • Distribution of OTP key basically requires a secure physical handover.
  • Access, securing and controlling who can use the OTP may not be easy.
  • Destruction of used keys may not be easy, most storages devices remove pointers to data for speed. Secure Digital cards and Solid-State drives will almost never overwrite old data, because this will  shorten the lifetime and performance of the storage device. And the written wear levelling algorithms which maintain the  3,000 to 5,000 block write cycle limit before failure of flash/SSD storage may remap blocks. And this means that even though you think that you are overwriting the same block you may actually be, and probably are, overwriting a totally different block.
  • Authentication, if the OTP was duplicated, there is no way to tell if fake messages were sent/received.
  • It is often described as unpractical, because it requires the same amount of key material as the data being transmitted.

Generation

The good

So what quantum sources are available for generating high quality random numbers.
  • Nuclear decay, when heavy atoms split into lighter elements they eject either alpha, beta or gamma radiation, or some combination. The half-life for each radioactive element is totally predictable but the actual timing of the decay events in between each half-life is totally random.
  • Shot noise, when electrons flow from one point to another in a circuit the number of electrons is not constant this is because of the discrete nature of electric charge. For instance 1 ampere of current consists of about 6.24×10^18 electrons per second; even though this number will randomly vary by several billion in any given second, such a fluctuation is minuscule compared to the current itself. The variation is temperature and frequency independent.
  • Photons, when large numbers of photons travel from one point in space to another the number of photons is not constant this is because of the discrete nature of photons. The variation is temperature and frequency independent.
  • Spontaneous parametric down-conversion  One photon enters a crystal, two photons leave, each with lower energy energy/frequency.
  • Band gap tunnelling electrons. You have a gap, you have electrons, every now and again random electrons jumps the gap.

Probably the most trusted source of  random numbers is from the timing of radioactive decay events. But even a highly radioactive isotope like Cæsium-137 can only generate about 100 bytes a second, using four counts to generate each bit. To fill a 3TB harddisk at that rate would take about 950 years using only one generator. With a two year warranty on most 3TB harddisks today, it would have failed when the disk was still nearly empty.

The not so bad (maybe)

Non-quantum sources are also available for generating random numbers.

  • Thermal noise from a resistor, amplified to provide a random voltage source.
  • Avalanche noise generated from an avalanche diode, or Zener breakdown noise from a reverse-biased Zener diode.
  • Atmospheric noise, echoes from the big bang and RF generated by lightening strikes

  And the ugly

Some commercial hardware for generating random numbers may, or may not, use a good high quality quantum source for their randomness. They then may either feed this into a hashing algorithm (SHA1, MD5, Whirlpool) to whiten/de-bias the randomness or feed it in as the seed to a deterministic random bit generator first before feeding it into a hashing algorithm to generate more random numbers per second. These modifications have the artificial effect of making the random numbers that are output pass FIPS 140-2 Annex C and Diehard tests for randomness.

Also with no access to the real random source it is impossible to detect if any external influence is biasing it's output to mostly all ones or all zeroes. Say Eve is modifying the electricity supply phase/voltage/waveform or changing the temperature/pressure of the environment of the device or zapping it with high energy electromagnetic waves, or even a beam of neutrons, anything to bias the output towards ones or zeroes.

Storage

Never on a SSD, unless the SSD is 99.99% full at all times. Spinning rust (AKA harddisk) still offers may advantages in securing a OTP over Solid State Drive technology. The biggest of which is the ability to fully destroy used pad.

Transfer

When a transfer happens it should be a two way exchange. The reason for a two way exchange is to avoid the same two people communicating with each other using the same communal pad. One pad means that if both parties independently decided to communicate at the same time a collision would occur, where the same pad is used twice. Where as if Alice has a pad (from Bob), that is only used in only sending messages to Bob, and Bob has a pad (from Alice) that is only used in sending messages to Alice, then the same pad can not be accidentally used twice. And in using two (or more) independent OTP's  this removes any requirement for an independent, secure,  communications channel is required to synchronise the usage of a single OTP.

Correct Use

Correct use of a OTP requires the following:
  • The OTP consists of real random numbers.
  • Only two copies of the OTP exist (sender and receiver).
  • Each OTP is used only once.
  • Each copy of a OTP is destroyed immediately after use.
Method
A previously prepared OTP key is combined one bit at a time with the plaintext message to produce the ciphertext. To decipher the ciphertext, the same key would be again combined character by character, producing the plaintext.
XOR Truth Table

pi@raspberrypi ~ $ echo -n 'Hello World!' | xxd -b
0000000: 01001000 01100101 01101100 01101100 01101111 00100000  Hello
0000006: 01010111 01101111 01110010 01101100 01100100 00100001  World!                                     .
 
pi@raspberrypi ~ $ dd if=/dev/random bs=1 count=12 2>/dev/null | xxd -b
0000000: 11010101 00001110 10111111 01110001 10001010 10010100  ...q..
0000006: 00100110 01010001 01100101 10110101 10101110 11010100  &Qe...
 
pi@raspberrypi ~ $

   SENDING
   -------
   message: 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 ...
   OTP:     1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 ...
   XOR      -----------------------------------
   cipher:  1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 ...

   RECEIVING
   ---------
   cipher:  1 0 0 1 1 1 0 1 0 1 1 0 1 0 1 1 ...
   OTP:     1 1 0 1 0 1 0 1 0 0 0 0 1 1 1 0 ...  
   XOR      -----------------------------------
   message: 0 1 0 0 1 0 0 0 0 1 1 0 0 1 0 1 ...
 
 
 

No comments:

Post a comment