[Nitrokey HSM] M of N threshold scheme security due 64 bit password

Good evening.
I’ve started with HSM2 and N-of-M Shamir’s Secret Sharing, but I’m concerned about Security in Nitrokey implementation.
sc-hsm-tool give output as follow:
— cut —
The DKEK will be enciphered using a randomly generated 64 bit password.
This password is split using a (N-of-N) threshold scheme).
— cut —

As far as I know, DKEK is AES 256 key. Why only 64 bit long password/secret is used to encrypt 256 long bit key? For me it is strange, because a chain is only as strong as its weakest link.
Am I wrong or in N-M threshold scheme in practice we have 64 bits security for DKEK? Old (developed almost 50 years ago), not good DES has effectively 56 bits.

In “standard” key backup and restore with DKEK scenerio with preselected number of key shares, each key shares is 256 bit long - right? (all key shares are XOR-ed to produce DKEK).

So comparing N of M threshold scheme to “standard” DKEK scenerio with preselected number =1 of key share, we need at least N=4 (==> M >=4) if we need comparable security level, because 4*64 bits = 256 bits. Am I right or wrong?

Comparing security of 1 of 2 threshold schema to “standard” DKEK is as 64 to 256 bits ==> 2^64 to 2^256: The difference is 2^192!

Any suggestions?

Why in N-M treshold schema implementation only 64 bits passwords/Share value are used? Due the hardware limitation in Shamir’s Secret Sharing implementation?

SSS is only used to split the password protecting the encrypted DKEK share.

In a real world scenario you use at least 2 DKEK shares, that are 256 bit each and that are xored internally during share import. You can then protect each share using either a plain password or split the password using SSS for multiple key custodians.

Limiting the password in n-of-m to 64 is done for usability reasons: Writing down or entering 16 hexdigits is something that can be done by the average user. Doing that with 256 bit entropy and 64 hex digits and multiple key custodians is unrealistic.

But you are right, the encrypted DKEK share is protected by only 64 bit entropy. That is the reason why it is important to keep the DKEK share at a safe place (or even print it to paper and keep in a vault).

I understand that using M of N threshold scheme, with 64 bit entropy without at least 2 DKEK shares is not good idea from security point of view.
On the other hand, using Shamir’s Secret Sharing AND many DKEK shares is very complicated and impractical, inconvenient in business reality :-). We need STRONG but SIMPLE solution, like 3 of 7 secret for ONE DKEK secret. Long password for protecting Shamir’s secret (or better files) are OK.

In my humble opinion using only 1 DKEK with LONG (256 bits entropy == 64 hex digits) password for SSS is more comfortable.
The issue is how to represent and store those 64 hex digits. Maybe not as digits, but as file.

I think about solution similar to DKEK shares in pbe files, but with M of N threshold scheme.

Let’s say we generate M pbe files, and we must use N of them (N of M *.pbe file) to rebuild DKEK.

Just files instead hex digits. No one normal can remember 16 nor 64 hex digits :-). In corporate reality N of M Shamir’s Secret Sharing is perfect solution, but with files, and without more than 1 DKEK shares.

Shamir is S in RSA :-).

N-of-M for DKEK shares is meant for access control, not to create the share. Of course there are a lot of different options to handle the DKEK. You could have an AES master key on a different HSM to derive specific DKEK shares or you could encrypt the share using PGP. You can implement whatever scheme you feel suitable. That is the beauty of Open Source :wink:

the 64bit entropy is actually not as bad as it seems. As the result of the secret sharing follows the data flow as passwords, it is also subjected to a password based key generation function. evp_bytestokey is from OpenSSL and calculates a chain of hashes (output of the n-1th hash is input to the nth hash). As iter is set to 10^7, you get password strengthening of about log_2(10^7)=23.3 additional bits. (For each brufeforce attempt, you need to do 10^7 basic crypto operations). For technical reasons of the Shamir-Secret-Sharing (the prime must be bigger than the secret) the first bit of the secret is set to zero, so you actually only have a 63 bit secret to begin with. Adding both, you get a stretched security level of 86.3 bits, which I would deem good enough, except against state sponsored attackers.

To quantify the complexity: In 2012 you could do 16*10^9 MD5 calculations on modern GPUs. The expected time to bruteforce the DKEK share encryption key would thus be 2^63/2*10^7/(16*10^9/s) = 91 Million GPU Years.

More Links which I couldn’t do inline because of restrictions for new users:

1 Like

Oh and by the way, that is not correct. The bits don’t add up, as the result of the Shamir-Secret-Sharing is a single 64bit integer (a number in the Galois Field of the used prime).

Just a small update: current generation GPU GeForce 3080 does ~55 GH (1GH = 10^9 hash operations) for MD5 using Hashcat:

1 Like