Predictable SSH host keys

[oittaa]

Hello,
Raspbian (2015-11-21-raspbian-jessie.zip SHA1: ce1654f4b0492b3bcc93b233f431539b3df2f813) doesn't enable hardware random number generator by default. This causes generation of predictable SSH host keys on the first boot.

As soon as the systems starts up systemd-random-seed tries to seed /dev/urandom, but /var/lib/systemd/random-seed is missing, because it hasn't been created yet. /etc/rc2.d/S01regenerate_ssh_host_keys is executed, but /dev/urandom pool doesn't have that much entropy at this point and predictable SSH host keys will be created.

Original /etc/init.d/regenerate_ssh_host_keys (/etc/rc2.d/S01regenerate_ssh_host_keys is a symbolic link to it):

Code: Select all

#!/bin/sh
### BEGIN INIT INFO
# Provides:          regenerate_ssh_host_keys
# Required-Start:
# Required-Stop:
# Default-Start: 2
# Default-Stop:
# Short-Description: Regenerate ssh host keys
# Description:
### END INIT INFO

. /lib/lsb/init-functions

set -e

case "$1" in
  start)
    log_daemon_msg "Regenerating ssh host keys (in background)"
    nohup sh -c "yes | ssh-keygen -q -N '' -t dsa -f /etc/ssh/ssh_host_dsa_key && \
      yes | ssh-keygen -q -N '' -t rsa -f /etc/ssh/ssh_host_rsa_key && \
      yes | ssh-keygen -q -N '' -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key && \
      yes | ssh-keygen -q -N '' -t ed25519 -f /etc/ssh/ssh_host_ed25519_key && \
      systemctl enable ssh && sync && \
      rm /etc/init.d/regenerate_ssh_host_keys && \
      update-rc.d regenerate_ssh_host_keys remove && \
      printf '\nfinished\n' && systemctl start ssh" > /var/log/regen_ssh_keys.log 2>&1 &
    log_end_msg $?
    ;;
  *)
    echo "Usage: $0 start" >&2
    exit 3
    ;;
esac

The script could be modified to test HW RNG and seed /dev/urandom, if one is found.

Code: Select all

#!/bin/sh
### BEGIN INIT INFO
# Provides:          regenerate_ssh_host_keys
# Required-Start:
# Required-Stop:
# Default-Start: 2
# Default-Stop:
# Short-Description: Regenerate ssh host keys
# Description:
### END INIT INFO

. /lib/lsb/init-functions

set -e

case "$1" in
  start)
    log_daemon_msg "Regenerating ssh host keys (in background)"
    modprobe -q bcm2708-rng && dd if=/dev/hwrng of=/dev/urandom count=1 bs=4096 2>/dev/null
    nohup sh -c "yes | ssh-keygen -q -N '' -t dsa -f /etc/ssh/ssh_host_dsa_key && \
      yes | ssh-keygen -q -N '' -t rsa -f /etc/ssh/ssh_host_rsa_key && \
      yes | ssh-keygen -q -N '' -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key && \
      yes | ssh-keygen -q -N '' -t ed25519 -f /etc/ssh/ssh_host_ed25519_key && \
      systemctl enable ssh && sync && \
      rm /etc/init.d/regenerate_ssh_host_keys && \
      update-rc.d regenerate_ssh_host_keys remove && \
      printf '\nfinished\n' && systemctl start ssh" > /var/log/regen_ssh_keys.log 2>&1 &
    log_end_msg $?
    ;;
  *)
    echo "Usage: $0 start" >&2
    exit 3
    ;;
esac

ssh-keygen command uses OpenSSL internally, which seeds it's userspace CSPRNG from /dev/urandom. You can test this yourself by running the following command:

Code: Select all

strace -xe trace=file,read,write,close ssh-keygen -f /tmp/ssh_host_rsa_key -N '' -t rsa

Output:

Code: Select all

...
open("/dev/urandom", O_RDONLY|O_NOCTTY|O_NONBLOCK) = 3
read(3, "\xfc\x60\x50\x8b\x46\x12\xd2\x3b\x62\xc4\x34\x8f\x21\x1d\xef\xe4\x15\xa7\xda\x05\x4f\x07\xc6\x8e\xd7\x84\x24\x54\xc5\xf9\x90\xb2", 32) = 32
close(3)                                = 0
...

I would suggest everyone to regenerate their Raspbian SSH host keys, if they're still using the ones generated automatically.

[oittaa]

Patch to seed /dev/urandom before generating SSH keys. Requires rdiff.

SHA256
3b6c063ad5bb02d9a62270b6672fb9a1aa055c5644d4d2e7b73a17d0ba6086e6 2015-11-21-raspbian-jessie.img.patch.zip

Code: Select all

unzip 2015-11-21-raspbian-jessie.img.patch.zip
rdiff patch 2015-11-21-raspbian-jessie.img 2015-11-21-raspbian-jessie.img.patch 2015-11-21-raspbian-jessie-patched.img
dd bs=4M if=2015-11-21-raspbian-jessie-patched.img of=/dev/sdX

MODERATOR CHANGE: I've removed the patch from this post. Without analysis, I cannot tell if this patch is secure or not (it appeared to be a binary patch which I find untrustworthy, and not the best way of passing on fixes). To to OP - please report the issue on github, and supply a source code patch. This will then be peer reviewed and included in the source tree if necessary.

[oittaa]

You can compare the resulting boot partitions:

Code: Select all

head -c 67108864 2015-11-21-raspbian-jessie.img | sha256sum
head -c 67108864 2015-11-21-raspbian-jessie-patched.img | sha256sum

Output from both commands should be:

Code: Select all

f4fed8b6ba53ff54ce32a7cbee60b2acbfe32bdd9ccc53043ae09ff067893d65  -

Then compare the root partitions. Only difference should be in /etc/init.d/regenerate_ssh_host_keys

Code: Select all

sudo losetup -o 67108864 /dev/loop0 2015-11-21-raspbian-jessie.img
sudo losetup -o 67108864 /dev/loop1 2015-11-21-raspbian-jessie-patched.img
mkdir /tmp/orig
mkdir /tmp/patched
sudo mount /dev/loop0 /tmp/orig/
sudo mount /dev/loop1 /tmp/patched/
sudo diff -ru --no-dereference /tmp/orig/ /tmp/patched/
sudo umount /tmp/orig/ /tmp/patched/
sudo losetup -d /dev/loop0
sudo losetup -d /dev/loop1
rmdir /tmp/orig/ /tmp/patched/

[fruit-uk]

Interesting.
Thought there might have been more comments by now - but perhaps too early in the morning.

[DougieLawson]

What have you changed? How do we know your ZIP file isn't a virus or something that will totally compromise our systems?

If you have an issue with the kernel then report it at https://github.com/raspberrypi/linux don't post random ZIP files on the forum.

[oittaa]

What have you changed? How do we know your ZIP file isn't a virus or something that will totally compromise our systems?

If you have an issue with the kernel then report it at https://github.com/raspberrypi/linux don't post random ZIP files on the forum.

[Mod edited for insult-slinging - if we see any more, we'll hand down a ban.]

I posted exactly what I've changed and how you can verify it. Why would I report anything regarding kernel, when the problem is in the startup scripts?

EDIT:
https://www.raspbian.org/RaspbianBugs mentions:

If there is no specific project for the package in question then the RPi-Distro/repo project should be used.

I actually did that, but it seems like nobody is reading those reports: https://github.com/RPi-Distro/repo/issues/6

[Joe Schmoe]

I'm sorry, but are you blind?

Another -5 for DL.

Looks like he is dipping into the minus numbers on the week.

[oittaa]

I'm sorry, but are you blind?

Another -5 for DL.

Looks like he is dipping into the minus numbers on the week.

Was it too hard to test what it actually does?

[oittaa]

Here's a way to patch the startup script without a binary patch.

put this to /tmp/raspbian.patch

Code: Select all

--- /tmp/orig/etc/init.d/regenerate_ssh_host_keys	2015-11-21 22:33:43.953655590 +0200
+++ /tmp/patched/etc/init.d/regenerate_ssh_host_keys	2015-11-25 05:28:39.074387956 +0200
@@ -16,6 +16,7 @@
 case "$1" in
   start)
     log_daemon_msg "Regenerating ssh host keys (in background)"
+    modprobe -q bcm2708-rng && dd if=/dev/hwrng of=/dev/urandom count=1 bs=4096 2>/dev/null
     nohup sh -c "yes | ssh-keygen -q -N '' -t dsa -f /etc/ssh/ssh_host_dsa_key && \
       yes | ssh-keygen -q -N '' -t rsa -f /etc/ssh/ssh_host_rsa_key && \
       yes | ssh-keygen -q -N '' -t ecdsa -f /etc/ssh/ssh_host_ecdsa_key && \

Then execute these commands:

Code: Select all

mkdir /tmp/raspbian-jessie
sudo losetup -o 67108864 /dev/loop0 2015-11-21-raspbian-jessie.img
sudo mount /dev/loop0 /tmp/raspbian-jessie/
cd /tmp/raspbian-jessie/etc/init.d/
sudo patch < /tmp/raspbian.patch
cd
sudo umount /tmp/raspbian-jessie
sudo losetup -d /dev/loop0
rmdir /tmp/raspbian-jessie

[DougieLawson]

Well done Joe Schmoe, you've achieved your aim, you are now blocked by me on the forum.

[oittaa]

To to OP - please report the issue on github, and supply a source code patch. This will then be peer reviewed and included in the source tree if necessary.

Can you point me to the correct Github page, where regenerate_ssh_host_keys is hosted?

[magarto]

I have an error:
losetup: 2015-11-21-raspbian-jessie.img: failed to set up loop device: Cannot find file

One more question, do I need to create SSH keys again once I finish the commands?

[jamesh]

To to OP - please report the issue on github, and supply a source code patch. This will then be peer reviewed and included in the source tree if necessary.

Can you point me to the correct Github page, where regenerate_ssh_host_keys is hosted?

I've forwarded this thread to the FOundation who will be ab le to give more advice.

In the meantime, the FOundation git hub page is here

https://github.com/raspberrypi/

[jamesh]

Foundation has been looking into it, expected solution similar to that proposed.

https://github.com/RPi-Distro/repo/issues/6

[technion]

https://github.com/RPi-Distro/repo/issues/6

That issue has been closed, first asking for proof, then making an incorrect assertion regarding key generation.

ssh-keygen utilises OpenSSL's rsa_generate_key_ex, which ultimately calls BN_generate_prime_ex, using a horrible series of gotos and pointer arithmetic, navigates around dual_ec_drbg and ultimately pulls the data from /dev/urandom, which does not make assertions about its seeding.

[ShiftPlusOne]

https://github.com/RPi-Distro/repo/issues/6

That issue has been closed, first asking for proof, then making an incorrect assertion regarding key generation.

ssh-keygen utilises OpenSSL's rsa_generate_key_ex, which ultimately calls BN_generate_prime_ex, using a horrible series of gotos and pointer arithmetic, navigates around dual_ec_drbg and ultimately pulls the data from /dev/urandom, which does not make assertions about its seeding.

The issue was closed because it was not the originally reported issue (which has been addressed). The entropy thing is a separate issue, which hasn't been reported as such but will be addressed in the next image.

I've never made any assertions and have made it clear that what I said there was simply going off memory.

[huygens]

This issue is not specific to Raspbian/Raspberry Pi. This problem of the SSH host keys generated at first boot after installation of a system affects all Linux distributions.

On systems with low entropy gathering capabilities (such a VM guests, some embedded systems, headless servers, etc.) it can be a bigger problem. So it is advisable to regenerate the SSH hosts keys but not necessarily mandatory.
Note that some algorithm are more sensitive than others to "weak" randomness, notably DSA.

There are already mitigations, many Linux distribution are saving a seed file during the installation to provide some better randomness during the first boot. This mitigation is not really possible when you use an image which you write on disk, much like we do "installation" with Raspbian.

So yes, Raspbian will use a random number when generating the SSH host keys. This random number could be guessed if an attacker knows the state of the Raspberry Pi during its first boot (was a mouse plugged? was a network cable plugged or other USB devices presents?), and still it would be quite a task to find it. So each user should evaluate the threat depending on the use case of their Raspberry Pi.

This problem is known and the Linux community is trying to solve it already. In Linux kernel (possibly 3.17 but for sure 3.19) there is a new syscall getrandom(2) (see presentation here: https://lwn.net/Articles/606141/). This syscall can be blocking until the system has gathered enough initial entropy, when used on boot this can slightly delay the boot time but provides good random numbers for an SSH host key generation. LibreSSL is using it. OpenSSL is not yet using it, but hopefully one day this will be solved. Note that urandom is not the only randomness input that OpenSSL is using for seeding its own CSPRNG, but it could be the only on the first boot after installation.

I would say: if you are paranoid or want to expose SSH to the internet or have a security requirement for this, then you should regenerate anyway yourself the SSH host keys no matter if your distribution is doing it well or not. You probably want only 1 or 2 supported algorithms for your SSH host keys (e.g. only ed25519 or RSA) and with specific options (e.g. RSA with 4096 bit key length). You want to be in control.
If you are in the other categories, then a secret service agency has probably no interest in your Raspberry Pi and you probably do not need to care about this your favourite distribution is probably doing a good enough job.

Now can we still do a better job without just falling into paranoia? Yes in the future, there are research going on in this field, (e.g. http://cseweb.ucsd.edu/~swanson/papers/ ... ntropy.pdf) which have not yet landed in the Linux kernel. For now, it could be documented that a user my consider regenerating the SSH host keys after eiher making sure enough entropy has been gathered by the OS, or on another system where enough entropy is available to generate them.

I have in the past suggested that in a blog article regarding installing Linux on Raspberry Pi (http://www.berthon.eu/2015/installing-l ... -easy-way/). It details how to activate the hardware RNG and then regenerate the SSH host keys.

[AGWA]

ssh-keygen is not necessarily generating weak keys, since the kernel might have already gathered enough entropy from the environment. Someone needs to do a bunch of trial first boots with a Raspberry Pi and look for the following message in the dmesg, which indicates that /dev/urandom was read with insufficient entropy available:

random: ssh-keygen urandom read with N bits of entropy available

This would be extremely helpful in determining how serious this problem is.

[Cromarty]

I'm sorry, but are you blind?

Another -5 for DL.

Looks like he is dipping into the minus numbers on the week.

Was it too hard to test what it actually does?

I'm totally blind. But that doesn't make me stupid. Please don't use terms like that as insults. Or do you assume all blind folks should be sitting in a big shed somewhere making lamp-shades rather than hacking?