[kwlug-disc] Fwd: Postgresql hash index as a mitigation of timing attack

[Mikalai Birukou]

The following is an in-depth analysis of the topic by Tim McLean 
(https://www.chosenplaintext.ca/). Posting his thoughts with the permission.

***

Hmmmmm, this is an interesting question!
It seems like it would depend significantly on how postgres implements 
the index. I think it would definitely make the attack harder.

It looks like 'hash' indexes in postgres are implemented using linear 
hashing: 
https://github.com/postgres/postgres/tree/master/src/backend/access/hash
Roughly, a hash function /H/ is applied to a key /k/ (in our case, k = 
the session id), and the last /b/ bits of /H/(/k/) are used to determine 
the memory address of one of 2^/b/ buckets.
Inside the bucket, a binary search is used to find the entry matching 
/H/(/k/).
(There's also some fancy stuff going on to handle adding more buckets as 
the index grows in size, so /b/ will change over time, but that's not 
too relevant here)

So it seems like timing attacks could discover a fair bit of information 
about /H/(/k/). Cache timing attacks could figure out which bucket was 
accessed, and maybe where in the bucket the binary search ended up at. 
Also, the binary search might involve comparisons that are not timing safe.

Now, learning /H/(/k/) might not be useful to the attacker, since hash 
functions can be irreversible. So, what is /H/?

/H/ seems to be a custom hash function design: 
https://github.com/postgres/postgres/blob/73b7f48f78d27b1baf1a6541cbaae0fe6bd6186d/src/backend/access/hash/hashfunc.c#L332
Since it's not a cryptographic hash, the normal security guarantees do 
not apply. Learning /H/(/k/) might reveal useful info about /k/! So that 
may be a problem.

(Aside: this all makes me wonder if postgres is vulnerable to a denial 
of service attack where an attacker purposely supplies values that all 
hash to the same bucket index, forcing worst-case performance?)

Another thought that I have: if /H/ is weak enough, then once we have 
learned /H/(/k/), we may be able to generate preimages (other values 
that have the same hash) that look like session ids.
So we can generate /k/_0, /k/_1, ..., /k/_F such that /H/(/k/_0) = 
/H/(/k/_1) = ... = /H/(/k/_F) = /H/(/k/). In other words, we find a 
bunch of session id strings that hash to the right value.
Maybe we can make it so that /k/_0 starts with '0', /k/_1 starts with 
'1', ..., /k/_F starts with 'F'.
My understanding is that, if we try a session id that has the right hash 
value, postgres will access the right bucket, find the entry with the 
real session id, and then do a string comparison between the real 
session id with the session id that was provided. This comparison 
probably isn't timing safe!

I don't know if this attack would work though, since it really depends 
on how strong /H/ is.

***

How about a different solution? Let's assume the session ids are 
generated using a cryptographically secure random number generator and 
have 128 bits of entropy (e.g. 16 bytes encoded as 32 hex chars).

If we hash the session id with a cryptographic hash (say, SHA-256), it 
would be impossible to figure out the session id from looking at the 
hash (it would take 2^127 guesses on average, and the world doesn't have 
enough electricity to do this many calculations -- no need for a 
password hash here).

So what if, instead of storing the session id in the database, we store 
`sha256(session_id)` instead? When we get a session id from a client, we 
hash the session id and do a database query with the hash.

The database might do a string comparison that leaks information about 
the hash -- that's fine. Even if the attacker gets the full hash, they 
still can't figure out the session id. The only code at risk for timing 
attacks now is the piece that receives the session id from the client 
and hashes it with SHA-256. It's unusual to see timing leaks in SHA-256 
though, so that's unlikely to be a problem.

The important piece here is that the server must do the hashing. If we 
do the session id hashing on the client side, then we're back to the 
original problem again :)

Tim

On Wed, Jun 6, 2018 at 3:00 PM, Mikalai Birukou <mb at 3nsoft.com 
<mailto:mb at 3nsoft.com>> wrote:

    Hi Tim,

    Following timing attacks thoughts and a recent KWLUG talk about
    Postgresql db, the following idea came to mind. What do you think?

    Cheers.

    -------- Forwarded Message --------

    Context (as a follow up to Hadi's presentation on the 4-th of June):

    Sometimes we store secret session ids in db, and we use these for
    authentication. Usually there is query that get respective record,
    searching a table for a given by user session id.
    Usual `WHERE` clause uses the most fast comparison, which run timing is
    dependent on input values. This can be used as a base for an attack with
    session id guessing via timing.

    Question:

    Hadi, and others, will hash index work as a quick fix here?

    1) Should ensure that a query, abusable by an attack, always uses index.

    2) Index on a secret (e.g. session id) is a hash index. I assume it
    means that provided by a user (attacker) value is hashed, and fast
    comparison will occur on hashes.
    Hashes that are close to each other, like `a...`, `aD...`, `aDf...`,
    which is a guessing sequence will be coming from values that are not
    very close to each other. Unless hash has a simple unhash function,
    there seem to be no way to arrange guessing sequence on an attacking
    side.

    If both 1 and 2 are achievable, then a simple switch to hash index can
    be a mitigation.
    Whereas, the other way, as heard on one of ProtonMail's tech talks, is
    for developer to split a secret token into two part, with only first
    part being used in `WHERE` clause, while biz app does constant time
    comparison of the second part.

    _______________________________________________
    kwlug-disc mailing list
    kwlug-disc at kwlug.org <mailto:kwlug-disc at kwlug.org>
    http://kwlug.org/mailman/listinfo/kwlug-disc_kwlug.org
    <http://kwlug.org/mailman/listinfo/kwlug-disc_kwlug.org>


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://kwlug.org/pipermail/kwlug-disc_kwlug.org/attachments/20180612/97d36c02/attachment.htm>