Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Don't use GMPY rand for key generation, ever.
#!/usr/bin/env python2
# Extract the "improved" key generation code from cryptowrapper.py
# and tunnelcrypto.py, as of: a623e25e10e5e96ea1d5b85853b23bea00ee439f
from gmpy import mpz, rand
DIFFIE_HELLMAN_MODULUS = mpz(0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020BBEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381FFFFFFFFFFFFFFFF)
rand('init', 128)
rand('seed')
def generate_diffie_not_secret():
dh_secret = 0
while dh_secret >= DIFFIE_HELLMAN_MODULUS or dh_secret < 2:
dh_secret = rand("next", DIFFIE_HELLMAN_MODULUS)
dh_secret = mpz(dh_secret) # Redundant, rand() returns a mpz.
return dh_secret
#
# Why this is totally broken (still).
#
# As I noted in my initial writeup, gmpy.rand() under the hood is a LCG. The
# parameters depend on how big of a cycle you want, when initialized with
# rand('init, 128), it is of the form:
#
# x = (48A74F367FA7B5C8ACBB36901308FA85 * x + 1) % (2^128).
#
# It doesn't particularly matter what it's seeded with, because it's trivial to
# break, but when initialized with rand('seed'), the gmpy code does this:
#
# if(arg) gmp_randseed(randstate, Pympz_AS_MPZ(arg));
# else gmp_randseed_ui(randstate, rand());
#
# So, the way the initialization is currently done, the else branch is taken,
# and libc's rand() is used (unseeded) to initialize an predictable PRNG,
# which is then directly used for key generation.
#
# While the actual value returned from libc's rand() used this way is
# implementation specific, the behavior is consistent and trivial to predict.
#
# Per IEEE Std 1003.1 (Which mirrors the ISO C standard):
#
# The srand() function uses the argument as a seed for a new sequence of
# pseudo-random numbers to be returned by subsequent calls to rand(). If
# srand() is then called with the same seed value, the sequence of
# pseudo-random numbers shall be repeated. If rand() is called before any
# calls to srand() are made, the same sequence shall be generated as when
# srand() is first called with a seed value of 1.
#
# So the new version of the code is initializing a trivially broken PRNG, with
# output from another trivially broken PRNG that is initialized with hard
# coded seed of "1".
# To illustrate the point, here's output that I shouldn't have, if key
# generation is actually random.
#
# Note that this was generated with glibc 2.20's rand() used to seed GMP's
# rand(), if your system's rand() is different from the one I use, the values
# will be different (but still very deterministic), and there are not that many
# implementations of rand() around.
not_so_secrets = [
mpz(0xb43d2488d8be2449e737dd6308168ab2c22668e57cb1a10a140ebabcc01ab988b331289d248731af85720ddbee86609da2877b56962c84c8f481e85e942a5b6e871add8296accc54880a785ef1f5d466e0632dd76b65fccff6b69d1af7a99d9e0490f300829c0c2960bdd3fe3d47d17f135e32f79e32c6bbe65f965d63185694),
mpz(0xe5f1aa1d81ea0253d5fea0ee1426238bd7a932986b01435532045c46ac73e24dd767c79bde39a290ed1060af5dd00d66076a9fdd31e7ce3ea23492dc7fca7eaeec76856dd4e2f6421bed99ab22412e04cfbd371c21f77c5f6d53893ddeacd4d54b2959e74f1daf07be3e432ede4536f3b3f04375bb75d1232eae131cd7995956),
mpz(0x7933d4258f548b240ee9d06aa3e5f6c392ed4b0f81a757eaaabd21552d4487f24d278eeeb485a5eb9186cd35cec8b73d7a41fc95b22bece9d42e7d7ff10c6153be1acad61d195b7528c728fb49864f2c5403f273218cd5f4c28c7f31f4c749aff2d6b2df6ad82e2dd255d99e5c16c2bd79b1aebe2b8c0b8b4317142b7c658be3),
mpz(0x7d5f67b48a03ee9db387deb00a05e167cb6d1e2c96c16ed1fb25444c8e50720f95550fbbf0aed7570d5620b47939d299c940045ef4c97ef606ce5bc1edead272fb6978c7d3efc155f1e77588f12b5e791b3ff37879ac4cc95f587c0c37db72cfb3140f207a5db18fc913fba06a406d64c1fc7b9324513557a282ec511fe57b97),
mpz(0xab72062a5c695e55c571e289bca125d7eb6bc5f2f81f1f26847823e7f93a1aaa337203c5f8d9adde782e5bb10f58491ca86d72554f7b183694bbbd4c51d72a2c459ae48a39c6e83ea5d9bc71292e566c3e1f4995929cf6f2c579c1b39452f8b610d43d0b842f49df9ab9f1a69adaf23abb873fed3b8e889593276a70e058b87c),
mpz(0x898910f4b612840a8f374f786de52973794692dc9e39396abe8f488cb4b168db164b34d2a223a83ea55d8ef4cbcc08ec2851f1efdfc918129bcf2594c996b5ca5e68ef452b80cdfe62fbfcb36a86261e240b66082690f12a5fca169554c59154a7efdbf220c3a9180aab8d236512d16a744c349af4c826ae0fd2b26eba151213),
mpz(0x3e890818e36a5323c548664e6045889acc0b71ee6e65abd0bd3920b9e88bdedfc8e3e201ebe780632a0ec33abf1f3b4cfab57f9fbe8af8e40230cc3a3944c5f8ed4f885d1a2ae633793bc102251b6a37343286ac1d84ffdd8ae6ec4341ea4dd8efd8727588c0d8ed5c50851c50d9509a4414fcc15a81b748a13df419b75caeb6),
mpz(0xae99da45aa24034213c609f41b02858ff03381671bf98bfde2693e92f86aecde09c3cce082cc6190b66f800fb4ae8f1db5011fb7770b7f22787616a4a5278a5396a5c3cf3f2269dd012f1aa8e594a933f10dc306394588f32de437a511961447c1f48daa8b88f04c7a296c616110a9c4a0f0f0c4319c42bb3a19ebd593a10bbe),
mpz(0x1ece477295cc5c53e98ace4887dd87a5aa1f7ccc68a470f9f267f5ff81ac0e64e023bad1407499fde34ba66b145e8b498c74b0a555d1c83bca7a30bc644580a5f5dfec4f3e913a17754ca208177818705a4dc9f711d109f369cf4ef64b3d23048b7b39c73b6737586fc396cdf68d220a40eae5ba8b381adc002e8581ff8a6057),
mpz(0x1016f2902c0ac456a78abc59112b6d29bf0b8caccf72fb9eb08336889c24696c9bd5a4b1e4c4eeb3ecce8d0222db7b69633cceb3c6d30a02c3e8ca72022c518d6b3a1b9a21580a431af4427cbf1212d63bc013e058276114e617bfa04a28af9fab6feb170f9d2ebfbff768886353816b34502050b9b4b7263e3482f4718d61f8)
]
try:
for expected in not_so_secrets:
actual = generate_diffie_not_secret()
if expected != actual:
raise RuntimeError("expected != actual")
print("Kids, don't use rand() for key generation ever, the output is"
"very predictable,\nespecially with a hard coded seed.")
except RuntimeError:
# Note that this simple test passing isn't a guarantee that this is secure.
print("Huh? The keys are different!")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment