Attacks on dictionaries when the keys are integers

Python Help
1

I was recently surprised to hear about the use of anti-hash-table in codeforces:

https://codeforces.com/blog/entry/101817

For some context, “hacking” in codeforces is a specific part of the competition. The idea is to “hack” other participants solutions by providing valid input data that would cause their code to fail on a given problem. In this particular instance, “hackers” would provide some input data that maximize the amount of hash collisions for a specific implementation of hash tables, causing the participant’s code to run too slowly for the problem constrains, eventually failing with a time limit exceeded status.

It turns out that Python in particular is vulnerable to this specific “hack” when the keys of a dictionary are integers. The surprising part is that this attack does not rely on the integers having the same hash (typically, the size of the input data is limited in a way such that it does not exceed the value ofsys.hash_info.modulus). Instead, it relies on abusing the sequence of cells that the lookup algorithm will use to check whether a given item is already part of the hash table or not.

This can be easily reproduced with the following code:


def corrupt_keys(n):
    # Find the power of two lower than n
    bit_length = n.bit_length() - 1
    size = 1 << bit_length

    # Fill the dictionary with at least 33% and at most 66% of n
    fill = int(size * 0.65)

    # Insert a key in slot 1
    yield size + 1

    # Insert a key in each subsequent index
    x = 1
    mask = size - 1
    for _ in range(fill):
        x = (x * 5 + 1) & mask
        yield x

    # Each 1 will have to go through `fill + 1` steps to find its correct spot
    # In total, this produces n²/2 lookup on average
    for _ in range(n - fill - 1):
        yield 1


def test():
    n = 100000
    keys = list(corrupt_keys(n))
    assert len(keys) == n
    # Takes 5 seconds
    {k: 1 for k in keys}

Note how inserting 100_000 integers in a dictionary takes about 5 seconds, even though all those keys are in the [1, 65537]range.

For reference, there are plenty of useful information in the comment that explains the logic behind the use of the x * 5 + 1 recurrence in the cpython source code:

What surprised me is that I haven’t been able to find any discussion about this “attack”, and whether something should be done about it (although I most probably missed some). Maybe an actual denial-of-service attack based on this is not realistic, but I would have at least expected some comments mentioning it (especially since a protection against dos attacks already exists for bytes and strings).

Can anyone provide me with more resources regarding this issue? Thank you :slight_smile:

2

(It’s noteworthy that the specific Wrapper implementation shown off there is a broken class since int(0) == Wrapper(int(0)) but hash(int(0)) != Wrapper(int(0)))

3

There’s a lot of related info in the comments on this recently closed (“not planned”) issue report:

There’s been no discussion over the years because nobody cares much :wink:. It’s obvious how to construct ints that create long collision chains for dicts or for sets. It’s exceedingly unlikely to happen with non-contrived inputs.

As the code comments you found already explained, CPython is very keen to exploit that the hash codes for “small ints” are very regular: in common cases, there are no collisions at all when indexing a dict by a contiguous range of ints. Guaranteed.

“Speed matters” here. Any number of Web-ish gimmicks allow users to feed strings to Python apps that use the strings as dict keys, so “DOS attacks” based on contriving collections of specific bad-behaving strings were a worry.

“Fixing that” isn’t just a matter of using a “crypto strength” hash function. That doesn’t help at all so long as the hash function used is the same across runs. It also requires picking a hash function “at random” when the program starts. That’s what Python’s “hash randomization” is about for hashing strings.

Nobody ever saw a good reason to endure that extra complication and expense for “non string-like” (strings, bytes, datetime) hashable types.

Horrid collisions are possible in any hash-based scheme. If an app can’t endure that, it’s better off not using dicts or sets at all. There are other schemes with guaranteed good worst-case behavior. But their best and “expected” cases are slower (e.g., balanced binary search trees of various flavors).

4

Hello,

just one small observation (maybe its just me not understanding the intent/problem here). The following:

implies a range, and not just an upper bound. Perhaps the following is what you meant:

fill = int(size * 0.33), int(size * 0.65)

Then this:

becomes this (?):

for _ in range(fill[0], fill[1]+1):

???

5

No, they mean “fill it with a number of entries in this range range”, and then pick a specific number from that range for the script (i.e. ~65%, which is between 33% and 66%)

6

Ya, contriving “catastrophic” cases is delicate. Replace “0.65” with “0.67” and the program takes just a few milliiseconds.

As is, there are no collisions at all while building the table until hitting the long tail of 1’s in the keys. Then each attempt to add 1 does a linear search over the entire dict (due to collisions).

That’s a key to understanding this: it’s trying to build a longest-possible collision chain starting with the specific key 1. It doesn’t start with yield 1 because then adding 1 later would succeed on the first probe. Instead it yields size + 1 at the start, which goes into the dict slot at index 1 because only the last few bits matter at the start. And size is just large enough so that the last retained bits remain just 0b1 as the dict grows larger as it gets fulller.

That’s why changing to .67 eliminates the sloth: then the dict grows again, to a size where all the bits in size + 1 matter, and the slot at dict index 1 remains empty (so trying to insert 1 only needs one probe).

7

Ok, got it.

If that is the case, I wonder if they would like to move that as a user selectable value (argument to the function so that it can vary per function call versus fixed inside the function - but if it stays the same for all function calls, then disregard).

def corrupt_keys(n, percent_range): # vary per function call if so desired
8

I doubt it. The code isn’t really useful, it’s just contriving a spectacularly bad case of long collision chains. In general, dicts dynamically resize so that the number of occupied slots is 1/3 to 2/3rd the dict’s (current) maximum capacity. They’re really indirectly controlling for the final dict capacity, so that their mask value is correct for the final size. Given that, the longest collision chain is obtained by making the dict as large as it can get without growing yet again, so they want to hug the 2/3 end.

I’ll include a more fleshed-out version of that code that, among other things, makes it clear that building the dict remains blazing fast regardless - it’s searching for a specific value that bogs down horribly,

Code 
# https://discuss.python.org/t/attacks-on-dictionaries-when-the-keys-are-integers/102812
def corrupt_keys(n, special):
    # Find the power of two lower than n
    bit_length = n.bit_length() - 1
    size = 1 << bit_length
    mask = size - 1

    # Fill the dictionary with at least 33% and at most 66% of n
    fill = int(size * 0.65)
    print("n", n, "size", size, "fill", fill, "mask", hex(mask))
    # Insert a key in slot `special`
    if special >= mask:
        raise ValueError(f"{mask=:x} not wide enough to hide {special=:_}")
    yield size + special

    # Insert a key in each subsequent index
    x = special
    for _ in range(fill - 1):
        x = (x * 5 + 1) & mask
        yield x

def ftime(x):
    if x >= 1:
        tag = "s"
    elif x >= 1e-3:
        tag = "ms"
        x *= 1e3
    elif x >= 1e-6:
        tag = "us"
        x *= 1e6
    else:
        tag = "ns"
        x *= 1e9
    return f"{x:.3f}{tag}"

def test(n, special=1):
    from time import perf_counter as now
    keys = list(corrupt_keys(n, special))
    start = now()
    d = dict.fromkeys(keys, None)
    finish = now()
    print("time to build dict",
          ftime(finish - start))
    if special in d:
        print("WARNING! special value", special, "already in dict")
    todo = len(d)
    start = now()
    for _ in range(todo):
        ignore = special in d
    finish = now()
    print("time to look for", special, todo, "times",
          ftime(finish - start))

test(100000)
9

Did you mean != hash(Wrapper(int(0)))?

Anyway, you’re supposed to use Wrapper instances exclusively, not mix them with regular ints.

10

Have a look at the issue that led to Python’s randomization of string hashes:

From the intro:

Web application servers or platforms commonly parse attacker-controlled POST form data into
hash tables automatically, so that they can be accessed by application developers.

If the language does not provide a randomized hash function or the application server does
not recognize attacks using multi-collisions, an attacker can degenerate the hash table by
sending lots of colliding keys.

So that’s a common case, where a hash table with string keys is built by the server/platform code, before the application developer’s code gets it. So the application developer’s code can’t defend against attacks because it’s too late. It needs to be defended against earlier, when the hash table gets built. So Python decided to randomize string hashes.

That’s not the case with ints. At least I’m not aware of a common scenario where people use some framework to parse user data and build a hash table with int keys from it. For example at Codeforces, you parse the input yourself and build the hash table yourself. So you can defend against such attacks there.

11

A quote I found:

the method would need to be implemented for all hashable Python types

It was already discussed, and it was said that only hash(str) need to be modified.

Sounds like that “already discussed” is what you’re looking for, but this is in the middle of a thread with 300-400 posts, so I won’t search for it :slight_smile:

12

@tim.one

Thanks for the thorough explanation, it makes a lot of sense.

As the code comments you found already explained, CPython is very keen to exploit that the hash codes for “small ints” are very regular: in common cases, there are no collisions at all when indexing a dict by a contiguous range of ints. Guaranteed.

Yes hashing small integers as themselves is very useful, I understand that changing that is not realistic. I suppose that in order to fix the specific issue I described, one could change the function that derives the next index to look up instead. For instance, initializing perturb to hash ^ some_random_value instead of hash would probably make this attack much harder to pull off (maybe not impossible though?).

I understand however that the gain is quite specific and probably doesn’t justify changing a code that worked just fine for a decade without anyone complaining about it :slight_smile:

@MegaIng @onePythonUser

just one small observation (maybe its just me not understanding the intent/problem here). The following: […] implies a range, and not just an upper bound.

Sorry that my comment about the 33% ~ 66% wasn’t clear. Here’s the detailed explanation.

Dictionaries double in size once they reach a certain capacity (2/3 of the current size if I get this right). Since those sizes are powers of 2, we need to find the power of 2 lower than n and use it as our target size for the dictionary. That means we have the following inequalities: size <= n < 2 * size

We don’t want to insert more than size * 2/3 items into our dictionary (otherwise, the dict size will double again and our scheme won’t work anymore), so inserting only fill = int(size * 0.65) items is just a way to stop before this critical point.

Now, plugging this into our inequalities gives: 0.65 / 2 * n < fill <= 0.65 * n. Which lead me to write that depending on where n is between two powers of 2, we:

fill the dictionary with at least 33% and at most 66% of n

(This should have been 32.5% and 65% to be more precise)

That means we will then do n - fill slow lookup operation, with this number being also between 33% and 66% (or 35% and 67.5% to be precise).

Note that the maximum number of cell lookup can be computed by computing the derivative of fill + (n - fill) * fill which gives n + 1 - 2 fill = 0 which gives fill = (n + 1) / 2. That means that the worse case occurs when fill is about n / 2, yielding about n² / 2 cell lookups. This corresponds to n being 1.3 times a power of 2. However, this doesn’t change much compare to the cases where n is a bit more or a bit less than a power of 2, since they yield about 2 n² / 9 cell lookups.

With those results we can conclude that the attack will be efficient (i.e. yielding at least 0.22 n² cell lookups) no matter where n is between two powers of 2.

13

@Stefan2

That’s not the case with ints. At least I’m not aware of a common scenario where people use some framework to parse user data and build a hash table with int keys from it. For example at Codeforces, you parse the input yourself and build the hash table yourself. So you can defend against such attacks there.

Sure, I understand that the attack we’re talking about has a much smaller scale than the one addressed in bpo-13703. And as you said defending against it is very doable, either using the int subclass approach mentioned in the codeforces post, or even simpler, converting the integers to hexstrings or bytes before using them as keys.

Sounds like that “already discussed” is what you’re looking for […]

Oh thank you. I found plenty of interesting comments in the corresponding bpo. Alternative solutions were discussed, such as the use of universal hash functions, as well as a collision counting approach.

14

I suppose it depends a lot on what some_random_value means, exactly. I don’t see that anything would really improve if we picked some specific random value once, and used it forever after.

Picking a new “really-ish” random value each time the interpreter starts is what “hash randomization” already does, and I suppose that same value could be used inside the dict and set implementations. Or, perhaps, better, change nothing about them, but arrange for the builtin hash() function to xor that seed with every hash value all objects compute.

Bur it’s not an itch I have, and I’m not inclined to change anything - real work, more complication, with no appreciable practical gain I can see.

Anyone who wants to pursue it should put thought into what the “threat model” is they’re addressing. Tricks in this topic are about hardening collision resolution, but no such thing can help at all in cases where many distinct inputs are contrived that have the very same hash value. They’ll all use the very same probe sequence regardless of how convoluted the definition of the probe sequence is made. It’s trivial to do this for ints, although it requires creating unbounded ints.

More like a quarter century now! The base idea of generating a pseudo-random probe sequence, that eventually covers all possible slots, and that folds in higher-order hash bits as the probe sequence advances, was first introduced in May of 2001.

At the time, the scheme required more knowledge to understand, based on division by x in the finite field GF(2**k)[x]/p where p is a primitive polynomial in x of degree k. picked in advance for each k.

Reports of “real life very bad cases” ended then. It was very effective. But also easy to contrive bad collision chains, although the underlying theory was so “advanced” that I guess we obtained some “security through obscurity” to most would-be casual hackers’ eyes.

The code was surprisingly simple. The current code is a little simpler and faster, but much easier for “just folks” to understand. That counts too. But its primary attraction for me was that it folds in 5 fresh higher-order bits per probe step, where the earlier “division by x” folded in just 1 fresh bit per step.

Gloss: many hash table implementations get all the bits of the hash code in play at the very start, most typically by finding the remainder of the hash code modulo a fixed prime, or more rarely by computing a CRC. checksum. It’s easier to get high-quality results that way, but division is much slower than just making off the last k bits, and in typical “found it!” cases the very first probe succeeds despite the dirt-cheap initial index computation.

15

I was very intrigued by this, so I did a bit of source code archaeology and I had to go back to python 2.1 to find the implementation, with the corresponding commit dating back to January 1997:

So basically you picked each primitive polynomial p so that x is a generator of the corresponding group. This way, getting the next increment is a simple matter of multiplying by x, which can be conveniently implemented as a simple bit shift by 1, and taking the result mod p, implemented as single conditional xor. That’s so cool.

I couldn’t find this part though. As far as I can tell, only 3 more fresh bits were used but only once, when choosing the first value for incr:

Maybe the “1 fresh bit per step” thing was added later and I missed it.

Yes I was thinking of some_random_value to be a member of _Py_HashSecret_t initialized when the interpreter starts like the existing hash randomization does.

But would the nice properties of having integers hashed as themselves remain? At least the hashes to all the values in a [0, 2^k-1] range still map to the same range, so we would still have the “better-than-random behavior” for continuous ranges of ints.

Yes although it’s pretty common to impose limits on user-provided values, and sys.hash_info.modulus is especially large. But I get your point, there is no silver bullet here.

And I can see how “my solution got hacked on codeforces” is not a very convincing threat model :upside_down_face:

16

Good sleuthing! That was the start of the “exploit finite fields” approach, but it was a few years before the final crucial piece was introduced: divide by x instead of multiplying. Here’s that commit:

Very cool, yes :smile:.

See the later commit I already linked to at the start. Multiplying “shifts left” and so loses high-order bits. Dividing is almost as easy (in very rare cases it can result in 0, which needs to be guarded against), but “shifts right” so brings high-order bits into play as the probe sequence advances.

Either way gives a fast way to visit all table slots in a pseudo-random order depending on the hash code, and without expensive HW division (CPython’s original dict implementation used the common “mod by a prime” approach). By switching to division instead of multiplication, many plausible “bad cases” were sped by factors of thousands.

However, like the current approach, division (unlike multiplication) can see a probe sequence visit some table slot(s) more than once. It appears to be unavoidable in any scheme that doesn’t account for all the hash code bits from the start, feeding them in as it goes along. It’s a minor inelegance, but seemingly has no practical bad consequences.

Yup, that’s the way to go if someone wants to pursue it.

More generally, regardless of range, and regardless of k (> 0), if the last k bits of a collection of ints are distinct, xor’ing with a constant leaves them distinct. That’s the important part (no collisions - “better than random”) to me.

But, in fact, any change to any visible behavior, documented or not, does leave some people unhappy :slightly_frowning_face:.

17

I should note that there’s probably another strong reason now: the “finite field” approaches both needed a conditional branch on each iteration (multiply is “shift- left + maybe-xor”; division is “maybe-xor + shift-right”, plus an additional but highly predictable “if zero” branch). Since the bits follow a pseudo-random ordering, the branches are unpredictable.

Over time, architectures seem to have evolved to make branch misprediction ever more costly. The current perturb >>= 5; j = (5*j + 1 + perturb) & mask scheme is branch-free, and with some exploitable instruction-level parallelism.

So, lovely as they were, there’s no material regret over moving away from the finite field approaches.

18

Gloss: some C compilers, with some options, can transform some simple code with branches to branch-free code using modern “conditional move” HW instructions. However, there’s no portable way to force that under standard C. There are more long-winded (& expensive) portable ways to eliminate branches, though (e.g., see here).

In context, the C code

if (incr > mask)
    incr ^= poly;

could be rewritten as the slitghtly tricky

incr = incr > mask ? incr ^ poly : incr;

or

incr ^= incr > mask ? poly : 0;

and some compilers with some options will recognize that it’s safe (“short-circuiting” is never needed in this code) to evaluate both outcomes and then pick the right one after with a conditional move instruction.

A portable way to force branch-free code, at least with int expessions, is to use arithmetic to compute “the right one”: Change:

result = boolean_condition ? iftrue : iffalse:

to

cond = boolean_condition; /* int 1 if true, 0 if false */
result = iftrue * cond + iffalse * (1 - cond);

Generally too obscure for my tastes, but it’s become much more practical as HW int multiply has become much faster over the years, and HW added the ability to work on multiple multiplies simultaneously.

Back when the 5*j + 1 recurrence was first introduced, int multiply was still so expensive that it generally paid to write it as (j << 2) + j + 1 instead.

Everything Matters™ :wink:.

19

Thanks a lot for taking the time to go back to the changes that went through this lookup sequence implementation, it’s fascinating. I wanted to take the time to do a bit more research, but I can’t resist addressing this point:

I pasted the different implementations into Compiler Explorer to see how the corresponding assembly code on x86-64 looks like (with -O1 and -O2 optimizations), and the result is quite interesting:

mulx:
        lea     eax, [rdi+rdi]
        xor     edx, eax
        cmp     eax, esi
        cmovg   eax, edx
        ret
divx:
        mov     edx, edi
        and     edx, 1
        neg     edx
        and     edx, esi
        xor     edx, edi
        mov     eax, edx
        sar     eax
        ret
lcg:
        lea     eax, [rsi+rsi*4]
        sar     edi, 5
        lea     eax, [rax+1+rdi]
        and     eax, edx
        ret

The multiplication by x uses the “conditional move” instruction you mentioned, but the division by x does something more clever. It basically transforms this:

	if (incr & 1)
		incr ^= poly;
	incr >>= 1;

Into this branchless code:

    incr ^= -(incr & 1) & poly
    incr >>= 1

I don’t know how python was compiled when the division approach was still around, but maybe the compiler used the same trick and those versions of python didn’t even suffer from those conditional branches? I think it makes this clever division approach even slicker :slight_smile:

20

Also, the 5*x+1 assembly code shows something interesting. You mentioned:

It turns out that those operations are so simple that the CPU can perform them with instructions usually used for address manipulation:

        lea     eax, [rsi+rsi*4]
        sar     edi, 5
        lea     eax, [rax+1+rdi]

I imagine that this allows for nice instruction-level parallelism as you mentioned.