Some of you may have seen my article in the latest 2600 magazine about newLISP, a very fast scripting language based on LISP.
Well, the HiR crew has, for the better part of a year, been kicking around cryptography concepts. We keep coming back to one-time pad cryptography. It's fascinating in its simplicity. It's so computationally trivial that a human can quickly encrypt or decrypt a simple modular addition one-time pad scheme with nothing but a pencil and paper. The other thing is that, when implemented properly, OTP is perfectly secret and highly resistant to all forms of cryptanalysis. To this day, OTP is one of the most powerful and feared crypto schemes in existance.
Back here in computer world, we do a comparison on two numeric values assigned to the "cleartext" message. Since all ASCII characters have a decimal value in an 8-bit character space (256 distinct combinations), it's very easy to perform a bitwise Exclusive Or (XOR) on the cleartext and the key. XOR is simply "one or the other but not both". Let's try a cleartext of the letter A (binary 01000001) XOR against a key of "q" (binary 01110001). Comparing the bits vertically, the result will only have a "1" wherever either A or q have a differing bit at that location, but will have a "0" wherever both bits are the same.
"A"=01000001
"q"=01110001
-----00110000 (as it turns out, this is an ASCII uppercase "O")
newLISP, like all LISP based languages, handles lists and symbols very well. I just played around with this concept on the newLISP command line, and the result was fun, but not very practical as executed. I'll discuss ways to make this tinkering session a little more practical at the end of the article.
Ideally, the key would not be a string, but a very solid random set of characters known by the parties who are encrypting messages to one another. This doesn't even need to be a string, it may be binary random data...
A few things about this code. First, I'm a newbie at newLISP. Let me describe how some of this stuff works. The "explode" command turns a string variable into a list of characters. "char" turns a character into its ASCII decimal equivalent, or an ASCII decimal number back into a character. "map" simply takes the operation (such as "char") and uses that operation on a list. So (map char (explode cleartext)) would return the output of "char" for each individual character in the contents of the "cleartext" variable. Confusing enough? Okay, awesome!
newLISP code that I type will be in bold, red italics.
newLISP output will be in bold.
My comments will be in italics.
# newlisp
newLISP v.9.0 on OSX UTF-8, execute 'newlisp -h' for more info.
#first, I'll assign a key and convert it to a list of ascii numbers.
> (set 'key "Pa5$w0rd!")
"Pa5$w0rd!"
> (set 'kcharlist (map char (explode key)))
(80 97 53 36 119 48 114 100 33)
#Then, I'll assign a cleartext string and convert it to a list of ascii numbers as well.
> (set 'cleartext "HiR ownz.")
"HiR ownz."
> (set 'ccharlist (map char (explode cleartext)))
(72 105 82 32 111 119 110 122 46)
#In many languages, newLISP included, the carat "^" is the symbol for XOR. This line outputs the XOR values for each character compared between the cleartext and key)
> (set 'cryptcharlist (map ^ ccharlist kcharlist))
(24 8 103 4 24 71 28 30 15)
#Note that some of the characters from the XOR operation are non-printable, so their ASCII string notation /nnn is used instead.
> (set 'cryptostring (join (map char cryptcharlist)))
"\024\008g\004\024G\028\030\015"
#Now on the receiving end, we take the known key character list and we XOR the crypto character list. In reality we'd have to generate these again but we'd already set the variables above. No sense repeating the process here.
> (set 'decryptcharlist (map ^ cryptcharlist kcharlist))
(72 105 82 32 111 119 110 122 46)
#Finally, we take that string of numbers and join them after converting them from ASCII Decimal to characters again.
> (set 'decryptstring (join (map char decryptcharlist)))
"HiR ownz."
Now, as I'd mentioned before, in order to be really practical, you'd need an actual one-time pad that was very random. What I made above was a variant of Vernam cipher to give you a taste of how simple XOR based encryption is, not a genuine one-time pad. A few things that would make the above more practical:
- A lot of the steps could have been consolidated. I broke it down to show how things worked. I could have simply put all of the logic in one line, but it would have been confusing.
- The key and cleartext should be able to be read from a file. As implemented above, this should work with binary data (executables, images, etc) and with a very random binary key (pad) file.
- In the code above, the key needs to be the exact same number of characters as the cleartext. If implemented practically, the program should read the length of the cleartext and use that many bytes of the random pad.
- In a true one-time pad scheme, the sender and recipient both possess the same random key data, but the sender must destroy the part of the key that was used as soon as the encryption is performed. That way, only the recipient(s) may decrypt the message, as they have the only existing copy of the key. In turn, the recipient must destroy the part of the key used to decrypt the message so that in the event the encrypted message was compromised, there is no existing copy of the key available to aid in decryption.
- The above inconveniences have been the main downfall to widespread use of OTP.
- OTP's strength relies heavily on protocol, not technology.
--Ax0n
Posts
