1

Recently, GitLab[1] and GitKraken[2] notified users about a vulnerability in GitKraken version v in range 7.6.0<=v<=8.0.0. Those versions are affected by CVE-2021-41117[3] and therefore, generate weak SSH keys. Now, as an administrator of a GitLab instance, I want to know, if any of my users use weak keys generated by a vulnerable GitKraken version.

I'd be grateful for any tips on how to tell if a keypair is weak, having a public key.

[1] https://about.gitlab.com/blog/2021/10/11/notice-for-gitkraken-users-with-gitlab/
[2] https://www.gitkraken.com/blog/weak-ssh-key-fix
[3] https://nvd.nist.gov/vuln/detail/CVE-2021-41117

1

CVE-2021-41117 explains that the affected versions GitCraken used a weak random number generator to generate key pairs. Therefore, it is possible that identical keypairs may have been created by two different users using the software. So, it is possible that someone else may have the same key pair as one of your users. If that person notices that their public key is the same as your user's, then this means that they also know your user's private key, because these are also the same.

A bad actor may even use the weak RNG to generate large numbers of keypairs, in hopes of finding one that matches one in use.

If someone else knows the private key of one of your users (by way of the above), then they can use this to authenticate with your system as that user.

So, to answer your question:

I'd be grateful for any tips on how to tell if a keypair is weak, having a public key.

All keypairs generated by affected versions of GitCraken are weak, because the underlying RNG used to generate these keypairs was weak.

Unfortunately, there is no way for you to know if someone else has the same keypair as one of your uses as a result of this bug; or if a bad actor may exploit this bug to generate the same keypair as one of your users in the future. Additionally, the advisory does not describe a particular way of identifying a keypair that was created by the weak RNG. This is why the advisory is recommending that users cease using any keys that were generated with affected versions of GitCraken, revoke these keys, and replace these keys with newly generated ones. But, this requires action on the part of the user that created the keypair.

6
  • Just note that this is an EXTREMELY SERIOUS flaw. A statement from the NVD reads: each byte in the RNG seed has a 97% chance of being 0 due to incorrect conversion. Someone can easily exhaust all possible key combinations with a bug like this, so all your users need to regenerate their keys immediately.
    – Nelson
    Oct 20 at 2:39
  • The nature of the bug is just a disaster due to JS being total garbage. Missing window object, defaults to Math.Random(), then a function incorrectly calls fromCharCode twice and basically turns most of the generated random number in to 0s. Lovely.
    – Nelson
    Oct 20 at 2:45
  • Maybe just as an idea... I could pretend to be a bad actor and generate a large number of keypairs using RNG with a lot of zeroes. And check all the user keys against this dictionary. But it would be probably not really feasible to generate each and every weak keypair to have a 100% cleanup. Am I right?
    – Danny Lo
    Oct 20 at 8:05
  • I think the sections from the advisory that @Nelson highlights are very pertinent. But, I don't see how one would connect the dots from the weak random numbers generated by the flawed RNG, to the underlying P and Q in the primary key, and then ultimately to the modulus in the public key, so that one could identify a keypair generated from the flawed RNG by examining the public key. github.blog/… talks about identifying such keys, but on the basis of the user agent information in git logs.
    – mti2935
    Oct 20 at 14:49
  • @mti2935 The hard part is the keys themselves look ok, despite having approximately 40 million or less unique keys in the entire pool. (Rough estimate: 64 characters choose 3, * 1,000, assuming 3 digits out of the 64 are non-zero and are randomly between 0-9). You now have to run around with this 4 Gb file (40 million keys * 100 characters) and compare it to every key of every user. It's a lot of work to figure it out.
    – Nelson
    Oct 21 at 2:17
0

All keys affected are considered weak.

Key points in the CVE-2021-41117 NVD bulletin:

The impact is that each byte in the RNG seed has a 97% chance of being 0 due to incorrect conversion. When it is not, the bytes are 0 through 9.

So cryptographically speaking, at even 512-bits (64 characters), you'll only have an extremely tiny fraction of unique keys. All your users must immediately generate all their keys because a brute force attack is trivial with entropy of this level.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.