Yaotp -- Yet Another One-Time Pad (c) 2004 Plasmoid -------------------------------------------------------------------------- $Id: yaotp.txt,v 1.1.1.1 2006/10/29 20:33:25 plasmoid Exp $ > Introduction Welcome to the documentation of Yaotp (Yet Another One-Time Pad), a tool that implements so called one-time pads and that is useful only to the totally paranoid geek. Beside the boring en- and decryption the core features include: * Real random number generation by audio sampling and hashing. Generated data passes the DIEHARD RNG test suite. * Automatic sanity check of random data using statistic values (mean, deviation, entropy) to avoid sampling EMI noise or silence. * Key management that enforces one-time usage and irreproducible key destruction similar to secure-delete[3]. * Obligatory message compression, checksumming, uuencoding and PGP-like ASCII output. * No whistles and bells, but a tool for the true security fanatic. (Maybe even NSA-resistant). The first section of this document will introduce the concept of one-time pads, their theoretical security and the painful practice. After that introduction, a short tutorial illustrating the usage of Yaotp follows. The last sections cover the details of Yaotp's key generation and management. The document closes with some notes for furious readers. > One-Time Pad in a Nutshell The one-time pad is based on the Vernam cipher which encrypts a message by XOR'ing each cleartext bit with a key bit. The one-time pad extends the cipher through the following four conditions: (a) The key consists of truly random data (b) The key length equals the cleartext length (c) The key is used only one time (d) The key is irreproducibly destroyed after usage In theory the one-time pad achieves perfect security, because the randomness and the length of the key guarantee that each cleartext bit flips with 50% probability during encryption. No matter how much computing or memory capacity an attacker utilizes an encrypted message stays secure as long as each key is used only once and irreproducibly destroyed afterwards. In practice the situation is different. If only one of the above conditions does not hold, the security of the one-time pad can get horribly weak. If you search the web, you will find several implementations that either violate condition (a) by using a pseudo-random number generator or condition (b) by expanding the initial key to fit the cleartext length. Unfortunately the one-time pad gets rather impractical if all conditions hold. Following is a list of drawbacks that illustrate the real trouble: * Enormous key length: Encrypting 600Mb of data requires generation and storage of another 600Mb for the one-time pad. * Old-fashioned key exchange: The one-time pad, if used correctly, is more secure than any key exchange algorithm and thus it is necessary to personally exchange the pads on a mobile medium. * Key destruction: The one-time pad requires a read-write medium and special methods for irreproducible key destruction, e.g. secure-delete[3]. Nevertheless if used with true (or nearly) random data this cipher is secure against any (or most) attackers while its simplicity ensures transparent en- and decryption. It is the right choice for the totally paranoid geek and high-security issues beyond any imagination. > A Quick Tutorial on Yaotp The following tutorial is meant for the nervous and uptight reader that wants to play around before learning any background. 1. Select an audio source for random number generation. Common sources are TV and radio stations, e.g. MTV or other chaotic music channels, and street, water or line noise. The key generation may take several hours, therefore ensure that the source is constantly available in quality and volume. For example radio news, interviews and signal skips may drastically slow down the key generation. 2. Testing the audio source and the sound device Launch Yaotp in test mode by executing the following command and adjust the volume of your sound device until no or very few bad buffers appear: $ yaotp -t You can provide a different sound device using the "-s" option. Re-run your test with fixed volume for at least 3 minutes to guarantee good random quality. 3. Generating a key (or one-time pad) Mount a mobile device, e.g. a memory stick, MP3 player or digital camera, for read and write access and run Yaotp with the following options in order to create a key on the device: $ yaotp -g -k /mnt/usb1/key.1 If you generate the key on your hard disk and later move it to a mobile device, you have to wipe the original file using secure-delete[3]. If don't do so the one-time pad is insecure and it is possible to re-construct a copy from your hard disk. In order to organize multiple key use the "-l" option and add different labels to your keys. 4. Exchanging the key Take your mobile device and meet your communication partner in person. Copy the key file to his mobile device. $ cp /mnt/usb1/key.1 /mnt/usb2/key.2 It is a good choice to have both keys on mobile media, because those can be carried around and thus provide more privacy and security. 5. Encrypting a message Once the key has been exchanged it is easy to encrypt a message using Yaotp. Run Yaotp with the following options to encrypt the file /tmp/foo using a key stored on your mobile device $ cat /tmp/msg | yaotp -e -k /mnt/usb1/key.1 Yaotp will checksum, compress, encrypt and uuencode your message. The part of your key file that was used for encryption will be automatically wiped and gets irreproducibly destroyed. 6. Decrypting a message The decryption process is as simple as encryption. Launch Yaotp with the following options: $ cat /tmp/crypt | yaotp -d -k /mnt/usb2/key.2 When testing this procedure it is a very common mistake to use the same key file for local en- and decryption. It is essential for Yaotp to have two copies of the key and thus decryption will fail on a single copy. > Key Generation Details Key generation is essential for the security of one-time pads. Most attacks against one-time pads are either based on a faulty key generation or a lack of entropy in the used source. The key generation in Yaotp is based on a random number generator (RNG) that extracts random bits from sampled audio data. The process itself is divided into five distinct phases: 1. Sampling Yaotp records multiple buffers each containing 65536 words from the provided sound device, e.g. /dev/dsp. The device is configured to sample mono audio data with 44.000Hz and 16bit precision. The result of this phase are buffers with 65536 16bit words of audio data. 2. Cropping Regarding audio data higher bits contain less entropy than lower bits. In this phase the words within each buffer are cropped to their lower 8 bits, so that the result are buffers with 65536 bytes each. 3. Sanity Checks Each buffer has to pass three sanity checks. If one test fails the buffer is skipped. Unfortunately it is very hard to measure the randomness of a given buffer. Therefore the sanity checks are based on three simple statistical values that are necessary, but not sufficient for measuring randomness. Statistical Value Expected Tolerance i. Byte mean ~ 127.5 +/- 8 ii. Byte deviation ~ 63.75 +/- 2 iii. Byte entropy ~ 8.0 +/- 0.08 The result of this phase are only those buffers that pass all three sanity checks. 4a. Byte Reversal (optional) Even though the buffers contain only the lower 8 bits of the audio data, it is likely that not all 8 bits flip uniformly. To compensate this problem a little bit, the bytes within each second buffer are reversed using the function REV. REV(b) ~ The bits within the byte b are reversed, so that less significant bits become more significant bits and vice versa. E.g. byte a = 0011 1010 is reversed to REV(a) = 0101 1100. As a result of this phase half of the buffers are unchanged and half of the buffers have reversed bytes. 4b. Overlaying (optional) If one combines several bits with XOR, the result is random if only of the initial bits is random. Therefore multiple buffers should be "overlayed" using the XOR function. E.g. Four buffers a,b,c,d of length n will be "overlayed" to form a buffer x also of length n. x_i = a_i XOR b_i XOR c_i XOR d_i In conjunction with the byte reversal the buffer x is constructed according to the following formula. x_i = a_i XOR REV(b_i) XOR c_i XOR REV(d_i) A bit of the resulting buffer is random, if the corresponding bit in one of the overlayed buffers was random. The more overlays are performed the more likely are random bits. The default are four overlays. 5. Hashing Hashing is the very soul of (pseudo-)random number generation. A hash function that meats the typical conditions of non-linearity, avalanche and completeness, enforces random bit extraction and hardens any reverse analysis. Yaotp works with the MD5, SHA and RIPEMD algorithm. The number of input bytes that are hashed to one byte is determined by the hash ratio. If the ratio is r, r bytes of each buffer are hashed into one byte. The result of this phase are buffers of length n/r. After phase 5 the buffers contain high quality random data. The quality has been measured with the DIEHARD[1] test suite. Yaotp keys (or one- time pads) pass all DIEHARD tests and can be considered at least very random. Following is figure that illustrates the phases 4a, 4b and 5. Audio buffers (lower bytes of 16bit 44kHz sampling) a_1 ... a_n b_1 ... b_n c_1 ... c_n d_1 ... d_n 4a. Byte | | | | Reversal | REV(b_i) | REV(d_i) | | | | 4b. Overlays '-----XOR------+------XOR------+-----XOR-----' number = 4 | x_1 ... x_n/2 ... x_n 5. Hashing | ratio = 2 MD5 | x1 ... x_n/2 Random Numbers The phases 4a and 4b are optional, because they can be replaced by hashing if the hash ratio is raised accordingly. E.g. The default setup of 4 overlays with byte reversal and a hashing with ratio 2 ("-o 4 -r 2") can be replaced by hashing with ratio 8 ("-r 8"). Hashing is far more secure than the simple overlays, but it isn't that transparent. Decide for yourself, if you want to trust the hash algorithms alone. > Key Management Details In opposite to other ciphers key management is a very important part of the one-time pad. Basically the Yaotp implementation has to ensure that the conditions (c) and (d) hold, thus key bytes are used only once for en- or decryption and irreproducibly destroyed afterwards. * One-time Usage Yaotp stores the generated random data, the one-time pad, in a so called key file. The header of this file contains the available bytes and the current offset of the pad. If Yaotp is used to en- or decrypt a message, the available bytes are decreased and the offset is increased. The key file is considered "empty" if the offset reaches the EOF mark. You can run Yaotp with the print command "-p" to display the current state of a key. $ ./yaotp -p -k /mnt/usb1/key.1 Key file: /mnt/usb1/key.1 Total key size: 8192 Available key size: 2031 Creation time: Thu Aug 5 16:14:55 2004 Key label: Test Key By keeping track of the available bytes and the offset Yaotp ensures that each key byte is used only once and also allows multiple en- and decryption processes with the same key file. * Key Destruction If Yaotp would just change the offset of a key file, the used parts of the key would be still present in the file. Even if the parts are overwritten with zero's, experts can still recover them from most electro-magnetic media. To cope with this situation Yaotp uses a wipe technique proposed by Peter Gutmann[4] that is also used in secure-delete[3]. The used parts are overwritten several times with random and specific patterns. According to Gutmann a reconstruction is far from possible. Key destruction is essential for the one-time pad and therefore pads must not be stored on read-only media, e.g. CD-ROM. Keeping a one-time pad secure also requires caution of the user. If for example the pad is stored on a workstation computer an attacker might easily compromise the security of the pad. I recommend to store all one-time pads on mobile media and keep them near yourself. Excellent media are MP3 players or digital cameras because of their "dual-use" ability. > Food for the Furious 1. Rant: "The Vernam cipher is exactly the one-time pad" Often "one-time pad" and "Vernam cipher" are used synonymously. I consider the one-time pad to be an extended Vernam cipher, because according to [2] Vernam used a looped tape of random numbers as the key and thus violated condition (b). 2. Rant: "A modern block cipher is as secure as Yaotp." The core security of a block cipher relies on its structure, e.g. rounds, substitutions and permutations, while the core security of the one-time pad relies on the randomness of the key. Breaking a block cipher is very hard and far beyond my skills, but I consider reconstructing bits recorded from an unknown audio source, fuzzed with line noise, cropped to the lower bits, overlayed several times and finally hashed, to be a harder task. But I may be wrong. 3. Rant: "There is no absolute security. Yaotp is insecure." True. The one-time pad is information-theoretically secure, thus if any security breach arises in Yaotp the root is my faulty implementation or a lack of entropy in the audio source. If you come up with a working attack, e.g. by analyzing EMI noise within random bytes, please let me know and drop a mail. 4. Rant: "Audio sampling? /dev/random is a better source." There is definitely a lot of entropy in /dev/random, but it takes ages to collect some megabytes of data. This could be a sign for a good source. Nevertheless experiments with data generated by Yaotp prove equal randomness measured using DIEHARD[1] even though generation took only one hour. 5. More to come. I am happy to receive further rants and flames. ;) > Closing Words Thanks for reading this document and don't waste too much of your free time coping with one-time pads. Matter of importance and privacy may better be discussed near a cold bear in a nice pub. Cheers to all members of THC, TESO and Phenoelit, Plasmoid > References [1] Marsaglia, G. DIEHARD - A Battery of Tests for Random Number Generators (RNG), http://stat.fsu.edu/~geo/diehard.html [2] Kahn, D. The Code-Breakers. Macmillan Pub Co; Reissue edition (1967), ASIN 0025604600 and Revised edition (1996) ISBN 0684831309 [3] Hauser, V. Secure Delete for files, disk space, swap and memory, http://www.thc.org/download.php?t=r&f=secure_delete-3.1.tar.gz [4] Gutmann, P. Secure Deletion of Data from Magnetic and Solid-State Memory, http://www.cs.auckland.ac.nz/~pgut001/pubs/secure_del.html