P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\titulka.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\titulka.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\titulka.jpg
PV204 Security technologies
Trusted element, side channels attacks
Petr Švenda        svenda@fi.muni.cz        @rngsec
Centre for Research on Cryptography and Security, Masaryk University
D:\Documents\Obrázky\services_icon_full_bw5.jpg

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
The masterplan for this lab
1.Project, teams
2.Implementation of modular exponentiation (RSA)
3.Understand naïve and square&multiply algorithm
–Toy example with integers (32 bits)
4.Understand how to measure operation (clock())
–Pre-prepared functions – console or file output
–Visualization of multiple measurements (R, http://plot.ly...)
–What can be inferred from measurements
5.Use large datatype MPI instead of int (> 102 bits)
6.Understand blinding as protection technique
7.Assignment
2
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Project, teams, first deadline next week!
•Form group, exchange contact, agree periodic joint meetings
•Make sure you know what to do for the next deadline
–Form team, pick three certificates, book with me (9.3.2020)
–Analyze certificates, prepare report and presentation: (19.3.2020)
–
•
•
3
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Faster modexp: Square and multiply algorithm
•
•
•
•
•
•
•How to measure?
–Exact detection from simple power trace
–Extraction from overall time of multiple measurements
•
| PV204 TE, Side-channels LAB 5.3.2020
4
Gilbert Goodwill, http://www.embedded.com/print/4408435
// M = C^d mod N
// Square and multiply algorithm
x = C                         // start with ciphertext
for j = 1 to n {           // process all bits of private exponent
    x = x*x mod N       // shift to next bit by x * x (always)
    if (d_j == 1) {      // j-th bit of private exponent d
      x = x*C mod N    // if 1 then multiple by Ciphertext
    }
}
return x       // plaintext M
Executed always

How to attack:
-What if you have debugger?
-What if you have just breakpoint inside d_j condition?

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Naïve vs. square and multiply algorithm
•SideChannelExercise.zip source code from IS
•Inspect naïve and square&multiply algorithm
–Limited to integers (unsigned long) for simplicity
•Measure timings
–Pre-prepared measurement functions
•measureExponentiation()
–clock() used for measurement (usually 1ms granularity)
•measureExponentiationRepeat()
–Make defined number of repeats and stores results into file
•Identify dependency of algorithm on secret value
5
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Setup
•Create new Visual Studio 2015 Project
–File->New->Project->VisualC++->Win32 Console app
–Turn off ‘Precompiled header’ and ‘SDL checks’
•Paste SideChannelExercise.cpp from IS instead of project’s main file
•Copy all remaining files into directory where stdafx.cpp is
•Add bignum.c into compilation
–Solution->Source files->Add->Existing item
•Try to compile
•Insert breakpoint (begin of main()) – F9
•Run program in debug mode – F5
•Execute next step of program – F10
6
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Naïve modular exponentiation algorithm
•
•
•
•
•
•
•What is disadvantage of this algorithm?
•Is algorithm vulnerable to timing side-channel?
•Is algorithm vulnerable to another side-channel?
7
| PV204 TE, Side-channels LAB 5.3.2020
typedef unsigned long ULONG;
const int ULONG_LENGTH = sizeof(ULONG);
ULONG naiveExponentiation(ULONG message, ULONG exponent, ULONG modulus) {
       ULONG result = message;
       for (int i = 1; i < exponent; i++) {
               // result = (result * message) % modulus; // this may cause type overflow
               result *= message;
               result %= modulus;
       }
       return result;
}

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
–
8
| PV204 TE, Side-channels LAB 5.3.2020
typedef unsigned long ULONG;
const int ULONG_LENGTH = sizeof(ULONG);
ULONG squareAndMultiply(ULONG message, ULONG exponent, ULONG modulus) {
       // Obtain effective length of exponent in bits
       int sizeExponent = ULONG_LENGTH;
       ULONG mask = 1;
       ULONG bit = 0;
       for (int i = 0; i < ULONG_LENGTH * 8; i++) {
               bit = exponent & mask;
               if (bit != 0) { sizeExponent = i + 1; }
               mask <<= 1;
       }
       // Compute square and multiply algorithm
       ULONG result = 1;
       for (int i = sizeExponent - 1; i >= 0; i--) {
               //result = (result * result) % modulus; // this may cause type overflow
               result *= result;
               result %= modulus;
               if ((exponent & (1 << i)) != 0) { // given bit is not 0
                       // result = (result * message) % modulus; // this may cause type overflow
                       result *= message;
                       result %= modulus;
               }
       }
       return result;
}

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Pair activity: Analysis of square&multiply algorithm
•Form pairs (e.g., with your neighbour) [21 minutes]
•Look and code together (before ready to answer the question)
•Two roles:
–Educator – explains the answer to the given question to his/her pair
–Sceptic – tries to find any flaw or weak point in Educator’s reasoning
•Educator keep explaining until Sceptic can’t find any flaw
–not more than 3 mins per question
–Sceptic notes down interesting issues raised
•Switch roles after every question (from next slide)
•
•
•
| PV204 TE, Side-channels LAB 5.3.2020
9

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Pair activity: Analysis of square&multiply algorithm
•Pre-prepared function squareAndMultiply()
1.What is advantage of this algorithm with respect to naïve algorithm?
2.Is int (ULONG) enough for cryptographic security?
3.Is algorithm vulnerable to timing side-channel?
4.Which part of code is dependent on secret value?
5.
•Pre-prepared function  measureExponentiation(65535, 65535, 10000003L, SQUAREANDMULTIPLY);
1.How is measured time depending on a secret value?
2.Is this algorithm easier or harder for attacker to mount timing attack wrt naïve exp?
3.How to mask dependency on secret exponent?
•
10
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Big integers (MPI from mbedTLS library)
•32 bits are not enough, 4096 is recommended (RSA)
–No native type in C/C++, use mbedTLS’s MPI
•
11
| PV204 TE, Side-channels LAB 5.3.2020
void squareAndMultiplyMPI(const mpi* message, const mpi* exponent, const mpi* modulus,
                                         mpi* result) {
       // Obtain length of exponent in bits
       int sizeExponent = 0;
       int maxBitLength = mpi_size(exponent) * 8;
       for (int i = 0; i < maxBitLength; i++) {
               if (mpi_get_bit(exponent, i) != 0) { sizeExponent = i + 1; }
       }
       // Compute square and multiply algorithm
       mpi_lset(result, 1);
       for (int i = sizeExponent - 1; i >= 0; i--) {
               mpi_mul_mpi(result, result, result); // result *= result;
               mpi_mod_mpi(result, result, modulus); // result %= modulus;
               if (mpi_get_bit(exponent, i) != 0) { // given bit is not 0
    mpi_mul_mpi(result, result, message);
                   mpi_mod_mpi(result, result, modulus);
               }
       }}

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Create large (pseudo-)random MPI
•generateRNG() is function callback to fill single int
12
| PV204 TE, Side-channels LAB 5.3.2020
mpi message; mpi_init(&message);
mpi exponent; mpi_init(&exponent);
mpi modulus; mpi_init(&modulus);
// Cryptographically large number (2048b)
const int NUMBER_SIZE = 256;
// Init with pseudorandom values (prng will always start with same value)
mpi_fill_random(&message, NUMBER_SIZE, generateRNG, NULL);
mpi_fill_random(&exponent, NUMBER_SIZE, generateRNG, NULL);
mpi_fill_random(&modulus, NUMBER_SIZE, generateRNG, NULL);
// Fix MSb and LSb of modulus to 1
modulus.p[0] |= 1; mpi_set_bit(&modulus, 1, 1);

measureExponentiationMPI(&message, &exponent, &modulus, SQUAREANDMULTIPLY);

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Measure times with MPI
•Operation with large MPI can be measured
–100s-1000s ms
•Visualize histogram of multiple measurements
–Pre-prepared measurements functions with file output
•measureExponentiationRepeat()
–https://plot.ly (Histogram, Traces®Range/bins 1)
–pyplot, R…
•Try repeated measurement with the same data
•Try repeated measurement with the different data
•Are measured times constant? Why?
•
•
13
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Fix: Blinding
•Create squareAndMultiplyBlindedMPI() as improved version of squareAndMultiplyMPI()
1.Generate random value r and compute re mod N
2.Compute blinded ciphertext b = c * re mod N
3.Decrypt b and then divide result by r
4.
4.
4.
•(r is random number, but invertible mod N)
•
14
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Defense introduced by OpenSSL
•RSA blinding: RSA_blinding_on()
–https://www.openssl.org/news/secadv_20030317.txt
•Decryption without protection: M = cd mod N
•Blinding of ciphertext c before decryption
1.Generate random value r and compute re mod N
2.Compute blinded ciphertext b = c * re mod N
3.Decrypt b and then divide result by r
•r is removed and only decrypted plaintext remains
–
–
–
–
–
15
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
•
16
| PV204 TE, Side-channels LAB 5.3.2020

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Assignment 2: Protection via bogus branch
•Modify squareAndMultiplyMPI() code (use version without blinding)
–When exponent’s bit is not 1, add “bogus” branch as a protection against leakage
–
•Perform analysis on the original and protected version
–Timing measurements for 1000 measurements, visualize as histograms
–Scenario 1: Same data, same exponent
–Scenario 2: Same exponent, low hamming weight of data
–Scenario 3: Same exponent, high hamming weight of data
–Scenario 4: Low/high hw exponent and random data
–Optional: add 1-2 other sensible scenarios
•Compile and evaluate in Debug and Release profiles
–Can you observe any difference? Why? What are security implications?
•IMPORTANT: Think! Some scenarios make sense. Some not.
–Make explicit claim in discussion of every scenario if it makes sense from security point of view
17
| PV204 Trusted element 22.2.2017
 if (mpi_get_bit(exponent, i) != 0) { // given bit is not 0)

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Assignment – what to submit
•Source code of your protected operation
•2 pages of text and figures
–Describe how bogus branch is removing the dependency of execution time on the secret exponent
–Description of setup (methodology, sw, hw)
–Visualized measurements (histograms, 4 scenarios)
–Discussion of difference observed
–Discussion of attack feasibility against original/protected implementation
•Submit before 12.3. 23:59am into IS HW vault
–Soft deadline: -1.5 points for every started 24 hours
•
18
| PV204 Trusted element 22.2.2017

P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
P:\CRCS\2012_0178_Redesign_loga_a_JVS\PPT_prezentace\sablona\pracovni\normalni.jpg
                       www.crcs.cz/rsa  @CRoCS_MUNI
Example vizualization (credits: J. Masarik)
19
| PV204 TE, Side-channels LAB 5.3.2020