Timing Side Channel on error-correcting code
up vote
2
down vote
favorite
This question may be a basic question but it is not clear to me at the moment.
I have an Error Correcting Code (ECC) in a key-encapsulation scheme designed for post-quantum cryptography which operates on secret data.
The ECC I am using is constant time as long as the number of errors which need to be corrected is constant, and as long as those errors occur at the same positions in the message. The runtime does not depend on the secret data itself, only on the #errors and their positions in the secret data.
Does this leak any useful information? The # of errors which occur is not always constant in a real scenario...
side-channel-attack
edited Nov 11 at 17:48
kelalaka
4,27911636
asked Nov 11 at 11:42
jonnyx
133
add a comment |
up vote
2
down vote
favorite
This question may be a basic question but it is not clear to me at the moment.
I have an Error Correcting Code (ECC) in a key-encapsulation scheme designed for post-quantum cryptography which operates on secret data.
The ECC I am using is constant time as long as the number of errors which need to be corrected is constant, and as long as those errors occur at the same positions in the message. The runtime does not depend on the secret data itself, only on the #errors and their positions in the secret data.
Does this leak any useful information? The # of errors which occur is not always constant in a real scenario...
side-channel-attack
edited Nov 11 at 17:48
kelalaka
4,27911636
asked Nov 11 at 11:42
jonnyx
133
add a comment |
up vote
2
down vote
favorite
up vote
2
down vote
favorite
This question may be a basic question but it is not clear to me at the moment.
I have an Error Correcting Code (ECC) in a key-encapsulation scheme designed for post-quantum cryptography which operates on secret data.
The ECC I am using is constant time as long as the number of errors which need to be corrected is constant, and as long as those errors occur at the same positions in the message. The runtime does not depend on the secret data itself, only on the #errors and their positions in the secret data.
Does this leak any useful information? The # of errors which occur is not always constant in a real scenario...
side-channel-attack
edited Nov 11 at 17:48
kelalaka
4,27911636
asked Nov 11 at 11:42
jonnyx
133
This question may be a basic question but it is not clear to me at the moment.
I have an Error Correcting Code (ECC) in a key-encapsulation scheme designed for post-quantum cryptography which operates on secret data.
The ECC I am using is constant time as long as the number of errors which need to be corrected is constant, and as long as those errors occur at the same positions in the message. The runtime does not depend on the secret data itself, only on the #errors and their positions in the secret data.
Does this leak any useful information? The # of errors which occur is not always constant in a real scenario...
side-channel-attack
side-channel-attack
edited Nov 11 at 17:48
kelalaka
4,27911636
asked Nov 11 at 11:42
jonnyx
133
edited Nov 11 at 17:48
kelalaka
4,27911636
asked Nov 11 at 11:42
jonnyx
133
edited Nov 11 at 17:48
kelalaka
4,27911636
edited Nov 11 at 17:48
kelalaka
4,27911636
edited Nov 11 at 17:48
kelalaka
4,27911636
4,27911636
asked Nov 11 at 11:42
jonnyx
133
asked Nov 11 at 11:42
jonnyx
133
asked Nov 11 at 11:42
jonnyx
133
133
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
up vote
2
down vote
accepted
This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.
If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.
A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.
answered Nov 11 at 12:25
Meir Maor
5,1281828
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
accepted
This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.
If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.
A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.
answered Nov 11 at 12:25
Meir Maor
5,1281828
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
add a comment |
up vote
2
down vote
accepted
This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.
If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.
A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.
answered Nov 11 at 12:25
Meir Maor
5,1281828
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
add a comment |
up vote
2
down vote
accepted
up vote
2
down vote
accepted
This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.
If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.
A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.
answered Nov 11 at 12:25
Meir Maor
5,1281828
This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.
If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.
A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.
answered Nov 11 at 12:25
Meir Maor
5,1281828
answered Nov 11 at 12:25
Meir Maor
5,1281828
answered Nov 11 at 12:25
Meir Maor
5,1281828
answered Nov 11 at 12:25
Meir Maor
5,1281828
5,1281828
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
add a comment |
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
thanks for sharing your thoughts. What I can do, is change the code such that it always calls the routine which corrects all designed errors, instead of shortcutting if eg. only 1 error is detected. I would still get different runtimes depending on the location, which is better than before I guess, but still not perfect right?
– jonnyx
Nov 11 at 13:20
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
This indeed seems like an improvement, and if all attacker can do is induce some bits to be set to 1 randomly that would prevent the simple attack I proposed for recovering number of set bits in the data. Not sure what the attacker can actually reasonably do without more information on the complete setup.
– Meir Maor
Nov 11 at 16:27
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63870%2ftiming-side-channel-on-error-correcting-code%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
