Dice Random Numbers

Generating data with entropy, or random number generation (RNG), is a well-known difficult problem. Many crypto algorithms and protocols assumes random data is available. There are many implementations out there, including /dev/random in the BSD and Linux kernels and API calls in crypto libraries such as GnuTLS or OpenSSL. How they work can be understood by reading the source code. The quality of the data depends on actual hardware and what entropy sources were available — the RNG implementation itself is deterministic, it merely convert data with supposed entropy from a set of data sources and then generate an output stream.

In some situations, like on virtualized environments or on small embedded systems, it is hard to find sources of sufficient quantity. Rarely are there any lower-bound estimates on how much entropy there is in the data you get. You can improve the RNG issue by using a separate hardware RNG, but there is deployment complexity in that, and from a theoretical point of view, the problem of trusting that you get good random data merely moved from one system to another. (There is more to say about hardware RNGs, I’ll save that for another day.)

For some purposes, the available solutions does not inspire enough confidence in me because of the high complexity. Complexity is often the enemy of security. In crypto discussions I have said, only half-jokingly, that about the only RNG process that I would trust is one that I can explain in simple words and implement myself with the help of pen and paper. Normally I use the example of rolling a normal six-sided dice (a D6) several times. I have been thinking about this process in more detail lately, and felt it was time to write it down, regardless of how silly it may seem.

A die with six sides produces a random number between 1 and 6. It is relatively straight forward to intuitively convinced yourself that it is not clearly biased: inspect that it looks symmetric and do some trial rolls. By repeatedly rolling the die, you can generate how much data you need, time permitting.

I do not understand enough thermodynamics to know how to estimate the amount of entropy of a physical process, so I need to resort to intuitive arguments. It would be easy to just assume that a die produces 2.5 bits of entropy, because log_2(6)~=2.584. At least I find it easy to convince myself intuitively that 2.5 bits is an upper bound, there appears to me to be no way to get out more entropy than that out looking at a die roll outcome. I suspect that most dice have some form of defect, though, which leads to a very small bias that could be found with a large number of rolls. Thus I would propose that the amount of entropy of most D6’s are slightly below 2.5 bits on average. Further, to establish a lower bound, and intuitively, it seems easy to believe that if the entropy of particular D6 would be closer to 2 bits than to 2.5 bits, this would be noticeable fairly quickly by trial rolls. That assumes the die does not have complex logic and machinery in it that would hide the patterns. With the tinfoil hat on, consider a die with a power source and mechanics in it that allowed it to decide which number it would land on: it could generate seamingly-looking random pattern that still contained 0 bits of entropy. For example, suppose a D6 is built to produce the pattern 4, 1, 4, 2, 1, 3, 5, 6, 2, 3, 1, 3, 6, 3, 5, 6, 4, … this would mean it produces 0 bits of entropy (compare the numbers with the decimals of sqrt(2)). Other factors may also influence the amount of entropy in the output, consider if you roll the die by just dropping straight down from 1cm/1inch above the table. There could also be other reasons why the amount of entropy in a die roll is more limited, intuitive arguments are sometimes completely wrong! With this discussion as background, and for simplicity, going forward, I will assume that my D6 produces 2.5 bits of entropy on every roll.

We need to figure out how many times we need to roll it. I usually find myself needing a 128-bit random number (16 bytes). Crypto algorithms and protocols typically use power-of-2 data sizes. 64 bits of entropy results in brute-force attacks requiring about 2^64 tests, and for many operations, this is feasible with today’s computing power. Performing 2^128 operations does not seem possible with today’s technology. To produce 128 bits of entropy using a D6 that produces 2.5 bits of entropy per roll, you need to perform ceil(128/2.5)=52 rolls.

We also need to design an algorithm to convert the D6 output into the resulting 128-bit random number. While it would be nice from a theoretical point of view to let each and every bit of the D6 output influence each and every bit of the 128-bit random number, this becomes difficult to do with pen and paper. Update:This blog post used to include an algorithm here, however it was clearly wrong (written too late in the evening…) so I’ve removed it — I need to come back and think more about this.

So what’s the next step? Depends on what you want to use the random data for. For some purposes, such as generating a high-quality 128-bit AES key, I would be done. The key is right there. To generate a high-quality ECC private key, you need to generate somewhat more randomness (matching the ECC curve size) and do a couple of EC operations. To generate a high-quality RSA private key, unfortunately you will need much more randomness, at the point where it makes more sense to implement a PRNG seeded with a strong 128-bit seed generated using this process. The latter approach is the general solution: generate 128 bits of data using the dice approach, and then seed a CSPRNG of your choice to get large number of data quickly. These steps are somewhat technical, and you lose the pen-and-paper properties, but code to implement these parts are easier to verify compared to verifying that you get good quality entropy out of your RNG implementation.

The Case for Short OpenPGP Key Validity Periods

After I moved to a new OpenPGP key (see key transition statement) I have received comments about the short life length of my new key. When I created the key (see my GnuPG setup) I set it to expire after 100 days. Some people assumed that I would have to create a new key then, and therefore wondered what value there is to sign a key that will expire in two months. It doesn’t work like that, and below I will explain how OpenPGP key expiration works; how to extend the expiration time of your key; and argue why having a relatively short validity period can be a good thing.
Continue reading

Offline GnuPG Master Key and Subkeys on YubiKey NEO Smartcard

I have moved to a new OpenPGP key. There are many tutorials and blog posts on GnuPG key generation around, but none of them matched exactly the setup I wanted to have. So I wrote down the steps I took, to remember them if I need to in the future. Briefly my requirements were as follows:

  • The new master GnuPG key is on an USB stick.
  • The USB stick is only ever used on an offline computer.
  • There are subkeys stored on a YubiKey NEO smartcard for daily use.
  • I want to generate the subkeys using GnuPG so I have a backup.
  • Some non-default hash/cipher preferences encoded into the public key.

Continue reading

OpenPGP Key Transition Statement

I have created a new OpenPGP key 54265e8c and will be transitioning away from my old key. If you have signed my old key, I would appreciate signatures on my new key as well. I have created a transition statement that can be downloaded from https://josefsson.org/key-transition-2014-06-22.txt.

Below is the signed statement.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA512

OpenPGP Key Transition Statement for Simon Josefsson

I have created a new OpenPGP key and will be transitioning away from
my old key.  The old key has not been compromised and will continue to
be valid for some time, but I prefer all future correspondence to be
encrypted to the new key, and will be making signatures with the new
key going forward.

I would like this new key to be re-integrated into the web of trust.
This message is signed by both keys to certify the transition.  My new
and old keys are signed by each other.  If you have signed my old key,
I would appreciate signatures on my new key as well, provided that
your signing policy permits that without re-authenticating me.

The old key, which I am transitioning away from, is:

pub   1280R/B565716F 2002-05-05
      Key fingerprint = 0424 D4EE 81A0 E3D1 19C6  F835 EDA2 1E94 B565 716F

The new key, to which I am transitioning, is:

pub   3744R/54265E8C 2014-06-22
      Key fingerprint = 9AA9 BDB1 1BB1 B99A 2128  5A33 0664 A769 5426 5E8C

The entire key may be downloaded from: https://josefsson.org/54265e8c.txt

To fetch the full new key from a public key server using GnuPG, run:

  gpg --keyserver keys.gnupg.net --recv-key 54265e8c

If you already know my old key, you can now verify that the new key is
signed by the old one:

  gpg --check-sigs 54265e8c

If you are satisfied that you've got the right key, and the User IDs
match what you expect, I would appreciate it if you would sign my key:

  gpg --sign-key 54265e8c

You can upload your signatures to a public keyserver directly:

  gpg --keyserver keys.gnupg.net --send-key 54265e8c

Or email simon@josefsson.org (possibly encrypted) the output from:

  gpg --armor --export 54265e8c

If you'd like any further verification or have any questions about the
transition please contact me directly.

To verify the integrity of this statement:

  wget -q -O- https://josefsson.org/key-transition-2014-06-22.txt|gpg --verify

/Simon
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.12 (GNU/Linux)

iLwEAQEKAAYFAlOnV+AACgkQ7aIelLVlcW89XgUAljJgYfReyR9/bU+Om6UHUttt
CAOgSRqdcQSQ2hT69vzuhb/bc8CslIQcBtGqTgxDFsxEFhbm5zKn+tSzy5MHNHqt
MsqHcZjlYuYVhMXDhka+cfyhtd9zIxjVE5vk8v+GqEGoh8DGYq0vPy3VfvcSz5Z3
MSUpSj8gN00jlU1z4nad3maEq0ApvsLr8EsLZmtxF5TNFvzJ8mmwY+gHBGHjVYkB
8AQBAQoABgUCU6dX4AAKCRAGZKdpVCZejD1eDp46XGL2puMp0le2OF75WIUW8xqf
TMiZeB99ruk3P/jvuLnGPP2J5o7SIKE50FkMEss0yvxi6jBlHk+cJeKWGXVjBpxU
0QHq063NU+kjbMYwDfi5ZxXqaKeYODJm8Xmfh3d7lRaWF5rUOosR8nC/OROSrhg4
TjlAbvbxpQsls/JPbbporK2gbAtMlzJPD8zC8z/dT+t0qjlce8fADugblVW3bACC
Kl53X4XpojzNd/U19tSXkIBdNY/GVJqci+iruiJ1WGARF9ocnIXVuNXsfyt7UGq4
UiM/AeDVzI76v1QnE8WpsmSXzi2zXe3VahUPhOU2nPDoL53ggiVsTY3TwilvQLfX
Av/74PIaEtCi1g23YeojQlpdYzcWfnE+tUyTSNwPIBzyzHvFAHNg1Pg0KKUALsD9
P7EjrMuz63z2276EBKX8++9GnQQNCNfdHSuX4WGrBx2YgmOOqRdllMKz6pVMZdJO
V+gXbCMx0D5G7v50oB58Mb5NOgIoOnh3IQhJ7LkLwmcdG39yCdpU+92XbAW73elV
kmM8i0wsj5kDUU2ys32Gj2HnsVpbnh3Fvm9fjFJRbbQL/FxNAjzNcHe4cF3g8hTb
YVJJlzhmHGvd7HvXysJJaa0=
=ZaqY
-----END PGP SIGNATURE-----

Creating a small JPEG photo for your OpenPGP key

I’m in the process of moving to a new OpenPGP key, and I want to include a small JPEG image of myself in it. The OpenPGP specification describes, in section 5.12.1 of RFC 4880, how an OpenPGP packet can contain an JPEG image. Unfortunately the document does not require or suggest any properties of images, nor does it warn about excessively large images. The GnuPG manual helpfully asserts that “Note that a very large JPEG will make for a very large key.”.

Researching this further, it seems that proprietary PGP program suggests 120×144 as the maximum size, although I haven’t found an authoritative source of that information. Looking at the GnuPG code, you can see that it suggests around 240×288 in a string saying “Keeping the image close to 240×288 is a good size to use”. Further, there is a warning displayed if the image is above 6144 bytes saying that “This JPEG is really large”.

I think the 6kb warning point is on the low side today, however without any more researched recommendation of image size, I’m inclined to go for a 6kb 240×288 image. Achieving this was not trivial, I ended up using GIMP to crop an image, resize it to 240×288, and then export it to JPEG. Chosing the relevant parameters during export is the tricky part. First, make sure to select ‘Show preview in image window’ so that you get a file size estimate and a preview of how the photo will look. I found the following settings useful for reducing size:

  • Disable “Save EXIF data”
  • Disable “Save thumbnail”
  • Disable “Save XMP data”
  • Change “Subsampling” from the default “4:4:4 (best quality)” to “4:2:0 (chroma quartered)”.
  • Try enabling only one of “Optimize” and “Progressive”. Sometimes I get best results disabling one and keeping the other enabled, and sometimes the other way around. I have not seen smaller size with both enabled, nor with both disabled.
  • Smooth the picture a bit to reduce pixel effects and size.
  • Change quality setting, I had to reduce it to around 25%.

See screenshot below of the settings windows.

GnuPG photo GIMP settings window

Eventually, I managed to get a photo that I was reasonable happy with. It is 240×288 and is 6048 bytes large.

GnuPG photo for Simon

If anyone has further information, or opinions, on what image sizes makes sense for OpenPGP photos, let me know. Ideas on how to reduce size of JPEG images further without reducing quality as much would be welcome.

Portable Symmetric Key Container (PSKC) Library

For the past weeks I have been working on implementing RFC 6030, also known as Portable Symmetric Key Container (PSKC). So what is PSKC? The Portable Symmetric Key Container (PSKC) format is used to transport and provision symmetric keys to cryptographic devices or software.

My PSKC Library allows you to parse, validate and generate PSKC data. The PSKC Library is written in C, uses LibXML, and is licensed under LGPLv2+. In practice, PSKC is most commonly used to transport secret keys for OATH HOTP/TOTP devices (and other OTP devices) between the personalization machine and the OTP validation server. Yesterday I released version 2.0.0 of OATH Toolkit with the new PSKC Library. See my earlier introduction to OATH Toolkit for background. OATH Toolkit is packaged for Debian/Ubuntu and I hope to refresh the package to include libpskc/pskctool soon.

To get a feeling for the PSKC data format, consider the most minimal valid PSKC data:

<?xml version="1.0"?>
<KeyContainer xmlns="urn:ietf:params:xml:ns:keyprov:pskc" Version="1.0">
  <KeyPackage/>
</KeyContainer>

The library can easily be used to export PSKC data into a comma-separated value (CSV) format, in fact the PSKC library tutorial concludes with that as an example. There is complete API documentation for the library. The command line tool is more useful for end-users and allows you to parse and inspect PSKC data. Below is an illustration of how you would use it to parse some PSKC data, first we show the content of a file “pskc-figure2.xml”:

<?xml version="1.0" encoding="UTF-8"?>
<KeyContainer Version="1.0"
	      Id="exampleID1"
	      xmlns="urn:ietf:params:xml:ns:keyprov:pskc">
  <KeyPackage>
    <Key Id="12345678"
         Algorithm="urn:ietf:params:xml:ns:keyprov:pskc:hotp">
      <Issuer>Issuer-A</Issuer>
      <Data>
        <Secret>
          <PlainValue>MTIzNA==
          </PlainValue>
        </Secret>
      </Data>
    </Key>
  </KeyPackage>
</KeyContainer>

Here is how you would parse and pretty print that PSKC data:

jas@latte:~$ pskctool -c pskc-figure2.xml 
Portable Symmetric Key Container (PSKC):
	Version: 1.0
	Id: exampleID1
	KeyPackage 0:
		DeviceInfo:
		Key:
			Id: 12345678
			Issuer: Issuer-A
			Algorithm: urn:ietf:params:xml:ns:keyprov:pskc:hotp
			Key Secret (base64): MTIzNA==

jas@latte:~$

For more information, see the OATH Toolkit website and the PSKC Library Manual.

Using OATH Toolkit with Dropbox

Today there was an announcement that Dropbox supports two-factor authentication. On their page with detailed instructions there is (at the bottom) a link to the man page of the OATH Toolkit command line utility oathtool. OATH Toolkit is available in Ubuntu 12.04 and Debian Wheezy. (Note that the 1.10.4 version in Ubuntu does not support the base32 features.) There is not a lot of details in the documentation on Dropbox’s site on how to use oathtool, but I have experimented a bit with the setup and I’d like to share my findings. I assume you are somewhat familiar with the OATH Toolkit; if not I suggest reading my earlier introduction to OATH Toolkit.

To use OATH Toolkit’s command line utility to generate OTPs that are accepted by Dropbox, here is how you proceed. When you enable two-factor authentication on Dropbox’s site, you must select “Use a mobile app” and on the next screen with the QR code image, click the “enter your secret key manually” link. You will then be presented with a code that looks like this: gr6d 5br7 25s6 vnck v4vl hlao re

Now this code is actually space-delimitted base32 encoded data, without any padding. Since version 1.12.0, oathtool can read base32 encoded keys. However, parsing the raw string fails, so to make it work, you need to remove the spaces and add padding characters. I have yet to see any documentation on the Dropbox implementation, but I assume they always generate 16 binary octets that are base32 encoded into 26 characters like the codes that I have seen. The code is the cryptographic key used for the HMAC-SHA1 computation described in the RFC 6238 that specify OATH TOTP. If you study the base32 encoding you discover that 26 characters needs six pad characters. So converted into proper base32, the string would be gr6d5br725s6vnckv4vlhlaore======. Now generating OTPs are easy, see below.

jas@latte:~$ oathtool --verbose --totp --base32 "gr6d5br725s6vnckv4vlhlaore======"
Hex secret: 347c3e863fd765eab44aaf2ab3ac0e89
Base32 secret: GR6D5BR725S6VNCKV4VLHLAORE======
Digits: 6
Window size: 0
Step size (seconds): 30
Start time: 1970-01-01 00:00:00 UTC (0)
Current time: 2012-08-27 21:22:54 UTC (1346102574)
Counter: 0x2ACA9C5 (44870085)

125860
jas@latte:~$

Dropbox’s implementation is robust in that it requests a valid OTP from me, generated using the secret they just displayed, before proceeding. This verifies that the user was able to import the key correctly, and that the users’ OATH TOTP implementation appears to work. If I type in the OTP generated from oathtool this way, it allowed me to enable two-factor authentication and I agreed. From that point, signing into the Dropbox service will require a OTP. I invoke the tool, using the same arguments as above, and the tool will use the current time to compute a fresh OTP.

Reflecting on how things could work smoother, I suppose oathtool could be more permissive when it performs the base32 decoding so that the user doesn’t have to fix the base32 spacing/padding manually. I’ll consider this for future releases.

Unattended SSH with Smartcard

I have several backup servers that run the excellent rsnapshot software, which uses Secure Shell (SSH) for remote access. The SSH private key of the backup server can be a weak link in the overall security. To see how it can be a problem, consider if someone breaks into your backup server and manages to copy your SSH private key, they will now have the ability to login to all machines that you take backups off (and that should be all of your machines, right?).

The traditional way to mitigate SSH private key theft is by password protecting the private key. This works poorly in an unattended server environment because either the decryption password needs to be stored in disk (where the attacker can read it) or the decrypted private key has to be available in decrypted form in memory (where attacker can read it).

A better way to deal with the problem is to move the SSH private key to a smartcard. The idea is that the private key cannot be copied by an attacker who roots your backup server. (Careful readers may have spotted a flaw here, and I need to explain one weakness with my solution: an attacker will still be able to login to all your systems by going through your backup server, however it will require an open inbound network connection to your backup server and the attacker will never know what your private key is. What this does is to allow you to more easily do damage control by removing the smartcard from the backup server.)

In this writeup, I’ll explain how to accomplish all this on a Debian/Ubuntu-system using a OpenPGP smartcard, a Gemalto USB Shell Token v2 with gpg-agent/scdaemon from GnuPG together with OpenSSH.

Continue reading

Introducing the OATH Toolkit

I am happy to announce a project that I have been working quietly on for about a year: the OATH Toolkit. OATH stands for Open AuTHentication and is an organization that specify standards around authentication. That is a pretty broad focus, but practically it has translated into work on specifying standards around deploying and using electronic token based user authentication such as the YubiKey.

YubiKey

OATH’s most visible specification has been the HOTP algorithm which is a way to generate event-based one-time passwords from a shared secret using HMAC-SHA1. HOTP has been published through the IETF as RFC 4226. Built on top of HOTP is the time-based variant called TOTP, which requires a clock in the token. OATH do some other work too, like specifying a data format for transferring the token configuration data (e.g., serial number and shared secret) called PSKC.
Continue reading

On Password Hashing and RFC 6070

The RFC Editor has announced a new document, RFC 6070, with test vectors for PKCS5 PBKDF2. The document grow out of my implementation of SCRAM for GNU SASL. During interop testing, more than one other implementation turned out to have mistakes in the PBKDF2 implementation. It didn’t help that there weren’t any stable test vectors for PBKDF2, so that we could do black-box testing of our PBKDF2 implementations against well-known and stable test vectors. Debugging this was time consuming. The document addresses this problem.

So what is PBKDF2?
Continue reading