7
$\begingroup$

We have a system that processes data. Each entity has an ID that is generated using uuid4() in Python. Later, that ID is used as a partition key for AWS Kinesis. Kinesis docs say they MD5 this partition key and use it to distribute data across the provisioned shards.

Until recently this was working well, but recently a high load system with 30 million records and eight shards started putting nearly everything on shard four. That could only happen if the MD5(instance.id) ended up between $4\cdot 2^{125}$ and $5\cdot 2^{125}$ for millions of independently generated UUIDs.

Sure enough, I have a huge list of uuids in that bucket after applying md5. These values are certainly uuid4 and they are all unique. If I split them into 16 buckets I get a fairly even distribution across two of those buckets.

I thought maybe the system had low entropy when the UUIDswere generated, but even if our IDs themselves were sequential or otherwise nonuniform I’d expect the MD5 hashing to redistribute them.

I’m left thinking there must be a special relationship between UUID and MD5 that is altering the distribution. Is that it? What can explain this distribution?

Here are 100 of the UUID4 values, in hex:

8799fd0d38ba4e02b6bf43f5de6799d4    9f5159d9ebae461ebd3733b3aeff87f6
c92d4ecff58a40be9e48be8ebaa456f2    d63ca2bcc9184394ac8e836a0e431cf9
827710f5bcd74da2a05588e34180a75f    5d645c21471b4be5a50192112e13d244
edba5c23fa7142c7a70e4e41a36cab86    e388ac49ee664b04995b09439c4cf000
a004a6b0c59d4599bd8bc7f115a71c1c    c98d931a698d4ee396d7403ee3b998df
9d22d0b7741b41ff8e55a2d2171cd4b0    b1a7d86d80b04c608442e7cea1e4f8ab
d0f344348b9b48eaba9d8f1d7b41a8d8    926694f6fc874ba48d74c501ddcdde26
ee73f55448604e3c8106b4c0cef3788f    cf5fd7fee614456b9a441cec52fa210c
3e35d6dece554ca699c09fece6297db6    0c14c595e6c047eca5829fce48265f1e
3735e410cda748a7b908d38096bcf706    585e0d5f77534247934f946422fc10fe
2e41e81a929b4e8b894ac3fb092bc33f    1b255bf030474fe8af131635e6634647
315f57d0f1b64b1698e2290c9853f6bb    b8066497c85547fe8988107be80950fa
17a4a71b47344912835fe6dd3913ae2b    dcda6f1dc5e54e3e819f98e3d6ba958b
b7c59cafe3f6421ba1d3f5c1fa4d1d93    7723a3d355a04f8b8a873e6aff11b274
b9c8a1babb8b49ec889d8c0795dd5fd4    adfe93e7289c494287bc535c088f04a3
28c212f046e647618c93e00fda239ad1    981523f48f7d4ae9aca2a4b91558aeef
873abfe9f178450a94ecf369c35e63b2    04d41e0ee4604b41a4cd7a03af20ff7f
71fe56d24fc74b95866b9e10e219a6fe    09e463d986034284b055c185fc4c460d
bcafb85b0a2d43a2929047c7ffcd210d    2dba964591fd4404ac63e071002c2586
c4ab3e2320aa4de6b7ab1dd36a230184    ef6b88c32e854cd5b59df3e018cce1f6
2736bf1a626741f489e0e3114efd3fbc    2efeb1dfa389425fabd52bf9edbee5fa
b3092609d5b34da2ae5773f6ae3e28b5    576bd3c87f1b4da4bc905bcb0322cf3b
5f488e6d754f40caa4cc11bebdef169d    ec763ae7f72f42368c34cdad2d936169
658d2ea5db85432f8bbbde7b74a9d505    9d192e219d1e4114aae3bf960ae6ec5f
ae4bed0cc9754b4bb337cbc23a550bd6    a35a78d7cb474291b12ed10c3f97bcd0
10f369a3d5534c3ab7ab6275f47f8541    6737e813e8044a09a98b0787de81aa16
c82cee35e5c244228a86cdece99a36f2    501ef498116846f49819e9f7b4d9062b
adf5f9e04edc4c769c56f8926972594e    16c4d96b5b6d4aed9c4d5802199dbf42
f64e7c6d65a247adae3c743f142d54d8    21ad704178114a27a9c509a9793d9ed9
9a394ad6440b449e85c77ffae962e2ba    b902eaae56134a7a84a02ef53f7f2b4e
20215f6520b149868791327329776d42    91afc6fe15ea4ee8b1eb8c67fc6a901e
d4b99047782f42fbb3496f8a083f8841    6a7a2e146382498596e442b93f8b548f
484cf5b6c6e74a50884651d8bd30dd25    7931d06f18474803b81206601093280c
1f8939ec64064ce1a1c0ed1d1656306f    10e40847dabc4384bad75159aaf88376
51fc78e3f2d844de8b305aa5db643d32    bfcbb5192b614747b5b3fd09a4bc6369
7350ea1e4a85475ab9a2324fa9dda195    dbb20005d9644c199c12faa038e3edff
3b0a42fb4bbc49d2a6ef74bfd6da6d5b    1066143d0b8f4d19a88e1c27ca08af7f
3c52547d67404069be61054be3bd4197    a78ecaf1d7cb4f3bbdab3fb34993f90d
ab20ce5e2d8e4baa9cd89ce3a6acb699    3f1791072194448c9733e1b89c104a3c
a7c5fd52710642a2abf07c42117638ba    ee49ca425b11471a88d1c1438dca0df3
7d85bead1c274a439c25fbf0355cf014    e9a6cb3adfca455285cc991723c01c54
eda705703e3d42f6b6750132c00d6bd5    8101aec657a34abb811d45cb1df89913
856521de33474cd08961ba108712c12e    c4d51f2350254003afac31171c388cb4
63d6f31ce73249c89b6b5aa9e5b623d8    9841a82199574fe7a205aa5982ba14d8
84ad8c14df7d4909acf842befb36b9bb    3efa41a0e8aa4da19fa9fb7fb749cc2b
e96efdee94dc41bea1db7ad87c9bebb6    3c324772db9e4741a16727eba8c02e5d
97f53611475e47a3b294163e1e1b7f26    838cd9e7f88648b9af4fe000999d6451
bb1cbcba73444a34a3fadfa51ed807fa    fce44469b3b841f3abe53b771ec21b5d
a70413ef89314f8c9aaad620e3d529bb    c6f0a9288f7d49febbc28053113d0881
2d3e0e488a104232b5584fdd6a904964    ece6b3c3e63740a38d0751ccb6367117

A simple way to identify this problem is to look at the top three bits in the md5sum of those uuids and note that they're all 0b100. Something like

#!/usr/bin/env python

import fileinput, hashlib, uuid

for line in fileinput.input():
    hex_ = hashlib.md5(line.strip().encode()).hexdigest()
    bin_ = bin(int(hex_, 16))
    print(bin_[:5])
$\endgroup$
  • 3
    $\begingroup$ Where are the UUID's generated? If they are generated on the client side, a malicous party could easily generate UUID's whose hashes are within $4 \cdot 2^{125}$ and $5 \cdot 2^{125}$. He actually needs just 8 attempts to find such a UUID on average, even when using random UUID's. $\endgroup$ – VincBreaker Mar 5 '19 at 9:27
  • 1
    $\begingroup$ I imagine the issue stems from a mistake in the UUID generation process. There is nothing special about MD5 that would result in a visibly biased output. Even MD5 is not that broken. $\endgroup$ – forest Mar 5 '19 at 9:35
  • $\begingroup$ @VincBreaker the UUIDs are generated on the host, not by any client code. $\endgroup$ – kojiro Mar 5 '19 at 15:29
  • $\begingroup$ @forest I mean, that seems like an inescapable conclusion, but I don't see how. We generate the UUIDs using python's standard library uuid.uuid4. We don't use md5 directly anywhere in our code, and without it I can't think of a way to even reproduce this behavior on purpose, much less by accident. $\endgroup$ – kojiro Mar 5 '19 at 15:35
3
$\begingroup$

We are told that the uuids are generated by a process that (I'm confident) does not even compute the MD5 of what it outputs, and that observed uuids have a highly biased top 3 bits in their MD5, making them land in a certain bucket.

Given that for input defined independently of MD5's 128-bit initialization value (even maliciously), MD5's output is as well equidistributed as a random function, the inescapable conclusion is that the observed uuids are not a uniform sample of the generated uuids. One plausible hypothesis is that observed uuids are (or tend to be) observed because they landed in that certain bucket.

This is even stated in the question:

I have a huge list of uuids in that bucket after applying md5

| improve this answer | |
$\endgroup$

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.