search

OpenWhiteBox / AES

Implementations of white-box AES constructions and their cryptanalyses.
BSD 3-Clause "New" or "Revised" License
209 stars 31 forks source link

Full algorithm security dynamic binary analysis #4

Closed kaoh closed 7 years ago

kaoh commented 7 years ago

Was the "full" version designed to be resistent against dynamic binary analysis? https://eprint.iacr.org/2015/753.pdf

Bren2010 commented 7 years ago

I don't know if it is it resistant or not. I believe I expected it to be, but was never able to confirm.

kaoh commented 7 years ago

Sure? The paper states:

This approach allows one to extract the secret key material from white-box implementations significantly faster and without specific knowledge of the white-box design in an automated manner

I.e. it is using a similar technique like the differential power analysis. Mentioned counter measures are:

As a potential countermeasure against DCA, the embedded (and possibly merged with other functionality) static random data is used to select which affine equivalence is used for the encoding when accessing a particular look-up table. This results in a variable encoding (at run-time) instead of using a fixed encoding. Such an approach can be seen as a form of masking as used to thwart classical first-order DPA.

So, does the scheme use some randomized approach here?

doegox commented 7 years ago

Let me give my opinion @kaoh (I'm one of the authors of the DCA paper). Contrary to the other attacks, ours requires to run against a real implementation and deducing the robustness of a given scheme just by reading the paper is hazardous, to say the least. In this specific case there is a real implementation available, which is IMHO very valuable compared to most the previous papers that don't provide any code at all.

So we've just to try and see, right? Well, there is an additional difficulty to mount the attack and see what happen: this white-box is written in Go and when we tried the DCA against the other implementations provided in the OpenWhiteBox project (Chow and Xiao-Lai implementations), also written in Go, we discovered that Go adds quite a mess on top of the initial algorithm.

Compare e.g. an execution trace of Chow in Go: visual_trace_full 3 with an execution trace of Chow in C (from CHES 2016 challenge): visual_trace_full Xiao-Lai in Go doesn't look better: visual_trace_full 2

So at this point, we cannot conclude. I may give a try on the full implementation now that it's available but if I fails at breaking it, we can't be sure it will be because it's natively secure against DCA or because of the Go mess, in which case some fine tuning and filtering might still break it. I would be more confident of the results if I try the attack e.g. against an implementation written in C or C++.

kaoh commented 7 years ago

Thanks for the clarification. I assume the added mess is a result of the Go behavior of acting like an interpreted language with garbage collection, reflection, etc. This might be the same for C# and Java, script languages, etc., I guess? So, applying DCA here would require to trace one layer above before this runtime environment behavior (and the interpreter in case of Java and C#, ...) can spoil the result? But back to your DCA paper: In practice any implementation using deterministic runtime behavior should we attackable?

doegox commented 7 years ago

C# and Java: it might be indeed but be aware that some languages are very easily decompilable and can therefore be ported to e.g. C (without knowing the key) then be attacked.

Script languages: here it's even easier to port to C as you don't need to decompile it first. See https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_aes_kryptologik written in JavaScript, ported to C then broken.

Tracing one layer above is indeed also a good trick to do, see e.g. https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_des_sstic2012 written in Python and broken by tracing from the language itself. (otherwise a low level trace of a simple hello world produces sth like 6Gb of data!)

Any implementation using deterministic runtime behavior should be attackable? Not necessarily. See e.g. variants of NoSuchCon 2013 challenge https://github.com/SideChannelMarvels/Deadpool/tree/master/wbs_aes_nsc2013_variants. Even when the external encodings are removed, DCA doesn't work on this one because it's using internal 8-bit encodings (instead of e.g. the 4-bit encodings of Chow). You can see it as if each S-Box was surrounded by two random unknown S-Boxes therefore its characteristics are completely masked. Only a version without internal encodings could be broken by DCA. But the original construction still suffers from other attacks (DFA, algebraic attacks)