Mixing
How are large numbers handled in cryptography and cryptanalysis?
Clash Royale CLAN TAG#URR8PPP
up vote
2
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
asked 5 hours ago
kelalaka
2,560624
add a comment |Â
up vote
2
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
asked 5 hours ago
kelalaka
2,560624
Last link is broken for me.
– Maarten Bodewes
5 hours ago
Try GMP
– AleksanderRas
4 hours ago
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
4 hours ago
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
1 hour ago
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
1 hour ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
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
asked 5 hours ago
kelalaka
2,560624
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
asked 5 hours ago
kelalaka
2,560624
asked 5 hours ago
kelalaka
2,560624
edited 5 hours ago
asked 5 hours ago
kelalaka
2,560624
asked 5 hours ago
kelalaka
2,560624
asked 5 hours ago
kelalaka
2,560624
2,560624
Last link is broken for me.
– Maarten Bodewes
5 hours ago
Try GMP
– AleksanderRas
4 hours ago
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
4 hours ago
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
1 hour ago
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
1 hour ago
add a comment |Â
Last link is broken for me.
– Maarten Bodewes
5 hours ago
Try GMP
– AleksanderRas
4 hours ago
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
4 hours ago
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
1 hour ago
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
1 hour ago
Last link is broken for me.
– Maarten Bodewes
5 hours ago
Last link is broken for me.
– Maarten Bodewes
5 hours ago
Try GMP
– AleksanderRas
4 hours ago
Try GMP
– AleksanderRas
4 hours ago
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
4 hours ago
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
4 hours ago
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
1 hour ago
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
1 hour ago
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
1 hour ago
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
1 hour ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
3
down vote
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 2 hours ago
Thomas Pornin
67.1k12175253
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
3
down vote
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 2 hours ago
Thomas Pornin
67.1k12175253
add a comment |Â
up vote
3
down vote
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 2 hours ago
Thomas Pornin
67.1k12175253
add a comment |Â
up vote
3
down vote
up vote
3
down vote
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 2 hours ago
Thomas Pornin
67.1k12175253
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 2 hours ago
Thomas Pornin
67.1k12175253
answered 2 hours ago
Thomas Pornin
67.1k12175253
answered 2 hours ago
Thomas Pornin
67.1k12175253
answered 2 hours ago
Thomas Pornin
67.1k12175253
67.1k12175253
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-are-large-numbers-handled-in-cryptography-and-cryptanalysis%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
Last link is broken for me.
– Maarten Bodewes
5 hours ago
Try GMP
– AleksanderRas
4 hours ago
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
4 hours ago
Related: crypto.stackexchange.com/questions/35586/…
– Ilmari Karonen
1 hour ago
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
1 hour ago