

(47 intermediate revisions by 3 users not shown) 
Line 1: 
Line 1: 
−  == RSA Attack Theory ==
 +  {{WarningboxThis tutorial has been updated for ChipWhisperer 5 release. If you are using 4.x.x or 3.x.x see the "V4" or "V3" link in the sidebar.}} 
−  We won't go into what RSA is, see the [[wikipedia:RSA_(cryptosystem)RSA Wikipedia]] article for a quick background. What we really care about is the following pieces of sudocode from that article used in decrypting a message:
 +  {{WarningboxThis tutorial works differently than in V4, now utilizing a fault attack instead of a power analysis attack.}} 
   
−  <syntaxhighlight lang="C">
 +  {{Infobox tutorial 
−  /**
 +  name = B11: Breaking RSA 
−  * Decrypt
 +  image = 
−  *
 +  caption = 
−  * @param {c} int / bigInt: the 'message' to be decoded (encoded with RSA.encrypt())
 +  software versions = 
−  * @param {d} int / bigInt: d value returned from RSA.generate() aka private key
 +  capture hardware = 
−  * @param {n} int / bigInt: n value returned from RSA.generate() aka public key (part I)
 +  Target Device = 
−  * @returns {bigInt} decrypted message
 +  Target Architecture = Arm 
−  */
 +  Hardware Crypto = No 
−  RSA.decrypt = function(c, d, n){
 +  Purchase Hardware = 
−  return bigInt(c).modPow(d, n);
 +  }} 
−  };  +  <! To edit this, edit Template:Tutorial_boilerplate > 
−  </syntaxhighlight>  +  {{Tutorial boilerplate}} 
   
−  The most critical piece of information is that value ''d''. It contains the private key, which if leaked would mean a compromise of the entire system. So let's assume we can monitor a target device while it decrypts any message (we don't even care what the message is). Our objective is to recover d.
 +  * Jupyter file: '''Fault_5RSA_Fault_Attack.ipynb''' 
   
−  Let's consider our actual target code, which will be the RSA implementation in avrcryptolib. This has been copied over to be part of the ChipWhisperer repository, and you can see the implementation [https://github.com/newaetech/chipwhisperer/blob/master/hardware/victims/firmware/crypto/avrcryptolib/rsa/rsa_basic.c#L163in rsa_basic.c of rsa_dec()]. The function in question looks like this:
 
   
−  <syntaxhighlight lang="c">
 +  == XMEGA Target == 
−  uint8_t rsa_dec(bigint_t* data, const rsa_privatekey_t* key){
 +  
−  if(key>n == 1){
 +  
−  bigint_expmod_u(data, data, &(key>components[0]), &key>modulus);
 +  
−  return 0;
 +  
−  }
 +  
−  if(key>n == 5){
 +  
−  if (rsa_dec_crt_mono(data, key)){
 +  
−  return 3;
 +  
−  }
 +  
−  return 0;
 +  
−  }
 +  
−  if(key>n<8  (key>n5)%3 != 0){
 +  
−  return 1;
 +  
−  }
 +  
−  //rsa_dec_crt_multi(data, key, (key>n5)/3);
 +  
−  return 2;
 +  
−  }
 +  
−  </syntaxhighlight>
 +  
   
−  We'll consider the case where ''key>n == 5'', so we have the ''rsa_dec_crt_mono()'' to attack. You can see that function [https://github.com/newaetech/chipwhisperer/blob/master/hardware/victims/firmware/crypto/avrcryptolib/rsa/rsa_basic.c#L53at Line 53 of that same file]. I've removed all the debug code in the following so you can better see the program flow:
 +  This tutorial is not available for XMEGA targets. 
   
−  <syntaxhighlight lang="c">
 +  == ChipWhispererLite ARM / STM32F3 Target == 
−  uint8_t rsa_dec_crt_mono(bigint_t* data, const rsa_privatekey_t* key){
 +  
−  bigint_t m1, m2;
 +  
−  m1.wordv = malloc((key>components[0].length_B /* + 1 */) * sizeof(bigint_word_t));
 +  
−  m2.wordv = malloc((key>components[1].length_B /* + 1 */) * sizeof(bigint_word_t));
 +  
−  if(!m1.wordv  !m2.wordv){
 +  
−  //Out of memory error
 +  
−  free(m1.wordv);
 +  
−  free(m2.wordv);
 +  
−  return 1;
 +  
−  }
 +  
−  bigint_expmod_u(&m1, data, &(key>components[2]), &(key>components[0]));
 +  
−  bigint_expmod_u(&m2, data, &(key>components[3]), &(key>components[1]));
 +  
−  bigint_sub_s(&m1, &m1, &m2);
 +  
−  while(BIGINT_NEG_MASK & m1.info){
 +  
−  bigint_add_s(&m1, &m1, &(key>components[0]));
 +  
−  }
 +  
   
−  bigint_reduce(&m1, &(key>components[0]));
 +  See the following for using: 
−  bigint_mul_u(data, &m1, &(key>components[4]));
 +  * ChipWhispererLite 32bit (STM32F3 Target) 
−  bigint_reduce(data, &(key>components[0]));
 +  * ChipWhispererLite Capture + STM32F3 Target on UFO Board (including NAESCAPACKL1/L2 users) 
−  bigint_mul_u(data, data, &(key>components[1]));
 +  * ChipWhispererPro + STM32F3 Target on UFO Board 
−  bigint_add_u(data, data, &m2);
 +  
−  free(m2.wordv);
 +  
−  free(m1.wordv);
 +  
−  return 0;
 +  
−  }
 +  
−  </syntaxhighlight>
 +  
   
 +  https://chipwhisperer.readthedocs.io/en/latest/tutorials/fault_5openadccwlitearm.html#tutorialfault5openadccwlitearm 
   
−  Note all the calls to <code>bigint_expmod_u()</code> with the private key material. If we could attack that function, all would be lost. These functions are elsewhere  it's in the [https://github.com/newaetech/chipwhisperer/blob/master/hardware/victims/firmware/crypto/avrcryptolib/bigint/bigint.c#L812 bigint.c file at Line 812]. Again we can see the source code here:
 +  == ChipWhisperer Nano Target == 
   
−  <syntaxhighlight lang="c">
 +  This tutorial is not available for the ChipWhisperer Nano. 
−  oid bigint_expmod_u(bigint_t* dest, const bigint_t* a, const bigint_t* exp, const bigint_t* r){
 +  
−  if(a>length_B==0  r>length_B==0){
 +  
−  return;
 +  
−  }
 +  
−   +  
−  bigint_t res, base;
 +  
−  bigint_word_t t, base_b[MAX(a>length_B,r>length_B)], res_b[r>length_B*2];
 +  
−  uint16_t i;
 +  
−  uint8_t j;
 +  
−  res.wordv = res_b;
 +  
−  base.wordv = base_b;
 +  
−  bigint_copy(&base, a);
 +  
−  bigint_reduce(&base, r);
 +  
−  res.wordv[0]=1;
 +  
−  res.length_B=1;
 +  
−  res.info = 0;
 +  
−  bigint_adjust(&res);
 +  
−  if(exp>length_B == 0){
 +  
−  bigint_copy(dest, &res);
 +  
−  return;
 +  
−  }
 +  
−  uint8_t flag = 0;
 +  
−  t=exp>wordv[exp>length_B  1];
 +  
−  for(i=exp>length_B; i > 0; i){
 +  
−  t = exp>wordv[i  1];
 +  
−  for(j=BIGINT_WORD_SIZE; j > 0; j){
 +  
−  if(!flag){
 +  
−  if(t & (1<<(BIGINT_WORD_SIZE1))){
 +  
−  flag = 1;
 +  
−  }
 +  
−  }
 +  
−  if(flag){
 +  
−  bigint_square(&res, &res);
 +  
−  bigint_reduce(&res, r);
 +  
−  if(t & (1<<(BIGINT_WORD_SIZE1))){
 +  
−  bigint_mul_u(&res, &res, &base);
 +  
−  bigint_reduce(&res, r);
 +  
−  }
 +  
−  }
 +  
−  t<<=1;
 +  
−  }
 +  
−  }
 +  
−   +  
−  SET_POS(&res);
 +  
−  bigint_copy(dest, &res);
 +  
−  }
 +  
−  </syntaxhighlight>
 +  
−   +  
−  Within that file, the part is the loop at the end. This is actually going through and doing the required ''a**exp % r '' function. If you look closely into that loop, you can see there is a variable <code>t</code>, which is set to the value <code>t = exp>wordv[i  1];</code>. After each run through the loop it is shifted left one. That <code>t</code> variable contains the private key, and the reason it is shifted left is the following piece of code is checking if the MSB is '0' or '1':
 +  
−   +  
−  <syntaxhighlight lang="c">
 +  
−  bigint_square(&res, &res);
 +  
−  bigint_reduce(&res, r);
 +  
−  if(t & (1<<(BIGINT_WORD_SIZE1))){
 +  
−  bigint_mul_u(&res, &res, &base);
 +  
−  bigint_reduce(&res, r);
 +  
−  }
 +  
−  </syntaxhighlight>
 +  
−   +  
−  What does this mean? While there is datadependent code execution! If we could determine the program flow, we could simply '''read the private key off one bit at a time'''. This will be our attack on RSA that we perform in this tutorial.
 +  
−   +  
−  == Hardware Setup ==
 +  
−   +  
−  == Building Example ==
 +  
−   +  
−  == Finding SPA Leakage ==
 +  
−   +  
−  We'll now get into experimenting with the SPA leakage. To do so we'll use the "SPA Setup" script, then make a few modifications.
 +  
−   +  
−  Run the SPA setup script.
 +  
−   +  
−  Change the CLKGEN to be CLKGEN x1 via DCM
 +  
−   +  
−  [[File:B11_clkgenx1.png400px]]
 +  
−   +  
−  Change the length of the trigger to be 24000 samples:
 +  
−   +  
−  [[File:B11_settriglen.png400px]]
 +  
−   +  
−  If you are using Capture V3.5.2 or later you will have support for the length of the trigger output being high reported back to you. If you run capture1 for example you'll see the trigger was high for XX cycles:
 +  
−   +  
−  This is way too long! You won't be able to capture the entire trace in your 24000 length sample buffer. Instead we'll make the demo even shorter  in our case looking at the source code you can see there is a "flag" which is set high only AFTER the first 1 is received. Thus using a fixed plaintext, change the input plaintext to be
 +  
−   +  
−  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
 +  
−   +  
−  We'll only be able to change the LAST TWO bytes, everything else will be too slow. So change the input plaintext to
 +  
−   +  
−  00 00 00 00 00 00 00 00 00 00 00 00 00 00 80 00
 +  
−   +  
−  And you can see the power trace change drastically, as below:
 +  
−   +  
−  [[File:B11_RSA_example8000.png400px]]
 +  
−   +  
−  Finally, let's flip another bit. Change the input plaintext as follows, such that bit #4 in the final bit is set HIGH. We can plot the two power traces on top of each other, and you see that they are differing at a specific point in time:
 +  
−   +  
−  [[File:B11_RSA_bit4diff.png400px]]
 +  
−   +  
−  Walking back from the right, you can see this almost directly matches bit numbering for those last two bytes:
 +  
−   +  
−  [[File:B11_RSA_example8010_annotated.png400px]]
 +  
−   +  
−   +  
−  [[File:B11_plaintext_setting.png400px]]
 +  
−   +  
−  [[File:B11_acqsetting.png400px]]
 +  
−   +  
−   +  
−  == Automating Attack ==
 +  
−   +  
−  The final step is to automate this attack. There are a few ways to do this  we'll demonstrate a basic method, that you can extend to do a complete attack. In this example we're going to use a repeatable sequence, and look for the delay between this sequence. If we see a larger delay we know a squaremultiply has occurred, otherwise it was only a square.
 +  
−   +  
−  We'll simply define a "reference" sequence, and look for this sequence in the rest of the power trace. The following will be done in regular old Python, so start up your favorite Python editor to finish off the tutorial.
 +  
−   +  
−  Our objectives are to do the following:
 +  
−   +  
−  # Load the trace file.
 +  
−   +  
−  # Find a suitable reference pattern.
 +  
−   +  
−  # Using the reference pattern, find the timing information and break the RSA power trace.
 +  