Certifying the Uncertifiable

A Critique of Common Criteria EAL4+

using the DESFire EV1 TRNG

Darren Hurley-Smith
Julio Hernandez-Castro

14/03/2017
Introduction

I The Common Criteria for Information Technology Security

Evaluation has been in effect since 1999
I ISO/IEC 15408: it is a ’living’ set of standards, in a process of
constant review
I The DESFire EV1 is a Common Criteria EAL4+ [1] certified
smart card
I It boasts a ’True’ Random Number Generator (TRNG), which
is assessed as part of its certification under BSI AIS 31 [2]
I Our analysis of this TRNG has led us to scrutinise the CC
EAL4+ testing methodologies regarding the DESFire EV1 [3]
Common Criteria: Evaluation Assurance Levels

I EAL is measured in seven levels (1-7), indicating the depth

and intrusiveness of the assessment process [1]
I EAL4+ indicates ”Methodological Design, Testing and
Review”
I This level is stated to be suitable for organisations with ”good
commercial development practices which, though rigorous, do
not require substantial specialist knowledge, skills, and other
resources”
Common Criteria EAL4+

I EAL4 requires a full definition of target design and

functionality, to allow for a security process review
I Improves on EAL3 by demanding increased production-line
security, design description and implementation representation
for the target product
I Independent testing is carried out:
I Developer testing is analysed
I Guided by functional specification
I Evidence of anti-tampering/production-line security must be
provided (Automation of key production stages)
A Recap of the DESFire EV1
I The DESFire EV1 is currently used in the Oyster Card system
(TfL)
I Transport for London (TfL) issued approximately 8 million
DESFire EV1-based cards in the 2015/2016 period [4]
I EV1 possesses a crypto-coprocessor and True Random Number
Generator

Figure 1: DESFire EV1 4K

I The Mifare DESFire EV1 has been successfully emulated [5],

and its power characteristics have been analysed in depth [6]
Our Previous Work

I We have previously analysed the TRNG output of 3 DESFire

EV1 4k cards in-depth
I We found consistent biases towards specific byte values in the
output [3]
I Our findings were responsibly disclosed to NXP, who
confirmed our findings
I But 3 is a very small sample: To check if this is a
product-wide issue, more testing had to be done!
Methodology: Data collection

I Previous work provided insight into the EV1 TRNG:

I 3 EV1 64MB sets collected in our previous work
I 64MB of data from an EV2 is used for comparison
I AES-128 authentication (key initialised to zero)
I 1 MB of data was retrieved from 50 DESFire EV1 4k
and 50 DESFire EV1 2k cards
I Data collection took an average of 3 hours per card to
gather 62,500 AES-128 encrypted values
I 5 cards were read in parallel using a python script
I Each nonce (16-bytes long) was extracted from a
different authentication session
Methodology: Lab Set-up

(a) Laptop with reader (b) ACR122U

and DESFire EV1 cards reader with 2 of
100 Mifare
DESFire EV1 cards

Figure 2: Experimental set-up used to collect TRNG data

I Toshiba Laptop Specification: i7 processor, 8GB RAM

I Reader: 5 x ACR122U (CCID)
Methodology: ENT and Testing Criteria

I The collected data was tested using ENT

I Our previous work found that the EV1 passed many
randomness test batteries
I Dieharder and NIST STS 2.1.2 were used but found
nothing significant
I Byte-level ENT testing found biases
I The Debian kernel implementation of ENT was used
I R implementation of Chi-square GoF used to validate
I Further validation with MATLAB’s built in Chi-sq function
Previous Results: ENT over 3 EV1 4k Cards

Table 1: Mifare DESFire EV1 ENT results for 64MB of TRNG output

ENT EV1 Card 1 EV1 Card 2 EV1 Card 3 Optimal/Expected

Entropy 7.999969 7.999989 7.999972 8
Optimal Compress. 0 0 0 0
chi-square 2709.10 973.07 2470.32 255
Arith. Mean 127.492921 127.500582 127.5006 127.5
Monte Carlo π est. 3.14167 3.142019 3.141909196 3.14159
S. Correlation 0.000008 0.000045 0.000093 0.0

I These results show our previously published results of 64MB

samples from 3 cards
I 64MB is a large amount of TRNG data, unlikely to be
collected when cards are in legitimate use or testing
I Do these results appear at lower sample sizes?
Effects of Reduced Sample Size (1MB Sample)

Table 2: Mifare DESFire EV1 ENT results for 1MB of TRNG output

ENT EV1 Card 1 EV1 Card 2 EV1 Card 3 Optimal/Expected

Entropy 7.999780 7.999820 7.999786 8
Optimal Compress. 0 0 0 0
chi-square 305.47 (1.65%) 249 (59.41%) 297.03 (3.62%) 255
Arith. Mean 127.6015 127.5626 127.5082 127.5
Monte Carlo π est. 3.13620558 3.140892564 3.140388562 3.14159
S. Correlation -0.000068 0.001339 -0.001751 0.0

I All cards perform better on this test with smaller samples and
have p-values greater than 0.01 for the chi-square test
I This indicates that the bias may be missed if tests are not
performed on a large enough sample
I However, results of 290+ are still terrible!
Effects of Reduced Sample Size (5KB Sample)

Table 3: Mifare DESFire EV1 ENT results for 5KB of TRNG output

ENT EV1 Card 1 EV1 Card 2 EV1 Card 3 Optimal/Expected

Entropy 7.999635 7.999640 7.999641 8
Optimal Compress. 0 0 0 0
chi-square 253.55 (51.3%) 249.26 (58.96%) 249.03 (59.36%) 255
Arith. Mean 127.6015 127.6324 127.4534 127.5
Monte Carlo π est. 3.13744549 3.145452582 3.140388562 3.14159
S. Correlation -0.000579 0.001990 -0.001204 0.0

I At 5KB, all tests pass the chi-square test with p-values greater
than 0.01 and within acceptable bounds of the expected value
I Bias becomes apparent in samples larger than 7.5KB
I Could the EV1 pass tests because the sample size is too
small?
Analysis: Bias

(a) Mifare DESFire EV1 mean bias (b) Random Data

Figure 3: Bias graph of two 64MB datasets

I The EV1 (a) shows a clear non-random trend

I Repetitive pattern, clear cycles, almost no values close to zero
Analysis: Fourier Analysis of the Bias

(a) EV1 Card 1 (b) EV1 Card 2 (c) EV1 Card 3

Figure 4: Fourier series for the biases from three 64MB TRNG samples

I All cards demonstrate a regular period of 32 biased values

I Exactly half of the possible byte values occur more frequently
Initial Findings

I Previously, researchers have used NIST, Dieharder, chi-square

goodness of fit, uniqueness and uniformity tests
I These are not sufficient to find the bias in the EV1 TRNG
I Chi-square tests performed in the literature focus on bit-level
analysis, but the bias occurs at the byte level in this TRNG
I More thorough analysis at the bit, byte and multi-byte levels is
required
Further Testing

I Preliminary results showed a significant bias in the EV1 TRNG

I Disclosure of our findings to NXP resulted in them confirming
our findings
I Further analysis would require three key activities:
I The study of additional Mifare DESFire cards and related
products (EV2)
I Collection of larger data samples from more EV1 cards
I Masking tests highlight the observed bias and its magnitude
Analysis: EV2 Bias and Fourier Analysis

(a) EV2 Bias (b) EV2 Fourier Analysis

Figure 5: Analysis of the DESFire EV2 TRNG (1 card, 64MB of data)

I The EV2 card we tested did not exhibit the EV1’s consistent
bias
Analysis: Bit-Mask Test Results 1

(a) Random Source (b) EV1 Card 1

Figure 6: Graphs showing the bias of masks applied over 64MB samples

I Random source has biases of magnitude 10-4

I EV1 has biases of magnitude 10-3
I Bit-masking highlighted a significant bias away from masks of
’00011000’ (int 24)
Analysis: Bit-Mask Test Results 2

(a) EV1 Card 2 (b) EV1 Card 3

Figure 7: Graphs showing the bias of masks applied over 64MB samples

I As can be seen in Figures 16 (a) and (b), this trend holds

across all three EV1 64MB data sets
Analysis: Bit-Mask Test Results 3

(a) Random Source (b) EV2

Figure 8: Graphs showing the bias of masks applied over 64MB samples

I The same test applied over the EV2 data set did not find any
significant (10-3 ) biases
I Both sources appear randomly distributed
Testing 100 EV1 Cards

I Having established the bias and its behaviour in different tests

and data-set sizes, we tested 100 cards
I 50 were 2k model and 50 were 4k model DESFire EV1 cards
I 4k cards were randomly selected from a pool of 100 cards
I 2k cards were randomly selected from a pool of 200 cards
I ENT and a Masking Test were used to extract and identify
the biases for these cards
100 DESFire EV1 ENT Results

Figure 9: Chi-sq GoF results for 100 1MB DESFire EV1 TRNG samples,
compared with Urandom output
100 DESFire EV1 ENT Results

I The vast majority (78%) of EV1 cards fail the Chi-sq GoF test
I The mean EV1 Chi-sq result is 314.17, far above the target
value (approximately 256)
I These are results for a relatively easy to procure sample size,
of merely 1MB of TRNG output
I Cards derive from 3 batches, randomly selected from a pool of
300 cards to minimise issues of sequentiality within batches
100 DESFire EV1 Masking Test Results

Figure 10: Masking Test for 100 1MB DESFire EV1 TRNG samples
Worst performing Cards

Figure 11: Worst performing cards

I The 5 worst performing cards all have Chi-sq GoF results

worse than 415!
I The observed bias is between -0.0036 and -0.0061
Outlier: Card 4

Figure 12: Anomalous result

I Card 4 exhibits a bias towards 24 (0.0028), which is

anomalous and as yet unexplained
Conclusion: EV1 Testing

I Clear & consistent biases have been found in the EV1 TRNG
I We have responsibly disclosed our findings to NXP
I They have responded, confirming our findings
I They have suggested the issue lies in the whitening function
I A more detailed analysis confirms that there is a consistent
’00011000’ bias on many bytes
I No practical attacks have been identified at this point
I The EV2 doesn’t share the identified flaw
Our Recommendations

I Increase the size of the sample tested:

I At least 100 instances of the TOE, preferably far more, as
evidenced by Bernstein et al. in 2013 [7]
I Enlarge sample size (At least 1MB, but preferably 16MB or
more in line with EAL level)
I Include more randomness tests (provably guarantee that these
tests are uncorrelated)
I Perform these tests on words of 1-bit, 4-bit, byte, and larger
sizes, appropriate to the TOE
I Perform all tests on related functions in isolation, conjunction
and after implementation in the TOE
I Ensure the correlation between tests is known, to evaluate the
veracity of results in tests based on limitations perceived in
others
Future Work

I Expand the tested cards to include other Common Criteria

EAL 4/5+ RFID smart cards:
I Felica
I Legic
I Investigate other evaluation award schemes, such as FIPS
140-2 Lvl. 2 [7]
I Testing under variable environmental conditions (hot, cold,
humid, etc.)
I Developing a comprehensive library of tests with usage
guidelines based on our findings
Acknowledgements

I This work was funded by InnovateUK as part of the

authenticatedSelf project, under reference number 102050.

I We would like to thank ECOST - Cryptacus for their valuable

and insightful discussion of this work.
I We would also like to thank NXP Semiconductors Ltd. for
their timely and professional communication following the
responsible disclosure of our findings.
References
1. Federal Office for Information Security. Bsi-dsz-cc-0955-2016 for nxp secure smart card controller
p6021y vb including ic dedicated software from nxp semiconductors germany gmbh. Technical report,
Federal Office for Information Security, 2016.
2. Bundesamt fur Sichterheit in der Informationstechnik. Evaluation of random number generators
version 0.10. Technical report, Bundesamt fur Sichterheit in der Informationstechnik, 2013.
3. Darren Hurley-Smith and Julio Hernandez-Castro. Bias in the mifare desfire ev1 trng. In Radio
Frequency Identification: 12th International Workshop, RFIDsec 2016, Hong Kong, China, November
30-December 2, 2016. Springer International Publishing, 2016.
4. Transport for London. Adult Oyster Cards Issued 2015/16.
http://content.tfl.gov.uk/oyster-card-sales.pdf, 2016.
5. Timo Kasper, Ingo Von Maurich, David Oswald, and Christof Paar. Chameleon: A versatile emulator
for contactless smartcards. In International Conference on Information Security and Cryptology, pages
189–206. Springer, 2010.
6. Timo Kasper, David Oswald, and Christof Paar. Side-channel analysis of cryptographic rfids with
analog demodulation. In International Workshop on Radio Frequency Identification: Security and
Privacy Issues, pages 61–77. Springer, 2011.
7. Daniel J Bernstein, Yun-An Chang, Chen-Mou Cheng, Li-Ping Chou, Nadia Heninger, Tanja Lange,
and Nicko Van Someren. Factoring rsa keys from certified smart cards: Coppersmith in the wild. In
International Conference on the Theory and Application of Cryptology and Information Security,
pages 341–360. Springer, 2013.
.

Questions?
 Measuring the Distance
Investigating the DESFire EV2 Distance Bounding Protocol

Kevin Soules
Darren Hurley-Smith
Julio Hernandez-Castro

14/03/2017
Introduction

I Distance bounding implementations have begun to appear in

contemporary RFID smart cards
I The DESFire EV2 is a Common Criteria EAL5+ certified
smart card [1] that possesses a distance bounding protocol
I This protocol is tied to the Virtual Card Architecture (VCA)
which has not been present in previous cards
I Previous experience with the more accessible EV1 [2] has
helped us to derive APDUs for the distance bounding protocol
Distance Bounding Protocols
I Relay attacks can allow attackers to remotely compromise
communication sessions [3]
I Session hijacks, manipulation of data and man-in-the-middle
attacks are all possible outcomes of a relay attack

Figure 1: Relay Attack [4]

I Distance bounding protocols aim to mitigate relay attacks:

I Measure if communicating device is within a given distance [5]
I Limitations centre around the hardware constraints of target
systems:
I Minimum opportunity space is determined by the speed with
which bounds can be computed [6]
An Example Distance Bounding Protocol

Figure 2: Hancke and Kuhn’s distance bounding protocol [7]

DESFire EV2

Figure 3: DESFire EV2 component diagram [1]

I Like it’s predecessor, the EV1, the EV2 possesses

crypto-coprocessors (3DES and AES-128) and a TRNG
module
I Distance bounding is achieved by combining other services
Lab Set-up

Figure 4: Three readers and target card (Left) & Spectroscope with
reader, card and probe (Left)
Investigating the EV2 DB Protocol 1

I Additionally, a Toshiba Laptop and ACR122U CCID RFID

reader were used
I Public documentation outlines basic APDU and response
sizes:
I This same documentation outlines the need to initialise a
virtual card application (and online guides to this process exist)
I Thus, APDU derivation was largely an issue of command byte
and content identification
I A solid grounding in NXP error codes is a great help!
(You’ll see a lot of them)
Investigating the EV2 DB Protocol 2

I Search space for APDU bytes is only 256 values, so trial and
error is feasible:
I Public NXP documentation only provides APDU name (not
value), and a basic overview of command structure
I The simplest command to derive was PreparePC
I The most complex APDU command was VerifyPC
I This was further complicated by obfuscation:
I The EV2 has measures against brute force of the verification
phase
Distance Bounding Protocol Overview

Figure 5: Mifare DESFire EV2 VC selection and distance bounding

PreparePC

Figure 6: Mifare DESFire EV2 PreparePC Command

I This command informs the prover of an impending distance

bounding operation:
I The prover responds to the command with configuration data
(used in VerifyPC as vPCresponse)
I The prover also computes random number B (RndB ) in
preparation for the next phase
ProximityCheck

Figure 7: Mifare DESFire EV2 ProximityCheck Command

I The verifier computes random value A which is an 8 byte

number
I The verifier sends a 1-8 byte portion of RndA
I The prover responds with an equal sized portion of RndB
I This process repeats until a full 8 bytes has been transferred
each way between prover and verifier
I Times are measured from last byte out to first byte in, with
the verifier measuring all timings
VerifyPC

Figure 8: Mifare DESFire EV2 VerifyPC Command

I This phase allows the prover and verifier to authenticate, and

is mutual:
I The verifier sends
CMAC(cmd||vPCresponse||RndB [0]||RndA [0]||...||RndB [n]||RndA [n])
concatenated to 8 bytes (odd indices)
I If this is found to be valid by the prover, it responds with
CMAC(resp||vPCresponse||RndB [0]||RndA [0]||...||RndB [n]||RndA [n])
concatenated to 8 bytes (odd indices)
I The verifier checks this CMAC for validity
Preliminary Timing Tests

I After derivation of the correct commands, we studied timings:

I A spectroscope was used to record the radio communication

visually
I Peak to peak measurement provided an approximation of the
round trip time (RTT)
I The rationale for this study was to determine if there are
signifiers of when the card is in a fail-state
I The round trip time of the ProximityCheck command is
analysed to begin determining the size of the bound
Timing Results: Raw Spectroscope Output

Figure 9: Successful (top) and Failed Communication (bottom)

Timing Results: Higher Resolution Output

Figure 10: Detailed analysis of successful 1 pass 8 byte distance bound

Timing Results: ProximityCheck

Figure 11: 50 Proximity Check command RTT measurements

Timing Results: VerifyPC

Figure 12: 50 Proximity Check command RTT measurements

Security Considerations

Table 1: Security features: Comparison of EV2 and distance bounding

protocols (HK and SK results referenced from [8])

Err. Resist Privacy MA

HK [7, 8] No - No
SK (MA) [8] Yes Yes Yes
SK (no MA) [8] Yes Yes No
EV2 ProxCheck [1] Yes No Yes

I Error resistance is provided by final MAC checks

I Privacy is not provided: communication in not encrypted for
these operations
I Mutual authentication is provided in the final phase
Conclusion
I We have scrutinised the EV2 distance bounding protocol:
I The protocol has been analysed
I Timings have been subject to a preliminary study
I There appear to be some differences between the timings of
successful and failed VerifyPC commands:
I These are not significant at this point
I It is simpler to just restart the reader if trying to brute force
the CMAC!
I The NXP implementation of distance bounding differs
significantly from the literature:
I The fast phase (ProximityCheck) is a bidirectional exchange of
randomly generated bytes
I There is no security on the fast-phase itself
I Security is provided by the exchange of MAC values in the
VerifyPC phase
I The hardware constraints of the EV2 appear to influence the
protocol greatly
Future Work

I Conduct a more accurate analysis of timings, to confirm any

findings
I Prepare and execute practical attacks against the protocol,
based on our theoretical observations
I Continue to expand our understanding of this command set:
much functionality remains hidden at this time
I Identify hardware countermeasures: the inclusion of fail-state
obfuscation indicates an increase in hardware countermeasures
implemented by NXP
I Conduct experiments in a variety of environmental conditions
to determine their effect(s) on the Distance Bounding protocol
Acknowledgements

I This work was funded by InnovateUK as part of the

authenticatedSelf project, under reference number 102050.

I We would like to thank ECOST - Cryptacus for their valuable

and insightful discussion of this work.
References
1. NXP Semiconductors Ltd. MF3D(H)x2 MIFARE DESFire EV2 contactless multi-application IC. NXP
Semiconductors Ltd., 2 edition, February 2016.
2. Darren Hurley-Smith and Julio Hernandez-Castro. Bias in the mifare desfire ev1 trng. In Radio
Frequency Identification: 12th International Workshop, RFIDsec 2016, Hong Kong, China, November
30-December 2, 2016. Springer International Publishing, 2016.
3. Laurent Bussard and Walid Bagga. Distance-bounding proof of knowledge to avoid real-time attacks.
In Security and Privacy in the Age of Ubiquitous Computing, pages 223–238. Springer, 2005.
4. Infosec Institute. Relay attack diagram, 2015.
5. Stefan Brands and David Chaum. Distance-bounding protocols. In Advances in
Cryptology-EUROCRYP93, pages 344–359. Springer, 1994.
6. Cas Cremers, Kasper B Rasmussen, Benedikt Schmidt, and Srdjan Capkun. Distance hijacking
attacks on distance bounding protocols. In Security and Privacy (SP), 2012 IEEE Symposium on,
pages 113–127. IEEE, 2012.
7. Gerhard P Hancke and Markus G Kuhn. An rfid distance bounding protocol. In Security and Privacy
for Emerging Areas in Communications Networks, 2005. SecureComm 2005. First International
Conference on, pages 67–73. IEEE, 2005.
8. Chong Hee Kim, Gildas Avoine, François Koeune, François-Xavier Standaert, and Olivier Pereira. The
swiss-knife rfid distance bounding protocol. In Information Security and Cryptology–ICISC 2008,
pages 98–115. Springer, 2009.
.

Questions?
 Automatic Related Key Cryptanalysis of Block Ciphers
with CP

David Gerault

LIMOS, University Clermont Auvergne

This presentation sums up 4 publications in collaboration with Pascal Lafourcade, Marine Minier,
Christine Solnon, Siwei Sun, Qianqian Yang, Yosuke Todo, Kexin Qiao, Lei Hu

14 mars 2017
Cryptacus 2017

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
1 / 21 S
 Ubiquitous Computing Systems

A lot of devices
Low computational power
Many security challenges
David Gerault (LIMOS, University Clermont Auvergne Automatic
This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
2 / 21 S
 Block Ciphers

Hi
Enc
Cryptacus!

X C

Block Cipher Property

Output undistinguishable from the output of a random function

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
3 / 21 S
 Use of Block Ciphers in Ubiquitous Systems

Encryption
Building Hash Functions
Pseudorandom Function (PRF)
...

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
4 / 21 S
 Why automatic tools ?

Designing a secure block cipher is difficult

Exhaustive search untractable

Many attack types, with different adversary capabilities
Very hard to evaluate
Iterative process : needs to be reasonably fast

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
5 / 21 S
 Related Key Differential Cryptanalysis
δX
X X’

ENC δK ENC
K K’

C C’
δC ?

A picks X , δX , δK and receives f (K , X ) and f (K ⊕ δK , X ⊕ deltaX ), and must

determine if f is a random function or a given block cipher.

Difficult part
The difficult part for the attacker is to find δX , deltaK , δC such that
(δX , δK → δC ) with a high probability.
David Gerault (LIMOS, University Clermont Auvergne Automatic
This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
6 / 21 S
 2 steps solving

Step 1 : boolean abstraction Step 2 : actual byte values

∆=0 δ=0
∆=1 δ 6= 0
Finds candidate solutions Check their consistency

Step 1
Step1(n) gives an output X, composed of ∆X , ∆K , ∆C , the difference
propagation path and a bound on the probability.

Step 2
Step2(X) returns a probability and the difference values along the path if X is
consistent, 0 otherwise.

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
7 / 21 S
 Example of output for Step 1

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
8 / 21 S
 Relevance of RK for Ubiquitous Systems ?

Collisions in Hash Functions (XBox)

Key distribution
Key update

Related Key cryptanalysis finds a lot of use cases in embedded devices.

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine 2017
Minier, Christine
9 / 21 S
 First target : the AES (Advanced Ecryption Standard)
Key K
(4x4 bytes)

KS

ARK S SR MC ARK S

Plaintext X Ciphertext Xn
(4x4 bytes) (4x4 bytes)
n times

AES
Proposed by Daemen and Rijmen in 1997
Standard since 2000
Plaintext X = 128 bits ≡ 4 × 4 bytes ,
Key K = 128, 192 or 256 bits (in this talk,
128 bits ≡ 4 × 4 bytes)

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
10 / 21 S
 Related Work & Contributions : AES

Problem
Searching for optimal related key differential characteristics on 3, 4 and 5 rounds
of AES-128 (n ∈ {3, 4, 5}, |K | = 4 × 4 bytes)

Previous work
Biryukov et al., 2010 : Branch & Bound
→ Several hours
Fouque et al., 2013 : Graph traversal
→ 30 minutes, 60 Gb memory, 12 cores

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
11 / 21 S
 Related Work & Contributions : AES

Problem
Searching for optimal related key differential characteristics on 3, 4 and 5 rounds
of AES-128 (n ∈ {3, 4, 5}, |K | = 4 × 4 bytes)

Previous work
Biryukov et al., 2010 : Branch & Bound
→ Several hours
Fouque et al., 2013 : Graph traversal
→ 30 minutes, 60 Gb memory, 12 cores

Our results (CP 2016)

20 minutes, negligible memory, single core
New differential characteristics
|K | ∈ {192, 256} within reach (see eprint)

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
11 / 21 S
 Second target : Midori

Repeat n times
WK WK

X0

SB SC MC
SB
KA
KA KA
X C
SB

Midori
Proposed by Banik et al. in 2015
Lightweight by design
Plaintext X = 64 or 128 bits ≡ 4 × 4
nibbles or bytes
Key K = 128 bits

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
12 / 21 S
 Related Work & Contributions : Midori

Problem
Searching for optimal related key differential characteristics on full round
Midori-64 and Midori-128

Previous work
Midori-64 : Dong, 2016 : Custom algorithm
→ 14 rounds (out of 16), 2116 operations
Midori-128 : Not done

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
13 / 21 S
 Related Work & Contributions : Midori

Problem
Searching for optimal related key differential characteristics on full round
Midori-64 and Midori-128

Previous work
Midori-64 : Dong, 2016 : Custom algorithm
→ 14 rounds (out of 16), 2116 operations
Midori-128 : Not done

Our results (Indocrypt 2016)

Few hours
Full round for both versions
Practical attacks :
Midori-64 : 235
Midori-128 : 243

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
13 / 21 S
 How ? With CP
CONVERT TO MODEL
PROBLEM
CSP

FEED TO A SOVER

ONE SOLUTION

SOLVER ALL SOLUTIONS

OPTIMAL SOLUTION

Holy Grail
“Constraint programming represents one of the closest approaches computer
science has yet made to the holy grail of programming : the user states the
problem, the computer solves it.” (E. Freuder)
David Gerault (LIMOS, University Clermont Auvergne Automatic
This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
14 / 21 S
 CSP

Define variables on given domains

[23..42] x
bool y
array [1..N,1..M] of floats δ . . .
Define constraints, i.e. relations between them
x +y <5
Table : (a, b, c) ∈ {(2, 3, 4), (1, 7, 2)}
Sums, products, alldifferent . . .
(optional) Define an objective function to optimize
Maximize(Sum(i in 1..N, j in 1..M) δ[i][j])
Feed it to the solver, and let the magic happen...

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
15 / 21 S
 Meh, just another automatic tool

Other automatic tools exist

SAT
Mixed Integer Linear Programming (MILP)
...

Question : Why do I come with a new one ?

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
16 / 21 S
 Meh, just another automatic tool

Other automatic tools exist

SAT Boolean variables
Mixed Integer Linear Programming (MILP) Linear inequalities
...

Question : Why do I come with a new one ?

Response : Not new, MILP and SAT are subsets of CP

CP
No limitations on variables nor constraints
Uses algorithms from the other methods
There exist tools translating from CP to the others

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
16 / 21 S
 How CP compares with MILP

(See FSE 2017 paper for details)

It is human readable !
Performs at least as good
Can handle 8-bit SBoxes

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
17 / 21 S
 Modelling properly

Straightforward modelling
With a naive approach, more than 90 millions inconsistent step 1 solutions found
for 4 rounds of AES-128 with 11 active SBoxes

More elaborate modelling

With a more suble approach, 0 step 1 solutions

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
18 / 21 S
 Example : XOR Constraint
(white = 0, colored 6= 0)
Byte values Boolean abstraction
δA δB δC ∆A ∆B ∆C
⊕ = ⊕ =
⊕ x = x ⊕ =

Inferring equalities
XORs introduce a lot of branching, but storing information about equality or
difference during step 1 helps filtering a lot !
David Gerault (LIMOS, University Clermont Auvergne Automatic
This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
19 / 21 S
 Example : XOR Constraint
(white = 0, colored 6= 0)
Byte values Boolean abstraction
δA δB δC ∆A ∆B ∆C
⊕ = ⊕ =
⊕ x = x ⊕ =
x ⊕ y = z ⊕ = ?
x ⊕ x = ⊕ = ?

∆A ∆B ∆C
0 0 0
0 1 1
1 0 1
1 1 ?

Inferring equalities
XORs introduce a lot of branching, but storing information about equality or
difference during step 1 helps filtering a lot !
David Gerault (LIMOS, University Clermont Auvergne Automatic
This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
19 / 21 S
 Other ways to improve a CP model

Variable ordering -> Starting with the most constrained one

Value choice -> If you want to minimize a sum, affecting variables to 0 first
is a good idea...
Blackbox heuristics
Try a different solver ? The power of MiniZinc

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
20 / 21 S
 Conclusion and future challenges

Conclusion
CP is great
Recovered known bounds on the AES way faster
Practical RK attacks on Midori
Future challenges
Other ciphers
Other security properties

David Gerault (LIMOS, University Clermont Auvergne Automatic

This presentation
Relatedsums
Key Cryptanalysis
up 4 publications
of Block
in collaboration
Ciphers withwith
CPPascal
14 mars
Lafourcade,
2017Cryptacus
Marine2017
Minier, Christine
21 / 21 S
 Constant-Time Callees
with Variable-Time Callers

Cesar Pereida Garcı́a

Billy Bob Brumley
Tampere University of
Technology Finland
Outline
• Enabling Cache-Timing Attacks
• Motivation
– Brief History of Cache-Timing Attacks
• Recipe for Side-Channel Attacks
– Step 1, 2, 3, 4 and 5
• End-to-End Cache-Attack
– TLS & SSH
– Crypto libraries
• Conclusions
2
Enabling Cache-Timing Attacks

https://source.ggy.bris.ac.uk/mediawiki/index.php?title=File:Memory-Hierarchy.jpg&limit=500

3
 Brief History of
Cache-Timing Attacks
for Public Key
Cryptography
in OpenSSL
4
 Cache-Timing Attacks for Public Key Cryptography
OpenSSL Version

0.9.7
Cryptosystem
0.9.8 DSA
RSA
1.0.1 ECDSA
1.0.2
1.1.0

4
12
10

8
08
06

16
02

1
0

20
20
20

20
20
20

20
20

20

Year
ECDSA RSA DSA
2009 - Brumley & Hakala (P+P/LI-I) 2005 - Percival (E+R/L1-D) 2010 - Aciicmez et al. (P+P/L1-I)
2014 - Benger et al. 2007 - Aciicmez et al. (SBPA/L1-I) 2016 - Pereida García et al.
(F+R/LLC/secp256) (F+R/Perf. Deg./LLC)
2014 - Yarom & Benger 2008 - Aciicmez & Schindler (SBPA/L1-D)
(F+R/LLC/Binary Field) 2016 - Yarom et al. (Cache-Bank Collision L1)
2015 - van de Pol et al. (F+R/LLC)
2016 - Allan et al.(F+R/Perf. Deg./LLC)
5
 Relevant Changes Introduced due to Cache-Timing Attacks
OpenSSL Version

0.9.7
Cryptosystem
0.9.8 DSA
RSA
1.0.1 ECDSA
1.0.2
1.1.0

14

16
02

12
06

10

18
08
40

20

20
20

20
20

20

20
20
20

Year
2005: RSA EXP 2007: RSA INV
● BN_FLG_EXP_CONSTTIME ● BN_mod_inverse_no_branch
● BN_mod_exp_mont_consttime ● BN_div
● BN_FLG_CONSTTIME
2012: ECDSA POINT MULT
● EC_GFp_nistp256_method: Constant-time 2015: ECDSA FAST & MOD INV
scalar multiplication (fixed window & masking) ● EC_GFp_nistz256_method
● Research shifts to secp256k1 (wNAF) ● BN_mod_exp_mont_consttime + FLT

6
Recipe for Side-Channel
Attacks on Digital
Signatures

7
Recipe for a Side-Channel Attack

1) Take an algorithm that 2) Measure the side-channel 3) Run the leaked data
uses confidential data. leakage. through a signal processing
machine.

4) Convert sequences to bits 5) Let it rest in a lattice for Et voilà, you have a private
and combine with message and some time. key.
signature.
8
 Step 1
Take a primitive and an
algorithm that uses
confidential data
9
ECDSA
Given:

Signing:
Note: Nonce k is recoverable if at least 3 bits are leaked for each signature.

Constant-Time Scalar by Point Multiplication

Modular Inversion?

10
Modular Inversion (OpenSSL 1.0.1)

11
Binary Extended Euclidean Algorithm
Cache-Attack
Fact OpenSSL
BBEA

Number of right-shifts on v

BN_rshift1 Number of right-shifts on u

Number and order of subtractions on v

Number and order of subtractions on u

Only one loop per iteration

BN_usub
U loop is the only loop that can be
executed during the first iteration

k is protected, i.e. padded with modulus

n
12
 Step 2
Measure the
Side-Channel Leakage

13
 [1]
Flush+Reload on the BEEA

BN_rshift1

BN_usub

[1] Yarom, Yuval, and Katrina Falkner. "FLUSH+ RELOAD: A High Resolution, Low Noise, L3 Cache Side-Channel Attack." USENIX. 2014.

14
Improved Performance Degradation
Objective: Identify the addresses with the highest impact
● Better probing
● Better degradation

1) Identify the candidate methods 2) Degrade one memory 3) Count cache-misses and CPU
and their memory addresses. address at a time. cycles using performance
counters (perf).
BN_mod_inverse → 0xE7940
BN_rshift1 → 0xE48E0
BN_usub → 0xD7B00
BN_uadd → 0xD7800
BN_rshift → 0xDDFC0

15
Setup and Attack Scenario
Setup
● Intel Core i5-2400
Sandy Bridge 3.10
GHz
● 8 GB memory
● Ubuntu 16.04 LTS
“Xenial” 64-bits
● OpenSSL 1.0.1u

16
 Step 3
Apply Signal Processing

17
Signal Processing
Trace
● Template &
Cross-correlation
● Apply moving average.
● Raw → Clean
● Translate to LS sequence

LSLLSLSL...
18
 Step 4
Recover Bits

19
Bit Recovery

LSLLSLSL... 01001010...

SLLLLL... 100000...
20
Bit Recovery

26 Bits >= 3
2
Length
Sequences
L=5

21
Bit Recovery

22
 Step 5
Lattice Attack

23
Lattice Attack
Input parameters to Lattice: Lattice information:
● Bits recovered ● Dimension d + 2
● Messages ● Implemented in Sage
● Signatures ● BKZ reduction (block size 30)

[8] Cabrera Aldaya et al. "SPA vulnerabilities of the binary extended Euclidean algorithm." Journal of Cryptographic Engineering (2016):
1-13.

24
End-to-End Protocol
Attack

25
End-to-End Protocol Attack

26
Cryptographic Libraries
• Crypto libraries are a prime target for CTA!
• We offered a patch to the libraries
• OpenSSL 1.0.1 development reached EOL starting January 2017.
• OpenSSL 1.0.1 shipped with Ubuntu LTS 12.04 and 14.04; Debian
7.0 and 8.0; and SUSE.
• Upgrade to OpenSSL 1.0.2 or higher.
• Otherwise, apply the patch!

27
Conclusions
• Constant-time implementations need to be tested.
• The BEEA modular inversion enables practical
cache-timing attacks.
• The performance degradation technique improves
trace quality.
• Different key bit recovery approaches are possible.
• Cache-Timing attacks are increasing in popularity and
complexity every year.

28
Thank you
Questions?

29
 The Success Rate Reconsideration of the MIM Attack
Against HB# Authentication Protocols
Siniša Tomović, Milica Knežević and Miodrag J. Mihaljević

Siniša Tomović

Mathematical Institute of the Serbian Academy of Sciences and Arts

sinisatom@turing.mi.sanu.ac.rs

Sutomore, Montenegro, 14.3.2017

Sutomore, Montenegro, 14.3.2017 1/

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 2/
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Introduction

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 3/
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Introduction

Introduction

RFID (Radio-Frequency Identification) devices: supply-chain

management, payment and transportation systems, tracking of
goods...
RFID system: Tag, Reader, authentication protocol
HB family of authentication protocols
Random-HB# and HB# : Gilbert, H., Robshaw, M.J.B., Seurin, Y.
HB # : Increasing the Security and Efficiency of HB+, Smart, N. (ed.)
EUROCRYPT 2008.

Sutomore, Montenegro, 14.3.2017 4/

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Random-HB# and HB# authentication protocols

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 5/
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Random-HB# and HB# authentication protocols

Random-HB# and HB# authentication protocols

T R
(secret X, Y) (secret X, Y)
e ← Ber m
τ
$ b
− Zk2Y
b← −−−−−−→
a $
←−−−−−− − Zk2X
a←

z
z = aX ⊕ bY ⊕ e −−−−→ ? kaX ⊕ bY ⊕ zk ≤ thr

Fig 1. Authentication procedure for RANDOM-HB# and HB# protocols. Secret keys X, Y are
random matrices in RANDOM-HB# , and Toeplitz matrices in HB# .

Sutomore, Montenegro, 14.3.2017 6/

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Security of Random-HB# and HB# protocols

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 7/
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Security of Random-HB# and HB# protocols

Security of Random-HB# and HB# protocols

Provably secure against GRS MIM attacks

General MIM OOV attack: Ouafi, K., Overbeck, R., Vaudenay, S.:
On the Security of HB# against a Man-in-the- Middle Attack. In:
Pieprzyk, J. (ed.) ASIACRYPT 2008.
Claim: Applicable to the whole HB family (with variable efficiency).

Sutomore, Montenegro, 14.3.2017 8/

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 9/
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

OOV MIM attack against Random-HB# and HB#

The secret values are extracted from the acceptance rate after repeating
certain MIM modifications.
1 Adversary eavesdropps to obtain: (ā, b̄, z̄ = āX ⊕ b̄Y ⊕ ē)
2

T A R
(secret X, Y) triplet (ā, b̄, z̄) (secret X, Y)
e ← Ber m
τ
$ b̂ = b ⊕ b̄
− Zk2Y
b← −−−−−−−−−→
â = a ⊕ ā $
←−−−−−−−−− − Zk2X
a←

ẑ = z ⊕ z̄
z = âX ⊕ bY ⊕ e −−−−−−−−−→ ? kaX ⊕ b̂Y ⊕ ẑk ≤ thr

Sutomore, Montenegro, 14.3.2017 10 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

OOV MIM attack against Random-HB# and HB#

kaX ⊕ b̂Y ⊕ ẑk = kaX ⊕ (b ⊕ b̄)Y ⊕ (z ⊕ z̄)k

= k(aX ⊕ bY ⊕ z) ⊕ (āX ⊕ b̄Y ⊕ z̄)k
= ke ⊕ ēk ≤ thr

3 Adversary repeats the MIM modification above for n times, and

counts the number c of successfull authentications.
4 Adversary estimates w̄ = kēk using:  
thr −(m−w̄ )τ −w̄ (1−τ )
c/n ≈ P(w̄ ) = P(ke ⊕ ēk ≤ thr ) ≈ Φ √ , for
mτ (1−τ )
n > n0 (r , w ).

Sutomore, Montenegro, 14.3.2017 11 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

OOV MIM attack against Random-HB# and HB#

θ2
n0 (r , w̄ ) = r2
R(w̄ ) where:
P(w̄ )(1−P(w̄ ))
R(w̄ ) = 2 (P 0 (w̄ ))2
P(w̄ ) ≈ Φ(u)
u 2
P 0 (w̄ ) ≈ − √ 1−2τ × √1 e − 2
mτ (1−τ ) 2π
thr −(m−w̄ )τ −w̄ (1−τ )
u= √
mτ (1−τ )
1
r ∈ { 2 , 1} (the choice of r defines the desired precision of n0 in the given
context).
wopt = argmin{n0 (w )}
w ∈1...m

Sutomore, Montenegro, 14.3.2017 12 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

OOV MIM attack against Random-HB# and HB#

6 Adversary reconstructs ē by flipping its bits and measuring its weight

again as described. Ie. he makes new MIM modifications using
(ā, b̄, z̄ = āX ⊕ b̄Y ⊕ ē ⊕ fk ).

P(w̄ + 1), if ēk = 0
P(ke ⊕ ē ⊕ fk k ≤ thr ) = ,
P(w̄ − 1), if ēk = 1
f̄k is the all zero-vector with exception that k-th bit is 1.
7 āX ⊕ b̄Y = z̄ ⊕ ē. Adversary repeats previous steps to obtain full
linear system with unknown secret matrices X, Y.

Sutomore, Montenegro, 14.3.2017 13 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

OOV MIM attack against Random-HB# and HB#

OOV Algorithm1 Approximating w̄

1: Input: ā, b̄, z̄, n
2: Output: P −1 ( nc ), an approximation of
w̄ = kāX ⊕ b̄Y ⊕ z̄k, where
P(w̄ ) = Pr [ke ⊕ ēk ≤ thr ]
thr −(m−w̄ )τ −w̄ (1−τ )
= Φ( √ )
mτ (1−τ )
3: Processing:
4: c = 0
5: for i = 1..n do
6: During a session, modify messages:
7: adversary replaces b with b̂ = b ⊕ b̄
8: adversary replaces a with â = a ⊕ ā
9: adversary replaces z with ẑ = z ⊕ z̄
10: if Verifier accepts the modified response then
11: c =c +1
12: end if
13: end for

Sutomore, Montenegro, 14.3.2017 14 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 OOV MIM attack against Random-HB# and HB#

OOV MIM attack against Random-HB# and HB#

OOV Algorithm2 Getting linear equations for secret X, Y

1: Input: ā, b̄, z̄
w̄est the expected weight of ē = āX ⊕ b̄Y ⊕ z̄
2: Output: System of linear equations āX ⊕ b̄Y = c̄
3: Processing:
4: c̄ = z̄
5: Call Algorithm1 with arguments ā, b̄, z̄ and n0 ( 12 , ω̄est ) = 4θ2 R(w̄est ) to get w̄
6: for i = 1..m do
7: Flip i-th bit of z̄ to get z̄i
8: Call Algorithm1 with arguments ā, b̄, z̄i and n0 (1, w̄ ) = θ2 R(w̄ ) to get w̄i
9: if w̄i = w̄ − 1 then
10: Flip i-th bit in c̄
11: end if
12: end for

Optimization techniques: flipping blocks and measuring weight.

Sutomore, Montenegro, 14.3.2017 15 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Emipirical evaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 16 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Emipirical evaluation of the OOV attack

Emipirical evaluation of the OOV attack

OOV Algorithm 1 (estimation of the noise weight):

Empirical succes rate ≈ 0.045 for the noise vector of optimal weight
(w = 77 for the given parameter set).
For noise vector weight in [60, 90]: ≈ 0.124.
Claimed theoretical succes rate is ≈ 0.9986.
Increasing the sample size does not improve the imprecision.
Proposed OOV MIM attack is not empirically succesfull.

Sutomore, Montenegro, 14.3.2017 17 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 18 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

 
thr −(m−w̄ )τ −w̄ (1−τ )
c/n ≈ P(w̄ ) = P(ke ⊕ ēk ≤ thr ) ≈ Φ √ , for
mτ (1−τ )
n > n0 (r , w ).

Ber τ Ber τ Ber τ ··· Ber τ e

µ = E (ke ⊕ ēk)

⊕ = w (1 − τ ) + (m − w )τ
σ 2 = Var (ke ⊕ ēk)
0 1 1 ··· 0 ē = mτ (1 − τ )

= ke ⊕ ēk Binomial ?

Ber τ Ber 1−τ Ber 1−τ ··· Ber τ  ⊕ ēk≤ thr ) ≈

P(ke
Φ thrσ−µ
2

Sutomore, Montenegro, 14.3.2017 19 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 20 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

Pn
Xi P(w )(1−P(w ))
c/n = X̄n = i=0
n , Xi ← Ber m
P(w ) E X̄n = P(w ), Var X̄n = n

√
|c/n − P(W )| rP 0 (w ) n
P{|c/n − P(w )| > rP 0 (w )} = P{| q |> p },
P(w )(1−P(w )) P(w )(1 − P(w ))
n

P 0 (w ) ≈ P(w + 1) − P(w )
√
√ rP 0 (w ) n
= 2Φ(−θ 2), θ = p
2P(w )(1 − P(w ))
= erfc(θ)

For θ high enough, c/n ≈ P(w ) with precision ±rP 0 (w ).

Sutomore, Montenegro, 14.3.2017 21 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 22 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

P(w̄ ) ≈ Φ(u)
u = thr −(m−
√ w̄ )τ −w̄ (1−τ )
mτ (1−τ )
u 2
P 0 (w̄ ) ≈ − √ 1−2τ × √1 e − 2
mτ (1−τ ) 2π
θ2
n0 (r , w̄ ) = r 2 R(w̄ ) where:
R(w̄ ) = 2 P(w̄(P)(1−P(
0 (w̄ ))2
w̄ ))
,
1
r ∈ { 2 , 1} (the choice of r defines the desired precision of n0 in the given
context).

Sutomore, Montenegro, 14.3.2017 23 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 24 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

Theorem. Let pā,b̄,z̄ denote the probability of successfull authentication

following MIM modification (ā, b̄, z̄). Suppose (ā, b̄, z̄ = āX ⊕ b̄Y ⊕ ē) is
a triplet obtained by a passive eavesdropping of the (Random-)HB#
protocol, and w = kēk. Then:

thr X
l   
X w m−w
pā,b̄,z̄ = PB(w , thr ) = τ w +2l−2α (1−τ )m−(w +2l−2α)
α l −α
l=0 α=0

PB(w + 1, thr ) = p0 , if ēk = 0
pā,b̄,z̄k = ,
PB(w − 1, thr ) = p1 , if ēk = 1
where z̄k = z̄ ⊕ f̄k , and f̄k is the all zero-vector with exception that k-th bit
is 1.

Sutomore, Montenegro, 14.3.2017 25 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 26 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

Proof.
First, notice that:
m
X m
X m
X w
X m−w
X
ke ⊕ ēk = (ei + ēi ) = (ei + 1) + ei = s̃i + si ,
i=0 i=0 i=0 i=0 i=0
ēi =1 ēi =0

where si and s̃i are Bernoully random variables, such that p(si = 1) = τ
and p(s̃i = 1) = 1 − τ .

Sutomore, Montenegro, 14.3.2017 27 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 28 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

pā,b̄,z̄ = PB(w , thr )

= PB(ke ⊕ ēk ≤ thr )
thr
X
= P(ke ⊕ ēk = l)
l=0

X X }
thr min{l,w w
X m−w
X
= P( s̃i = α) · P( si = l − α)
l=0 α=0 i=0 i=0

X X } hw 
thr min{l,w i m − w  
= (1 − τ )α τ w −α τ l−α (1 − τ )m−w −l+α
l=0 α=0
α l −α

X } w m − w 
thr min{l,w
X
= τ w +l−2α (1 − τ )m−(w +l−2α)
l=0 α=0
α l −α

ke ⊕ ēk follows the so-called Poisson-Binomial distribution PB(w,thr).

Sutomore, Montenegro, 14.3.2017 29 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 30 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Theoretical reevaluation of the OOV attack

On the other hand, since


w + 1, if ēk = 0
kē ⊕ f̄k k = ,
w − 1, if ēk = 1
we have that:

pā,b̄,z̄k = P(ke ⊕ ē ⊕ f̄k k ≤ thr )


PB(w + 1, thr ), if ēk = 0
=
PB(w − 1, thr ), if ēk = 1

Sutomore, Montenegro, 14.3.2017 31 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Theoretical reevaluation of the OOV attack

Correction of the OOV MIM attack against Random-HB#

and HB#

Correction of the OOV Algorithm1 Approximating w̄

1: Input: ā, b̄, z̄, n
2: Output: P −1 ( nc ), an approximation of
w̄ = kāX ⊕ b̄Y ⊕ z̄k, where
P(w̄ ) = Pr [ke ⊕ ēk ≤ thr ]
Pmin{l,w } w
m−w
w +l−2α
= PB(w ) = thr (1 − τ )m−(w +l−2α)
P
l=0 α=0 α l−α
τ
3: Processing:
4: c=0
5: for i = 1..n do
6: During a session, modify messages:
7: adversary replaces b with b̂ = b ⊕ b̄
8: adversary replaces a with â = a ⊕ ā
9: adversary replaces z with ẑ = z ⊕ z̄
10: if Verifier accepts the modified response then
11: c =c +1
12: end if
13: end for
14: return argmin {c/n − PB(w )}
w ∈1...m Sutomore, Montenegro, 14.3.2017 32 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Emipirical reevaluation of the OOV attack

Presentation overview
1 Introduction
2 Random-HB# and HB# authentication protocols
3 Security of Random-HB# and HB# protocols
4 OOV MIM attack against Random-HB# and HB#
5 Emipirical evaluation of the OOV attack
6 Theoretical reevaluation of the OOV attack
7 Theoretical reevaluation of the OOV attack
8 Theoretical reevaluation of the OOV attack
9 Theoretical reevaluation of the OOV attack
10 Theoretical reevaluation of the OOV attack
11 Theoretical reevaluation of the OOV attack
12 Theoretical reevaluation of the OOV attack
13 Emipirical reevaluation of the OOV attack
Sutomore, Montenegro, 14.3.2017 33 /
Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Emipirical reevaluation of the OOV attack

Emipirical reevaluation of the OOV attack

OOV Algorithm 1 (estimation of the noise weight):

Empirical succes rate ≈ 0.045 for the noise vector of optimal weight
(w = 77 for the given parameter set).
For noise vector weight in [60, 90]: ≈ 0.124.
Increasing the sample size does not improve the imprecision.
Proposed OOV MIM attack is not empirically succesfull.

Corrected OOV Algorithm1 (with Poisson-Binomial distribution employed):

Empirical succes rate ≈ 0.994 for the noise vector of optimal weight
(w = 77 for the given parameter set).
For noise vector weight in [60, 90]: ≈ 0.992.
Corrected OOV MIM attack becomes empirically succesfull.

Sutomore, Montenegro, 14.3.2017 34 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Emipirical reevaluation of the OOV attack

Correction of the OOV MIM attack against Random-HB#

and HB#
 
thr −(m−w̄ )τ −w̄ (1−τ )
c/n ≈ P(w̄ ) = P(ke ⊕ ēk ≤ thr ) = PB(w , thr )≈ Φ √ , for n > n0 (r , w ).
mτ (1−τ )

Sutomore, Montenegro, 14.3.2017 35 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Thank you!

Power by: LATEX- GNU Free Documentation License

Sutomore, Montenegro, 14.3.2017 36 /

Siniša Tomović (sinisatom@turing.mi.sanu.ac.rs) 36
 Enhancing the Honeywords System
Mitigating Active Adversaries

Ziya Alper Genç Mehmet Sabır Kiraz Süleyman Kardaş

University of Luxembourg TÜBİTAK BİLGEM Batman University

COST CRYPTACUS Workshop, 2017

Enhancing the Honeywords System

1 / 17
N
 Password Breaches

We got used to hear in the news about password breaches

Yahoo: 1 Billion
MySpace: 427 Million
LinkedIn: 177 Million
Dropbox: 68 Million
Tumblr: 65 Million
Adobe, VK, eBay, Evernote,. . .

Password collector: 1.2 Billion credentials FOR SALE

Free service at https://haveibeenpwned.com/

Enhancing the Honeywords System

2 / 17
N
 When do we realize that the
credentials are stolen?

Enhancing the Honeywords System

3 / 17
N
When the attacker sells them!

Enhancing the Honeywords System

4 / 17
N
 Hash + Salts 6= Security

Basic8 policy for passwords

8 characters using a-z, A-Z, 0-9
53 minutes enough to crack a password hash
hashcat: GPU based cracking
NVIDIA GTX1080: 8.6 × 109 BH/s
Sagitta Brutalis 1080: 21169 USD
8 x NVIDIA GTX1080: 68.8 × 109 BH/s
Even faster and lower time
GPU fields

Enhancing the Honeywords System

5 / 17
N
 Top 500 Passwords

Enhancing the Honeywords System

6 / 17
N
 How to Mitigate Offline Dictionary Attacks

An adversary
steals password hashes

leaves the system

has powerful computational powers

i.e. can find a password from its hash

Enhancing the Honeywords System

7 / 17
N
Honeywords System (Juels & Rivest 2013)
Multiple possible passwords: sweetwords
green3DOGS, red2CATS, yellow7BIRDS
User ID Username Hashes
1 u1 H (sw1,1 ) , · · · , H (sw1,n )
Only one of them is genuine 2 u2 H (sw2,1 ) , · · · , H (sw2,n )
··· ··· ···
m um H (swm,1 ) , · · · , H (swm,n )
Others are called honeywords

Adversary cannot distinguish between them after cracking the

hashes

Detecting Password Breaches

Auxiliary server: Honeychecker
Knows the order of the real password
Responsible for monitoring and alarming: risk of being detected

Enhancing the Honeywords System

8 / 17
N
Honeywords – Registration

Enhancing the Honeywords System

9 / 17
N
Honeywords – Login

Enhancing the Honeywords System

10 / 17
N
 Honeywords Generation Methods

Tail tweaking: password = BG+7y45

Sweetwords: BG+7q03, BG+7m55, BG+7y45, BG+7o92

Digit tweaking: password = 57!flowers

Sweetwords: 42!flowers, 57!flowers, 18!flowers, 93!flowers

Password model: password = blue7DOGS

Sweetwords: yellow4CATS, red2DRAGONS, blue7DOGS

Enhancing the Honeywords System

11 / 17
N
Usability and Compatibility Requirements of the
Honeyword System

At least same security before introducing honeywords

Different administrative domains, operating systems

If Honeychecker is unavailable, system may continue to work

Number of honeywords per user can be tuned as desired

Enhancing the Honeywords System

12 / 17
N
 Security Analysis

Overall security improved

Adversary must obtain both the login server and the honeychecker to
obtain a user’s password.

Same password on different systems:

Intersection attack: Compare the sweetwords
Sweetword submission attack

Vulnerable to active attacks

Enhancing the Honeywords System

13 / 17
N
 Active Attacks

Login server gets compromised

Set a new order for password: SET commands

Honeychecker compromised

Arbitrarily responding to CHECK commands

Enhancing the Honeywords System

14 / 17
N
Enhanced Honeywords – Registration

Enhancing the Honeywords System

15 / 17
N
Enhanced Honeywords – Login

Enhancing the Honeywords System

16 / 17
N
Thanks for your attention.

Enhancing the Honeywords System

17 / 17
N
An Improved Man-in-the-Middle Attack
Against HB# Authentication Protocols

Miodrag Mihaljević, Siniša Tomović and Milica Knežević

Mathematical Institute of
Serbian Academy of Sciences and Arts

- COST CRYPTACUS Workshop -

14-15 March 2017, Sutomeore, Montenegro
1
 Roadmap
• Part I:
- Motivation for the Work
- Summary of the Results
• Part II: Key Technical Elements
- Advanced Recovery of the Noise Bits
- Advanced Construction & Solving the System
of Equations
• Part III:
A number of Numerical Illustrations
• Concluding Notes
2
 Part I

- Motivation for the work

- Summary of the Results

3
Basic References
I.2 Motivation for our work

A problem with OOV [2] MIM attack

A Problem with OOV MIM Attack
A Problem and Its Solution
I.2 An Improved MIM Attack Against
HB# Authentication Protocols
Summary of our approach and
achieved results
 Comparison of OOV MIM and the
Proposed One
OOV MIM Attack Advanced
ASIACRYPT 2008
Approach
Phase I: Evaluation of
the acceptance rate after
same same
modification

Phase II: Recovering bits Employing inversion of Employing optimal

of the error vector the Gaussian function Bayesian decision which
minimizes the probability
of error
Phase III: Recovering Employing a Part-by-part solving the
straightforward solving of system of equations
secret key bits
the system of equations
 Table 1: Comparison of the complexities
of Secret Key recovery

Random HB# HB#

Claimed complexity of
the MIM attack claimed
in [2] 230.1 221.7

Complexity of the
proposed improved MIM
attack 225.3 217.5

14
Table 2: Approximate Gain in the complexities of
Secret Key recovery for the same success rate.

Random HB# HB#

Achieved Gain
(approximation) 211 29

15
 Part II
- Advanced Recovery of the Noise Bits
- Advanced Construction & Solving the
System of Equations

16
Advanced Recovery of the
Noise Bits
• Theorem 1 provides • Accordingly, the
the background for probability of error in
optimal Bayesian estimation (for given
estimation of the sample) of the noise
noise vector bits. bits is minimized, and
accordingly the
probability is
maximized that the
correct system of
equations is
constructed.
Modules for the Cryptanalysis
Advanced Construction & Solving
the System of Equations
System of the Equations
a
X

+
. e
=
. z
aX + bY + e = z
 Part-by-Part Solve & Check
• Entire system of • Independent solving
equations could be and checking the
split into subsystems, solutions provides
and each subsystem that higher probability
could be solved and of error in estimation
checked of bits in the vector of
independently. noise is tolerated.
• The above provides
reduction of the attack
complexity.
 Part III

A Number of Numerical
Illustrations

25
Numerical Illustrations on the
Noise Bits Recovery
Acceptance rate as a function of the modification noise vector weight
when thr = 113, m=441,

27
Probability distributions of the acceptance rate for three
different weights w of the noise vector after 500
authentication attempts

28
Probability distributions of the acceptance rate for three
different weights w of the noise vector after 5000
authentication attempts

29
 Probability distribution of the Acceptance Score when the
flipped bit is “1” and “0”, respectively, when n=100 modified
authentication sessions are considered

30
 Probability distribution of the Acceptance Score when the
flipped bit is “1” and “0”, respectively, when n=1500 modified
authentication sessions are considered

31
 Probability distributions of 8-bit segment weights of the
modification noise vector after n=100 modified authentications

32
 Probability distributions of 8-bit segment weights of the
modification noise vector after n=1500 modified authentications

33
Histogram of required number of modified authentication for
correct recovery an 8-bit noise-segment of certain weight

34
 Numerical Illustrations of the
Gain Implied by Advanced
Solving System of the Equations
The probability of success recovery of x bits of
noise when the bit error rate is a parameter

36
The probability of success recovery of x bits of
noise as a function of the bit error rate

37
Concluding Notes

38
 Main Messages of the Talk
• Developing of • The talk points out that
advances in up to now
lightweight and
known MIM attack are
secure possible making that the
authentication problem of designing
protocols for IoT is a lightweight and secure
challenge. authentication protocols
appears as additionally
• An important request challenging one.
is that authentication • An improved MIM attack
protocols should be against HB# authentication
secure against protocols has been
powerful MIM attacks. proposed and its main
technical issues have been
discussed. 39
Thank You Very Much for the
Attention,
and
QUESTIONS Please!

40