Crypto

The twenty-second DEFCON took over Las Vegas last week, and brought many interesting and notable speakers. I took a few notes from the talks that stood out to me, and I'm passing them along here.

Paul Vixie, Internet pioneer and DNS expert. Vixie spoke about his DNSDB project for accumulating global DNS resource records in a passive fashion, and making this information available to researchers and security product vendors. He also spoke about his DNS firewall for shielding users from malicious throwaway domain names.

Phil Zimmerman, creator of PGP and president of Silent Circle. Zimmerman spoke about wiretap overcompliance in the telecommunications industry, trust in cryptographic techniques, and his new endeavors at Silent Circle. Reading about Zimmerman's PGP efforts and the resulting drama (PGP: Pretty Good Privacy, Simson Garfinkel) is what got me interested in cryptography many years ago, so it was great to see a living legend on the stage. I did take issues with a few of his comments, though. When asked about trusting binary executables, Zimmerman mentioned the problem of distributing a binary which is identical to one that might be produced from source, due to differences in timestamps — and failed to discuss recent progress in reproducible build techniques which are meant to solve that problem. He also painted a somewhat rosy picture of the legislative attitude towards cryptography and privacy: we won the Crypto Wars in the 1990's, and cryptographic freedom can't be rolled back again now that everyone relies on it. This does not seem to be the case — last year, Congress and the administration was pushing a proposal which would effectively outlaw peer-to-peer communication systems that might be problematic to wiretap. (Thankfully, the Snowden revelations made the proposal politically toxic for now, and it has been shelved.)

Kenneth White, security researcher. White spoke about the Open Crypto Audit project which he launched along with cryptographer Matthew Green, and the drama caused by their first audit subject, TrueCrypt, being suddenly discontinued under mysterious circumstances. I've followed the progress of the Open Crypto Audit project and the ongoing news about the TrueCrypt disappearance, so there wasn't much in the talk that was new to me. It was interesting to hear that some of the biggest challenges of Open Crypt Audit were the community aspects of audit fundraising. White reported that they will finish the TrueCrypt audit in spite of the shutdown, and then move on to OpenSSL.

Dan Kaminsky, security researcher. Kaminsky scored a coveted two-hour slot in the Penn and Teller theater, which he fully used to discuss a variety of topics:

• Secure random by default. Kaminsky argued that most vulnerabilities resulting from random number generation are not due to exotic attacks on complex algorithms, but rather gross missteps in the use and generation of randomness. For instance, some software has been observed to only effectively use 32 bits of entropy, while others employ the use of linear feedback shift registers (LFSRs) in spite of their easy cryptanalysis. Kaminsky proposes a new Liburandy library which wraps /dev/urandom when appropriate.
• Storybits. Kaminsky invited Ryan Castellucci onto the stage to demonstrate Storybits 0.1, a new cryptomnemonic scheme for people to remember binary strings such as keys, fingerprints, secrets, etc. The system encodes the data as adjective-noun-verb tuples to make the data easier to remember, and provide error correction by way of spellcheck auto-correct.
• Memory hardening. Convinced that improper memory usage is a major cause of vulnerabilities, Kaminsky outlined several strategies for memory-hardening applications. These include use of a typed heap (as Google does in Chrome), the use of nondeterministic freeing (as Microsoft does in Internet Explorer), and a novel approach called IronHeap where 64-bit virtual memory addresses are simply never freed (although pages may be returned for MMU reuse). He also announced the formation of a team to memory-harden Firefox, to provide added security for the Tor Browser Bundle.
• Distributed Denial of Service (DDoS) mitigation. Kaminsky considers the rise of DDoS attacks using techniques such as datagram amplification to be an existential threat to the Internet. He proposes a new scheme of sending tracer packets within data flows to indicate when source address spoofing may be happening.
• NSA. Kaminsky is concerned that the NSA backlash may lead to a balkanization of the Internet, as various nations opt to develop their own internal systems for core Internet services.
• Apple bug bounties. Finally, Kaminsky is quite happy that Apple is offering bug bounties relating to Safari autoredirection.

Kaminsky's slides are available.

Ladar Levison, founder of Lavabit. Levison spoke about his proposed Dark Mail Alliance, a new electronic mail system designed to preserve the privacy of users. He began by announcing a new name for the project: DIME, the Dark Internet Mail Environment. I was a bit disappointed in the new name — "Dark" can have a sinister connotation for some people, and privacy preserving technologies should be marketed to the public with positive names reflecting the true value they provide. He should have renamed the project TIME, the Trustworthy Internet Mail Environment. Levison outlined the basic components of the system, including a server called Magma and a modified Thunderbird client called Volcano. DIME unfortunately does not provide forward secrecy for messages, although Levison pointed out that there was forward secrecy at the TLS1.2 line level. There was also talk of a pseudo-onion scheme to shield metadata and provide some small measure of anonymity, but it wasn't clear to me how this was implemented.

Adam Caudill, software developer and security researcher. In DEFCON's new Crypto Village, Caudill proposed a new secure electronic mail system called Simple Messaging and Identity Management Protocol (SMIMP). This scheme shares some of the same goals as Levison's DIME, but provides an alternative design intended to be developed in the open among the greater Internet engineering community. The most interesting thing to me was a Hashcash-like proof-of-work requirement for reducing spam.

While developing Valence, an input-only Android VNC client for remote controlling a computer, I've encountered several notable quirks in Apple Remote Desktop, Mac OS's built-in VNC server. Apple Remote Desktop (ARD) is based on VNC, a system developed in the late 1990's for controlling a remote computer, and its Remote Framebuffer (RFB) protocol. Generally, standard VNC clients can interoperate with ARD. An ARD server reports use of version "3.889" of the RFB protocol, which isn't a real version of RFB, but this version number can be used by clients to know that they are talking to an ARD server and not a conventional VNC server.

ARD authentication

During the RFB handshaking, a VNC server will announce which authentication methods it supports, and the client then picks from among these. Most VNC servers support a scheme known as "VNC authentication," which is a simple DES-based password challenge/response system. ARD offers VNC authentication, but it also offers a proprietary scheme which allows the user to also supply a username. This scheme is known as "Mac authentication" or "ARD authentication." Mac OS X 10.7 Lion includes an important change to the way ARD works: If you connect with VNC authentication, you are presented with a login screen which prompts you for a username and password before allowing you to control the desktop. If you connect with ARD authentication, this login screen is bypassed and you can immediately control the desktop.

Because Valence is an input-only VNC client, the login screen is a show-stopper: since the login screen cannot be seen, the user cannot login and control the desktop. The only way for Valence to support Lion's built-in VNC server was to add the ARD authentication scheme as an option. Apple has a support article which gives a high-level overview of the ARD authentication process, but it unfortunately does not contain the technical detail needed to implement the scheme. I was able to discover the technical details by studying the gtk-vnc open-source library, which implements ARD authentication thanks to a patch provided by Håkon Enger last year. (I'm not sure how Mr. Enger figured out the technique, but I'm grateful.)

The basic steps for performing ARD authentication are as follows:

1. Read the authentication material from the socket. A two-byte generator value, a two-byte key length value, the prime modulus (keyLength bytes), and the peer's generated public key (keyLength bytes).
2. Generate your own Diffie-Hellman public-private key pair.
3. Perform Diffie-Hellman key agreement, using the generator (g), prime (p), and the peer's public key. The output will be a shared secret known to both you and the peer.
4. Perform an MD5 hash of the shared secret. This 128-bit (16-byte) value will be used as the AES key.
5. Pack the username and password into a 128-byte plaintext "credentials" structure: { username[64], password[64] }. Null-terminate each. Fill the unused bytes with random characters so that the encryption output is less predictable.
6. Encrypt the plaintext credentials with the 128-bit MD5 hash from step 4, using the AES 128-bit symmetric cipher in electronic codebook (ECB) mode. Use no further padding for this block cipher.
7. Write the ciphertext from step 6 to the stream. Write your generated DH public key to the stream.
8. Check for authentication pass/fail as usual.

For further reference, my Java implementation of ARD authentication is available on GitHub.

Right-click problems in the Snow Leopard ARD v3.5 update

In July 2011, Apple pushed an update to Snow Leopard users which included a newer version of Apple Remote Desktop, the built-in VNC server. This new version, v3.5, interprets mouse buttons differently—the RFB "button-2" event is now used to indicate a right-click instead of the "button-3" event which is used on standard VNC implementations. This broke Valence's support for sending a right-click when the user performs a two-finger tap. To restore right-click support, I had to add a "send mouse button-2 instead of button-3" option to Valence's server configuration.

It is unclear to me why ARD v3.5 does this in Snow Leopard, why this problem doesn't exist in Lion, and why this problem doesn't appear when using the ARD client.

Foreign keyboard key mapping

Valence can be used to send international keys to VNC servers running on Linux or Windows with no problem. However, I was surprised to discover that these key events were often not correctly consumed by Macs. Upon investigation, I learned that the problem was worse—using a foreign keyboard layout can cause the wrong keys to be consumed by the Mac. The root cause appears to be the lack of support in Mac OS for allowing applications (such as a VNC server) to inject synthetic keysyms (symbolic representations of keys). Only injection of physical keycodes (numeric representations of actual keys on a keyboard) is supported. (Note that I'm borrowing "keysym" and "keycode" from X11 terminology, but most systems have equivalent concepts.)

Operating systems generally provide layers of abstraction around keyboard input, and some background is required to understand the problem. Keyboard hardware sends a "scancode" to the computer for each key pressed, using a scheme that dates back to the electrical configuration of rows and columns in early keyboards. These scancodes are then translated into more useful values one or more times before being provided to an application. On a Linux/X11 system, for instance, the scancodes are converted to "keycodes" which are simple representations of each physical key on the keyboard. The scancode to keycode mapping allows computers to use keyboards with different scancode conventions. For example, the 7th key from the left on the top letter row may be represented by different scancode bytes on different keyboards, but the operating system will always translate that key to the same keycode. The keycode, which still represents a physical key, is then mapped into a virtual value known as a keysym, based on the configured keyboard layout. For example, that 7th key on the top letter row would result in a keysym for "Y" when using a U.S. keyboard layout, but it would be translated into a "Z" when using a German keyboard layout. These abstraction layers allow applications to be written without needing to consider the keyboard electronics or the arrangement of keys on the keyboard. When the application receives a "Y" keysym, it knows that the user intended to enter "Y" regardless of which physical key they pressed to make it happen.

VNC clients send symbolic key representations, to avoid any of the headache with keyboard layouts. (The symbolic key representations used in the RFB protocol are defined to be identical to the X11 keysyms, but are trivially translatable into symbolic key values for other systems.) When a user presses a "Y", the VNC client sends 0x0079, which is the keysym for "Y", regardless of which physical key was pressed. The VNC server then injects a synthetic key event with the appropriate symbolic key for "Y" into the input system of the server. A user using a VNC client with a U.S. keyboard and a user using a VNC client with a German keyboard would both be able to type on a server with any defined keyboard layout without noticing any problems, because the VNC server injects the symbolic key and bypasses the whole messy business of keyboard layouts.

That's the theory, anyway. Unfortunately, since Mac OS doesn't seem to support symbolic injection, only physical keycode injection, the whole system falls apart. Here's what happens when an American user presses the 7th key of the top letter row ("Y" on the U.S. keyboard) while using a VNC client to control a server configured with a German keyboard:

• Linux and Windows. The VNC client sends 0x0079, the VNC symbolic key representation for the letter "Y". The VNC server receives this event, and says, "I see you want to press the letter Y on this computer. I'll send the symbolic key for "Y" directly to the running application. We won't worry about what kind of keyboard is physically attached to the server... it doesn't matter!" The application receives the keysym for "Y", and all is well.
• Mac OS. The VNC client sends 0x0079, the VNC symbolic key representation for the letter "Y". The VNC server receives this event, and says, "Gosh, the operating system's event API only lets me send physical key events, so I'll have to translate this into a physical keycode. I wonder how I can do that... Oh, I have a built-in list of how keysyms translate to keycodes for American keyboards, I'll use that! It looks like I should send the physical keycode representing the 7th key of the top letter row. Done!" After the VNC server injects the keycode, the operating system then performs its task of translating the physical keycode back into a keysym to be delivered to the application. Unfortunately, since the operating system is configured to be using a German keyboard layout, the keycode is translated into the keysym for "Z" instead of "Y". The user is shocked to see a "z" appear on the screen after he typed a "y"!

A sufficiently smart VNC server perhaps could try to work around this problem by (somehow) being aware of which keyboard layout is in use on the server, and having the information needed to translate keysyms to keycodes for all possible layouts. This may not even be feasible, but even if it is, it doesn't solve the problem: the remote user would still be unable to type characters that are not physically present on the server's keyboard.

A brief survey of open-source software that deals with key injection on Mac OS shows that my Valence app isn't alone in suffering from this issue—they all do. In fact, even Apple Remote Desktop cannot handle this correctly! The usual advice for using an ARD client to control an ARD server with a different keyboard mapping is to change the keyboard mapping on either the client or the server.

I have no solution for the foreign key problem at this time.

DES, the Data Encryption Standard, was developed by IBM and the US government in the 1970's. Today, DES is considered to be weak and crackable, and a poor choice for anyone in the market for an encryption algorithm. However, many legacy protocols still use DES, so it's important to have implementations handy.

I recently found myself looking for a simple standalone DES implementation to study. Most of the open-source DES implementations are either highly optimized into obfuscation, or sloppily written. Either way, it's hard to find a clearly written and well-commented implementation suitable for educational purposes. I decided it would be a good exercise to write one myself. I wrote the implementation in Java, for the extra challenge of performing bit manipulations on signed primitive types. This implementation is undoubtedly very inefficient, but is well-commented and should be easy to understand for anyone who wants to dive into a sea of Feistel functions, S-boxes, variable rotations, and permutations.

References

• "Data Encryption Standard." Wikipedia, The Free Encyclopedia.
• "The DES Algorithm Illustrated." J. Orlin Grabbe
• "DES Calculator." Lawrie Brown

Downloads

• DES.java - My DES implementation in Java