Image of the glider from the Game of Life by John Conway
Skip to content

Getting Root On The Nexus 6 With Android 6

This probably the 40th millionth time, since owning this phone, that I've needed to root my device. Because I keep doing it over and over, while also referring to past commands and notes, it's high time I blogged the steps. If I can benefit myself from my own blog post, then chances are someone else can. So, with that said, here's what we're going to do:

  1. Grab the latest Nexus factory images from Google.
  2. Update the phone by flashing all the images (without wiping user data).
  3. Flash the recovery with the latest TWRP image.
  4. Get root on the device with Chainfire's "system-less root" SuperSU package.
  5. Enable USB tethering and the wireless hotspot functionality.

Before beginning, I should mention that if the title isn't immediately clear, this post is specific to the Motorola Nexus 6, which is the phone I currently own. It's probably generic enough, however, to be applied to a few Nexus devices. Minus getting the factory Nexus images from Google, this might even be generic enough for non-Nexus devices, but you're on your own there. Proceed at your own risk. With that said, it's fairly hard to brick an Android phone these days.

Also, you need to make sure you have an unlocked bootloader. Google ships with the bootloader locked by default. Unlocking it, will wipe your user partition, meaning you will lose any and all user data (images, videos, text messages, application data, etc.). I'm going to assume that you've already unlocked the bootloader, and are ready to proceed.

TL;DR

If you don't want to read the post, and know what you're doing, here's the short of it:

$ tar -xf shamu-mmb29k-factory-9a76896b.tgz
$ cd shamu-mmb29k
$ adb reboot bootloader
$ fastboot flash bootloader bootloader-shamu-moto-apq8084-71.15.img
$ fastboot reboot-bootloader
$ fastboot flash radio radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img
$ fastboot reboot-bootloader
$ fastboot update image-shamu-mmb29k.zip
$ fastboot flash recovery twrp-2.8.7.1-shamu.img
$ fastboot reboot recovery
(reboot normally)
$ adb push UPDATE-SuperSU-v2.46.zip /sdcard/supersu.zip
$ adb reboot recovery
(install /sdcard/supersu.zip from TWRP)
(do not install TWRP root)
(reboot normally)
(install build.prop editor from Google Play)
(set "net.tethering.noprovisioning" to "true")

Otherwise ...

Getting the Google Nexus factory images

Navigate to https://developers.google.com/android/nexus/images#shamu and grab the version you are looking for. For example, I recently wanted to flash 6.0.1, so I grabbed the "MMB29K" image. Before flashing, I find it critical to verify the checksums. They are "27dde1258ccbcbdd3451d7751ab0259d" for MD5 and "9a76896bed0a0145dc71ff14c55f0a590b83525d" for SHA-1. So, after downloading, I pulled up a terminal, and verified them:

$ md5sum shamu-mmb29k-factory-9a76896b.tgz
27dde1258ccbcbdd3451d7751ab0259d  shamu-mmb29k-factory-9a76896b.tgz
$ sha1sum shamu-mmb29k-factory-9a76896b.tgz 
9a76896bed0a0145dc71ff14c55f0a590b83525d  shamu-mmb29k-factory-9a76896b.tgz

After examination, it's clear these checksums match, so I'm ready to flash.

Flashing the images

This step does not require root on your device. I'll need to connect my phone to my computer via USB, and verify that I can talk to it via adb(1). This means installing the Debian "android-tools-adb" and "android-tools-fastboot" packages if they're not already. After installed, I should be able to verify that I can talk to the phone:

$ sudo apt-get install android-tools-adb android-tools-fastboot
(...snip...)
$ adb devices
List of devices attached 
[serial number]      device

If your device is visible, we are ready to rock-n-roll. First, extract the tarball, and enter the directory:

$ tar -xf shamu-mmb29k-factory-9a76896b.tgz
$ cd shamu-mmb29k
$ ls -lh
total 2.3G
-rw-r--r-- 1 atoponce atoponce  124 Jan  1  2009 android-info.txt
-rw-r--r-- 1 atoponce atoponce 8.1M Jan  1  2009 boot.img
-rw-r----- 1 atoponce atoponce  11M Nov 18 16:59 bootloader-shamu-moto-apq8084-71.15.img
-rw-r--r-- 1 atoponce atoponce 6.2M Jan  1  2009 cache.img
-rw-r----- 1 atoponce atoponce  985 Nov 18 16:59 flash-all.bat
-rwxr-x--x 1 atoponce atoponce  856 Nov 18 16:59 flash-all.sh*
-rwxr-x--x 1 atoponce atoponce  814 Nov 18 16:59 flash-base.sh*
-rw-r----- 1 atoponce atoponce 964M Nov 18 16:59 image-shamu-mmb29k.zip
-rw-r----- 1 atoponce atoponce 113M Nov 18 16:59 radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img
-rw-r--r-- 1 atoponce atoponce 8.8M Jan  1  2009 recovery.img
-rw-r--r-- 1 atoponce atoponce 2.0G Jan  1  2009 system.img
-rw-r--r-- 1 atoponce atoponce 136M Jan  1  2009 userdata.img

Notice a couple of things- first, there are shell scripts "flash-all.sh" and "flash-base.sh" for Unix-like systems. Also, notice the "bootloader-shamu-moto-apq8084-71.15.img" & "radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img" raw images, as well as the "image-shamu-mmb29k.zip". These are the only files we're going to concern ourselves with when flashing the phone.

However, we want to be careful that we don't flash "userdata.img". This will format your user partition and all user data will be wiped (see above). What we're going to do, is basically the same execution as the "flash-all.sh" shell script. However, we're going to make just one small modification. Further, we need our phone already booted into the bootloader. As such, here's what we're going to do:

$ adb reboot bootloader
$ fastboot flash bootloader bootloader-shamu-moto-apq8084-71.15.img
$ fastboot reboot-bootloader
$ fastboot flash radio radio-shamu-d4.01-9625-05.32+fsg-9625-02.109.img
$ fastboot reboot-bootloader
$ fastboot update image-shamu-mmb29k.zip

Notice that I removed -w from that last command (if you looked in the "flash-all.sh" shell script). That option wipes user data, which would be necessary if we wanted to return the phone back to factory state. We don't- we're just upgrading. Also, I don't see the need for "sleep 5". Just wait for the phone to successfully reboot before running the next command.

At this point, the phone is successfully updated. If you were to reboot the phone, it would be perfectly operational as if you did an OTA update, or purchased it from the store. However, we want root, so we have a few more steps to accomplish.

Getting and flashing TWRP

This step also does not require root on your phone. I prefer TWRP for my recovery on Android. It's touch-based, which sets the UI apart from the other recoveries, and it's Free Software, unlike ClockworkMod. Both of these are big wins for me. Grab the latest image at https://twrp.me/devices/motorolanexus6.html. I downloaded twrp-2.8.1.7-shamu.img. Unfortunately, I couldn't find any checksums to check to verify the download. So, I installed it anyway, knowing I could flash the stock "recovery.img" if something goes wrong. So far, things have been great, so I calculated the checksums for you:

$ md5sum twrp-2.8.7.1-shamu.img 
f040c3a26f71dfce2f04339f62e162b8  twrp-2.8.7.1-shamu.img
$ sha1sum twrp-2.8.7.1-shamu.img
40017e584879fad2be4043c397067fe4d2d76c88  twrp-2.8.7.1-shamu.img
$ sha256sum twrp-2.8.7.1-shamu.img
ebe5af833e8b626e478b11feb99a566445d5686671dcbade17fe39c5ce8517c7  twrp-2.8.7.1-shamu.img

If those checkout, you should be safe in flashing. Currently, the phone should already be booted into the bootloader. If not, make sure it is. Once in the bootloader, we can flash TWRP then reboot normally:

$ fastboot flash recovery twrp-2.8.7.1-shamu.img

Now, it's critical that we don't normally reboot the phone. If we do, recovery will be overwritten, and we'll have to reflash. So, while your phone is still booted into the bootloader, reboot it into recovery. You can do this by pressing the volume up/down arrows, until rebooting into recovery is available, and pressing the power button. This should boot you into TWRP. Now that you're there, you can reboot the phone normally.

WARNING
It is possible that while booting, your phone will notify you that the system cannot be verified. One of two things will happen: either the boot will pause, and not go further, or will boot without despite the warning. If you flashed these exact versions, my phone boots without the warning at all. However, don't panic if you see it. Remember, you have the factory images. Just reflash the recovery.img, and you will be just fine.

More info can be found at http://www.xda-developers.com/a-look-at-marshmallow-root-verity-complications/.

Getting and flashing SuperSU (getting root)

WARNING
At this point, the phone should be booted into its regular state. We are now ready to root the phone. This means getting the latest SuperSU package, and installing it through TWRP. However, I need to throw out another caution. We'll be installing a beta version of SuperSU to do something called "system-less root". This means that the package will only be modifying the bootloader image to get root, and will not be touching the system partition. This is both good, and bad. It's good in that we only need to reflash the bootloader to remove root. It's bad in that this is experimental software, and really not ready for production. Further, unlike TWRP, SuperSU is proprietary software, which sucks. It does make me a bit nervous, to be honest, to rely on non-free closed-source proprietary software, on such a critical piece of my life. Proceed at your own risk.

As of this writing, you'll need to get the SuperSU package from the XDA forums at http://forum.xda-developers.com/showpost.php?p=64161125&postcount;=3. I grabbed version "BETA-SuperSU-v2.64-20151220185127.zip". There may be updates since this post was published.

Unfortunately, again, I did not see any published checksums. So, I've installed it, with the knowledge of how to reflash my bootloader should I encounter problems.

$ md5sum UPDATE-SuperSU-v2.46.zip 
332de336aee7337954202475eeaea453  UPDATE-SuperSU-v2.46.zip
$ sha1sum UPDATE-SuperSU-v2.46.zip 
6135f9d0af28e02f4292c324bf5983998e7ae006  UPDATE-SuperSU-v2.46.zip
$ sha256sum UPDATE-SuperSU-v2.46.zip 
d44cdd09e99561132b2a4cd19d707f7126722a9c051dc23f065a948c7248dc4e  UPDATE-SuperSU-v2.46.zip

Provided these checksums match, we're good to go. We need to push the ZIP to our phone with the Android debugger, and reboot into the TWRP recovery:

$ adb push UPDATE-SuperSU-v2.46.zip /sdcard/supersu.zip
$ adb reboot recovery

From the TWRP interface, tap "Install" and install the /sdcard/supersu.zip package. When it finishes, tap "Reboot". TWRP will ask if you would like to install the root provided by the image. You do NOT want to install this root- you just flashed one.

The phone should boot normally.

Enable USB tethering and the wireless hotspot

This step requires root. Finally, we want to enable the hotspot and tethering. Google is bending to wireless carriers, forcing the user to prove that they are subscribing to a cellular service that allows them to use USB tethering or the wireless hotspot. Personally, I find this dirty, and unfortunate. Even worse, is the fact that cellular providers think they can get away by charging double for using your own data. Data is data; it shouldn't matter if it comes from your phone, or your laptop connected to your phone. If they want to charge for overages on caps, whatever. But charging double, just because you connected your phone via USB? Or setting up a hotspot in your grandma's house, because she doesn't have WiFi but you have cellular coverage? Please. This is clearly grandfathered from the days of feature phones, where you couldn't tether or hotspot. So, you purchased a USB dongle to enable the hotspot. Even then, it was dirty, but it's clear that this is a byproduct of days gone by.

To enable tethering and the hotspot, you just need to add one line to /system/build.prop config file. Unfortunately, /system/ is mounted read-only. So, you'll have to remount it as read-write and edit the file. However, every attempt I have made at modifying it has ended up with an empty file- IE: losing all its contents. So, rather than editing it manually, there is an app for that.

Install https://play.google.com/store/apps/details?id=com.jrummy.apps.build.prop.editor&hl=en. Add "net.tethering.noprovisioning" and set the property to "true", then reboot your phone. At that point, you should be able to USB tether and setup a wireless hotspot.

Conclusion

This wasn't for the faint of heart or for someone who doesn't care about gaining the necessary control over their Android phone that root would give them (setting up firewalls, ad blockers, tethering/hotspot, etc.). However, as mentioned earlier, it's getting fairly difficult to hard brick and Android phone these days. Even better, the steps are getting somewhat standardized. IE: flash factory images, flash custom recovery, install SuperSU, & optionally enable tethering/hotspot.

Your GnuPG Private Key

This post is inspired by a discussion in irc://irc.freenode.net/#gnupg about Keybase and a blog post by Filippo Valsorda.

I was curious just exactly how my private key is encrypted. Turns out, gpg(1) can tell you directly:

$ gpg --output /tmp/secret-key.gpg --export-secret-keys 0x22EEE0488086060F
$ gpg --list-packets /tmp/secret-key.gpg
:secret key packet:
	version 4, algo 17, created 1095486266, expires 0
	skey[0]: [1024 bits]
	skey[1]: [160 bits]
	skey[2]: [1023 bits]
	skey[3]: [1023 bits]
	iter+salt S2K, algo: 3, SHA1 protection, hash: 2, salt: ad8d24911a490591
	protect count: 65536 (96)
	protect IV:  01 1e 07 58 4a b6 68 a0
	encrypted stuff follows
	keyid: 22EEE0488086060F
(...snip...)

Notice the line "iter+salt S2K, algo: 3, SHA1 protection, hash: 2, salt: ad8d24911a490591". In there, you see "algo: 3" and "hash: 2". What do those identifiers reference? If you refer to RFC4880, you can learn what they are:

Symmetric Encryption Algorithms

  1. Plaintext or unencrypted data
  2. IDEA
  3. 3DES
  4. CAST5
  5. Blowfish
  6. Reserved
  7. Reserved
  8. AES-128
  9. AES-192
  10. AES-256
  11. Twofish

Cryptographic Hashing Algorithms

  1. MD5
  2. SHA-1
  3. RIPEMD-160
  4. Reserved
  5. Reserved
  6. Reserved
  7. Reserved
  8. SHA-256
  9. SHA-384
  10. SHA-512
  11. SHA-224

I emphasized the defaults, which are CAST5 and SHA-1. So, your key is encrypted with the SHA-1 of your passphrase, which is used as the key for CAST5 to encrypt your private key. Thus, the whole security of your encrypted private key rests on the entropy of your passphrase, provided that sane defaults are chosen for the encryption and hashing algorithms, which they are.

CAST5 has been well analyzed and it is not showing any practical or near practical weaknesses. It is a sane default to chose for a symmetric encryption algorithm. However, CAST5 uses 64-bit blocks for encrypting and decrypting data, which may have some theoretical weaknesses. AES uses 128-bit blocks, and thus has a larger security margin. Because AES-256 is available as a symmetric encryption algorithm, there really is no reason to not use it, aside from feeling more secure.

SHA-1 is showing near practical attacks on blind collisions, but for use with keying a block cipher from a passphrase, it's still exceptionally secure. What is needed to break SHA-1 in this regard, is a pre-image attack. A pre-image attack is where you have the hash, but you do not know the input that created it. This is not brute force. This is able to break the algorithm in such a way, that provided with any hash, you can reliably produce its input. SHA-1 has a wide security margin here, so there really is nothing practical to worry about. However, with SHA-512 available, there is also really no reason why not to use a SHA-2 algorithm. In fact, aside from the increase security margin, SHA-512 is designed to work well on 64-bit platforms, but struggle with 32-bit. So this gives us an increased security margin, albeit negligible, against using something like SHA-256.

So, how can we change these? Turns out to be quite simple. All you need to do is specify the secret key symmetric encryption algorithm and hashing algorithm, then change your password (retype it with the same password if you don't want to change it):

$ gpg --s2k-cipher-algo AES256 --s2k-digest-algo SHA512 --edit-key 0x22EEE0488086060F
Secret key is available.

pub  1024D/0x22EEE0488086060F  created: 2004-09-18  expires: never       usage: SCA 
                               trust: unknown       validity: unknown
sub  1792g/0x7345917EE7D41E4B  created: 2004-09-18  expires: never       usage: E   
sub  2048R/0xCE7911B7FC04088F  created: 2005-07-04  expires: never       usage: S   
(...snip...)

gpg> passwd
(...snip...)
gpg> save

Now if we export our key, and look at the OpenPGP packets, we should see the new updates:

$ gpg --output /tmp/secret-key.gpg --export-secret-keys 0x22EEE0488086060F
$ gpg --list-packets /tmp/secret-key.gpg
:secret key packet:
	version 4, algo 17, created 1095486266, expires 0
	skey[0]: [1024 bits]
	skey[1]: [160 bits]
	skey[2]: [1023 bits]
	skey[3]: [1023 bits]
	iter+salt S2K, algo: 9, SHA1 protection, hash: 10, salt: 9c3dbf2880791f2e
	protect count: 65536 (96)
	protect IV:  db f5 e8 1c 98 03 99 7c 77 33 4e cd d3 3c 1f 4f
	encrypted stuff follows
	keyid: 22EEE0488086060F
(...snip...)

Now I have "algo: 9" which is "AES256" and "hash: 10" which is "SHA512" protecting my private key. I've gained a little bit extra security margin at the cost of retyping my passphrase. Not bad. Now, I'd like to pose you a question:

If I were to publish my encrypted GnuPG private key, think I'm crazy?

Let's look at this for a second. We know that the key is protected with AES-256. AES remains secure, after 15 years of intense scrutiny and analysis, and is showing no signs of wear. It's the most used symmetric encryption algorithm that protects HTTPS, SSH, VPN, OTR, Tor, and even your GnuPG encrypted emails. It protects social security numbers, credit card transactions, usernames and passwords, patient health records, hard drives, and on, and on, and on. AES is secure.

So, breaking the encrypted key will be at least as hard as breaking AES, which seems to be a long shot. So, you would be better off attacking my passphrase. Knowing that it was used as the key for AES, and that it is hashed with SHA-512, we can write a brute force algorithm to generate passphrases, hash them with SHA-512, and attempt at decrypting the AES key. After all, we have the salt and the IV right there in plaintext in the packets. Turns out, there are already projects for this.

This should be a breeze. Unless, of course, you have sufficient entropy behind your passphrase. What is sufficient entropy? Well, take some time searching "entropy" on my blog. You'll quickly learn that I recommend at least 80-bits. 100-bits would give you a paranoid security margin, even with the password being hashing with a fast hashing algorithm like SHA-512.

So, if the private key is encrypted with AES-256, and the passphrase has sufficient entropy to withstand a sophisticated attack, and it is hashed with SHA-512, then I should have no concern posting my encrypted key into the open, right?

Without further ado, here is my encrypted GnuPG private key:

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

- -----BEGIN PGP PRIVATE KEY BLOCK-----
Version: GnuPG v1

lQHpBEFLyzoRBACXCUta5CK+DCgnXn9wkqUumkcbenibGPBe3Y8IEY4BjkdbGdTN
tiGB+Tvo0hzn2qzy4mNPlOx/LWZWF2MdwF3WS77wwIskMb8W314zhE2RS0G318YY
X7zMGSF+7QiNXNsW/d0t1RonYOKIS96zKOtFQZrTr//V8+1rxEa4rvO5dwCgul0s
pt2BUDqwoy2Q/5UKgnmrzmsD/37/3g5zXykvTH2P6BlgTdfnVvpOLDT3CyWlAynz
u5hdmgYNT50I2w5TstY+uViYhAbMiyIT1HwBRcaQh8hUWkzDGyzJF7pS4pZeD0M9
u0P7Cejm2+ENdOX66ablWjP7GLJRcToGxnAZ6hgPpWLen8lHYaUK//g4JJx8UJ/n
wifeA/9xYWDi3ur/fFCKQZIPV9Ziw1oL58su948yWRn2WN7m74+bSldkXzkc4jRe
Q51FpGBHMswRIJKB6yG1FbfLum8ppGbvtz9NrMMZuirguTWetX8aJrjr0ddGjTsY
uZPfKoUiqDUXSFc3hmVgQQQ4MFdD3XYy6AQTyI1vstCS/Tdn7P4JAwqcPb8ogHkf
LmDb9egcmAOZfHczTs3TPB9Pg1SJqjvSz7nKDY87EVmeM46YBaCs1XScaOF4Gs+x
u0LNAxlfX3xOUIWRtCdBYXJvbiBUb3BvbmNlIDxhYXJvbi50b3BvbmNlQGdtYWls
LmNvbT6IWQQTEQIAGQUCQUvLOgQLBwMCAxUCAwMWAgECHgECF4AACgkQIu7gSICG
Bg/+cACeM0EeO7gE85/OSwMzxjvQAGB53jgAnik6qvFWyQtvp71KElbpZUsa0YNj
nQIoBEFLy0IQBwCjVGmY/PmOtRHtBIuANfg9zf8thGXZtFZWEgzHLGUgSfIjb0di
F24mwiVw2k3gzqBKuFBJ633F3AhwlTBnXS3tLWQgwSrm3BcCOOn+wJvwgUXa0iBn
gXhcq/7IL7HnKsYiG9EFMI8mAd10t7zdsA/dS2xUmFNexQvUdra/uRU+eeQbrXYe
iwfymw2RCZROl4/QXA9/a/aTyUhKgkj2vieo0jh394h7grPZxw0lgCclvTN/0jGq
dPkp56NMDb0eGlVzWeEiseD1JxXeYaSeToJP3zmx+nFoiBa+VVVeUhzYAwADBQb+
P373jEOwDu63py4FWdMPMYNWv1xFWLYI5hWaTKPSRwG/NZICRDF+QNztSmVOhW7Z
SFY/nTHq5yFp+QID63VMGv5Cunse9QXAoarecyV2hllwUq7l7wHujJhvvqyEgL9G
ah/drkZMGe8btYihz/M4g5i1P2DPr4CL/46eZxgjmjuVw7Nb0UsgUPgGizPCbnJ3
ye1ahxc1dOX80Guh0ZDRfR/ehZkk07wN2H6KRrxFCAmDaCR9KxwGYbpepND0t4HG
qCMji37lzYUrS4PV6yK0DGekqF98xgiIVBYFjF0jwQD+CQMKnD2/KIB5Hy5g4K9F
3JFIPxw+L+Gdc2MSYuJI3Y5kpZluUmYYYYFgOH64/J8egeYSSKWUIPqMhnwBWtbW
GQCNdztQyIIi6mB3YiDeK2AMnhRq+PwwwGG1iEYEGBECAAYFAkFLy0IACgkQIu7g
SICGBg+MhQCfZ7FNu4wMtdifkblGkN5Qqj+cYWYAoLiipdgnnhPTP2z7SgOsxiR4
YI4wnQPEBELI4BIBCADCobEk1f0sByuV4p2moEmZIXXEJhzTolO2mmBLBSmbjPMg
OBpAFTmWYXJxo8oZnNeeTOWN/hsHV9rmC/c/bZ7FGX4u/pN0l3qOSoSO6m6yvM/O
q4idyl17SfqDR9AUdEwJIA9zfSomzmzfO/q3rIAOPNkd71RQ4YMkHn8SfQLaojxl
+N5pPB29c6Cy+hltP6JRibAHgYCkxQGLK6ZLQ1LTwkDLNxCH8qfmHvg7M3qcXxl4
KOgtb8kNZ3PpAvek1GNL/eaF7nnd/u5uHuJM5V7czVHjpMbBfRGgLzR6Tu6v8qm7
nJzhSErxC7lK0hXLgGuHlk26bj9pzb+lfBk7GnkRAAYp/gkDCpw9vyiAeR8uYPUV
mINtxpejZeID6EaNZ8wTKNB1e3yt/As2Svkpcl1ivosbADhxCTFSJ4RtmEynFPCw
qgYbjuTBK+Fv2LSd7CYHJm4zZ/hfiCBgL4jI3ZY52qHFnBhgHtLwza/eLeaC0i4+
RWUAN9JEW1Ygpsh0ApRd1UvY8dGoLF24fy3C2jeh5Q3SVw2SnhUryLU7u6gTTLt4
yskT+/pzdNrb2n3dvLLUhQJ50SeTroa/swB/SXnjWtDSRGpvv3HAStHSENaZCIrV
e/u/WSNd99nklpYdPwh3UFO9OOayYErYiprEhLC7JjdVbqbu2aIfrw+nS/PS+tlm
wQTYH/DKA6wIeSZK4y9Byfrx3oq4DPk9pge7n3z3oz9pzd+xG2GMvExwKiCUlcF5
he5Peb4sTsJz0epMpwcBXFNYyVO++rZvBTABhgY5MQAcympoBAAcspo8AvBWx2xK
SaIyp5XDtT8jqey5Jjo3qmIQvdpo5oQub73JCMDSHi7KZ/IkgtggpgDqNh9bT5ZE
C7d3lprPFQJNQtFTO2K8NecRkgatn9Imomy1DidlnsCuZjqfamNVssWhm0uNu8SC
aJYBtC9kZXhBLAy0mFCMfJQ8ysDzlG3+Fu9wE9tCQvkh7y0ZKo9Ortqnwqp6S0I3
2xMBOg2EMHRP+ADF3q/i2wlgbH0MHsiX4oMxd0eIZV+rJIQSnO547UvvzAUBjXjZ
1l23wmg8FctYIE0UPsTo1QNArGO1sIOdv807UMolB9lq1pKAXkJP0GPRZLv9bLDj
kkKLEBELXCCQA0vDH+N/eGXRdJbWv5i0mOXmxK2JAZZw8rsJF3XZ22PABrC0NaCP
qHftcq20PPMCRZ/TfjQmwlot495KmLUJo2G6JasdcEilyPH2GVUwiqCM2/wOWk4U
xX+FmA40NYmU64hJBBgRAgAJBQJCyOASAhsCAAoJECLu4EiAhgYPt9kAn3r0Hhf9
aTFyowH3pgqIUiaMVQo5AKCFWzcU23YT0E2/LZNl6Yqzcs113Q==
=SHc5
- -----END PGP PRIVATE KEY BLOCK-----
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1

iQEcBAEBCgAGBQJWToHpAAoJEM55Ebf8BAiPk7kH+weVf8kVJRjSaSWE+Aft76iA
Nzj1cVUfpWoT/K139i3TMiZ6PpAQtCRyEakdxfeSfXiOz83pqmKSL5ADCdlRoxuB
HtkoLW6thETOs70mDrrsEQgBZgMYPMsiKG1W/M3xppRGZxUM7/UEXhjHYiThe1Qd
Dkwot+hu5EttQpu0kKFmPrviPpJOk0gJ5SQrhlROWCS+aT9TyhbswMRpSyurDZ2H
LppGk8EtBeWTsTf9AhemX1GFu4iJPwIDfZtiWOLGGjQn4ROqb/RWqLG254O//Gw6
jtDRGHIGyYk+2NQ6/gAKWI9Sxaz5kUxqKSzDU9WuDCE3peIB9HXM+ynFVKLgsXE=
=Rnfg
-----END PGP SIGNATURE-----

Now that this is posted, I should expect everyone to steal my GnuPG identity, parading around as me, forging signatures, correct? No, it's not happening. I trust the crypto. I trust the math. I trust the software.

Why? Why am I doing this? Well, a recent discussion popped up on IRC about Keybase. Some don't like the fact that they are encouraging you to upload your encrypted private key to the server. Some claim that it is "insecure". However, didn't we just logically and reasonably conclude that AES and SHA-2 are protecting my best interests? So, if it's insecure, then it can't be due to the crypto. It must be something else. Let's look at all the risk factors:

Keybase servers are compromised and you use the web interface
If the server is compromised, then the attackers can modify the code, providing malicious JavaScript to the browser, so when you successfully decrypt your private key, it can be sent and stored elsewhere under their control. There is nothing you can do here. You are screwed. This is a very valid concern.

Keybase servers are compromised and you use the command line interface
The attackers only have access to your encrypted private key. Provided you never use the web interface, all encryption and decryption as handled out-of-band. This means that regardless of the Keybase server compromise, the attackers will never actually get to forge signatures using your GnuPG private key.

Your local client is compromised
There is nothing I can do for you here. Keybase isn't to blame, and not even the gpg(1) client can protect you. You have bigger problems on your hands than the attackers gaining access to your unencrypted GnuPG private key.

I think a lot of GnuPG users are paranoid about their key getting leaked, because they are unsure of exactly how it is stored. Hopefully this post lays those fears to rest. If there are still concerns about the leak of encrypted private keys, then it's probably due to a fear of not fully understanding the strength of passwords and their entropy requirements. However, if you meet the necessary password entropy requirements, and your key is encrypted with CAST5/SHA-1 or AES-256/SHA-512, there is nothing wrong with keeping a backup of your GnuPG key on Github, AWS, Dropbox, or other "cloud" hosting solutions.

Trust the math. Trust the software.

By the way, if you do successfully recover my private key passphrase (and I know you won't), I would be interested in hearing from you. Send me a signed email with my private key, and I'll make it financially worth your while. 🙂

Now Using miniLock

I have been a long proponent of OpenPGP keys for a way to communicate securely. I have used my personal key for signing emails since ~ 2005. I have used my key at dozens and dozens of keysigning parties. I have used my key to store account passwords and credentials with vim(1), Python, and so many other tools. I have used my key to encrypt files to myself. And so much more. There is only one problem.

No one is using my key to send me encrypted data.

Sure, when attending keysigning parties, it's an encryption orgy. Attendees will sign keys, then send encrypted copies to recipients. And, of course, people will send encrypted emails before and after the party, for various reasons. But, when the party dies down, and people get back to their regular lives, and very few actually send encrypted data with OpenPGP keys. Realistically, it's rare. Let's be honest. Sure, there's the one-off, either as a corporation (XMission uses OpenPGP extensively internally for password storage) or individuals (sending encrypted tax forms to a spouse or accountant), but by large, it's rarely used.

I have a good idea of why, and it's nothing ground breaking- OpenPGP is hard. It's hard to create keys. It's hard to manage the keys. It's hard to grasp the necessary concepts of public keys, private keys, encryption, decryption, signatures, verification, the Web of Trust, user identities, key signing parties, revocation certificates, and so much more.

OpenPGP is just hard. Very hard.

Well, in an effort to encourage more people, such as my family and friends that would not use OpenPGP, to encrypt sensitive data, I've jumped on board with miniLock. What is miniLock? Currently, it's a Free Software browser application for the Google Chrome/Chromimum browser (not an extension). It uses ECC, bcrypt, BLAKE2, zxcvbn, and a number of other tools that you really don't need to worry about, unless you want to audit the project. All you need is an email and a password. The keys are deterministically generated based on that.

Think about this for a second. You don't need a public and private keyring to store your keys. You don't need to upload them to a key server. You don't need to attend keysigning parties, worry about the Web of Trust, or any of that other stuff that makes OpenPGP the nightmare it is.

All you need is an email and a password.

Unfortunately, this does have one big drawback- your email or password can't change, without changing your keys. However, the miniLock keys are cheap- IE: you can change them any time, or create as many as you want. You only need to distribute your miniLock ID. In fact, the miniLock ID is the entire public key. So, they don't even need to be long term. Generate a one-time session miniLock ID for some file that you need to send to your accountant during tax season, and call it good.

However, I prefer long-term keys, so as such, I created 3 IDs, one for each email account that I use. If you want to send me encrypted data, without the hassle of OpenPGP, feel free to use the correct miniLock ID for the paired email address.

Email miniLock ID
aaron.toponce@gmail.com mWdv6o7TxCEFq1uN6Q6xiWiBwMc7wzyzCfMa6tVoEPJ5S
atoponce@xmission.com qU7DJqG7UzEWYT316wGQHTo2abUZQk6PG8B6fMwZVC9MN
aaron.toponce@utah.edu 22vDEVchYhUbGY9Wi6EdhsS47EUeLKQAVEVat56HK8Riry

Don't misunderstand me. If you have an OpenPGP key, and would prefer to use that instead, by all means do so. However, if you don't want to setup OpenPGP, and deal with the necessary overhead, I can now decrypt data with miniLock. Maybe that will a better alternative for you instead.

Do XKCD Passwords Work?

You'll always see comments on web forums, social sites, blog posts, and emails about "XKCD passwords". This is of course referring to the XKCD comic by Randall Munroe describing what he thinks is the best password generator:

What no one has bothered asking, is if this actually works.

Lorrie Faith Cranor, director of the Carnegie Mellon Usable Privacy and Security Laboratory at Carnegie Mellon University, a member of the Electronic Frontier Foundation Board of Directors, and Professor in the School of Computer Science and the Engineering and Public Policy Department at Carnegie Mellon University, did ask this question. In fact, she studied to the point, that she gave a TED talk on the subject. The transcript of her talk can be found here. Here are the relevant bits (emphasis mine):

Now another approach to better passwords, perhaps, is to use pass phrases instead of passwords. So this was an xkcd cartoon from a couple of years ago, and the cartoonist suggests that we should all use pass phrases, and if you look at the second row of this cartoon, you can see the cartoonist is suggesting that the pass phrase "correct horse battery staple" would be a very strong pass phrase and something really easy to remember. He says, in fact, you've already remembered it. And so we decided to do a research study to find out whether this was true or not. In fact, everybody who I talk to, who I mention I'm doing password research, they point out this cartoon. "Oh, have you seen it? That xkcd. Correct horse battery staple." So we did the research study to see what would actually happen.

So in our study, we used Mechanical Turk again, and we had the computer pick the random words in the pass phrase. Now the reason we did this is that humans are not very good at picking random words. If we asked a human to do it, they would pick things that were not very random. So we tried a few different conditions. In one condition, the computer picked from a dictionary of the very common words in the English language, and so you'd get pass phrases like "try there three come." And we looked at that, and we said, "Well, that doesn't really seem very memorable." So then we tried picking words that came from specific parts of speech, so how about noun-verb-adjective-noun. That comes up with something that's sort of sentence-like. So you can get a pass phrase like "plan builds sure power" or "end determines red drug." And these seemed a little bit more memorable, and maybe people would like those a little bit better. We wanted to compare them with passwords, and so we had the computer pick random passwords, and these were nice and short, but as you can see, they don't really look very memorable. And then we decided to try something called a pronounceable password. So here the computer picks random syllables and puts them together so you have something sort of pronounceable, like "tufritvi" and "vadasabi." That one kind of rolls off your tongue. So these were random passwords that were generated by our computer.

So what we found in this study was that, surprisingly, pass phrases were not actually all that good. People were not really better at remembering the pass phrases than these random passwords, and because the pass phrases are longer, they took longer to type and people made more errors while typing them in. So it's not really a clear win for pass phrases. Sorry, all of you xkcd fans. On the other hand, we did find that pronounceable passwords worked surprisingly well, and so we actually are doing some more research to see if we can make that approach work even better. So one of the problems with some of the studies that we've done is that because they're all done using Mechanical Turk, these are not people's real passwords. They're the passwords that they created or the computer created for them for our study. And we wanted to know whether people would actually behave the same way with their real passwords.

So, in her research, XKCD passwords really didn't work out that well. They are longer in length, so they take longer to type, which increases the chance for error, and people are no better at remembering on XKCD passphrase, than they are a short string of random characters.

To me, this is unsurprising. If you look at the history of my blogging on passwords, you'll find that I continually advocate true random events to build your passwords, maximizing entropy. In my last post, I even blogged two shell functions that you can use to build XKCD passwords, and "monkey passwords" (monkeys generating passwords by banging away at a keyboard). Both target 80-bits of entropy in the generation. Check out the lengths:

$ gen-monkey-pass 9
cxqwtw63taxdr3zn	uaq4tbt43japmm2q	mptwrxhhb486yfuv
-cb73b9-kgzhmww3	s45t3x6r9smw-7yr	hjkgzkha-qup4gh4
34c5rg4ksw-aprvk	uug-2vq7pfze6dnp	s4qx4eazbnrd2pqe

$ gen-xkcd-pass 9
sorestdanklyAlbanyluckyRamonaFowler   (sorest dankly Albany lucky Ramona Fowler)
towsscareslaudedrobinawardsrenal      (tows scares lauded robin awards renal)
thinkhazelsvealjuggedagingscareen     (think hazels veal jugged agings careen)
tarotpapawsNolanpacketAvonwiped       (tarot papaws Nolan packet Avon wiped)
surgesakimbohardercruelArjunablinds   (surges akimbo harder cruel Arjuna blinds)
amountlopsedgemeaslyCannoninseam      (amount lops edge measly Cannon inseam)
EssexIzmirwizesPattygroutszodiac      (Essex Izmir wizes Patty grouts zodiac)
hoursmailedslamsvowedallowspar        (hours mailed slams vowed allow spar)
AfghanNigelnutriadillmoldertrolly     (Afghan Nigel nutria dill molder trolly)

XKCD passwords average 32 characters to achieve 80-bits of entropy, compared to 16 characters that "monkey passwords" produce. And, according to the research done by Lorrie, people won't necessarily recall XKCD passwords any easier than "monkey passwords". So, if that's the case, then what's the point? Why bother? Why not just create "monkey passwords", and use a password manager?

Exactly. It's 2015. There are password managers for your browser, all versions of every desktop operating system, command-line based utilities for servers, and even apps for your smartphone. There are plenty of "cloud" synchronization services to make sure each instance is up-to-date. At this point, your passwords should:

  • Contain at least 80-bits of entropy.
  • Be truly random generated (no influence from you).
  • Be unique for each and every account.
  • Be protected with two-factor authentication, where available.
  • Be stored in a password manager, that is easily accessible.

You'll remember the ones you type in frequently, and you'll memorize them quickly. The others are stored for safe keeping, should you need to recall them.

Password Generation in the Shell

No doubt, some people use password generators- not many, but some. Unfortunately, this means relying on 3rd party utilities, where the source code may not always be available. Personally, I would rather be in full control of the entire generation stack. I know how to make sure plenty of entropy is available in the generation, and I know which sources of entropy to draw on to maximize the entropy estimate. As such, I don't use tools like pwgen(1), apg(1), or anything else. I rely strictly on /dev/urandom, grep(1), and other tools guaranteed to be on every BSD and GNU/Linux operating system.

As such, the script below has been successfully tested in various shells on Debian GNU/Linux, PC-BSD, FreeBSD, OpenBSD, NetBSD, and SmartOS. If you encounter a shell or operating system this script does not work in, please let me know. Thanks to all those who helped me test it and offered suggestions for improvement.

So, with that said, here they are:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# No copyright. Released under the public domain.
# You really should have shuf(1) or shuffle(1) installed. Crazy fast.
shuff(){
    if [ $(command -v shuf) ]; then
        shuf -n "$1"
    elif [ $(command -v shuffle) ]; then
        shuffle -f /dev/stdin -p "$1"
    else
        awk 'BEGIN{
            "od -tu4 -N4 -A n /dev/urandom" | getline
            srand(0+$0)
        }
        {print rand()"\t"$0}'
| sort -n | cut -f 2 | head -n "$1"
    fi
}
gen_monkey_pass(){
    I=0
    [ $(printf "$1" | grep -E '[0-9]+') ] && NUM="$1" || NUM="1"
    until [ "$I" -eq "$NUM" ]; do
        I=$((I+1))
        LC_CTYPE=C strings /dev/urandom | \
            grep -o '[a-hjkmnp-z2-9-]' | head -n 16 | paste -s -d \\0 /dev/stdin
    done | column
}
gen_xkcd_pass(){
    I=0
    [ $(printf "$1" | grep -E '[0-9]+') ] && NUM="$1" || NUM="1"
    [ $(uname) = "SunOS" ] && FILE="/usr/dict/words" || FILE="/usr/share/dict/words"
    DICT=$(LC_CTYPE=C grep -E '^[a-zA-Z]{3,6}$' "$FILE")
    until [ "$I" -eq "$NUM" ]; do
        I=$((I+1))
        WORDS=$(printf "$DICT" | shuff 6 | paste -s -d ' ' /dev/stdin)
        XKCD=$(printf "$WORDS" | sed 's/ //g')
        printf "$XKCD ($WORDS)" | awk '{x=$1;$1="";printf "%-36s %s\n", x, $0}'
    done | column
}

Nothing fancy about them. The first function, "shuff" is really just a helper function for systems that might not have shuf(1) or shuffle(1) installed. It's used only in the "gen_xkcd_pass" function. The next function, "gen_monkey_pass" acts like monkeys banging on the typewriter. It reads /dev/urandom directly, reading the printable characters that come out of it, counting them to 16, and putting them in an orderly set of columns for output as seen below. The input is a total set of 32-characters, giving each character exactly 5-bits of entropy. So, at 16 characters, each password comes with exactly 80-bits of entropy. The character set was chosen to stay entirely lowercase plus digits, and remain unambiguous, so it's clear, and easy to type, even though it may still be hard to remember. The function can take a numerical argument, for generating exactly that many passwords:

$ gen_monkey_pass 24
awdq2zwwfcdgzqpm	t54zqxus77zsu6j6	-2h6dkp93bjdb496
thm9m9nusqxuewny	qmsv2vqw-4-q4b4d	ttbhpnh4n7nue5g8
ytt6asky765avkpr	grwhsfmyz872zwk3	mzq-5ytdv8zawhy6
zb46qgnt62k74xwf	uydrsh2axaz5-ymx	6knh32qj4yk885ea
vky55q2ubgaucdnh	5dhk9t97pfja9phj	rhn2qg734p83wnxs
-q2hb833c-54z-9j	t33shcc55e3kqcd6	q6fwn3396h4ygvq4
232hr73rkymerpyg	u2pq-3ytcpc79nb9	7hqqwqujz4mxa-en
jj9vdj3jtpjhwcp6	mqc97ktz-78tb2bp	q7-6jug86kqhjfxn

The last function, "gen_xkcd_pass" comes from the "correct horse battery staple" comic from XKCD. On every Unix system, there is a dictionary file installed at /usr/share/dict/words or /usr/dict/words. On Debian GNU/Linux, it contains 99,171 words (OpenBSD contains 234,979!). However, many of them have the apostrophe as a valid character. Taking out any punctuation and digits, we are left with just lowercase and uppercase characters for our words. Further, the total word space is limited to at least 3 characters in length and at most 6 characters in length. This leaves us with 19,198 words, or about 14.229-bits of entropy per word. This means generating at least 6 words to achieve an 80-bit entropy minimum. For clarity, the password is space-separated to the right in parens, to make it more clear what exactly the password is, as shown below. Even if all 6 words have 6 characters (the password is 36 characters in total), the formatted line will never be longer than 80 characters in width, making it fit perfectly in an 80x24 terminal. It also takes a numerical argument, for generating exactly that many passwords:

$ gen_xkcd_pass 8
flyersepticspantearruinedwoo         (flyer septic span tear ruined woo)
boasgiltCurrywaivegalsAndean         (boas gilt Curry waive gals Andean)
selectpugjoggedlargeArabicbrood      (select pug jogged large Arabic brood)
titshubbubAswancartharmedtaxi        (tits hubbub Aswan cart harmed taxi)
Reaganmodestslowleessamefoster       (Reagan modest slow lees same foster)
tussleFresnoJensentheirsNohhollow    (tussle Fresno Jensen theirs Noh hollow)
Laredoriffplunkbarredhikersrearm     (Laredo riff plunk barred hikers rearm)
demostiffnukesvarlethakegilt         (demo stiff nukes varlet hake gilt)

Of course, as you can see, some fairly obscure words pop out as a result, such as "filt" and "rearm". But then, you could think of it as expanding your vocabulary. If you install the "american-insane" dictionary, then you can get about 650,722 words in your total set, bringing your per-word entropy north of 16-bits. This would allow you to cut your number of generated words down to 5 instead of 6, to keep the 80-bits entropy minimum. But then, you also see far more obscure words than with the standard dictionary, and it will take a touch longer to randomize the file.

This script should be platform agnostic. If not, let me know what isn't exactly working in your shell or operating system, and why, and I'll try to address it.

Setting Up A Global VPN Proxy on Android with L2TP/IPSec PSK

In my last post in this short series, I want to discuss how to setup a transparent proxy on your Android phone using the builtin VPN for L2TP. As usual, the same precautions apply here. Don't be stupid with your data, just because you can hide it from your ISP.

In general, I'm skeptical of VPN service providers, which is partially why I'm writing this post. There isn't a VPN provider on this planet that will go to jail for you. And I don't buy into the hype that they aren't logging your traffic. Too often, VPN providers have been all too hasty to turn over user account information and logs, when Big Brother comes knocking. Instead, install strongSwan on your own L2TP VPN server, in a datacenter you trust to handle your traffic, and configure your Android to use that.

Unlike the previous posts, this one does not require root access. To start, you need to navigate to "Settings -> More -> VPN":

vpn-0 vpn-1

Tap the "+" sign to add a new VPN configuration. In this example, we'll configure it to connect to an L2TP/IPSec PSK VPN. As such, you'll need to fill out the server address (pixelated here), and the IPSec pre-shared key. Give the configuration a name, such as "My VPN", and tap "SAVE".

vpn-2 vpn-3 vpn-4

When tapping on the "My VPN" defined configuration, you will be asked to authenticate with your credentials. These can be from the operating system accounting database, LDAP, NIS, or IPSec specific. Provide your username and password, and tap "Save account information" if you want to save the credentials to disk on the phone. Then tap "CONNECT". At this point, you should see a little key in the status bar, confirming that you are indeed connected to the VPN server. If you want, you can create a "VPN" quick-access widget on your home screen, so you can get immediate access to your "My VPN" configuration with a single tap.

vpn-5 vpn-6 vpn-7

Setting Up A Global Tor Proxy on Android with Orbot

In my last post, I explained how to setup a Global SSH proxy on Android with ConnectBot and ProxyDroid. In this article, I'll do the same thing, but with Orbot. Also, as with the last article, the same precautions apply here. If you're on an untrusted or unknown network, using an encrypted proxy can be helpful. However, just because you're using Tor, doesn't mean you should trust its network blindly either. There are all sorts of practical attacks on Tor that have been reaching the press lately, and you would be wise to read them, and proceed with caution.

With that said, sometimes all you want to do is get around a content filter, such as viewing Reddit at church, or getting on Twitter while at work. Of course, there are necessary risks with those actions as well. Basically, don't be an idiot.

With that out of the way, this requires that you have root access on your phone, and that you have installed the Orbot Android app. Once the app is installed, we really only need to make one adjustment, and that is enabling two check boxes: "Transparent Proxying" and "Tor Everything":

orbot-2

As something you should keep in mind, you may also want to check "Use Bridges". Relay bridges are entry nodes that are not listed in the main Tor directory. As such, it is more difficult for ISPs to filter them. If you suspect that your ISP is blocking all known entry nodes, then using bridges can be helpful to get around the problem. But, using bridges may be unnecessary. Check if your Tor connection is getting filtered first. If so, enable the use of bridges, otherwise, you're just fine using Tor without them.

Also, Orbot has some interesting settings, such as specifically setting a whitelist of entry and exit nodes, and a black list of nodes to avoid. If you know someone is operating a Tor node, and you trust them, then I would recommend setting them as either an entry or exit, whichever is appropriate. The reason for this, is it is not impractical for a well-funded organization to have a large number of entry and exit nodes. If so, they can build traffic profiles on who is connecting to the entry node, and which site they are visiting from the exit. However, by specifying specific nodes for either entry or exit (or both), you eliminate this threat. Sadly enough, I could not get this working with Orbot.

One last setting that has caught my eye, is "Tor Tethering". If you use your phone as a wireless hotspot, or USB tethering, you can also transparently route all the traffic from those connected clients through the Tor proxy. I haven't tested this yet with the latest version, but with previous versions of Orbot, it didn't work.

Other settings are listed below, page after page.

orbot-1 orbot-3 orbot-4 orbot-5 orbot-6

When at the main page of the app, long-tap the power button in the center of the droid, to connect to the Tor network. When the arms of the droid are down, you are not connected. When the arms are yellow, and pointing to the sides of the phone, the app is trying to get a connecting to the Tor network. When the arms are green, pointing up, you are fully connected, and can start enjoying your proxy.

orbot-0 orbot-7 orbot-8

Notice that when you are connected, an onion icon is in the status bar at the top of the phone, showing as a permanent notification. If you have "Expanded Notifications" set, you can get IP address and country information in the notification. If you swipe the droid right or left, the droid will spin, and you will end up with a new "Tor Identity". Basically, you'll be connected to a new set of nodes.

orbot-9 orbot-10 orbot-11

Tapping the "CHECK BROWSER" button at the bottom left of the landing screen will use your default browser app to connect to https://check.torproject.org and verify whether or not transparent proxying over Tor is working.

Setting Up A Global SSH Proxy on Android with ConnectBot and ProxyDroid

I'm one that takes precautions with my data when on unfamiliar or untrusted networks. While for the most part, I trust TLS to handle my data securely, I find that it doesn't take much effort to setup a transparent proxy on my Android handset, to route all packets through an encrypted proxy.

In this case, I happen to work for the greatest ISP in the world, and so I have an SSH server in the datacenter. I wholly trust the network from my SSH server to the border routers, so the more traffic I can send that direction, the better. I realize that may not be the case for all of you. However, if you have an externally available SSH server on a trusted network, this post may be of interest.

First, setting up this proxy requires having root. I'm not going to cover how to get root in this post. You can find it elsewhere. Next, you'll need to apps installed; namely ConnectBot and ProxyDroid. Both are Free Software apps. Also, you can do this with SSH Tunnel on its own, if you have Android 4.2.2 or older. Unfortunately, it doesn't work for 4.3 and newer. I have Android 5.1, and it isn't setting up the firewall rules correctly.

Once they are installed, you'll want to set them up. Here I walk through setting up ConnectBot.

  1. Pull up ConnectBot from your app drawer, and setup a new connection by typing in the username, host, and optionally port.
  2. When asked if you want to accept the server's public SSH key, verify the key, then tap "YES"
  3. Enter in your password to connect, and verify that you can successfully connect to the remote SSH server.
  4. Now, disconnect, sending you back to the app's landing screen.

connectbot-1 connectbot-2 connectbot-3

  1. At this point, long-tap the SSH profile you just created, and tap "Edit port forwards".
  2. Tap the menu in the upper-right hand corner of the profile, and tap "Add port forward".
  3. Give the forward a nickname, such as "ProxyDroid".
  4. Tap "Dynamic (SOCKS)" from the list under "Type".
  5. Provide any source port. It must be above 1024, and cannot be currently in use. I find "1984" apropos.
  6. Leave the "Destination" blank, and tap "CREATE PORT FORWARD".

connectbot-4 connectbot-5 connectbot-6 connectbot-7

You now have sucessfully created a SOCKS listening port on localhost:1984. Now, we need to create software firewall rules in the phone, to globally forward all packets through localhost on port 1984, creating our transparent proxy. As such, pull up ProxyDroid, and I'll walk you through setting that up:

  1. In ProxyDroid, set "127.0.0.1" as the "Host".
  2. Match the port with what you set in ConnectBot's port forward ("1984" in our example).
  3. Set the "Proxy Type" to "SOCKS5"
  4. Scroll to the bottom of the app, and check the checkbox for "Global Proxy".
  5. OPTIONAL: Check the checkbox for "DNS Proxy".

That last step will tunnel DNS requests through the proxy also. Unfortunately, I have found it to be buggy, and unstable. So, leaving it unchecked, unfortunately, gives you a stable encrypted SSH proxy experience.

 

Now that both are configured, connect to your remote SSH server with ConnectBot that you have configured, then enable the proxy by tapping the slider next to "Proxy Switch". You should have a running global SSH proxy from your smartphone to the remote SSH server, where all packets are being sent. You can visit a site that returns your external IP address, such as http://findmyipaddress.com/, to verify that the source IP address of the HTTP request is the same IP address as your SSH server. If so, your packets are being tunneled through your SSH connection.

proxy-running

md5crypt() Explained

Recently, the Password Hashing Competition announced its winner, namely Argon2, as the future of password hashing. It's long since been agreed that using generic-purpose cryptographic hashing algorithms for passwords is not a best practice. This is due to their speed. Cryptographic hashing algorithms are designed to be lighting fast, while also maintaining large margins of security. However, Poul-Henning Kamp noticed in the early 1990s that the DES-based crypt() function was no longer providing the necessary margins of security for hashing passwords. He noticed how fast crypt() had become, and that greatly bothered him. Even worse, was the realization that FPGAs could make practical attacks against crypt() in practical time. As he was the FreeBSD release engineer, this meant putting something together that was intentionally slow, but also with safe security margins. He chose MD5 as the basis for his new "md5crypt password scrambler", as he called it.

Before delving into the algorithm, the first thing you'll notice is the strange number of steps and mixing that PHK does with his md5crypt() algorithm. When I was reading the algorithm, the first question that popped into my mind was: "Why not just do standard key-stretching with the password?" Something like this (pseudocode):

digest = md5(password + salt).digest()
rounds = 1000
while rounds > 0:
  digest = md5(password + salt + digest).digest()
  counter -= 1

This certainly seems to be the most straightforward approach, and the entirety of the security is based on the cryptographic security of MD5. If you were concerned about the output digest being recognizable, it might make sense to scramble it. You could scramble the remaining bytes in a deterministic fashion, which PHK actually ends up doing before saving to disk.

But then it hit me: PHK wanted his new algorithm to be intentionally slow, even if using MD5. This means adding additional steps to mixing the password, which requires more CPU, and thus, more time. If raw MD5 could process 1,000,000 hashes per second, then standard key-stretching of 1,000 iterations would bring it down to 1,000 hashes per second. However, if adding additional operations slows it down by 1/N-iterations, the the resulting throughput would be 1,000/N hashes per second. I can see it now- anything to slow down the process, without overburdening the server, is a gain. As such, the md5crypt() function was born.

Here is the algorithm, including what I think may be a bug:

  1. Set some constants:
    "pw" = user-supplied password.
    "pwlen" = length of "pw".
    "salt" = system-generated random salt, 8-characters, from [./0-9A-Za-z].
    "magic" = the string "$1$".
    "itoa64" = is our custom base64 string "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
    
  2. Initialize digest "a", and add the password, magic, and salt strings to it:
    da = MD5.init()
    da.update(pw)
    da.update(magic)
    da.update(salt)
    
  3. Initialize digest "b", and add the password, salt, and password strings to it:
    db = MD5.init()
    db.update(pw)
    db.update(salt)
    db.update(pw)
    final = db.digest()
    
  4. Update digest "a" by repeating digest "b", providing "pwlen" bytes:
    for(pwlen; pwlen > 0; pwlen -= 16):
      if(pwlen > 16):
        da.update(final)
      else:
        da.update(final[0:pwlen])
    
  5. Clear virtual memory
    memset(final, 0, length(final))
    
  6. Update digest "a" by adding a character at a time from either digest "final" or from "pw" based on each bit from "pwlen":
    for(i = pwlen; i; i >>= 1):
      if i % 2 == 1:
        da.update(final[0])
      else:
        da.update(pw[0])
    dc = da.digest()
    
  7. Iterate 1,000 times to prevent brute force password cracking from going to fast. Mix the MD5 digest while iterating:
    for(i=0; i<1000; i++)
      tmp = MD5.init()
      if i % 2 == 0:
        tmp.upate(dc)
      else:
        tmp.update(pw)
      if i % 3 == 0:
        tmp.update(salt)
      if i % 7 == 0:
        tmp.update(pw)
      if i % 2 == 0:
        tmp.update(pw)
      else:
        tmp.update(dc)
      dc = tmp.digest()
    
  8. Convert 3 8-bit words of digest "c" into 4 6-bit words:
    final = ''
    for a, b, c in ((0, 6, 12), (1, 7, 13), (2, 8, 14), (3, 9, 15), (4, 10, 5)):
      v = ord(dc[a]) < < 16 | ord(dc[b]) << 8 | ord(dc[c])
      for i in range(4):
        final += itoa64[v & 0x3f]
        v >>= 6
    v = ord(dc[11])
    for i in range(2):
      final += itoa64[v & 0x3f]
      v >>= 6
    
  9. Clear virtual memory:
    memset(dc, 0, length(dc))
    

Notice that between steps 5 and 6, the virtual memory is cleared, leaving the digest "final" as NULLs. Yet, in step 6, the for-loop attempts to address the first byte of digest "final". It seems clear that PHK introduced a bug in this algorithm, that was never fixed. As such, every implementation must add a C NULL in step 6, instead of final[0]. Otherwise, you will end up with a different output than the original source code by PHK.

Anyway, that's the algorithm behind md5crypt(). Here's a simple Python implementation that creates valid md5crypt() hashes:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
from hashlib import md5

# $ mkpasswd --method='md5' --salt='2Z4e3j5f' --rounds=1000 --stdin 'toomanysecrets'
# $1$2Z4e3j5f$sKZptx/P5xzhQZ821BRFX1

pw = "toomanysecrets"
salt = "2Z4e3j5f"

magic = "$1$"
pwlen = len(pw)
itoa64 = "./0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"

# Start digest "a"
da = md5(pw + magic + salt)

# Create digest "b"
db = md5(pw + salt + pw).digest()

# Update digest "a" by repeating digest "b", providing "pwlen" bytes:
i = pwlen
while i > 0:
    da.update(db if i > 16 else db[:i])
    i -= 16

# Upate digest "a" by adding either a NULL or the first char from "pw"
i = pwlen
while i:
    da.update(chr(0) if i & 1 else pw[0])
    i >>= 1
dc = da.digest()

# iterate 1000 times to slow down brute force cracking
for i in xrange(1000):
    tmp = md5(pw if i & 1 else dc)
    if i % 3: tmp.update(salt)
    if i % 7: tmp.update(pw)
    tmp.update(dc if i & 1 else pw)
    dc = tmp.digest()

# convert 3 8-bit words to 4 6-bit words
final = ''
for x, y, z in ((0, 6, 12), (1, 7, 13), (2, 8, 14), (3, 9, 15), (4, 10, 5)):
    # wordpress bug: < <
    v = ord(dc[x]) << 16 | ord(dc[y]) << 8 | ord(dc[z])
    for i in range(4):
        final += itoa64[v & 0x3f]
        v >>= 6
v = ord(dc[11])
for i in range(2):
    final += itoa64[v & 0x3f]
    v >>= 6

# output the result
print "{0}${1}${2}".format(magic, salt, final)

Ulrich Drepper created a "sha256crypt()" as well as "sha512crypt()" function, which is very similar in design, and which I'll blog about later.

It's important to note, that while PHK may have announced md5crypt() as insecure, it's not for the reasons you think. Yes, MD5 is broken, horribly, horribly broken. However, these breaks only deal with the compression function and blind collision attacks. MD5 is not broken with preimage or second preimage collisions. In the case of a stored md5crypt() hash, it requires either a brute force search or a preimage attack to find the plaintext that produced the hash. MD5 is secure with preimage attacks. The reason md5crypt() has been deemed as "insecure", is because MD5 is fast, fast, fast. Instead, password hashing should be slow, slow, slow, and no amount of creativity with MD5 can adequately address its performance. As such, you should migrate to a password hashing solution designed specifically to slow attackers, such as bcrypt or scrypt, with appropriate parameters for security margins.

The Chaocipher With Playing Cards

As you know, I am a cryptography hobbyist. More specifically, I have an interest in pencil and paper ciphers, also referred to as "hand ciphers" or "field ciphers". Since Bruce Schneier released his Solitaire Cipher for Neal Stephenson's book "Cryptonomicon" (known in the book as "Pontifex"), I have had a real desire to learn hand ciphers with playing cards, that I'll refer to as "card ciphers".

Further, in 1918, John F. Byrne invented a mechanical encryption system that he called "Chaocipher". He released an autobiography titled "The Silent Years", of which he describes the system without the algorithm, and releases a series of exhibits of ciphertexts for cryptography experts to break.

Unfortunately, because he didn't release the algorithm I think, no one took his encryption system seriously, despite his best efforts to get the War Department to use it. It wasn't until 2010 that the widow of John F. Byrne's son released the Chaocipher papers, mechanics, and artifacts to the National Cryptologic Museum in Maryland, that we finally fully understood the algorithm.

In this post, I am going to describe the algorithm using playing cards, whereas John F. Byrne's original invention required two circular rotating disks. Another hindering aspect to Byrne's invention was the mechanical engineering required. At best, the device is clunky and awkward to use. However, using playing cards, I think you'll find the system much more elegant, easier to carry around, and has the advantage of not being incriminating that you are carrying a cryptographic device. Playing cards were certainly available in the early 1900s, so it's unfortunate that he didn't think of using playing cards as the primary mechanism for the cipher.

Setup

The Chaocipher uses the concept of lookup tables to encrypt or decrypt a message. This is done by maintaining two separate alphabets. When encrypting a message, a character is located in the plaintext alphabet, and it's location is noted. Then, the ciphertext character is identified by locating the character in the ciphertext alphabet at the same position. After the ciphertext character has been recorded, both the plaintext and ciphertext alphabets are permuted. We'll get into those details in a moment, but first, let's set aside some definitions.

Because John F. Byrne's original invention required two circular disks, there are two definitions that you should be aware of:

Zenith
The top of the wheel or circle. In our case, this will be the top of the pile.

Nadir
The bottom of the wheel or circle. In our case, this will be in the middle of the pile (the 14th of 26 cards).

Deck
All 52 cards in a standard poker deck.
Pile
Either the red playing cards (Diamonds and Hearts) dedicated to the ciphertext alphabet, or the black playing cards (Clubs and Spades) dedicated to the plaintext alphabet. Each pile is exactly 26 cards.

Left alphabet
The red pile of playing cards containing the ciphertext characters A-Z.
Right alphabet
The black pile of playing cards containing the plaintext characters A-Z.

We will be treating our two piles (the red and black piles) as circular. The piles will always be face-up on the table and in our hands. The top card in the face-up pile will be the 1st card while the bottom card will be the 26th card. Because the pile is circular in nature, this means that the top and bottom cards in the pile are "next" to each other in succession. This means further, then, that the 14th card in the pile is our nadir, while the top card, or the 1st card in the pile, is our zenith.

Now that we've set that aside, we need to create some definitions so we know exactly which playing card in every suit is assigned to which English alphabet character. I've assigned them as follows:

Hearts and Spades Clubs and Diamonds
A 2 3 4 5 6 7 8 9 10 J Q K A 2 3 4 5 6 7 8 9 10 J Q K
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

This means that the English character "X" would be the Jack of Clubs in the plaintext "black" pile ("right alphabet" in Chaocipher-speak), and the Jack of Diamonds in the ciphertext "red" pile ("left alphabet" in Chaocipher-speak). This also means that the 8 of Spades would be the English character "H", just as much as the 8 of Hearts.

On a side note, if you wish to program this in software, and you populate an array with the values of 1 through 52 to represent each card in the deck, it's standard to use 1-13 for the Clubs, 14-26 for the Diamonds, 27-39 for the Hearts, and 40-52 for the Spades ("bridge order").

Algorithm

The algorithm can comprise of a standard "simple" set of steps, or using a more advanced "takeoff pattern" for enciphering and deciphering the message. First, let me discuss the simple pattern, then I'll look at the more advanced takeoff pattern.

An overview of the algorithm could be described as follows:

  1. Determine the ciphertext character according to the plaintext character (and vice versa for decryption).
  2. Permute the red pile.
  3. Permute the black pile.

Each of these three steps are executed in order until the message is exhausted.

Enciphering Plaintext

Looking at it in closer detail, suppose I had the following red and black piles (using "+" to identify the zenith, and "*" to identify the nadir):

            +                                      *
  red (ct): 7D 3H TH 2H JD AD 8H 8D 5H TD QH 9H JH 2D 6D KH QD 9D 5D KD AH 7H 6H 4H 4D 3D
black (pt): TC 3S JS 2C 5S AC 4C KC 9S TS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS 2S 5C KS 6C

If I wanted to encrypt the character "A", in the black deck, according to our table above, that would be the Ace of Spades. As such, I need to find the Ace of Spades in my black pile. While locating the card, I need to be counting, so I know the position in the pile that the Ace of Spades in in. In this case, the Ace of Spades is the 22nd card in the black pile. Thus, the 22nd card in the red pile is the Seven of Hearts:

            +                                      *                       ↓
  red (ct): 7D 3H TH 2H JD AD 8H 8D 5H TD QH 9H JH 2D 6D KH QD 9D 5D KD AH 7H 6H 4H 4D 3D
black (pt): TC 3S JS 2C 5S AC 4C KC 9S TS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS 2S 5C KS 6C

The Seven of Hearts produces the English character "G". Thus, with these two piles, "A" encrypts to "G" before permutation. Conversely, "G" would decrypt to "A" with these starting piles.

Permuting the Red and Black Piles

Now that we've discovered our plaintext and ciphertext characters, we need to cut the deck, such that both the plaintext and ciphertext characters are at the zenith of each pile. The resulting piles would then be as follows:

            +                                      *
  red (ct): 7H 6H 4H 4D 3D 7D 3H TH 2H JD AD 8H 8D 5H TD QH 9H JH 2D 6D KH QD 9D 5D KD AH
black (pt): AS 2S 5C KS 6C TC 3S JS 2C 5S AC 4C KC 9S TS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C

Permuting the Red Pile

Permuting the red pile follows the following steps:

  1. Remove the zenith + 1 card (2nd card) from the red pile.
  2. Place the removed card into the nadir of the red pile (will be the 14th card).

So, we'll follow these steps by taking the zenith + 1 card (2nd card), which is the "6H", and placing it at the nadir of the red pile (14th card). The resulting red pile will look as follows:

            +                                      *
  red (ct): 7H .. 4H 4D 3D 7D 3H TH 2H JD AD 8H 8D 5H TD QH 9H JH 2D 6D KH QD 9D 5D KD AH

            +                                      *
  red (ct): 7H 4H 4D 3D 7D 3H TH 2H JD AD 8H 8D 5H .. TD QH 9H JH 2D 6D KH QD 9D 5D KD AH

            +                                      *
  red (ct): 7H 4H 4D 3D 7D 3H TH 2H JD AD 8H 8D 5H 6H TD QH 9H JH 2D 6D KH QD 9D 5D KD AH

Permuting the Black Pile

Permuting the black pile follows the following steps:

  1. Take the zenith (top) card and place it at the bottom of the black pile.
  2. Remove the zenith + 2 card (3rd card) from the black pile.
  3. Place the removed card into the nadir of the black pile (will be the 14th card).

So, we'll follow these steps by taking the zenith card (top card), which is the "AS", and placing it at the bottom of the black pile. The resulting black pile will look as follows:

            +                                      *
black (pt): 2S 5C KS 6C TC 3S JS 2C 5S AC 4C KC 9S TS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS

Now take the zenith + 2 (3rd card), which is the "KS" and place it at the nadir of the black pile (14th card). The final black pile will look as follows:

            +                                      *
black (pt): 2S 5C .. 6C TC 3S JS 2C 5S AC 4C KC 9S TS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS

            +                                      *
black (pt): 2S 5C 6C TC 3S JS 2C 5S AC 4C KC 9S TS .. 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS

            +                                      *
black (pt): 2S 5C 6C TC 3S JS 2C 5S AC 4C KC 9S TS KS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS

As such, both the red and black piles should look like the following after enciphering the plaintext character "A" and permuting both piles:

            +                                      *
  red (ct): 7H 4H 4D 3D 7D 3H TH 2H JD AD 8H 8D 5H 6H TD QH 9H JH 2D 6D KH QD 9D 5D KD AH
black (pt): 2S 5C 6C TC 3S JS 2C 5S AC 4C KC 9S TS KS 9C 6S 7S 8S QS QC 7C JC 4S 3C 8C AS

To summarize, the algorithm steps are as follows:

  1. Find the plaintext character in the black pile.
  2. Record the position of this card in the black pile.
  3. Find the ciphertext character in the red pile by counting to that position.
  4. Bring the plaintext character to the zenith by cutting the deck at that position.
  5. Bring the ciphertext character to the zenith by cutting the deck at that position.
  6. Permute the red pile:
    1. Remove the zenith + 1 card from the red pile (2nd card).
    2. Insert the removed card into the nadir of the red pile (14th location).
  7. Permute the black pile:
    1. Move the card at the zenith to the bottom of the black pile.
    2. Remove the zenith + 2 card from the black pile (3rd card).
    3. Insert the removed card into the nadir of the black pile (14th location).

Make sure you understand these steps before continuing.

Permuting with a Takeoff Pattern

John F. Byrne described a "takeoff pattern" in which the left and right alphabets are used for both the plaintext and ciphertext characters. In the simple method, the right alphabet (black pile) is used exclusively for all plaintext characters in the message. So, if the plaintext message was "ATTACKATDAWN", then you could think of using the right pile 12 times, or "RRRRRRRRRRRR" ("BBBBBBBBBBBB" if we're thinking "black pile").

However, suppose you would like to use both of the red and black piles (left and right alphabets respectively) for your plaintext message. Then you could create a "takeoff pattern" for encrypting your text. Suppose you used the following takeoff pattern: "RLRRLLRRRLLL" (right, left, right, right, left, left, right, right, right, left, left, left). This means that you would use the right alphabet for the first plaintext character, then the left alphabet for the second plaintext character, the right alphabet for the 3rd, the right alphabet for the 4th, etc. Or, if using playing cards, you could think of the same takeoff pattern as "BRBBRRBBBRRR" (black, red, black, black, red, red, black, black, black, red, red, red).

Personally, I don't care for the takeoff pattern for two main reasons: first, the takeoff pattern needs to be communicated with the key. This may not be a problem if code books are distributed among field agents, as the takeoff pattern can be printed on the same page as the key. However, this does mean that the takeoff pattern needs to be as long as the key itself.

The second reason I don't care for the take of pattern, is due to the unnecessary complexity of the takeoff pattern itself, it greatly increases the chances to make a mistake. Already, the sender and recipient will be going back and forth frequently between the red and black pile of cards. By creating a takeoff pattern, this makes that back and forth more frequent. Further, if you are using the 3rd of 5 "L"s in a stream, but you think you are on the 4th "L", then the encryption or decryption will be wrong from there out. Chaocipher doesn't have the ability to correct itself from a mistake.

For these two reasons, I suggest that when using playing cards with the Chaocipher, that instead you always use the black pile for the plaintext characters, and the red pile for the ciphertext characters. Then, the only thing that you need to keep track of is the characters in the message itself.

Keying the Deck

Before executing the Chaocipher algorithm, the deck should be "keyed". This refers to the order of the deck. Both the sender and the recipient must have the same deck order in order to successfully encrypt and decrypt a message. The deck can be keyed by either a sufficient set of shuffling and cutting, or keyed with a key phrase. First, let's look at thoroughly shuffling and cutting a full 52-card deck.

Keying with Shuffling and Cutting

Suppose after thoroughly shuffling and cutting the deck, the deck order face-up is as follows:

|< - top                                                                                                                                         bottom ->|
3H 8D QH 4C 6S QS 8C 4D 9S 5D 8S QC 3C 6H JS 7H 5S TS QD 7C 4H JC KD TH 3S KS 6D 9C 9D 2C JD 2H 2D 6C 8H KC 9H JH 7S KH AS AH 5C AD TC 7D 4S 3D 2S TD 5H AC

We now need a deterministic algorithm for separating the red cards from the black cards. Holding the deck face-up in your hand, deal out two face-down piles, the left pile of red cards, and the right pile of black cards. Do this card-for-card, one-at-a-time. Do not grab a bunch of similarly-colored cards. This can introduce error into the keying process. Doing it one-at-a-time ensures exactness, and minimizes the chances for mistake.

After the full deck has been dealt into two face-down piles, turn the piles over, so they are face-up. Using the standard Chaocipher tokens of "+" to identify the zenith, or top of the pile, and the "*" to identify the nadir, or 14th card in the pile, your two piles should be in the following order:

            +                                      *
  red (ct): 3H 8D QH 4D 5D 6H 7H QD 4H KD TH 6D 9D JD 2H 2D 8H 9H JH KH AH AD 7D 3D TD 5H
black (pt): 4C 6S QS 8C 9S 8S QC 3C JS 5S TS 7C JC 3S KS 9C 2C 6C KC 7S AS 5C TC 4S 2S AC
            -----------------------------------------------------------------------------
  position:  1  2  3  4  5  6  7  8  9  1  1  1  1  1  1  1  1  1  1  2  2  2  2  2  2  2
                                        0  1  2  3  4  5  6  7  8  9  0  1  2  3  4  5  6

Verify that you can do this by hand, and that it matches with the deck order above. Remember, the red pile is our "left alphabet" in the Chaocipher which contains all ciphertext English characters. The black pile is our "right alphabet" in the Chaocipher which contains all plaintext English characters. In other words, if we converted them to English characters, then the left and right alphabets would be as follows, using the same notation to identify the zenith and nadir:

            +                         *
 left (ct): C U L Q R F G Y D Z J S V X B O H I K M A N T P W E
right (pt): Q F L U I H Y P K E J T X C M V O S Z G A R W D B N
            ---------------------------------------------------
  position: 1 2 3 4 5 6 7 8 9 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2
                              0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6

Keying with a Key Phrase

Already knowing the algorithm prepares you for using a key phrase to key the deck. Basically, you'll just use the characters in your key phrase as the plaintext message, using the black pile to find key key phrase character, just as you would if encrypting a message. Both piles will be permuted, as normal. The only difference is that you will be not be recording the ciphertext characters. Further, you will start with alphabetized piles.

Both piles will start with the following order:

            +                                      *
 left (ct): AH 2H 3H 4H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4D 5D 6D 7D 8D 9D TD JD QD KD
right (pt): AS 2S 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC

Suppose our key phrase is "CHAOCIPHER". Then, working through the steps character for character, they would follow the following order:

Locate "C" in the black pile:
            +                                      *
 left (ct): AH 2H 3H 4H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4D 5D 6D 7D 8D 9D TD JD QD KD
right (pt): AS 2S 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC

Bring both characters to zenith:
            +                                      *
 left (ct): 3H 4H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AS 2S

Permute the red pile. Remove the zenith + 1 card:
            +                                      *
 left (ct): 3H .. 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AS 2S

            +                                      *
 left (ct): 3H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D .. 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AS 2S

Insert the card into the nadir:
            +                                      *
 left (ct): 3H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4H 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 3S 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AS 2S

Permute the black pile. Move the top card to the bottom:
            +                                      *
 left (ct): 3H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4H 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 4S 5S 6S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AS 2S 3S

Remove the zenith + 2 card:
            +                                      *
 left (ct): 3H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4H 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 4S 5S .. 7S 8S 9S TS JS QS KS AC 2C 3C 4C 5C 6C 7C 8C 9C TC JC QC KC AS 2S 3S

            +                                      *
 left (ct): 3H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4H 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 4S 5S 7S 8S 9S TS JS QS KS AC 2C 3C 4C .. 5C 6C 7C 8C 9C TC JC QC KC AS 2S 3S

Insert the card into the nadir:
            +                                      *
 left (ct): 3H 5H 6H 7H 8H 9H TH JH QH KH AD 2D 3D 4H 4D 5D 6D 7D 8D 9D TD JD QD KD AH 2H
right (pt): 4S 5S 7S 8S 9S TS JS QS KS AC 2C 3C 4C 6S 5C 6C 7C 8C 9C TC JC QC KC AS 2S 3S

Repeat for "H", "A", "O", "C", "I", "P", "H", "E", & "R".

When you are finished keying the deck with the key phrase "CHAOCIPHER", you should have the following order for the red and black piles:

            +                                      *
 left (ct): 6D JH 7D 8D 9D 2D KH JD QD 2H 3H 6H 7H 8H 9H TH QH AD KD AH TD 3D 4H 5H 4D 5D
right (pt): 4S AS 3S JS 5S 7S 9S QS AC 2C 3C 4C 6S 2S 6C 8S 7C 8C KS TS 9C TC JC QC KC 5C

Enhancements

Initialization Vectors

One thing that we have learned with modern computer encryption primitives is to prepend initialization vectors to the ciphertext. The initialization vector must be random and unpredictable. However, its function is to create a unique state on the system before the plaintext is encrypted or before the ciphertext is decrypted. The point is to modify a secret state (our key, or pile orders) while ignoring the output. By adding an initialization vector to the system, we limit the effectiveness of attacks on the ciphertext. For example, if the initialization vector is 26 characters long (one character for each character in the English alphabet, or 26! total combinations), then 25 collisions on one initialization vector to launch an attack on the state (the last element can be determined by process of elimination).

Unfortunately, a 26-character initialization vector is not very practical to use by hand. Knowing that it is standard for field agents to break up their messages into blocks of five characters, it would seems reasonable to use a 5-character initialization vector. However, this doesn't seem to mix the state well enough.

For example, consider using an unkeyed deck to encrypt the text "AARON" 10 times with different initialization vectors at each round:

BSTPR VUYVS
LOKJY WJXTR
YFTLN WJLHQ
UAOZP UTVIV
YXTXU VILUH
WGQCJ UTLUE
LYPYZ WHYSS
QHESJ VHKEQ
CLZRN WVMRE
FEKEQ VUKDR

The first five characters in each ciphertext is the initialization vector, randomly generated. The second block of 5 characters is my name encrypted after the initialization vector keyed the deck. Notice that the first character in the second block seems to have a lot of "V"s and "W"s. If I do 100 rounds, and count the frequency of the first character, I get the following:

F:1, L:1, G:3, K:3, T:4, I:7, J:7, U:7, H:8, W:14, V:45

That is not a good distribution of characters for the first plaintext character being an "A" over 100 different initialization vectors. I would expect it to be much more diffuse. So, how about instead of a 5-character initialization vector, we bump it to 10? How does the frequency distribution look then?

A:1, I:1, U:1, V:1, X:1, Z:1, T:2, E:3, G:3, N:5, O:5, Q:5, B:6, C:6, F:7, D:10, S:11, R:13, P:18

That's a little bit better. A 26-character initialization vector would certainly show a flatter frequency distribution for the first ciphertext character in the message. However, as mentioned, that's cumbersome. So, at this point, it's up to you. Using a 5-character initialization vector would provide about 10 or 11 possible first ciphertext characters. Using a 10-character initialization vector increases that to about 18 with a flatter distribution.

PKCS#7 Padding

As mentioned, it has become a field cipher standard to separate your ciphertext into blocks of 5 characters. This means that if your message is not a multiple of 5 characters, to add padding at the end until it is. However, when the recipient decrypts the message, it should be unambiguous exactly what is padding, and what is not. The padding in PKCS#7 makes this possible.

We can define this easily enough be determining exactly how many characters must be added to pad the message into multiples of 5 characters. So, we'll count:

  • If the message needs only one character appended, append a single "V".
  • If the message needs two characters appended, append "WW".
  • If the message needs three characters appended, append "XXX".
  • If the message needs four characters appended, append "YYYY".
  • If the message is already a multiple of five characters, append "ZZZZZ".

By using the padding described above, after decrypting the message, the recipient needs to only look at the last character to determine exactly how many characters make up the padding, and to strip from the plaintext.

To illustrate this, let's take an unkeyed deck, add a 5-character initialization vector, and encrypt the message "ATTACK AT DAWN". This message is only 12 characters, so I would need to add "XXX" at the end of the message according to the definition above. This my message becomes (removing spaces) "ATTACKATDAWNXXX". Adding the 5-character initialization vector "KEQPN" then encrypting, I get the following result:

plaintext: ATTACK AT DAWN
initialization vector: KEQPN
padding: XXXX

ciphertext: KEQPN XLHTT PRUCA FHUEC

Of course, decrypting "KEQPN XLHTT PRUCA FHUEC" and removing the initialization vector "KEQPN" will reveal "ATTACKATDAWNXXX". It's clear to the recipient that "XXX" is padding, and can be stripped without affecting the plaintext.

Conclusion

This has been a lengthy post, and I commend you for reading this far. The Chaocipher is an interesting algorithm, and I'll be studying its properties as time moves forward. I think the Chaocipher fits well as playing card cipher, and gets as close to "bare metal" as you can without designing an actual mechanical mechanism with two rotating disks and removable character tiles. Playing cards are easy to carry around with you in your pocket, so its portability is nice.

Further, we can increase the strength of the algorithm, as mentioned, by adding an initialization vector at the start of the message, and by adding padding, we can stick with the standard of 5-character blocks in our ciphertext. Of course, this means adding 6-10 additional characters, but for a 160-character message, this doesn't seem too cumbersome.

There are some things that I have observed while using playing cards for the cipher hardware. First, encrypting and decrypting are slow. It takes me about a minute to encrypt/decrypt two-three characters. So, for a 160-character message, it could take the better part of an hour to work through.

Second, due to its slow speed, you may get tempted to try and speed things up a bit, so you can work through the message more quickly. However, this drastically opens you up to mistakes. I was encrypting the plaintext "JELLY LIKE ABOVE THE HIGHWIRE SIX QUACKING PACHYDERMS KEPT THE CLIMAX OF THE EXTRAVAGANZA IN A DAZZLING STATE OF FLUX" over and over. After about 10 ciphertexts, I wrote a Python script to automate the process for me. Only 1 of the ciphertexts was 100% accurate, character-for-character. And, unfortunately, 1 ciphertext was 0% accurate, with every character in the message incorrect. However, on the other 8 messages, I seemed to maintain accuracy for about 2/3 of the characters on most messages. Some others, I made a mistake more early on. Regardless, the point is, I was making frequent mistakes, despite my best effort to not do so. Only 1 out of 10 ciphertexts would decrypt cleanly. It might be worth having two decks, one for producing the ciphertext character, and one for double-checking your work. Of course, this slows you down further, but could be doable for minimizing mistakes.

However, the Chaocipher with playing cards is a fun cipher to work, and easy once you get the hang of it. I would recommend using plastic playing cards, such as the ones from Kem, Copag, or Bicycle Prestige. This way, the cards don't get gummed up like paper cards, are washable, last longer due to their extra durability, and overall, just are a better feeling playing card.

If you work the Chaocipher with playing cards, let me know what you think.

The Kidekin TRNG Hardware Random Number Generator

Yesterday, I received my Kidekin TRNG hardware random number generator. I was eager to purchase this, because on the Tindie website, the first 2 people to purchase the RNG would get $50 off, making the device $30 total. I quickly ordered one. Hilariously enough, I received a letter from the supplier that I was their first customer! Hah!

Image of the Kidekin Digital TRNG

Upon opening the package, I noticed the size of the TRNG. It's roughly 10.5 cm from end-to-end which makes it somewhat awkward for a device sitting in your USB port on your laptop. It would work fine sitting in the back of a desktop or server, out of the way, but on my Thinkpad T61, it's a bit large to be sitting there 24/7 feeding my kernel CSPRNG.

Plugging the device in, the kernel actually sees two USB devices, not just one, and sets them up as /dev/ttyUSB0 and /dev/ttyUSB1. Curious. Downloading the software ZIP file from their webpage, and looking through it, the following UDEV rules are provided:


$ cat /etc/udev/rules.d/98-kidekin.rules 
#SYMLINK+= method works on more systems, if it does not on your system, please switch to the NAME= method.

#disable the unused port.
#SUBSYSTEM=="tty", ATTRS{interface}=="kidekin_trng", ATTRS{bInterfaceNumber}=="00", NAME="kidekin_dont_use", MODE="0000", ENV{ID_MM_DEVICE_IGNORE}="1", ENV{ID_MM_CANDIDATE}="0"
SUBSYSTEM=="tty", ATTRS{interface}=="kidekin_trng", ATTRS{bInterfaceNumber}=="00", SYMLINK+="kidekin_dont_use", MODE="0000", ENV{ID_MM_DEVICE_IGNORE}="1", ENV{ID_MM_CANDIDATE}="0"

#connect kidekin TRNG to /dev/random
#SUBSYSTEM=="tty", ATTRS{interface}=="kidekin_trng", ATTRS{bInterfaceNumber}=="01", NAME="kidekin_trng", MODE="0777", RUN+="/bin/stty raw -echo -crtscts -F /dev/kidekin_trng speed 3000000", ENV{ID_MM_DEVICE_IGNORE}="1", ENV{ID_MM_CANDIDATE}="0"
SUBSYSTEM=="tty", ATTRS{interface}=="kidekin_trng", ATTRS{bInterfaceNumber}=="01", SYMLINK+="kidekin_trng", MODE="0777", RUN+="/bin/stty raw -echo -crtscts -F /dev/kidekin_trng speed 3000000", ENV{ID_MM_DEVICE_IGNORE}="1", ENV{ID_MM_CANDIDATE}="0"
SUBSYSTEM=="tty", ATTRS{interface}=="kidekin_trng", ATTRS{bInterfaceNumber}=="01", RUN+="/etc/init.d/rng-tools restart"

This is a bit assuming, and a bit overdoing it IMO, so I simplified it, and setup the following:

SUBSYSTEM=="tty", ATTRS{interface}=="kidekin_trng", ATTRS{bInterfaceNumber}=="01", SYMLINK+="kidekin", MODE="0777", RUN+="/bin/stty raw -echo -crtscts -F /dev/kidekin speed 3000000", ENV{ID_MM_DEVICE_IGNORE}="1", ENV{ID_MM_CANDIDATE}="0"

This avoids setting up a "do not use" symlink for the unnecessary USB device, and changes the symlink of the usable USB device to /dev/kidekin. This also doesn't restart rngd(8), as I'll administer that on my own. At this point, I am ready for testing.

First and foremost, I wanted to test its throughput:

$ dd if=/dev/kidekin count=1G | pv -a > /dev/null
[ 282KiB/s]

The device held stable at 282 KBps or roughly 2.2 Mbps. This is 75.2 KBps per dollar for my $30 purchase. Not bad.

The Kidekin is based on astable free running oscillators, or multivibrators. Unfortunately, a security proof does not accompany the device. So, while this may hold up to the suite of randomness tests, the output may not be cryptographically secure, and could also potentially be backdoored, as verifying the hardware is not easily doable. So, let's see if it at least holds up to the randomness tests. I created a 256 MB file, and ran the standard suites of tests:

$ dd if=/dev/kidekin of=entropy.kidekin bs=1M count=256 iflag=fullblock
256+0 records in
256+0 records out
268435456 bytes (268 MB) copied, 928.326 s, 289 kB/s

At this point, I can start my testing. First, let's quantify the amount of entropy per byte, as well as some basic tests with ent(1):

$ ent entropy.kidekin
Entropy = 7.999999 bits per byte.

Optimum compression would reduce the size
of this 268435456 byte file by 0 percent.

Chi square distribution for 268435456 samples is 248.92, and randomly
would exceed this value 59.56 percent of the times.

Arithmetic mean value of data bytes is 127.4924 (127.5 = random).
Monte Carlo value for Pi is 3.141825693 (error 0.01 percent).
Serial correlation coefficient is -0.000003 (totally uncorrelated = 0.0).

Everything good so far. How about the FIPS 140-2 tests for randomness:

$ rngtest < entropy.kidekin
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 2147483648
rngtest: FIPS 140-2 successes: 107292
rngtest: FIPS 140-2 failures: 82
rngtest: FIPS 140-2(2001-10-10) Monobit: 14
rngtest: FIPS 140-2(2001-10-10) Poker: 13
rngtest: FIPS 140-2(2001-10-10) Runs: 26
rngtest: FIPS 140-2(2001-10-10) Long run: 30
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=317.891; avg=7386.982; max=19073.486)Mibits/s
rngtest: FIPS tests speed: (min=6.563; avg=109.376; max=114.901)Mibits/s
rngtest: Program run time: 19261018 microseconds
$ echo $?
1

Again, so far so good. Some failures are expected with random input of this size. 82 failures versus 107292 successes is right on par with the tests. Now the Dieharder battery of tests:

$ dieharder -a < entropy.kidekin
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
        mt19937|  8.99e+07  | 722892634|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.87388974|  PASSED  
      diehard_operm5|   0|   1000000|     100|0.25081726|  PASSED  
  diehard_rank_32x32|   0|     40000|     100|0.80329585|  PASSED  
    diehard_rank_6x8|   0|    100000|     100|0.87234234|  PASSED  
   diehard_bitstream|   0|   2097152|     100|0.27873738|  PASSED  
        diehard_opso|   0|   2097152|     100|0.05958924|  PASSED  
        diehard_oqso|   0|   2097152|     100|0.10540020|  PASSED  
         diehard_dna|   0|   2097152|     100|0.30006047|  PASSED  
diehard_count_1s_str|   0|    256000|     100|0.43809130|  PASSED  
diehard_count_1s_byt|   0|    256000|     100|0.29758303|  PASSED  
 diehard_parking_lot|   0|     12000|     100|0.78081639|  PASSED  
    diehard_2dsphere|   2|      8000|     100|0.58294587|  PASSED  
    diehard_3dsphere|   3|      4000|     100|0.04012616|  PASSED  
     diehard_squeeze|   0|    100000|     100|0.97651988|  PASSED  
        diehard_sums|   0|       100|     100|0.01875349|  PASSED  
        diehard_runs|   0|    100000|     100|0.17566659|  PASSED  
        diehard_runs|   0|    100000|     100|0.78887310|  PASSED  
       diehard_craps|   0|    200000|     100|0.16369886|  PASSED  
       diehard_craps|   0|    200000|     100|0.42148915|  PASSED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.27534860|  PASSED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.45190499|  PASSED  
         sts_monobit|   1|    100000|     100|0.88204376|  PASSED  
            sts_runs|   2|    100000|     100|0.15277754|  PASSED  
          sts_serial|   1|    100000|     100|0.71489026|  PASSED  
          sts_serial|   2|    100000|     100|0.85005457|  PASSED  
          sts_serial|   3|    100000|     100|0.77631916|  PASSED  
          sts_serial|   3|    100000|     100|0.81111751|  PASSED  
          sts_serial|   4|    100000|     100|0.72512842|  PASSED  
          sts_serial|   4|    100000|     100|0.68758000|  PASSED  
          sts_serial|   5|    100000|     100|0.69083583|  PASSED  
          sts_serial|   5|    100000|     100|0.09706031|  PASSED  
          sts_serial|   6|    100000|     100|0.52758972|  PASSED  
          sts_serial|   6|    100000|     100|0.27970465|  PASSED  
          sts_serial|   7|    100000|     100|0.07925569|  PASSED  
          sts_serial|   7|    100000|     100|0.25874891|  PASSED  
          sts_serial|   8|    100000|     100|0.33647659|  PASSED  
          sts_serial|   8|    100000|     100|0.80952471|  PASSED  
          sts_serial|   9|    100000|     100|0.99948911|   WEAK   
          sts_serial|   9|    100000|     100|0.32461849|  PASSED  
          sts_serial|  10|    100000|     100|0.69360795|  PASSED  
          sts_serial|  10|    100000|     100|0.96022345|  PASSED  
          sts_serial|  11|    100000|     100|0.91349333|  PASSED  
          sts_serial|  11|    100000|     100|0.95918606|  PASSED  
          sts_serial|  12|    100000|     100|0.69821905|  PASSED  
          sts_serial|  12|    100000|     100|0.57652285|  PASSED  
          sts_serial|  13|    100000|     100|0.28393582|  PASSED  
          sts_serial|  13|    100000|     100|0.45849491|  PASSED  
          sts_serial|  14|    100000|     100|0.30832853|  PASSED  
          sts_serial|  14|    100000|     100|0.89099315|  PASSED  
          sts_serial|  15|    100000|     100|0.87022105|  PASSED  
          sts_serial|  15|    100000|     100|0.06938123|  PASSED  
          sts_serial|  16|    100000|     100|0.79568629|  PASSED  
          sts_serial|  16|    100000|     100|0.53218489|  PASSED  
         rgb_bitdist|   1|    100000|     100|0.38552808|  PASSED  
         rgb_bitdist|   2|    100000|     100|0.79403454|  PASSED  
         rgb_bitdist|   3|    100000|     100|0.66811643|  PASSED  
         rgb_bitdist|   4|    100000|     100|0.84954470|  PASSED  
         rgb_bitdist|   5|    100000|     100|0.90198903|  PASSED  
         rgb_bitdist|   6|    100000|     100|0.98808244|  PASSED  
         rgb_bitdist|   7|    100000|     100|0.25730860|  PASSED  
         rgb_bitdist|   8|    100000|     100|0.43237015|  PASSED  
         rgb_bitdist|   9|    100000|     100|0.90916135|  PASSED  
         rgb_bitdist|  10|    100000|     100|0.81131338|  PASSED  
         rgb_bitdist|  11|    100000|     100|0.31361128|  PASSED  
         rgb_bitdist|  12|    100000|     100|0.40786889|  PASSED  
rgb_minimum_distance|   2|     10000|    1000|0.03358258|  PASSED  
rgb_minimum_distance|   3|     10000|    1000|0.99298827|  PASSED  
rgb_minimum_distance|   4|     10000|    1000|0.47721533|  PASSED  
rgb_minimum_distance|   5|     10000|    1000|0.86641982|  PASSED  
    rgb_permutations|   2|    100000|     100|0.10084049|  PASSED  
    rgb_permutations|   3|    100000|     100|0.99560585|   WEAK   
    rgb_permutations|   4|    100000|     100|0.42217190|  PASSED  
    rgb_permutations|   5|    100000|     100|0.95466090|  PASSED  
      rgb_lagged_sum|   0|   1000000|     100|0.64120688|  PASSED  
      rgb_lagged_sum|   1|   1000000|     100|0.22106106|  PASSED  
      rgb_lagged_sum|   2|   1000000|     100|0.41244281|  PASSED  
      rgb_lagged_sum|   3|   1000000|     100|0.98880097|  PASSED  
      rgb_lagged_sum|   4|   1000000|     100|0.78380177|  PASSED  
      rgb_lagged_sum|   5|   1000000|     100|0.25533777|  PASSED  
      rgb_lagged_sum|   6|   1000000|     100|0.78150371|  PASSED  
      rgb_lagged_sum|   7|   1000000|     100|0.53903267|  PASSED  
      rgb_lagged_sum|   8|   1000000|     100|0.04436257|  PASSED  
      rgb_lagged_sum|   9|   1000000|     100|0.77174302|  PASSED  
      rgb_lagged_sum|  10|   1000000|     100|0.54862612|  PASSED  
      rgb_lagged_sum|  11|   1000000|     100|0.48691334|  PASSED  
      rgb_lagged_sum|  12|   1000000|     100|0.06308057|  PASSED  
      rgb_lagged_sum|  13|   1000000|     100|0.42530804|  PASSED  
      rgb_lagged_sum|  14|   1000000|     100|0.86907366|  PASSED  
      rgb_lagged_sum|  15|   1000000|     100|0.66262930|  PASSED  
      rgb_lagged_sum|  16|   1000000|     100|0.85485044|  PASSED  
      rgb_lagged_sum|  17|   1000000|     100|0.39817394|  PASSED  
      rgb_lagged_sum|  18|   1000000|     100|0.90608610|  PASSED  
      rgb_lagged_sum|  19|   1000000|     100|0.94996515|  PASSED  
      rgb_lagged_sum|  20|   1000000|     100|0.78715690|  PASSED  
      rgb_lagged_sum|  21|   1000000|     100|0.93364519|  PASSED  
      rgb_lagged_sum|  22|   1000000|     100|0.84438533|  PASSED  
      rgb_lagged_sum|  23|   1000000|     100|0.77439531|  PASSED  
      rgb_lagged_sum|  24|   1000000|     100|0.12530311|  PASSED  
      rgb_lagged_sum|  25|   1000000|     100|0.79035917|  PASSED  
      rgb_lagged_sum|  26|   1000000|     100|0.93286961|  PASSED  
      rgb_lagged_sum|  27|   1000000|     100|0.32567247|  PASSED  
      rgb_lagged_sum|  28|   1000000|     100|0.39563718|  PASSED  
      rgb_lagged_sum|  29|   1000000|     100|0.15628693|  PASSED  
      rgb_lagged_sum|  30|   1000000|     100|0.69368810|  PASSED  
      rgb_lagged_sum|  31|   1000000|     100|0.00197963|   WEAK   
      rgb_lagged_sum|  32|   1000000|     100|0.23325783|  PASSED  
     rgb_kstest_test|   0|     10000|    1000|0.18940877|  PASSED  
     dab_bytedistrib|   0|  51200000|       1|0.57007834|  PASSED  
             dab_dct| 256|     50000|       1|0.76567665|  PASSED  
Preparing to run test 207.  ntuple = 0
        dab_filltree|  32|  15000000|       1|0.60537852|  PASSED  
        dab_filltree|  32|  15000000|       1|0.78894908|  PASSED  
Preparing to run test 208.  ntuple = 0
       dab_filltree2|   0|   5000000|       1|0.11775507|  PASSED  
       dab_filltree2|   1|   5000000|       1|0.34799105|  PASSED  
Preparing to run test 209.  ntuple = 0
        dab_monobit2|  12|  65000000|       1|0.69182598|  PASSED  

Finally, a visual check on the data, even though it's safe to assume that it's "true random" given the previous testing:

$ dd if=white.bmp of=entropy.kidekin bs=1 count=54 conv=notrunc
54+0 records in
54+0 records out
54 bytes (54 B) copied, 0.000547208 s, 98.7 kB/s
$ gimp entropy.kidekin # convert to grayscale, export as "entropy.png"
$ optipng entropy.png
** Processing: entropy.png
512x512 pixels, 8 bits/pixel, grayscale
Input IDAT size = 250107 bytes
Input file size = 250564 bytes

Trying:
  zc = 9  zm = 8  zs = 0  f = 0		IDAT size = 215319
  zc = 9  zm = 8  zs = 1  f = 0		IDAT size = 214467
  zc = 1  zm = 8  zs = 2  f = 0		IDAT size = 214467
  zc = 9  zm = 8  zs = 3  f = 0		IDAT size = 214467
                               
Selecting parameters:
  zc = 1  zm = 8  zs = 2  f = 0		IDAT size = 214467

Output IDAT size = 214467 bytes (35640 bytes decrease)
Output file size = 214564 bytes (36000 bytes = 14.37% decrease)

And the result is:

RNG visual output of the Kidekin TRNG

My conclusion of the Kidekin TRNG is positive. I love the throughput of the device, loved the price, and aside from the UDEV rule, it is plug-and-play. Unfortunately, the TRNG is a bit on the big side for a physical device, and because it doesn't come with a security proof, and the hardware design is closed, I would be skeptical to trust it for your random numbers directly. Instead, I would recommend adding it the Linux kernel's CSPRNG, and rely on /dev/urandom instead. This is trivial with rngd(8). But, overall, I am very pleased with the device, and which I had actually purchased a second one.

Additional Testing Of The rtl-sdr Dongle As A HWRNG

A couple days ago, I put up a post about using the Realtek SDR dongles as a hardware true random number generator. I only tested the randomness of a 512 MB file. I thought this time, I would but a bit more stock into it. In this case, I let it run for a while, until it was 1.8 GB in size. Interestingly enough, it stopped getting bigger after that point. Not sure why. However, I ran more tests on that 1.8 GB file. Creating this file took its time:

$ tail -f /run/rtl_entropy.fifo | dd of=random.img iflag=fullblock
3554130+0 records in
3554130+0 records out
1819714560 bytes (1.8 GB) copied, 3897.22 s, 467 kB/s

This filled up a bit faster than I had previously tested, going at a clip of about 3.826 Mbps.

Now it was time for the testing:

$ ent random.img
Entropy = 8.000000 bits per byte.

Optimum compression would reduce the size
of this 1819714560 byte file by 0 percent.

Chi square distribution for 1819714560 samples is 246.86, and randomly
would exceed this value 63.11 percent of the times.

Arithmetic mean value of data bytes is 127.4990 (127.5 = random).
Monte Carlo value for Pi is 3.141611317 (error 0.00 percent).
Serial correlation coefficient is 0.000013 (totally uncorrelated = 0.0).

It passes with flying colors on entropy estimation, compression, chi-square distributions, arithmetic mean, the Monte Carlo estimation for Pi, and serial correlation. Testing further, I ran it through the FIPS 140-2 tests:

$ rngtest < random.img
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 14557716480
rngtest: FIPS 140-2 successes: 727288
rngtest: FIPS 140-2 failures: 597
rngtest: FIPS 140-2(2001-10-10) Monobit: 99
rngtest: FIPS 140-2(2001-10-10) Poker: 57
rngtest: FIPS 140-2(2001-10-10) Runs: 210
rngtest: FIPS 140-2(2001-10-10) Long run: 233
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=114.212; avg=6626.942; max=9536.743)Mibits/s
rngtest: FIPS tests speed: (min=61.133; avg=147.877; max=151.377)Mibits/s
rngtest: Program run time: 96034230 microseconds
You have new mail.
$ echo $?
1

Finally, the beast of beasts, I ran it through every Dieharder test. This took some time to complete. Here is a listing of the tests that it went through:

$ dieharder -l
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
Installed dieharder tests:
 Test Number	                     Test Name	              Test Reliability
===============================================================================
  -d 0  	                  Diehard Birthdays Test	      Good
  -d 1  	                     Diehard OPERM5 Test	      Good
  -d 2  	          Diehard 32x32 Binary Rank Test	      Good
  -d 3  	            Diehard 6x8 Binary Rank Test	      Good
  -d 4  	                  Diehard Bitstream Test	      Good
  -d 5  	                            Diehard OPSO	   Suspect
  -d 6  	                       Diehard OQSO Test	   Suspect
  -d 7  	                        Diehard DNA Test	   Suspect
  -d 8  	      Diehard Count the 1s (stream) Test	      Good
  -d 9  	        Diehard Count the 1s Test (byte)	      Good
  -d 10  	                Diehard Parking Lot Test	      Good
  -d 11  	Diehard Minimum Distance (2d Circle) Test	      Good
  -d 12  	Diehard 3d Sphere (Minimum Distance) Test	      Good
  -d 13  	                    Diehard Squeeze Test	      Good
  -d 14  	                       Diehard Sums Test	Do Not Use
  -d 15  	                       Diehard Runs Test	      Good
  -d 16  	                      Diehard Craps Test	      Good
  -d 17  	            Marsaglia and Tsang GCD Test	      Good
  -d 100  	                        STS Monobit Test	      Good
  -d 101  	                           STS Runs Test	      Good
  -d 102  	           STS Serial Test (Generalized)	      Good
  -d 200  	               RGB Bit Distribution Test	      Good
  -d 201  	   RGB Generalized Minimum Distance Test	      Good
  -d 202  	                   RGB Permutations Test	      Good
  -d 203  	                     RGB Lagged Sum Test	      Good
  -d 204  	        RGB Kolmogorov-Smirnov Test Test	      Good
  -d 205  	                       Byte Distribution	      Good
  -d 206  	                                 DAB DCT	      Good
  -d 207  	                      DAB Fill Tree Test	      Good
  -d 208  	                    DAB Fill Tree 2 Test	      Good
  -d 209  	                      DAB Monobit 2 Test	      Good

So here are the results:

 $ dieharder -a < random.img
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
        mt19937|  1.25e+08  | 169223456|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.91937112|  PASSED  
      diehard_operm5|   0|   1000000|     100|0.77213572|  PASSED  
  diehard_rank_32x32|   0|     40000|     100|0.04709503|  PASSED  
    diehard_rank_6x8|   0|    100000|     100|0.93031877|  PASSED  
   diehard_bitstream|   0|   2097152|     100|0.12183977|  PASSED  
        diehard_opso|   0|   2097152|     100|0.96023625|  PASSED  
        diehard_oqso|   0|   2097152|     100|0.61237304|  PASSED  
         diehard_dna|   0|   2097152|     100|0.66045974|  PASSED  
diehard_count_1s_str|   0|    256000|     100|0.16999968|  PASSED  
diehard_count_1s_byt|   0|    256000|     100|0.00992823|  PASSED  
 diehard_parking_lot|   0|     12000|     100|0.69592283|  PASSED  
    diehard_2dsphere|   2|      8000|     100|0.95358410|  PASSED  
    diehard_3dsphere|   3|      4000|     100|0.89028448|  PASSED  
     diehard_squeeze|   0|    100000|     100|0.81631204|  PASSED  
        diehard_sums|   0|       100|     100|0.03559934|  PASSED  
        diehard_runs|   0|    100000|     100|0.75027140|  PASSED  
        diehard_runs|   0|    100000|     100|0.43076351|  PASSED  
       diehard_craps|   0|    200000|     100|0.57749359|  PASSED  
       diehard_craps|   0|    200000|     100|0.00599436|  PASSED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.60121369|  PASSED  
 marsaglia_tsang_gcd|   0|  10000000|     100|0.04254338|  PASSED  
         sts_monobit|   1|    100000|     100|0.94352358|  PASSED  
            sts_runs|   2|    100000|     100|0.77549833|  PASSED  
          sts_serial|   1|    100000|     100|0.46198961|  PASSED  
          sts_serial|   2|    100000|     100|0.46002706|  PASSED  
          sts_serial|   3|    100000|     100|0.73076110|  PASSED  
          sts_serial|   3|    100000|     100|0.90967100|  PASSED  
          sts_serial|   4|    100000|     100|0.32002297|  PASSED  
          sts_serial|   4|    100000|     100|0.07478887|  PASSED  
          sts_serial|   5|    100000|     100|0.27486408|  PASSED  
          sts_serial|   5|    100000|     100|0.57409336|  PASSED  
          sts_serial|   6|    100000|     100|0.05095556|  PASSED  
          sts_serial|   6|    100000|     100|0.06341272|  PASSED  
          sts_serial|   7|    100000|     100|0.00941089|  PASSED  
          sts_serial|   7|    100000|     100|0.53679805|  PASSED  
          sts_serial|   8|    100000|     100|0.00122125|   WEAK   
          sts_serial|   8|    100000|     100|0.16239101|  PASSED  
          sts_serial|   9|    100000|     100|0.24007712|  PASSED  
          sts_serial|   9|    100000|     100|0.02659941|  PASSED  
          sts_serial|  10|    100000|     100|0.64616186|  PASSED  
          sts_serial|  10|    100000|     100|0.78783799|  PASSED  
          sts_serial|  11|    100000|     100|0.77618602|  PASSED  
          sts_serial|  11|    100000|     100|0.33875893|  PASSED  
          sts_serial|  12|    100000|     100|0.50423715|  PASSED  
          sts_serial|  12|    100000|     100|0.77528158|  PASSED  
          sts_serial|  13|    100000|     100|0.57625144|  PASSED  
          sts_serial|  13|    100000|     100|0.73422196|  PASSED  
          sts_serial|  14|    100000|     100|0.40891605|  PASSED  
          sts_serial|  14|    100000|     100|0.48542772|  PASSED  
          sts_serial|  15|    100000|     100|0.67319390|  PASSED  
          sts_serial|  15|    100000|     100|0.74730027|  PASSED  
          sts_serial|  16|    100000|     100|0.67519158|  PASSED  
          sts_serial|  16|    100000|     100|0.73171087|  PASSED  
         rgb_bitdist|   1|    100000|     100|0.87216594|  PASSED  
         rgb_bitdist|   2|    100000|     100|0.18831902|  PASSED  
         rgb_bitdist|   3|    100000|     100|0.16757216|  PASSED  
         rgb_bitdist|   4|    100000|     100|0.05327115|  PASSED  
         rgb_bitdist|   5|    100000|     100|0.75278396|  PASSED  
         rgb_bitdist|   6|    100000|     100|0.64749144|  PASSED  
         rgb_bitdist|   7|    100000|     100|0.20311557|  PASSED  
         rgb_bitdist|   8|    100000|     100|0.39994123|  PASSED  
         rgb_bitdist|   9|    100000|     100|0.52805289|  PASSED  
         rgb_bitdist|  10|    100000|     100|0.96091722|  PASSED  
         rgb_bitdist|  11|    100000|     100|0.97794399|  PASSED  
         rgb_bitdist|  12|    100000|     100|0.75009561|  PASSED  
rgb_minimum_distance|   2|     10000|    1000|0.58923867|  PASSED  
rgb_minimum_distance|   3|     10000|    1000|0.54294743|  PASSED  
rgb_minimum_distance|   4|     10000|    1000|0.59446131|  PASSED  
rgb_minimum_distance|   5|     10000|    1000|0.00047025|   WEAK   
    rgb_permutations|   2|    100000|     100|0.89040191|  PASSED  
    rgb_permutations|   3|    100000|     100|0.47917416|  PASSED  
    rgb_permutations|   4|    100000|     100|0.30964668|  PASSED  
    rgb_permutations|   5|    100000|     100|0.70217495|  PASSED  
      rgb_lagged_sum|   0|   1000000|     100|0.12796648|  PASSED  
      rgb_lagged_sum|   1|   1000000|     100|0.15077254|  PASSED  
      rgb_lagged_sum|   2|   1000000|     100|0.31141471|  PASSED  
      rgb_lagged_sum|   3|   1000000|     100|0.94974697|  PASSED  
      rgb_lagged_sum|   4|   1000000|     100|0.99256987|  PASSED  
      rgb_lagged_sum|   5|   1000000|     100|0.67854004|  PASSED  
      rgb_lagged_sum|   6|   1000000|     100|0.08600877|  PASSED  
      rgb_lagged_sum|   7|   1000000|     100|0.91633363|  PASSED  
      rgb_lagged_sum|   8|   1000000|     100|0.06794590|  PASSED  
      rgb_lagged_sum|   9|   1000000|     100|0.59024027|  PASSED  
      rgb_lagged_sum|  10|   1000000|     100|0.59285975|  PASSED  
      rgb_lagged_sum|  11|   1000000|     100|0.87178336|  PASSED  
      rgb_lagged_sum|  12|   1000000|     100|0.63401541|  PASSED  
      rgb_lagged_sum|  13|   1000000|     100|0.47202172|  PASSED  
      rgb_lagged_sum|  14|   1000000|     100|0.34616699|  PASSED  
      rgb_lagged_sum|  15|   1000000|     100|0.97221211|  PASSED  
      rgb_lagged_sum|  16|   1000000|     100|0.95576739|  PASSED  
      rgb_lagged_sum|  17|   1000000|     100|0.32367098|  PASSED  
      rgb_lagged_sum|  18|   1000000|     100|0.92792046|  PASSED  
      rgb_lagged_sum|  19|   1000000|     100|0.58128429|  PASSED  
      rgb_lagged_sum|  20|   1000000|     100|0.78197001|  PASSED  
      rgb_lagged_sum|  21|   1000000|     100|0.86068846|  PASSED  
      rgb_lagged_sum|  22|   1000000|     100|0.22496908|  PASSED  
      rgb_lagged_sum|  23|   1000000|     100|0.52387665|  PASSED  
      rgb_lagged_sum|  24|   1000000|     100|0.52748770|  PASSED  
      rgb_lagged_sum|  25|   1000000|     100|0.96442902|  PASSED  
      rgb_lagged_sum|  26|   1000000|     100|0.51298847|  PASSED  
      rgb_lagged_sum|  27|   1000000|     100|0.99123470|  PASSED  
      rgb_lagged_sum|  28|   1000000|     100|0.69774674|  PASSED  
      rgb_lagged_sum|  29|   1000000|     100|0.83646714|  PASSED  
      rgb_lagged_sum|  30|   1000000|     100|0.98573851|  PASSED  
      rgb_lagged_sum|  31|   1000000|     100|0.23580471|  PASSED  
      rgb_lagged_sum|  32|   1000000|     100|0.19150884|  PASSED  
     rgb_kstest_test|   0|     10000|    1000|0.67771558|  PASSED  
     dab_bytedistrib|   0|  51200000|       1|0.07152541|  PASSED  
             dab_dct| 256|     50000|       1|0.53841656|  PASSED  
Preparing to run test 207.  ntuple = 0
        dab_filltree|  32|  15000000|       1|0.09092747|  PASSED  
        dab_filltree|  32|  15000000|       1|0.83382174|  PASSED  
Preparing to run test 208.  ntuple = 0
       dab_filltree2|   0|   5000000|       1|0.37363586|  PASSED  
       dab_filltree2|   1|   5000000|       1|0.26890999|  PASSED  
Preparing to run test 209.  ntuple = 0
        dab_monobit2|  12|  65000000|       1|0.80810458|  PASSED  

I don't have an image to look at to visually verify that there are no obvious patterns. At 1.8 GB, I feel that it would be just a bit too unwieldy anyway. So, I'll need to trust the previous tests for randomness that the data really is random. After these 3 series of tests, I can only conclude that using a Realtek SDR as a HWRNG will generate as "true random" data as you can hope for.

Hardware RNG Through an rtl-sdr Dongle

An rtl-sdr dongle allows you to receive radio frequency signals to your computer through a software interface. You can listen to Amateur Radio, watch analog television, listen to FM radio broadcasts, and a number of other things. I have a friend to uses it to monitor power usage at his house. However, I have a different use- true random number generation.

The theory behind the RNG is by taking advantage of radio frequency noise such as atmospheric noise. which is caused by natural occurrences, such as weak galactic radiation from the center of our Milky Way Galaxy to the stronger local and remote lightning strikes. It's estimated that roughly 40 lightning strikes are hitting the Earth every second, which equates to about 3.5 million strikes per 24 hour period. Interestingly enough, this provides a great deal of entropy for a random number generator.

Check out Blitzortung. It is a community run site, where volunteers can setup lightning monitoring stations and submit data to the server. Of course, it isn't an accurate picture of the entire globe, but you can at least get some idea of the scope of lightning strikes around the continents.

Lightning Map of the United States

Unfortunately, however, the rtl-sdr dongle won't get down to the frequencies necessary for sampling atmospheric noise; about 100 KHz to 10 MHz, and above 10 GHz. However, it can sample cosmic noise, man-made (urban and suburban) noise, solar noise, thermal noise, and other terrestrial noises that are well within the tuner frequency range of the dongle.

In order to take advantage of this, you obviously need an rtl-sdr dongle. They're quite cheap, about $15 or so, and plug in via USB with an external antenna. Of course, the larger the antenna, the more terrestrial noise you'll be able to observe. With a standard telescoping antenna, I can observe about 3 Mbps of true random data.

The other piece, however, will be compiling and installing the rtl-entropy software. This will provide a FIFO file for observing the random data. Reading the random data can be done as you would read any regular file:

$ sudo rtl_entropy -b -f 74M
$ tail -f /run/rtl_entropy.fifo | dd of=/dev/null
^C8999+10 records in
9004+0 records out
4610048 bytes (4.6 MB) copied, 13.294 s, 347 kB/s

That's roughly 2.8 Mbps. Not bad for $15. Notice, that I passed the "-b" switch to detach the PID from the controlling TTY and background. Further, I am not tuning to the default frequency of 70 MHz, which is part of Band I in the North America band plan for television broadcasting. Instead, I am tuning to 74 MHz, which is in the middle of a break in the band plan, where no television broadcasting should be transmitted. Of course, you'll need to make sure you are tuning to a frequency that is less likely to encounter malicious interference. Even though the rtl_entropy daemon has built-in debiasing and FIPS randomness testing, a malicious source could interrupt with the operation of the output by transmitting on the frequency that you are listening to.

In order to guarantee that you have random data, you should send it through a battery of standardized tests for randomness. One popular test for randomness are the FIPS 140-2 tests. Suppose I create a 512 MB file from my sdr-rtl dongle, I can test it as follows:

$ rngtest < random.img
rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions.  There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 83886080
rngtest: FIPS 140-2 successes: 4190
rngtest: FIPS 140-2 failures: 4
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 1
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 2
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=174.986; avg=4379.165; max=4768.372)Mibits/s
rngtest: FIPS tests speed: (min=113.533; avg=147.777; max=150.185)Mibits/s
rngtest: Program run time: 560095 microseconds

It's expected to see some failures, but they should be outliers. There is also the Dieharder battery of randomness tests. This will take substantially longer to work through, but it can be done. Here are the first few lines:

$ dieharder -a < random.img 
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |rands/second|   Seed   |
        mt19937|  1.30e+08  | 334923062|
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.98331589|  PASSED  
      diehard_operm5|   0|   1000000|     100|0.12201131|  PASSED  
  diehard_rank_32x32|   0|     40000|     100|0.69993313|  PASSED  
    diehard_rank_6x8|   0|    100000|     100|0.55365877|  PASSED  
   diehard_bitstream|   0|   2097152|     100|0.85077208|  PASSED  
        diehard_opso|   0|   2097152|     100|0.76171650|  PASSED  

The whole dieharder results of my 512 MB random file can be found here.

Last, but not least, it helps to observe the data visually. In this image, I created a plain white file in Gimp, that was 600x600 pixels in size. I then counted the number of bytes in that file, and generated an equally sized random binary data file. Finally, I added the bitmap header to the file, converted it to a PNG file, optimized it, and uploaded it here. The steps are as follows:

$ gimp # create 600x600px plain white file and save as 16-bit "white.bmp"
$ ls -l white.bmp | awk '{print $5}'
720138
$ tail -f /run/rtl_entropy.fifo| dd of=random.img bs=1 count=720138 iflag=fullblock
720138+0 records in
720138+0 records out
720138 bytes (720 kB) copied, 24.8033 s, 29.0 kB/s
$ dd if=white.bmp of=random.img bs=1 count=54 conv=notrunc
$ gimp random.img # export to PNG file

When viewing the output, there should be no obvious patterns in the output. As an example:

Visual representation of random

For more practical use, here is a quick application for generating 80-bit entropy unambiguous passwords:

$ for i in {1..10}; do
> strings /run/rtl_entropy.fifo | grep -o '[a-hjkmnp-z2-9.]' | head -n 16 | tr -d '\n'; echo
> done
8dfn42w6dagqnt4z
2vcsqu6sew.g6pp2
kv9nstj4gq39x5f.
wmpdpy7yz75xrhkh
.4ra2b38hmbf5jw5
7ngyk3c58k3eeq7c
8e4t8ts3ykhckdst
9g6yqqce.bxrrhpb
xwnw6mtk8njv76b2
xdmd89n68f.kcthp

Obviously, the practical uses here can be for Monte Carlo simulations, game theory, gambling, cryptography, and other practical uses where high quality randomness is needed. Unfortunately, I can seem to get rngd(8) to add the /run/rtl_entropy.fifo file as a hardware device. So, I can't feed the Linux CSPRNG with with the dongle, other than "dd if=/run/rtl_entropy.fifo of=/dev/random", which doesn't increase the entropy estimate, of course.

Encrypting Combination Locks

This morning, my family and I went swimming at the community swimming center. Unfortunately, I couldn't find my key-based lock that I normally take. However, I did find my Master combination lock, but couldn't recall the combination. Fortunately, I knew how to find it. I took this lock with me to lock my personal items in the locker while swimming around in the pool.

While swimming, I started thinking about ways to better recall lock combinations in the future. The obvious choice is to encrypt it, so I could engrave the encrypted combination on the lock. However, it needs to be simple enough to do in my head should I temporarily forget it while swimming, and easy enough to recall if I haven't used the lock in a few years. Thankfully, this can be done easily enough with modulo addition and subtraction.

Before beginning, you need a 6-digit PIN that you won't easily forget. Tempting enough, dates can easily be in 6-digits, and something like a birthday or an anniversary are not hard to remember. Unfortunately, if someone knows you, and knows these dates, they can easily reverse the process to open the lock. So, as tempting as dates are, don't use them. Instead, you should probably use a 6-digit PIN, that only you would know, and always know. So, knowing this, let's see how this works.

You need to be familiar with modulus math, aka "clock math". The idea, is that after a certain maximum, the numbers reset back to 0. For example, 00:00 is midnight while 23:59 is the minute before. As soon as the hour is "24", then it resets back to 0, for a full 24-hour day. You could call telling time "mod 24 math". For combination locks, we're going to be using "mod 40 math", if the maximum number on your combination lock is "40", on "mod 60 math" if the max is "60", and so forth.

Suppose the combination to your lock is "03-23-36", and suppose your 6-digit PIN is "512133". Let's encrypt the combination with our PIN, by using "mod 40 subtraction". We'll use subtraction now, because most people have an easier time with addition than subtraction. When you are trying to rediscover your combination, you'll take your encrypted number, and do "mod 40 addition" to reverse it, and bring it back to the original combination lock numbers.

Here it is in action:

Encrypting the original combination

  03 23 36    <- original combination
- 51 21 33    <- secret PIN
= --------
 -48 02 03
= --------
  32 02 03    <- encrypted after "mod 40"

Because the first number in our combination is "03", and we are subtracting off "51", we end up with "-48". As such, we need to add "40" until our target new number is in the range of [0, 40), or "0 <= n < 40". This gives us "32" as the result. The rest of the numbers fell within that range, so no adjusting was necessary. I can then engrave "32-02-03" on the bottom of the lock, so when I hold the lock up while in a locker, the text is readable. Okay, that's all fine and dandy, but what about reversing it? Taking the encrypted combination, and returning to the original combination? This is where "mod 40 addition" comes in. For example:

Decrypting the encrypted combination

  32 02 03    <- encrypted combination
+ 51 21 33    <- secret PIN
= --------
  83 23 36
= --------
  03 23 36    <- original combination after "mod 40"

Notice that this time, the first number in our "mod 40 addition" is "83". So, we subtract of "40" until our original combination number is in the range of [0,40), or "0 <= n < 40", just like when doing "mod 40 subtraction" to create the new combination lock values. At worst case, you'll have to subtract a "40" only three times per number. On thing to watch out for, is that your encrypted combination numbers are far enough away from the original, that trying out the encrypted combination, won't accidentally open the lock, due to their proximity to the original numbers. If only one number is substantially off, that should be good enough to prevent an accidental opening. I want to come back to dates however, and why not to use them. Not only do they fall victim to a targeted attack, but they also have an exceptionally small key space. Assuming there are only 365 days per year, and assuming the attacker has a good idea of your age, plus or minus five years, that's a total of 3,650 total keys that must be tried following the common convention of "MM-DD-YY". It could be greatly reduced, if the attacker has a better handle on when you were born. If a 6-digit PIN is chosen instead, then the search space has 1,000,000 possible PINs. This is greater than the 64,000 possible maximum combination numbers a 40-digit Master lock could have, which puts the attacker on a brute force search for the original combination, if they aren't aware that Master combination locks can be broken in 8 tries or less.

The Lagged Fibonacci Generator

Lately, I have been studying pseudorandom number generators (PRNGs, also called "deterministic random bit generators", or DRBGs). I've been developing cryptographically secure PRNGs (CSPRNGs), and you can see my progress on Github at https://github.com/atoponce/csprng. This project is for nothing more than for me to somewhat get a feeling for new languages, while also learning a thing or two about applied cryptograhpy. However, for the subject of this post, I want to address one PRNG that is not cryptographically secure- the Lagged Fibonacci Generator.

What drew me to this generator was thinking about a way to have a PRNG to do by hand. I started thinking about different ways to construct a PRNG mathematically. But, before creating an algorithm, I needed to identify all the points that make a good PRNG. A good PRNG should have:

  • An easy implementation.
  • High efficiency in calculating the pseudorandom values.
  • Long (practically un-observable) periods for most, if not all initial seeds.
  • A uniform distribution over the finite space.
  • No correlation between successive values.

I put a great deal of thought into it, but couldn't come up with anything I was very proud of. I thought of using trigonometric functions, various logarithm functions, geometric and algebraic expressions, and even fancy equations using derivatives. The more I thought about it, the further away I drifted from something simple that could be done by hand with pencil and paper.

The best I came up with, which required using a scientific calculator, was forcing the sequence to grow (a monotonically increasing function), then forcing it into a finite field with a modulus. However, no matter what I threw at it, I always struggled with either dealing with "0" or "1". For example, taking the n-th exponent of either "0" or "1" will always return a "0" or "1". I realized quickly that multiplication might be a problem. For example, one thought I had was the following:

Si = Floor[(Si-1)3/2], mod M

This works out fine, until your output is a "0" or "1", then the generator sits on either of those numbers indefinitely. I realized that my function should probably just stick with addition, or I'm bound to get myself into trouble. I thought, and thought about it, then it hit me. It was my "Beautiful Mind" moment.

I thought of the Fibonacci sequence.

The Fibonacci sequence is monotonically increasing for two seeds S1 and S2, where 0 < S1 < S2. If you put an upper bound on the sequence via a modulus, you can limit it to a finite space, and I can have my PRNG. However, I also know that the distance between any two sequential digits in the Fibonacci sequence approaches the Golden Ratio Phi. I'm not sure how this would affect my simple PRNG, and if a correlation between successive digits could be identified, but I started scribbling down numbers on a text pad anyway.

Immediately, however, I found something interesting: If both seeds are even, then the whole sequence of numbers would be even. For example, take the following Fibonacci PRNG:

S1 = 6, S2 = 8, mod 10
6 8 4 2 6 8 4 2 6 8 4 2 ...

There are two problems happening here- first, the period of the PRNG is 4 digits- 6, 8, 4, & 2. Second, because even numbers were chosen for the seeds, even numbers are the only possibility for the PRNG. So, either one of the seeds or the modulus must be odd, or the PRNG algorithm needs to be modified.

At this point, I threw my hands up in the air, and said "screw it". I decided to see what history had discovered with simple PRNGs. Turns out, I wasn't far off. A Fibonacci sequence PRNG exists called the Lagged Fibonacci Generator. Here is how it works:

Sn = Sn-j ⊙ Sn-k mod M, 0 < j < k

Where "⊙" is any binary function, such as addition, subtraction, multiplication, or even the bitwise exclusive-or.

First off, it doesn't address the "all evens" problem with my naive generator. If addition is used to calculate the values, then at least one number in the seed must be odd. If multiplication is used, then at least k-elements must be odd. However, what is interesting about this generator, is that rather than picking the first and second elements of the list to calculate the random value (Si-1 and Si-2), any j-th and k-th items in the list can be used (Si-j and Si-k). However, you must have at least k-elements in the list as your seed before beginning the algorithm.

To simplify things, lets pick "j=3" and "k=7" mod 10 addition. I need at least seven elements in the list, and at least one of them must be odd. I've always like the phone number "867-5309", so let's use that as our seed. Thus, the first 10 steps of our generator would look like this:

j=3, k=7, mod 10 addition

        [j]       [k]
 1. 8 6 [7] 5 3 0 [9] => 7+9 = 6 mod 10
 2. 6 7 [5] 3 0 9 [6] => 5+6 = 1 mod 10
 3. 7 5 [3] 0 9 6 [1] => 3+1 = 4 mod 10
 4. 5 3 [0] 9 6 1 [4] => 0+4 = 4 mod 10
 5. 3 0 [9] 6 1 4 [4] => 9+4 = 3 mod 10
 6. 0 9 [6] 1 4 4 [3] => 6+3 = 9 mod 10
 7. 9 6 [1] 4 4 3 [9] => 1+9 = 0 mod 10
 8. 6 1 [4] 4 3 9 [0] => 4+0 = 4 mod 10
 9. 1 4 [4] 3 9 0 [4] => 4+4 = 8 mod 10
10. 4 4 [3] 9 0 4 [8] => 3+8 = 1 mod 10

Generated: 6 1 4 4 3 9 0 4 8 1

The following Python code should verify our results:

1
2
3
4
5
6
7
8
9
10
11
12
j = 3
k = 7
s = [8, 6, 7, 5, 3, 0, 9]
for n in xrange(10):
    for i in xrange(len(s)):
        if i is 0:
            out = (s[j-1] + s[k-1]) % 10 # the pseudorandom output
        elif 0 < i < 6:
            s[i] = s[i+1] # shift the array
        else:
            s[i] = out
            print s[i], # print the result

Running it verifies our results:

$ python lagged.py
6 1 4 4 3 9 0 4 8 1

It's a "lagged" generator, because "j" and "k" lag behind the generated pseudorandom value. Also, this is called a "two-tap" generator, in that you are using 2 values in the sequence to generate the pseudorandom number. However, a two-tap generator has some problems with randomness tests, such as the Birthday Spacings. Apparently, creating a "three-tap" generator addresses this problem. Such a generator would look like:

Sn = Sn-j ⊙ Sn-k ⊙ Sn-l mod M, 0 < j < k < l

Even though this generator isn't cryptographically secure (hint: it's linear), it meets the above requirements for a good PRNG, provided the "taps" are chosen carefully (the lags are exponents of a primitive polynomial), and the modulus is our traditional "power-of-2" (2M, such as 232 or 264). Supposing we are using a two-tap LFG, it would have a maximum period of:

(2k-1)*k    if exclusive-or is used
(2k-1)*2M-1 if addition or subtraction is used
(2k-1)*2M-3 if multiplication is used (1/4 of period of the additive case)

For a good LFG, it is found that a three-tap generator should be used, as a 3-element spacing correlation can be found in two-tap generators, and that initial taps should be very high for a large modulus. Further, the full mathematical theory hasn't been worked out on Fibonacci generators, so the quality of the generators rests mostly on the statistics of the generated output, and randomness tests.

However, this is simple enough to do by hand, if nothing else than to impress your friends.