towersfreak2006's blog

Python Sets/Dictionaries and Hacking?
By towersfreak2006, history, 6 weeks ago, In English

Hi there,

Someone much more knowledgeable than me warned about using sets and dictionaries in Python as they can be hacked. I somewhat overlooked this advice as I assumed no one would hack a random pleb, but then I saw a warning in the editorial of 1915E - Romantic Glasses at https://codeforces.me/blog/entry/123952 state "Be careful about using hash tables, as they can be hacked."

One of the responses in that thread linked to https://codeforces.me/blog/entry/62393 which provided some insights and workarounds for C++, but is there such a resource for Python? Is there a general rule of thumb for using such data structures and finding the appropriate problem-specific alternative (such as a list of tuples, which will often do)?

Thanks in advance!

  • Vote: I like it
  • +1
  • Vote: I do not like it

»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

generate a random seed at runtime and xor it with each elem of set / key of dict

For example, instead of set.add(x) u should do set.add(x^seed) where seed is a random integer that's generated at runtime

and when u wanna check membership, do x^seed in set instead of x in set

this works cuz of the property $$$a \oplus a=0$$$

An example code is given for the problem "given a list of n integers and q queries, reply YES/NO depending on whether the queried elem is present in the list or not"

from random import randint
seed=randint(0,2**32)

s=set()
n=int(input())
l=[int(x) for x in input().split()]
for x in l:s.add(x^seed)
q=int(input())
for _ in range(q):
    x=int(input())
    print("YES" if x^seed in s else "NO")

In order to hack this soln by hash collision, the hacker needs the value of seed. So, the probability of a successful hack is significantly low :)

Another method u can use is to just convert the integers into strings cuz python strings have randomized hash values across different runs... (in other words, python handles everything 4u if u use str instead of int)

but this runs slower than the xor method in some problems so try to use xor whenever possible...

the equivalent code in this method is

from random import randint
seed=randint(0,2**32)

s=set()
n=int(input())
l=[int(x) for x in input().split()]
for x in l:s.add(str(x))
q=int(input())
for _ in range(q):
    x=int(input())
    print("YES" if str(x) in s else "NO")

you can use a similar method for dict (d[key^seed]=v to assign and d[key^seed]/ d.get(key^seed,default) to read). u can also use the str method

→ Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Makes sense and very nice -- thanks!

    → Reply
  • »
    »
    6 weeks ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    I thought this approach was insufficient because it doesn't mix very well but in fact Python already has a built-in method for preventing collisions. It goes like this:

    • p = 2^61 - 1
    • hash(x) for an integer is just x mod p
    • Then hashes are reduced mod 2^k according to the size of the table. But then the funny part is that they use probing in the case of collisions and the probing depends on the entire hash.

    From CPython:

    The other half of the strategy is to get the other bits of the hash code into play. This is done by initializing a (unsigned) vrbl "perturb" to the full hash code, and changing the recurrence to:

    perturb >>= PERTURB_SHIFT;
j = (5*j) + 1 + perturb;
use j % 2**i as the next table index;

    Now the probe sequence depends (eventually) on every bit in the hash code, and the pseudo-scrambling property of recurring on 5*j+1 is more valuable, because it quickly magnifies small differences in the bits that didn't affect the initial index.

    So this tries to makes it so that as long as your ints are <= 10^18, you are completely safe. It's still vulnerable if you particularly insert every key in the probing sequence of a key you want to slow down and then query the slow key a bunch of times, but xor probably actually introduces just enough mangling to prevent that. I will caution that in more low-level approaches (such as C++ just doing chaining or normal linear probing I think) that this is weak.

    → Reply
»
6 weeks ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

just use c++ man, in the long run the switch is worth it

→ Reply