How to avoid side channel attacks when handling large numbers?
up vote
8
down vote
favorite
For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, Elliptic Curve, etc.
We have seen lots of side channel attacks due to timing differences or power usages analysis.
- How are large numbers handled in cryptography and cryptanalysis?
- What are the good libraries against side-channel attacks, including time and power analysis?
- Can we have a countermeasure to Acoustic cryptanalysis by a specific big number implementation?
modular-arithmetic side-channel-attack arithmetic
add a comment |
up vote
8
down vote
favorite
For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, Elliptic Curve, etc.
We have seen lots of side channel attacks due to timing differences or power usages analysis.
- How are large numbers handled in cryptography and cryptanalysis?
- What are the good libraries against side-channel attacks, including time and power analysis?
- Can we have a countermeasure to Acoustic cryptanalysis by a specific big number implementation?
modular-arithmetic side-channel-attack arithmetic
1
Try GMP
– AleksanderRas
Nov 7 at 11:58
I could be wrong but for counter mode AES the implementation could do all the big number maths in parallel or the day before, then just XOR bits when required.
– daniel
Nov 7 at 12:17
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
Nov 7 at 14:48
3
Reading your question more closely, I see that it focuses mostly on avoiding side channel attacks, but its current title does not really reflect that. I would recommend editing the title to make that clearer. Maybe something like "How to avoid side channel attacks when handling large numbers?"
– Ilmari Karonen
Nov 7 at 14:55
1
@daniel That doesn't make sense. First of all, AES doesn't use big number math. Second, generally the IV only is known when the bytes are required. In practice I haven't seen caching of a CTR-generated key stream far in advance; if CTR is cached at all it would be because of performance reasons (but I don't see that either).
– Maarten Bodewes
Nov 7 at 19:07
add a comment |
up vote
8
down vote
favorite
up vote
8
down vote
favorite
For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, Elliptic Curve, etc.
We have seen lots of side channel attacks due to timing differences or power usages analysis.
- How are large numbers handled in cryptography and cryptanalysis?
- What are the good libraries against side-channel attacks, including time and power analysis?
- Can we have a countermeasure to Acoustic cryptanalysis by a specific big number implementation?
modular-arithmetic side-channel-attack arithmetic
For cryptography, the platforms have limited size as 32 or 64-bit operations. We definitely need big numbers to implement the encryption/decryption and digital signatures for cryptosystems like RSA, Elliptic Curve, etc.
We have seen lots of side channel attacks due to timing differences or power usages analysis.
- How are large numbers handled in cryptography and cryptanalysis?
- What are the good libraries against side-channel attacks, including time and power analysis?
- Can we have a countermeasure to Acoustic cryptanalysis by a specific big number implementation?
modular-arithmetic side-channel-attack arithmetic
modular-arithmetic side-channel-attack arithmetic
edited Nov 8 at 10:20
asked Nov 7 at 11:07
kelalaka
2,864626
2,864626
1
Try GMP
– AleksanderRas
Nov 7 at 11:58
I could be wrong but for counter mode AES the implementation could do all the big number maths in parallel or the day before, then just XOR bits when required.
– daniel
Nov 7 at 12:17
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
Nov 7 at 14:48
3
Reading your question more closely, I see that it focuses mostly on avoiding side channel attacks, but its current title does not really reflect that. I would recommend editing the title to make that clearer. Maybe something like "How to avoid side channel attacks when handling large numbers?"
– Ilmari Karonen
Nov 7 at 14:55
1
@daniel That doesn't make sense. First of all, AES doesn't use big number math. Second, generally the IV only is known when the bytes are required. In practice I haven't seen caching of a CTR-generated key stream far in advance; if CTR is cached at all it would be because of performance reasons (but I don't see that either).
– Maarten Bodewes
Nov 7 at 19:07
add a comment |
1
Try GMP
– AleksanderRas
Nov 7 at 11:58
I could be wrong but for counter mode AES the implementation could do all the big number maths in parallel or the day before, then just XOR bits when required.
– daniel
Nov 7 at 12:17
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
Nov 7 at 14:48
3
Reading your question more closely, I see that it focuses mostly on avoiding side channel attacks, but its current title does not really reflect that. I would recommend editing the title to make that clearer. Maybe something like "How to avoid side channel attacks when handling large numbers?"
– Ilmari Karonen
Nov 7 at 14:55
1
@daniel That doesn't make sense. First of all, AES doesn't use big number math. Second, generally the IV only is known when the bytes are required. In practice I haven't seen caching of a CTR-generated key stream far in advance; if CTR is cached at all it would be because of performance reasons (but I don't see that either).
– Maarten Bodewes
Nov 7 at 19:07
1
1
Try GMP
– AleksanderRas
Nov 7 at 11:58
Try GMP
– AleksanderRas
Nov 7 at 11:58
I could be wrong but for counter mode AES the implementation could do all the big number maths in parallel or the day before, then just XOR bits when required.
– daniel
Nov 7 at 12:17
I could be wrong but for counter mode AES the implementation could do all the big number maths in parallel or the day before, then just XOR bits when required.
– daniel
Nov 7 at 12:17
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
Nov 7 at 14:48
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
Nov 7 at 14:48
3
3
Reading your question more closely, I see that it focuses mostly on avoiding side channel attacks, but its current title does not really reflect that. I would recommend editing the title to make that clearer. Maybe something like "How to avoid side channel attacks when handling large numbers?"
– Ilmari Karonen
Nov 7 at 14:55
Reading your question more closely, I see that it focuses mostly on avoiding side channel attacks, but its current title does not really reflect that. I would recommend editing the title to make that clearer. Maybe something like "How to avoid side channel attacks when handling large numbers?"
– Ilmari Karonen
Nov 7 at 14:55
1
1
@daniel That doesn't make sense. First of all, AES doesn't use big number math. Second, generally the IV only is known when the bytes are required. In practice I haven't seen caching of a CTR-generated key stream far in advance; if CTR is cached at all it would be because of performance reasons (but I don't see that either).
– Maarten Bodewes
Nov 7 at 19:07
@daniel That doesn't make sense. First of all, AES doesn't use big number math. Second, generally the IV only is known when the bytes are required. In practice I haven't seen caching of a CTR-generated key stream far in advance; if CTR is cached at all it would be because of performance reasons (but I don't see that either).
– Maarten Bodewes
Nov 7 at 19:07
add a comment |
2 Answers
2
active
oldest
votes
up vote
22
down vote
accepted
I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).
Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.
Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.
BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.
An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.
1
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
add a comment |
up vote
3
down vote
This answer tackles mostly the first bullet:
How are large numbers handled in cryptography and cryptanalysis?
Getting the result
Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g. thousands bits in RSA). The straightforward solutions to that issue are:
- Using a language without such limitation (like Python, GP/Pari, Mathematica..)
- Implementing the algorithms taught in elementary school for manual computation in decimal, using the language's constructs. Any Turing-complete language allows that. Coding such "bignum" library is a good but difficult exercise in programming. In languages which allow to overload arithmetic operators like
+
-
*
/
%
, simple expressions can keep a natural look. That can be extended to bases larger than 10 (like 16=24, 28, 216, 232..):+
-
have complexity $O(n)$, and schoolbook algorithms for*
/
%
are $O(n^2)$, where $n$ is a number of digits; a large base reduces $n$ and can boost performance. - Using a ready-made implementation of the previous approach.
- Using an external library, which might use another language; e.g. GMP.
Other issues
Either of the above works for educational purposes. But a cryptographer or cryptanalyst often has special needs:
- Security against timing attacks, where the duration of the computation is measured by an adversary and used to infer information about what's manipulated. While it might be possible to live with data-dependent timing using workarounds like blinding (as performed in some Java crypto libraries including Bouncy Castle), that's brittle. Ideally, a bignum library should be written from the grounds up to avoid data-dependent timing. That's hard, but BearSSL shows it's within human reach (Thomas Pornin only pretends to be a bear).
- Security against other side-channel attacks
- analysis of hardware-related emissions like power/EMI/acoustic (the later really is a form of the former, where fluctuations in CPU power consumption become sound, usually thru magnetostriction in power-supply coils, conceivably thru piezoelectric effect in capacitors)
- information leak to other attacker-controlled processes on the same hardware thru shared resources like memory, cache(s), branch predictors, arithmetic units..
- Performance (speed, computer resources)
The cryptographer should at least consider 1 and 2 when anything confidential is involved, which is often. However, when checking integrity of public data by verifying a digital signature, 1 and 2 are non-issues, as long as an adversary can not bypass the verification (perhaps by fault injection attack or some software bypass).
Performance (3) matters to many applications, and often limits what cryptanalysis (including factorization) can hope achieve.
Bibiography
For fast computer arithmetic, a useful reference is Richard P. Brent and Paul Zimmermann's Modern Computer Arithmetic, published by Cambridge University Press, 2010.
Somewhat dated, but simpler and more focused on cryptography: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, chapter 14, published by CRC Press, 1996.
Neither of these reference focus on constant-timeness. For this with decent speed, the underlying hardware first needs to be carefully analyzed, as did BearSSL.
add a comment |
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
22
down vote
accepted
I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).
Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.
Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.
BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.
An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.
1
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
add a comment |
up vote
22
down vote
accepted
I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).
Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.
Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.
BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.
An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.
1
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
add a comment |
up vote
22
down vote
accepted
up vote
22
down vote
accepted
I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).
Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.
Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.
BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.
An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.
I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).
Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.
Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.
BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.
An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.
answered Nov 7 at 14:36
Thomas Pornin
67.4k12177255
67.4k12177255
1
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
add a comment |
1
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
1
1
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
That was an excellent writeup on the mathematics.
– b degnan
Nov 8 at 16:09
add a comment |
up vote
3
down vote
This answer tackles mostly the first bullet:
How are large numbers handled in cryptography and cryptanalysis?
Getting the result
Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g. thousands bits in RSA). The straightforward solutions to that issue are:
- Using a language without such limitation (like Python, GP/Pari, Mathematica..)
- Implementing the algorithms taught in elementary school for manual computation in decimal, using the language's constructs. Any Turing-complete language allows that. Coding such "bignum" library is a good but difficult exercise in programming. In languages which allow to overload arithmetic operators like
+
-
*
/
%
, simple expressions can keep a natural look. That can be extended to bases larger than 10 (like 16=24, 28, 216, 232..):+
-
have complexity $O(n)$, and schoolbook algorithms for*
/
%
are $O(n^2)$, where $n$ is a number of digits; a large base reduces $n$ and can boost performance. - Using a ready-made implementation of the previous approach.
- Using an external library, which might use another language; e.g. GMP.
Other issues
Either of the above works for educational purposes. But a cryptographer or cryptanalyst often has special needs:
- Security against timing attacks, where the duration of the computation is measured by an adversary and used to infer information about what's manipulated. While it might be possible to live with data-dependent timing using workarounds like blinding (as performed in some Java crypto libraries including Bouncy Castle), that's brittle. Ideally, a bignum library should be written from the grounds up to avoid data-dependent timing. That's hard, but BearSSL shows it's within human reach (Thomas Pornin only pretends to be a bear).
- Security against other side-channel attacks
- analysis of hardware-related emissions like power/EMI/acoustic (the later really is a form of the former, where fluctuations in CPU power consumption become sound, usually thru magnetostriction in power-supply coils, conceivably thru piezoelectric effect in capacitors)
- information leak to other attacker-controlled processes on the same hardware thru shared resources like memory, cache(s), branch predictors, arithmetic units..
- Performance (speed, computer resources)
The cryptographer should at least consider 1 and 2 when anything confidential is involved, which is often. However, when checking integrity of public data by verifying a digital signature, 1 and 2 are non-issues, as long as an adversary can not bypass the verification (perhaps by fault injection attack or some software bypass).
Performance (3) matters to many applications, and often limits what cryptanalysis (including factorization) can hope achieve.
Bibiography
For fast computer arithmetic, a useful reference is Richard P. Brent and Paul Zimmermann's Modern Computer Arithmetic, published by Cambridge University Press, 2010.
Somewhat dated, but simpler and more focused on cryptography: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, chapter 14, published by CRC Press, 1996.
Neither of these reference focus on constant-timeness. For this with decent speed, the underlying hardware first needs to be carefully analyzed, as did BearSSL.
add a comment |
up vote
3
down vote
This answer tackles mostly the first bullet:
How are large numbers handled in cryptography and cryptanalysis?
Getting the result
Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g. thousands bits in RSA). The straightforward solutions to that issue are:
- Using a language without such limitation (like Python, GP/Pari, Mathematica..)
- Implementing the algorithms taught in elementary school for manual computation in decimal, using the language's constructs. Any Turing-complete language allows that. Coding such "bignum" library is a good but difficult exercise in programming. In languages which allow to overload arithmetic operators like
+
-
*
/
%
, simple expressions can keep a natural look. That can be extended to bases larger than 10 (like 16=24, 28, 216, 232..):+
-
have complexity $O(n)$, and schoolbook algorithms for*
/
%
are $O(n^2)$, where $n$ is a number of digits; a large base reduces $n$ and can boost performance. - Using a ready-made implementation of the previous approach.
- Using an external library, which might use another language; e.g. GMP.
Other issues
Either of the above works for educational purposes. But a cryptographer or cryptanalyst often has special needs:
- Security against timing attacks, where the duration of the computation is measured by an adversary and used to infer information about what's manipulated. While it might be possible to live with data-dependent timing using workarounds like blinding (as performed in some Java crypto libraries including Bouncy Castle), that's brittle. Ideally, a bignum library should be written from the grounds up to avoid data-dependent timing. That's hard, but BearSSL shows it's within human reach (Thomas Pornin only pretends to be a bear).
- Security against other side-channel attacks
- analysis of hardware-related emissions like power/EMI/acoustic (the later really is a form of the former, where fluctuations in CPU power consumption become sound, usually thru magnetostriction in power-supply coils, conceivably thru piezoelectric effect in capacitors)
- information leak to other attacker-controlled processes on the same hardware thru shared resources like memory, cache(s), branch predictors, arithmetic units..
- Performance (speed, computer resources)
The cryptographer should at least consider 1 and 2 when anything confidential is involved, which is often. However, when checking integrity of public data by verifying a digital signature, 1 and 2 are non-issues, as long as an adversary can not bypass the verification (perhaps by fault injection attack or some software bypass).
Performance (3) matters to many applications, and often limits what cryptanalysis (including factorization) can hope achieve.
Bibiography
For fast computer arithmetic, a useful reference is Richard P. Brent and Paul Zimmermann's Modern Computer Arithmetic, published by Cambridge University Press, 2010.
Somewhat dated, but simpler and more focused on cryptography: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, chapter 14, published by CRC Press, 1996.
Neither of these reference focus on constant-timeness. For this with decent speed, the underlying hardware first needs to be carefully analyzed, as did BearSSL.
add a comment |
up vote
3
down vote
up vote
3
down vote
This answer tackles mostly the first bullet:
How are large numbers handled in cryptography and cryptanalysis?
Getting the result
Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g. thousands bits in RSA). The straightforward solutions to that issue are:
- Using a language without such limitation (like Python, GP/Pari, Mathematica..)
- Implementing the algorithms taught in elementary school for manual computation in decimal, using the language's constructs. Any Turing-complete language allows that. Coding such "bignum" library is a good but difficult exercise in programming. In languages which allow to overload arithmetic operators like
+
-
*
/
%
, simple expressions can keep a natural look. That can be extended to bases larger than 10 (like 16=24, 28, 216, 232..):+
-
have complexity $O(n)$, and schoolbook algorithms for*
/
%
are $O(n^2)$, where $n$ is a number of digits; a large base reduces $n$ and can boost performance. - Using a ready-made implementation of the previous approach.
- Using an external library, which might use another language; e.g. GMP.
Other issues
Either of the above works for educational purposes. But a cryptographer or cryptanalyst often has special needs:
- Security against timing attacks, where the duration of the computation is measured by an adversary and used to infer information about what's manipulated. While it might be possible to live with data-dependent timing using workarounds like blinding (as performed in some Java crypto libraries including Bouncy Castle), that's brittle. Ideally, a bignum library should be written from the grounds up to avoid data-dependent timing. That's hard, but BearSSL shows it's within human reach (Thomas Pornin only pretends to be a bear).
- Security against other side-channel attacks
- analysis of hardware-related emissions like power/EMI/acoustic (the later really is a form of the former, where fluctuations in CPU power consumption become sound, usually thru magnetostriction in power-supply coils, conceivably thru piezoelectric effect in capacitors)
- information leak to other attacker-controlled processes on the same hardware thru shared resources like memory, cache(s), branch predictors, arithmetic units..
- Performance (speed, computer resources)
The cryptographer should at least consider 1 and 2 when anything confidential is involved, which is often. However, when checking integrity of public data by verifying a digital signature, 1 and 2 are non-issues, as long as an adversary can not bypass the verification (perhaps by fault injection attack or some software bypass).
Performance (3) matters to many applications, and often limits what cryptanalysis (including factorization) can hope achieve.
Bibiography
For fast computer arithmetic, a useful reference is Richard P. Brent and Paul Zimmermann's Modern Computer Arithmetic, published by Cambridge University Press, 2010.
Somewhat dated, but simpler and more focused on cryptography: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, chapter 14, published by CRC Press, 1996.
Neither of these reference focus on constant-timeness. For this with decent speed, the underlying hardware first needs to be carefully analyzed, as did BearSSL.
This answer tackles mostly the first bullet:
How are large numbers handled in cryptography and cryptanalysis?
Getting the result
Many computer languages and most computer hardware do not directly support variables larger than 64-bit (hence product of larger than 32-bit integers), or double that. Many cryptographic algorithms use much wider integers (e.g. thousands bits in RSA). The straightforward solutions to that issue are:
- Using a language without such limitation (like Python, GP/Pari, Mathematica..)
- Implementing the algorithms taught in elementary school for manual computation in decimal, using the language's constructs. Any Turing-complete language allows that. Coding such "bignum" library is a good but difficult exercise in programming. In languages which allow to overload arithmetic operators like
+
-
*
/
%
, simple expressions can keep a natural look. That can be extended to bases larger than 10 (like 16=24, 28, 216, 232..):+
-
have complexity $O(n)$, and schoolbook algorithms for*
/
%
are $O(n^2)$, where $n$ is a number of digits; a large base reduces $n$ and can boost performance. - Using a ready-made implementation of the previous approach.
- Using an external library, which might use another language; e.g. GMP.
Other issues
Either of the above works for educational purposes. But a cryptographer or cryptanalyst often has special needs:
- Security against timing attacks, where the duration of the computation is measured by an adversary and used to infer information about what's manipulated. While it might be possible to live with data-dependent timing using workarounds like blinding (as performed in some Java crypto libraries including Bouncy Castle), that's brittle. Ideally, a bignum library should be written from the grounds up to avoid data-dependent timing. That's hard, but BearSSL shows it's within human reach (Thomas Pornin only pretends to be a bear).
- Security against other side-channel attacks
- analysis of hardware-related emissions like power/EMI/acoustic (the later really is a form of the former, where fluctuations in CPU power consumption become sound, usually thru magnetostriction in power-supply coils, conceivably thru piezoelectric effect in capacitors)
- information leak to other attacker-controlled processes on the same hardware thru shared resources like memory, cache(s), branch predictors, arithmetic units..
- Performance (speed, computer resources)
The cryptographer should at least consider 1 and 2 when anything confidential is involved, which is often. However, when checking integrity of public data by verifying a digital signature, 1 and 2 are non-issues, as long as an adversary can not bypass the verification (perhaps by fault injection attack or some software bypass).
Performance (3) matters to many applications, and often limits what cryptanalysis (including factorization) can hope achieve.
Bibiography
For fast computer arithmetic, a useful reference is Richard P. Brent and Paul Zimmermann's Modern Computer Arithmetic, published by Cambridge University Press, 2010.
Somewhat dated, but simpler and more focused on cryptography: Alfred J. Menezes, Paul C. van Oorschot and Scott A. Vanstone's Handbook of Applied Cryptography, chapter 14, published by CRC Press, 1996.
Neither of these reference focus on constant-timeness. For this with decent speed, the underlying hardware first needs to be carefully analyzed, as did BearSSL.
edited Nov 8 at 11:27
answered Nov 8 at 7:13
fgrieu
75.9k7155319
75.9k7155319
add a comment |
add a comment |
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63759%2fhow-to-avoid-side-channel-attacks-when-handling-large-numbers%23new-answer', 'question_page');
}
);
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
1
Try GMP
– AleksanderRas
Nov 7 at 11:58
I could be wrong but for counter mode AES the implementation could do all the big number maths in parallel or the day before, then just XOR bits when required.
– daniel
Nov 7 at 12:17
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
Nov 7 at 14:48
3
Reading your question more closely, I see that it focuses mostly on avoiding side channel attacks, but its current title does not really reflect that. I would recommend editing the title to make that clearer. Maybe something like "How to avoid side channel attacks when handling large numbers?"
– Ilmari Karonen
Nov 7 at 14:55
1
@daniel That doesn't make sense. First of all, AES doesn't use big number math. Second, generally the IV only is known when the bytes are required. In practice I haven't seen caching of a CTR-generated key stream far in advance; if CTR is cached at all it would be because of performance reasons (but I don't see that either).
– Maarten Bodewes
Nov 7 at 19:07