Searching for a differential characteristic (differential cryptanalysis)
$begingroup$
Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.
I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.
So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.
cryptanalysis differential-analysis
$endgroup$
add a comment |
$begingroup$
Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.
I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.
So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.
cryptanalysis differential-analysis
$endgroup$
1
$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago
add a comment |
$begingroup$
Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.
I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.
So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.
cryptanalysis differential-analysis
$endgroup$
Currently I am doing some research on differential cryptanalysis. In general I got a good idea about the attack and how it is done.
I am currently talking about ciphers with multiple rounds. It seems that the success of a attack is depending on a good differential characteristic through the cipher. There are way which have good statistical values and some more which have not. In the paper there is often a good differential characteristic shown which works very well. But there is never a talk about how to find them. For sure I read about some heuristics like "look for differential characteristics with small amount of active sboxes" or something like that.
So my Question: How can I find a good differential or lets say, all? I am looking for a algorithm or a good description which I could implement on my own.
cryptanalysis differential-analysis
cryptanalysis differential-analysis
edited 3 hours ago
hardyrama
8991527
8991527
asked 8 hours ago
chris000rchris000r
13016
13016
1
$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago
add a comment |
1
$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago
1
1
$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago
$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).
Δx = X' xor X'' =>
Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]
=[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]
We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).
As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.
In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):
choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.
-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:
-Each SBox has differential property and should affect in
each round in the differential characteristic when it is
activated.
-Multiply calculated probabilities by the prior probability in
order to finding rounds differential characteristics.
A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf
$endgroup$
add a comment |
$begingroup$
The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
$$
prod_{S_i ~mathrm{active~in~differential~trail}}
P(Delta_{in},Delta_{out},S_i),
$$
where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.
In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.
$endgroup$
add a comment |
Your Answer
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f68755%2fsearching-for-a-differential-characteristic-differential-cryptanalysis%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).
Δx = X' xor X'' =>
Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]
=[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]
We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).
As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.
In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):
choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.
-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:
-Each SBox has differential property and should affect in
each round in the differential characteristic when it is
activated.
-Multiply calculated probabilities by the prior probability in
order to finding rounds differential characteristics.
A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf
$endgroup$
add a comment |
$begingroup$
Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).
Δx = X' xor X'' =>
Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]
=[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]
We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).
As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.
In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):
choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.
-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:
-Each SBox has differential property and should affect in
each round in the differential characteristic when it is
activated.
-Multiply calculated probabilities by the prior probability in
order to finding rounds differential characteristics.
A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf
$endgroup$
add a comment |
$begingroup$
Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).
Δx = X' xor X'' =>
Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]
=[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]
We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).
As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.
In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):
choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.
-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:
-Each SBox has differential property and should affect in
each round in the differential characteristic when it is
activated.
-Multiply calculated probabilities by the prior probability in
order to finding rounds differential characteristics.
A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf
$endgroup$
Finding differential characteristic means analyzing the structure of the given cipher(substitution and permutation elements). This analyzing means, we should track the input differentials(Δi) through the different elements of the cipher and produce related output differential(Δo).
Δx = X' xor X'' =>
Δx=[ΔX1,ΔX2,ΔX3,....ΔXn]
=[X'1 xor X''1, X'2 xor X''2, X'3 xor X''3,...,X'n xor X''n]
We repeat this to round - 1. Each of these paths are called "Differential characteristic" and each of them has its own happening chance(probability).
As mentioned, in the paces of tracking Δi to Δo, we should consider that cipher structure is made of different confusion and diffusion elements which these elements effect the path in each round and leads to activating some SBoxes(called Active SBoxes). But the most important factor is finding the probability of each differential path(differential characteristic) and choosing the highest one(or ones) among them. The rout with the highest probability is the objection of the analyzer.
In order to find these differential characteristics we can use one of these three methods( It is general recommendation but not exact!!!):
choose each differential characteristic in the cipher structure visually and calculate probability for them. However we should mention that this method is not applicable for the most variety of ciphers in that the number of input to the cipher is big( at least 16 bit) and if we want to have a precise estimation of differential status of the cipher,nearly we should test 2^16 input differentials and calculate the probability for each round. In the most situations this way is impossible.
** Use Sage S-box MILP toolkit ** which is developed and intended to calculate the differential characteristics for well-known block ciphers which have Substitution and permutation structure in them. This toolkit can be found in: http://www.swmath.org/?term=differential%20cryptanalysis and in this paper: https://www.esat.kuleuven.be/cosic/publications/article-2080.pdf the way of using them is explained.(I should remark that in the given toolkit, you should make some modifications in order to use them like changing the "coin solver"). This method is a very good way to finding the number of active SBoxes and calculating the differential characteristic of the cipher.
-Implementation on our own code in order to find the differential characteristics with the highest probability among all input differentials. It is not hard and possible. We firstly should define all input differentials (states) and then calculate the probability of each state by considering these two factors:
-Each SBox has differential property and should affect in
each round in the differential characteristic when it is
activated.
-Multiply calculated probabilities by the prior probability in
order to finding rounds differential characteristics.
A good reference: https://www.engr.mun.ca/~howard/PAPERS/ldc_tutorial.pdf
But I should mention that finding differential characteristic for Feistel structures have a different story and a good reference is in:
http://www.cs.haifa.ac.il/~orrd/BlockCipherSeminar/Lecture2-Differential.pdf
edited 3 hours ago
answered 3 hours ago
Arsalan VahiArsalan Vahi
15610
15610
add a comment |
add a comment |
$begingroup$
The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
$$
prod_{S_i ~mathrm{active~in~differential~trail}}
P(Delta_{in},Delta_{out},S_i),
$$
where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.
In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.
$endgroup$
add a comment |
$begingroup$
The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
$$
prod_{S_i ~mathrm{active~in~differential~trail}}
P(Delta_{in},Delta_{out},S_i),
$$
where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.
In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.
$endgroup$
add a comment |
$begingroup$
The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
$$
prod_{S_i ~mathrm{active~in~differential~trail}}
P(Delta_{in},Delta_{out},S_i),
$$
where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.
In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.
$endgroup$
The details depend on the exact cipher design. However what you need to optimize (maximize) is the probability
$$
prod_{S_i ~mathrm{active~in~differential~trail}}
P(Delta_{in},Delta_{out},S_i),
$$
where the deltas are the input and output differences to Sbox $S_i,$ and the differential trail is usually chosen to cover $r-1$ rounds for an $r$ round cipher.
In the case of SPN networks with wire crossing permutation layer, as in the Heys tutorial in the comment, you should look for an output differential with low Hamming weight to minimize the number of active Sboxes in the next round.
answered 4 hours ago
kodlukodlu
9,37311331
9,37311331
add a comment |
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.
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%2f68755%2fsearching-for-a-differential-characteristic-differential-cryptanalysis%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
1
$begingroup$
this might help you : cs.bc.edu/~straubin/crypto2017/heys.pdf
$endgroup$
– hardyrama
8 hours ago