As of August 2020 the site you are on (wiki.newae.com) is deprecated, and content is now at rtfm.newae.com.

Difference between revisions of "Tutorial B11 Breaking RSA"

From ChipWhisperer Wiki
Jump to: navigation, search
(→‎RSA Attack Theory)
 
(56 intermediate revisions by 3 users not shown)
Line 1: Line 1:
−
== RSA Attack Theory ==
+
{{Warningbox|This 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:
+
{{Warningbox|This 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_5-RSA_Fault_Attack.ipynb'''
  
−
Let's consider our actual target code, which will be the RSA implementation in avr-crypto-lib. 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#L163|in 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->n-5)%3 != 0){
+
−
return 1;
+
−
}
+
−
//rsa_dec_crt_multi(data, key, (key->n-5)/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#L53|at 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">
+
== ChipWhisperer-Lite 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]));
+
* ChipWhisperer-Lite 32-bit (STM32F3 Target)
−
bigint_reduce(data, &(key->components[0]));
+
* ChipWhisperer-Lite Capture + STM32F3 Target on UFO Board (including NAE-SCAPACK-L1/L2 users)
−
bigint_mul_u(data, data, &(key->components[1]));
+
* ChipWhisperer-Pro + 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_5-openadc-cwlitearm.html#tutorial-fault-5-openadc-cwlitearm
  
−
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_SIZE-1))){
+
−
flag = 1;
+
−
}
+
−
}
+
−
if(flag){
+
−
bigint_square(&res, &res);
+
−
bigint_reduce(&res, r);
+
−
if(t & (1<<(BIGINT_WORD_SIZE-1))){
+
−
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_SIZE-1))){
+
−
bigint_mul_u(&res, &res, &base);
+
−
bigint_reduce(&res, r);
+
−
}
+
−
</syntaxhighlight>
+
−
 
+
−
What does this mean? While there is data-dependent 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.
+

Latest revision as of 05:26, 29 July 2019

This 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.

This tutorial works differently than in V4, now utilizing a fault attack instead of a power analysis attack.

B11: Breaking RSA
Target Architecture Arm
Hardware Crypto No
Software Release V3 / V4 / V5

This tutorial will introduce you to measuring the power consumption of a device under attack. It will demonstrate how you can view the difference between assembly instructions. In ChipWhisperer 5 Release, the software documentation is now held outside the wiki. See links below.

To see background on the tutorials see the Tutorial Introduction on ReadTheDocs, which explains what the links below mean. These wiki pages (that you are reading right now) only hold the hardware setup required, and you have to run the Tutorial via the Jupyter notebook itself. The links below take you to the expected Jupyter output from each tutorial, so you can compare your results to the expected/known-good results.

Running the tutorial uses the referenced Jupyter notebook file.

  • Jupyter file: Fault_5-RSA_Fault_Attack.ipynb


XMEGA Target

This tutorial is not available for XMEGA targets.

ChipWhisperer-Lite ARM / STM32F3 Target

See the following for using:

  • ChipWhisperer-Lite 32-bit (STM32F3 Target)
  • ChipWhisperer-Lite Capture + STM32F3 Target on UFO Board (including NAE-SCAPACK-L1/L2 users)
  • ChipWhisperer-Pro + STM32F3 Target on UFO Board

https://chipwhisperer.readthedocs.io/en/latest/tutorials/fault_5-openadc-cwlitearm.html#tutorial-fault-5-openadc-cwlitearm

ChipWhisperer Nano Target

This tutorial is not available for the ChipWhisperer Nano.

Retrieved from "http://wiki.newae.com/index.php?title=Tutorial_B11_Breaking_RSA&oldid=4083"