Why is double encryption that's equivalent to single encryption no better than single encryption?Weakness in double encryptionHow to show that Affine crypto have a valid decryptionBreak double encryptionRegarding Key Strength with DES and Blowfish2DES vs. two-key triple encryption, with no decryption stepCan double-encrypting be easier to break then either algorithm on its own?“Double Encryption” using the same cipher?DES - Weakness in SboxProperty of a good cipher system
How can I convince my department that I have the academic freedom to select textbooks and use multiple-choice tests in my courses?
Simple Markdown viewer for Windows
Can socialism and capitalism coexist in the same country?
How to move the cursor to the next instance of the text the cursor is currently on?
What is this Kanji? I can’t find it anywhere?
Velocity is to speed as acceleration is to?
Which object has been to space the most times?
Calculate the movement required to get from one angle to another angle on a compass
Why "alle Tale" and not "alle Täler"?
How can I repair a leak in a PVC water line without bringing down the system for an extended period of time?
Tension in a massless string being pulled at its ends with unequal forces
Are optimal hyperparameters still optimal for a deeper neural net architecture?
Advent of Code 2019: Day 1
"Applicants for asylum must prove that they have fifteen family members in the Netherlands."
Does "dd" by itself do anything?
Should I still follow "programming to an interface not implementation" even if I think using concrete class members is the simpler solution?
Is this homebrew Dragon Rider class balanced compared to the other official classes?
Why impeachment now?
Grabbing values between quotation marks
What is latinum and where does it occur?
What attributes of a Pokemon can be improved?
Permanent river of lava
Is there any reason a person would voluntarily choose to have PMI?
Schemes/ Mechanisms that could provide one time decryption?
Why is double encryption that's equivalent to single encryption no better than single encryption?
Weakness in double encryptionHow to show that Affine crypto have a valid decryptionBreak double encryptionRegarding Key Strength with DES and Blowfish2DES vs. two-key triple encryption, with no decryption stepCan double-encrypting be easier to break then either algorithm on its own?“Double Encryption” using the same cipher?DES - Weakness in SboxProperty of a good cipher system
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;
.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;
$begingroup$
In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:
"if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"
Why is this?
cryptanalysis des multiple-encryption
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
$endgroup$
add a comment
|
$begingroup$
In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:
"if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"
Why is this?
cryptanalysis des multiple-encryption
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
$endgroup$
14
$begingroup$
I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward.
$endgroup$
– chepner
Oct 17 at 13:59
$begingroup$
Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking.
$endgroup$
– Nat
Oct 17 at 14:45
$begingroup$
Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle).
$endgroup$
– Damon
Oct 17 at 17:35
add a comment
|
$begingroup$
In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:
"if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"
Why is this?
cryptanalysis des multiple-encryption
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
$endgroup$
In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:
"if a cryptosystem is such that double encryption is equivalent to a single encryption, then there is no additional security obtained by double encryption"
Why is this?
cryptanalysis des multiple-encryption
cryptanalysis des multiple-encryption
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
edited Oct 17 at 17:00
AleQuercia
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
asked Oct 16 at 15:02
AleQuerciaAleQuercia
4051 silver badge9 bronze badges
4051 silver badge9 bronze badges
14
$begingroup$
I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward.
$endgroup$
– chepner
Oct 17 at 13:59
$begingroup$
Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking.
$endgroup$
– Nat
Oct 17 at 14:45
$begingroup$
Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle).
$endgroup$
– Damon
Oct 17 at 17:35
add a comment
|
14
$begingroup$
I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward.
$endgroup$
– chepner
Oct 17 at 13:59
$begingroup$
Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking.
$endgroup$
– Nat
Oct 17 at 14:45
$begingroup$
Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle).
$endgroup$
– Damon
Oct 17 at 17:35
14
14
$begingroup$
I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward.
$endgroup$
– chepner
Oct 17 at 13:59
$begingroup$
I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward.
$endgroup$
– chepner
Oct 17 at 13:59
$begingroup$
Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking.
$endgroup$
– Nat
Oct 17 at 14:45
$begingroup$
Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking.
$endgroup$
– Nat
Oct 17 at 14:45
$begingroup$
Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle).
$endgroup$
– Damon
Oct 17 at 17:35
$begingroup$
Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle).
$endgroup$
– Damon
Oct 17 at 17:35
add a comment
|
1 Answer
1
active
oldest
votes
$begingroup$
This is simply saying that if a cryptosystem has a functional composition that is
$$ h_k(x) = f_k_1(g_k_2(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = beginpmatrix1 & 2 & 3 & 4 & 5 \2 & 4 & 1 & 3 & 5 endpmatrix text and Q = beginpmatrix1 & 2 & 3 & 4 & 5 \ 5 & 4 & 3 & 2 & 1 endpmatrix$$ The compositon of the two keys is
$$R =QP = beginpmatrix1 & 2 & 3 & 4 & 5 \4 & 2 & 5 & 3 & 1 endpmatrix$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^2499$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^28$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.
The academical works on DES closure
1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.
‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
$endgroup$
2
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
5
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
1
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
|
show 2 more comments
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/4.0/"u003ecc by-sa 4.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%2f75120%2fwhy-is-double-encryption-thats-equivalent-to-single-encryption-no-better-than-s%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
This is simply saying that if a cryptosystem has a functional composition that is
$$ h_k(x) = f_k_1(g_k_2(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = beginpmatrix1 & 2 & 3 & 4 & 5 \2 & 4 & 1 & 3 & 5 endpmatrix text and Q = beginpmatrix1 & 2 & 3 & 4 & 5 \ 5 & 4 & 3 & 2 & 1 endpmatrix$$ The compositon of the two keys is
$$R =QP = beginpmatrix1 & 2 & 3 & 4 & 5 \4 & 2 & 5 & 3 & 1 endpmatrix$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^2499$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^28$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.
The academical works on DES closure
1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.
‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
$endgroup$
2
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
5
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
1
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
|
show 2 more comments
$begingroup$
This is simply saying that if a cryptosystem has a functional composition that is
$$ h_k(x) = f_k_1(g_k_2(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = beginpmatrix1 & 2 & 3 & 4 & 5 \2 & 4 & 1 & 3 & 5 endpmatrix text and Q = beginpmatrix1 & 2 & 3 & 4 & 5 \ 5 & 4 & 3 & 2 & 1 endpmatrix$$ The compositon of the two keys is
$$R =QP = beginpmatrix1 & 2 & 3 & 4 & 5 \4 & 2 & 5 & 3 & 1 endpmatrix$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^2499$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^28$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.
The academical works on DES closure
1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.
‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
$endgroup$
2
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
5
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
1
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
|
show 2 more comments
$begingroup$
This is simply saying that if a cryptosystem has a functional composition that is
$$ h_k(x) = f_k_1(g_k_2(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = beginpmatrix1 & 2 & 3 & 4 & 5 \2 & 4 & 1 & 3 & 5 endpmatrix text and Q = beginpmatrix1 & 2 & 3 & 4 & 5 \ 5 & 4 & 3 & 2 & 1 endpmatrix$$ The compositon of the two keys is
$$R =QP = beginpmatrix1 & 2 & 3 & 4 & 5 \4 & 2 & 5 & 3 & 1 endpmatrix$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^2499$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^28$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.
The academical works on DES closure
1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.
‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
$endgroup$
This is simply saying that if a cryptosystem has a functional composition that is
$$ h_k(x) = f_k_1(g_k_2(x)) $$
then you can find a key for single encryption that works as the double encryption.
For example: consider the permutation cipher where a permutation is a key. The permutations are forming a group, named permutation group, under the composition. Therefore, double encryption in permutation cipher is just another permutation, i.e. another key. Therefore you will not get a benefit.
To see this, let simplify the alphabet into 5 letters and let $P$ and $Q$ be two keys for a 5 letter permutation cipher:
$$P = beginpmatrix1 & 2 & 3 & 4 & 5 \2 & 4 & 1 & 3 & 5 endpmatrix text and Q = beginpmatrix1 & 2 & 3 & 4 & 5 \ 5 & 4 & 3 & 2 & 1 endpmatrix$$ The compositon of the two keys is
$$R =QP = beginpmatrix1 & 2 & 3 & 4 & 5 \4 & 2 & 5 & 3 & 1 endpmatrix$$ and this is another permutation $R$, i.e. $R$ is a key that works as a single key.
Now turn back to DES:
Campbell and Wiener in 1992 showed that DES is not a group (paywalled) (and paywall-free). They showed that that the size of the
subgroup generated by the set of DES permutations is greater than $10^2499$. Therefore this value is far greater than potential attacks on DES which would exploit a small subgroup. As a result, DES has no such weakness. Actually, we will be surprised that a well-designed block cipher will be forming a group.
If there is such property that is the DES forms a subgroup of the permutation group then there exists a known-plaintext attack on DES that requires, on average $2^28$ steps showed by Judy H. Moore and Simmons (paywalled).
Also, forming a group will reduce the Triple-DES or more generally the multiple encryptions into single encryption.
The academical works on DES closure
1982 - D. Coppersmith, “In Defense of DES”, personal communication‡ Don Coppersmith was first to ask this. And he developed a method to show that lower bound on the size of the subgroup generated by the DES permutation is to be greater than the number of DES permutations, providing conclusive proof that set of DES permutations is not closed.
1988 - Burton S. KaliskiJr.Ronald L. RivestAlan T. Sherman, Is the Data Encryption Standard a group? (Results of cycling experiments on DES) (pay-walled), and pay-wall free.
They introduce a novel cycling closure tests which gave evidence that the
set of DES permutations is not closed. However, they assumed that DES pseudo-random function on their experiments. Therefore the claims are difficult to prove.
1989 - Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search. New results and applications to DES (pay-walled)
1989 Jean-Jacques Quisquater, Jean-Paul Delescaille How easy is collision search? Application to DES (pay-walled)
1992 - Campbell and Wiener DES is not a group (paywalled) (and paywall-free). In their conclusive work, they used a similar technique of Quisquater and Delescaille's work.
‡ This work claimed to be
described briefly in a posting to sci.crypt on Usenet News, 1992 May 18. This needs a link!
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
edited Oct 18 at 14:40
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
answered Oct 16 at 15:28
kelalakakelalaka
13.5k4 gold badges34 silver badges61 bronze badges
13.5k4 gold badges34 silver badges61 bronze badges
2
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
5
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
1
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
|
show 2 more comments
2
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
5
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
1
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
2
2
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
Another simple example of a “group” cipher is the XOR cipher, where (M^K1)^K2 = M^(K1^K2).
$endgroup$
– dan04
Oct 17 at 19:41
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
$begingroup$
@dan04 Yes, with cycle length 2. The permutation group is a better example since the Block ciphers are actually randomly selecting permutations from the possible permutations. We expect that a probabilistic adversary cannot distinguish them from Random Permutations.
$endgroup$
– kelalaka
Oct 17 at 19:57
5
5
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
$begingroup$
... and then there are those who think that ROT-13 is too easy to break and apply it twice
$endgroup$
– Hagen von Eitzen
Oct 18 at 7:31
1
1
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
This answer has several places where the grammar is awkward and it's hard to tell which direction a statement is being made in, like "providing conclusive proof that DES is not" and "Actually, we will be surprised that a well-designed block cipher will have this property." (where it's unclear if "this property" is the positive or negative). Etc.
$endgroup$
– R..
Oct 18 at 13:22
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
$begingroup$
@R.. does it better now?
$endgroup$
– kelalaka
Oct 18 at 14:40
|
show 2 more comments
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%2f75120%2fwhy-is-double-encryption-thats-equivalent-to-single-encryption-no-better-than-s%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
14
$begingroup$
I assume the question is really, "how can double encryption be equivalent to single encryption"? Because the if/then is pretty straightforward.
$endgroup$
– chepner
Oct 17 at 13:59
$begingroup$
Is @chepner's interpretation correct? Because this question can be edit'd to better reflect what you're interested in asking.
$endgroup$
– Nat
Oct 17 at 14:45
$begingroup$
Well if it's equivalent, you have the same binary blob either way. It's pretty obvious that it's none better than just encrypting once. No? What's interesting is that even if it's not equivalent, then the logic 1+1 = 2 isn't true (think meet in the middle).
$endgroup$
– Damon
Oct 17 at 17:35