<html>
<head>
<meta content="text/html; charset=UTF-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#330033">
On 1/13/2012 5:35 PM, Victor Stinner wrote:
<blockquote
cite="mid:CAMpsgwYFfTvpkfiLCDLoeBZrWJPOdpGN=deEhrOoLzzHf4ubpw@mail.gmail.com"
type="cite">
<blockquote type="cite">
<pre wrap="">- Glenn Linderman proposes to fix the vulnerability by adding a new
"safe" dict type (only accepting string keys). His proof-of-concept
(SafeDict.py) uses a secret of 64 random bits and uses it to compute
the hash of a key.
</pre>
</blockquote>
<pre wrap="">
We could mix Marc's collision counter with SafeDict idea (being able
to use a different secret for each dict): use hash(key, secret)
(simple example: hash(secret+key)) instead of hash(key) in dict (and
set), and change the secret if we have more than N collisions. But it
would slow down all dict lookup (dict creation, get, set, del, ...).
And getting new random data can also be slow.
SafeDict and hash(secret+key) lose the benefit of the cached hash
result. Because the hash result depends on a argument, we cannot cache
the result anymore, and we have to recompute the hash for each lookup
(even if you lookup the same key twice ore more).
Victor
</pre>
</blockquote>
<br>
So integrating SafeDict into dict so it could be automatically
converted would mean changing the data structures underneath dict.
Given that, a technique for hash caching could be created, that
isn't quite as good as the one in place, but may be less expensive
than not caching the hashes. It would also take more space, a
second dict, internally, as well as the secret.<br>
<br>
So once the collision counter reaches some threshold (since there
would be a functional fallback, it could be much lower than 1000),
the secret is obtained, and the keys are rehashed using
hash(secret+key). Now when lookups occur, the object id of the key
and the hash of the key are used as the index and hash(secret+key)
is stored as a cached value. This would only benefit lookups by the
same object, other objects with the same key value would be
recalculated (at least the first time). Some limit on the number of
cached values would probably be appropriate. This would add
complexity, of course, in trying to save time.<br>
<br>
An alternate solution would be to convert a dict to a tree once the
number of collisions produces poor performance. Converting to a
tree would result in O(log N) instead of O(1) lookup performance,
but that is better than the degenerate case of O(N) which is
produced by the excessive number of collisions resulting from an
attack. This would require new tree code to be included in the
core, of course, probably a red-black tree, which stays balanced.<br>
<br>
In either of these cases, the conversion is expensive, because a
collision threshold must first be reached to determine the need for
conversion, so the hash could already contain lots of data. If it
were too expensive, the attack could still be effective.<br>
<br>
Another solution would be to change the collision code, so that
colliding keys don't produce O(N) behavior, but some other
behavior. Each colliding entry could convert that entry to a tree
of entries, perhaps. This would require no conversion of "bad
dicts", and an attack could at worst convert O(1) performance to
O(log N).<br>
<br>
Clearly these ideas are more complex than adding randomization, but
adding randomization doesn't seem to be produce immunity from
attack, when data about the randomness is leaked.<br>
</body>
</html>