Authenticated Key Exchange with SPEKE or DH-EKE

I’ve been researching PAKE algorithms recently and there doesn’t seem to be a good explanation of Encrypted Key Exchange with Diffie Hellman (DH-EKE) out there. The best way to learn something is to teach it. So in that spirit, here follows my explanation of SPEKE and DH-EKE.

The Problem

Alice and Bob want to exchange data. This data is sensitive, so it needs to be encrypted and authenticated. Traditionally, there are two methods that can be used to solve this problem.

The first method is to use public-key cryptography; most commonly x509 certificates. This can provide very strong cryptography. However, it also has some weaknesses. The biggest weakness is how to trust the remote certificate. PKI is the traditional solution. But this involves trusting a third party (or, more usually, many third parties). In the current climate of espionage, this is likely to be unacceptable to Alice and Bob. Additionally, in many x509 setups, the user authentication actually happens within the encrypted channel; often by sending a password over the wire. Ewww.

The second method is to use symmetric cryptography; most commonly a shared password. The problem here is that the strength of the cryptography is inversely related to the usability of the cryptography: no easy to remember password can have the same entropy as a randomly generated 4096-bit number.

The Solution

Enter PAKE. Password Authenticated Key Exchange allows Alice and Bob to establish an ad hoc session key used to encrypt all their data with strong cryptography while establishing mutual trust through a shared password. Further more, when using PAKE, an attacker who is able to listen in on the conversation or modify the packets sent will learn nothing about the password used to authenticate the exchange nor about the strong session key itself. Nor is any trust on a third party required.

The basic principle of PAKE is to use a weak shared password to authenticate an exchange of strong, randomly generated public keys. Once completed, these keys can be used to derive session keys. Even though weak passwords are used, they are (hopefully) used in such a way so as not to jeopardize the creation of a strong session key.

While there are a variety of PAKE algorithms, in this article I will be focusing on two very similar algorithms: SPEKE and DH-EKE. These two algorithms are well defined and tested. That is not to say that they are perfectly secure. Both algorithms have various weaknesses. Some newer algorithms promise to solve some of these problems. It is, however, outside the scope of this article to evaluate all of these. So I’ll stick with two of the more traditional algorithms.

Diffie-Hellman Key Exchange

Diffie-Hellman Key Exchange

In order to understand DH-EKE or SPEKE, we must first understand the underlying Diffie-Hellman Key exchange (DHKE). DHKE allows two parties to create a key used for exchanging encrypted data from the exchange of two public keys from a set of public/private key pairs.

In the table above, uppercase values are private (they need to be secret) and lowercase values are public.

Here is how it works (these numbers correspond to the steps in the above table):

  1. Both parties agree on parameters of the exchange. These parameters are public and this agreement can happen over the network. The variable p is a large safe prime. Similarly, g is a generator for a finite cyclic group.
  2. Alice generates a random private key (A) and a corresponding public key (a). Bob does the same (B and a, respectively).
  3. Both parties exchange their public keys over the network.
  4. Alice calculates the encryption key (K) by raising Bob’s public key (b) to the power of her own secret key (A) modulo p. Similarly, Bob calculates the same encryption key (K) by raising Alice’s public key (a) to the power of his own secret key (B) modulo p.
  5. All network data is encrypted using the calculated key. Data can be decrypted by either party’s secret key. Since these are never transmitted over the network and it is not possible to determine the private key from the public key or the parameters, an eavesdropper cannot decrypt the data.

A few caveats are necessary at this point.

First, K is almost never used as the encryption key directly, since it may have some weak bits. Usually, a derived key (K’) is calculated using hashing to eliminate this weakness.

Second, while it is true that K (or K’) is secret and anything it encrypts can be decrypted only by the two parties who performed this exchange, this is completely vulnerable to a man-in-the-middle (MitM) attack. This is because neither side of the exchange is authenticated. Hence the need for an authenticated key exchange.

Simple Password Exponential Key Exchange (SPEKE)

Simple Password Exponential Key ExchangeSPEKE makes only one small change to the Diffie-Hellman Key Exchange. Rather than agreeing on a shared generator, each party will compute a generator (G; Step 2) by squaring the hash of some shared password. Because the generator (G) is now derived from a password, it is private.

Note that in Step 5, Alice’s computation of K will be the same as Bob’s computation of K if and only if the shared password used in Step 2 are the same. Hence, if only Alice and Bob know the shared password, then this algorithm is safe from a MitM attack. And since the generator (G) is private, no offline dictionary attack is possible.

Note well, however, that no validation of K has occurred. So while Alice knows that data encrypted with K cannot be read by anyone but Bob, she still doesn’t know whether the person on the other end of the exchange is, in fact, Bob. If it isn’t Bob on the other end, K will contain a nonsensical value and any data encrypted by it will be irretrievable (assuming the security of the underlying cryptography system).

SPEKE has two major weakness, however.

First, because the hash of the password is squared to create the generator (G), there is a guaranteed collision of an inverse hash. That is, both the hash of the password and the inverse of the hash of the password will output the same generator (G). This means that a clever attacker could, with some advanced planning, attempt at least two password guesses at once; halving the time required to successfully execute a dictionary attack.

Second, because the square of the hash of the password cannot efficiently generate a point on an elliptic curve, SPEKE is entirely incompatible with elliptic curve cryptography. It is possible to work around this by using an admissible encoding formula to ensure that all potential password hash values can be permuted to fall as a point on an elliptic curve.

Diffie-Hellman Encrypted Key Exchange

Diffie-Hellman Encrypted Key ExchangeLike SPEKE, DH-EKE presumes that each side knows a shared secret. This is typically a hash of a password (Step 1). However, instead of changing the generator (g), DH-EKE encrypts one or both of the public keys during transmission (Step 4a, 4b, and 4c list the traditional variants; all of equal strength). This leads to two outcomes.

First, because this encryption is unauthenticated, so long as the public keys (a or b) are indistinguishable from random, it will be impossible to tell whether or not decryption of these values was successful or not; making offline dictionary attacks impossible.

Second, if Alice’s password is different from Bob’s, then Alice’s K will be different than Bob’s K. This implies that a MitM attack is also impossible. Note well, again, that no validation of K has occurred. Hence, if Alice encrypts something for Bob using K, it will be decryptable if and only if Bob is on the other side of the connection and he knows the password. Otherwise, the resulting encrypted data will be undecryptable.

Like SPEKE, DH-EKE has two weaknesses. Both of these weaknesses are caused by the presumption that the public keys are indistinguishable from random.

First, when using standard discrete log problems, at least some of the bits of the public keys are predictable. This is by definition since the value of the public key is between 1 and p-1 and the buffer it is sent in is a multiple of 8-bits. Thus, there will always be some zero bits. While this is not likely to enable an offline dictionary attack, it may be sufficient to allow offline elimination of some passwords. There may be some way to mitigate these weak bits, but there is no such mitigation standardized so any attempted mitigation is of unknown value.

Second, the same problem exists for elliptic curves, only much worse. This weakness at least has a workaround where admissible encodings can be used to hash the elliptic curve points before being encrypted. This has been well defined in the EC-DH-EKE with an admissible encoding variant; along with several other derivatives of this approach. It is beyond the scope of this article to enumerate all of these.

Key Validation

Key Validation

I have elected to omit key validation from the descriptions of SPEKE and DH-EKE above. However, key validation is necessary in most cases to establish trust. There are a variety of methods for implementing key validation. I have listed two commonly used validation techniques in the above table. Both of them use some undefined key derivation technique to derive K’ from K.

In validation Option 1, Alice and Bob independently create a random value. After exchanging the random values using the specified schema, each side can test that the returned random value matches the one that was sent. This proves that both sides have the same K.

In validation Option 2, Alice and Bob simply exchange hashed values of K’. Since either side can compute these values independently, each side can verify the other value. Again, this proves that both sides have the same K.

 

 

 

 

 

 

 

FreeOTP Releases

The past few weeks have seen new releases of FreeOTP on both of our supported platforms.

FreeOTP iOS

FreeOTP iOS
FreeOTP iOS

On iOS, we released a small bug-fix release to the initial version we published several months ago. Aside from a crasher bug, the main theme of this release is UI refinement.

Editing and reordering is now modal. When in edit mode, a single press will bring up the edit menu and a long-press will activate reordering. We also now properly handle scrolling when there are too many tokens for the screen. Lastly, the token is automatically copied to the clipboard when activating a new token code.

All in all, this is a solid release.

FreeOTP Android

FreeOTP Android
FreeOTP Android

On Android, we released a major release which brings many new features and UI refinements. The biggest of these is image support. Images can be selected for each token. Images can also be provisioned to the device via an undocumented OTP URI query parameter. Aside from image support, the UI has begun to shift towards the Material Design specifications (for the upcoming Android L release). This includes a change from the card UI to a grid UI. Additionally, like iOS, tokens are now automatically copied to the clipboard.

One note about permissions is necessary. In the new Android release, the INTERNET and READ_EXTERNAL_STORAGE permissions are now required. In the latter case, this enables us to read images stored on the external storage. In the former case, this permits OTP token provisioners (the people who give you the QR code) to bundle a link to a token image. We feel this features is worth the additional permission. In the case of iOS, FreeOTP already has these permissions and uses them responsibly. Android will be no different. If you don’t trust us, you can read the code.

If you are running CyanogenMod, or have installed an app which allows you to manage permissions on installed apps, you can feel free to turn off the internet permission. You will not lose any functionality except automatic provisioning of token images.

Side Tabs for Empathy in Fedora 20

Andres Gomez recently made a patch for Empathy to put the tabs on the side. This patch is fantastic for any of us who idle in a large number of IRC channels. Since that includes me, I have created a COPR repo with a build of Empathy that includes this patch. So if you’re running F20 and using rhughes’ build of GNOME 3.12 and would like to use side tabs in Empathy, feel free to use it.

FreeOTP in Your Own Language

On Monday we announced the immediate availability of FreeOTP, the open source OTP app for Android.  The response has been fantastic! We immediately had a huge surge in installs and a lot of positive reviews. If you haven’t yet had a chance to post your review, do it now.

However, unless your language is English, FreeOTP doesn’t currently speak your language. Help us solve this problem! Translating Android apps isn’t difficult, and in most cases requires little other than editing an XML file. If you would like to contribute a translation, please file a ticket or send us an email. We’re glad to help you any way we can!

Announcing FreeOTP

I’d like to announce the general availability of FreeOTP for Android. It is available for install now in the Google Play store.

FreeOTP is a multi-factor authentication client based on the HOTP and TOTP standards. FreeOTP features:

  • A FLOSS code base
  • Support for HOTP or TOTP
  • Native QR code scanning
  • Adherence to the Android UI design principles
  • Tablet support

We anticipate that FreeOTP should work with any server providing HOTP or TOTP support, including the upcoming OTP support in FreeIPA.

So, if you fancy a bit of adventure, please try FreeOTP! We welcome your feedback. Please also don’t forget to leave your positive reviews on Google Play so that it will be easier for other Android users to find out about FreeOTP.

We have also developed FreeOTP for iOS and are currently working to bring it to the Apple App Store. Please stay tuned for future news!

The FreeOTP project is hosted on Fedora Hosted. We welcome your feedback and contributions.

Lexington in exemplum

Bluegrass Airport is a microcosm of Lexington, KY. It is also a fantastic example of everything I love about living here. To be sure it is a small airport: one terminal, two concourses and a collection of puddle-jumpers that fly only to larger airports. But everything about flying here reminds me of why I choose to live in the Bluegrass.

There is never traffic leading into the airport, nor could you get confused about where to go. Everything is clearly labelled. The landscaping is well appropriated and the buildings are clean, modern and offer free WiFi. I have only once seen a line for security, and it was when a large group was flying. Every employee, both public and private, smiles and wishes you good day or a safe flight.

Flying out of Lexington may be small on features, but it is big on charm. It has one restaurant (deSha’s) and one coffee stand. But the food is always high quality, prepared quickly and at a fair price. On my last trip, upon approaching the desk of the coffee stand, I was offered an apology that they had just raised their prices. However, they told me that since I was the first customer since the price raise they would give me my item at the old price!

This theme extends all over Lexington. While it may not have everything, it is big enough to have everything you need without the problems larger cities face. It is clean, friendly, well appointed and with an abundance of charm (especially, driving through its nearby horse farms). You couldn’t ask for a better place to raise a family!

Seth Vidal in Memoriam

I was extremely saddened today to hear of the loss of Seth Vidal. Although I can’t claim to have known him well, we had met on several occasions and was able to work on a side project with him. Seth will always be special to me because my first foray into Python was reading and attempting to understand some code he had written. Seth also had a great sense of humor. He could turn almost anything into a joke. Seth’s impact on Fedora was in many ways immeasurable. Judging by his code and infrastructure alone couldn’t do him justice. His wit and enthusiasm were contagious.

My sincerest condolences go out to his family and friends. Our thoughts and prayers are with you.

FreeIPA Two Factor Authentication Test Day

Welcome testdayers! Today’s test day will feature FreeIPA’s new Kerberos OTP support.

FreeIPA’s OTP support is a new feature and we are not yet providing a comprehensive management UI. But with a little tweaking of LDAP via some provided helper scripts, we should be able to test upstream plumbing work that makes OTP possible on MIT krb5.

Please check out the test day page where you will find live CDs and instructions on how to test. In particular, we are actively looking for people to test OTP against your own third party 2FA services. This will help us establish a list of known good solutions and give us targets for improving our compatibility.

Wether you join us on IRC or via email, we look forward to hearing from you!

 

QEMU with PowerPC64 Guests

TL;DR

For a fully functioning Debian Sid PPC64 guest image, follow the README.txt here: http://npmccallum.fedorapeople.org/qemu/ppc64/debian/

QEMU 1.4.0

With QEMU 1.4.0, PPC64 guests are close to working out of the box. It took some exploration to figure out exactly how to make this work, but it is mostly simple once you figure it out. In short, PPC64 emulation has a flakey IDE controller. This causes random lockups. You can work around this on Debian Sid.

Things that Don’t Work

  • virtio disks: This appears to be a QEMU problem as I can’t get it to work without random lockups on numerous distros, most notably Fedora 18.
  • graphical console: The only way to get the system to boot is with -nographic.
  • boot-loader after install: I’m not sure why, but this crashes QEMU. The workaround is to load the kernel/initrd directly and bypass the boot-loader.
  • power management: There are no fancy features like rebooting or powering off. You’ll have to do it manually.
  • Fedora 18: The PPC64 ISO appears not to have drivers for either the ATA or SCSI controllers that QEMU supports. Since virtio support doesn’t appear to work (see above), that means Fedora 18 has no disk driver support.

Installing Debian Sid

  1. Create a temporary directory:

    mkdir ppc64; cd ppc64

  2. Download the Debian Sid kernel image:

    wget http://ftp.us.debian.org/debian/dists/sid/main/installer-powerpc/current/images/powerpc64/netboot/vmlinux

  3. Download the Debian Sid initrd image:

    wget http://ftp.us.debian.org/debian/dists/sid/main/installer-powerpc/current/images/powerpc64/netboot/initrd.gz

  4. Create a disk image:

    qemu-img create -f qcow2 debian-sid-ppc64.qcow2 10G

  5. Start QEMU:

    qemu-system-ppc64 -nographic -hda debian-sid-ppc64.qcow2 -kernel vmlinux -initrd initrd.gz -append “console=ttyPZ0 libata.dma=0 debian-installer/allow_unauthenticated=true”

    1. console=ttyPZ0 – This is needed to make the console work when using -nographic.
    2. libata.dma=0 – This disables DMA on the ATA controller. It makes the controller more stable (NOTE: I didn’t say perfectly stable…).
    3. debian-installer/allow_unauthenticated=true – When I tried to install the first time through, I got to the end and got complaints about unsigned packages. This is likely a simple error in the repo. NOTE WELL: this option disables security.
  6. Follow install instructions.
  7. When the OS tries to reboot, it won’t work. Just shut down the VM.
  8. Start QEMU again:

    qemu-system-ppc64 -nographic -hda debian-sid-ppc64.qcow2

  9. Notice that QEMU crashes: Uh oh!
  10. Use qemu-nbd to mount your boot/root partition and extract the kernel and initrd images. Alternatively, just download them from here.
  11. Start QEMU again:

    qemu-system-ppc64 -nographic -hda debian-sid-ppc64.qcow2 -kernel vmlinux-3.2.0-4-powerpc64 -initrd initrd.img-3.2.0-4-powerpc64 -append “console=ttyPZ0 libata.dma=0 root=/dev/sda3″

  12. Bask in all the PPC64 guest glory!

 

 

 

Migrating the Blog to OpenShift

So this weekend I migrated the blog to Red Hat’s awesome new OpenShift service. If you are reading this, it means the migration was successful! Overall it went fairly smoothly. I’ve migrated my install multiple times at this point, so I was familiar with the process. But I also found that Deon Garrett has written some great documentation.

One of the problems identified by Deon is the inability to CNAME the root of the domain. Basically he uses a common domain provider’s URL Forwarding feature to redirect example.com to www.example.com. This workaround is great for a typical WordPress install. But for a subdomain-style, multisite installation, you have a problem where his forwarding approach results in an infinite redirect loop.

The key is that in a subdomain-style multisite installation, WordPress redirects www.example.com back to example.com. In order to fix this, we need to trick WordPress into thinking that www.example.com is, in fact, example.com. You can do this simply by adding a single line to your .htaccess file:

RequestHeader edit Host “^www\.(.*)$” “$1″

This line strips ‘www.’ from the start of every Host header. This works in my installation, but you might need something a bit more specific for your installation. For additional options, see mod_headers.

If you have interest in deploying WordPress on OpenShift, you should note that I have provided pull requests for updating OpenShift’s WordPress to 3.5.1 (the latest) and for enabling multisite WordPress uploads.

Happy OpenShifting!