Why is double encryption that's equivalent to single encryption no better than single encryption?Weakness in double encryptionBreak 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
Can the fact that Trump issued a Do Not Testify be used in impeachment articles?
Is "montäglich" commonly used?
Translate 主播 in this context
Is there any way to get an instant or sorcery on the field as a permanent? What would happen if this occurred?
TSP with revenue maximization
Reliable temperature/humidity logging with Python and a DHT11
Why would prey creatures not hate predator creatures?
Would an intelligent alien civilisation categorise EM radiation the same as us?
Can the treble clef be used instead of the bass clef in piano music?
How to explain to traditional people why they should upgrade their old Windows XP device?
SSH host identification changes on one wireless network
Is staccato implied in the bass on this Burgmuller Arabesque?
Static forces on a rocket engine
How can I add an ammeter and/or voltmeter to my home breaker panel?
What are the minimum element requirements for a star?
Should I tell an editor that I believe an article I'm reviewing is not good enough for the journal?
What other tricks were there to get more data onto floppy disks?
Which of these will work? HDMI to VGA or HDMI to USB?
Integration of three dimensional function gives wrong answer!
Can't CD to Desktop anymore
"Startup" working hours - is it normal to be asked to work 11 hours/ day?
Why are there so many binary systems?
Is it a mistake to use a password that has previously been used (by anyone ever)?
Buddha Hinduism
Why is double encryption that's equivalent to single encryption no better than single encryption?
Weakness in double encryptionBreak 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
3431 silver badge8 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
3431 silver badge8 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
3431 silver badge8 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
3431 silver badge8 bronze badges
asked Oct 16 at 15:02
AleQuerciaAleQuercia
3431 silver badge8 bronze badges
edited Oct 17 at 17:00
AleQuercia
asked Oct 16 at 15:02
AleQuerciaAleQuercia
3431 silver badge8 bronze badges
asked Oct 16 at 15:02
AleQuerciaAleQuercia
3431 silver badge8 bronze badges
asked Oct 16 at 15:02
AleQuerciaAleQuercia
3431 silver badge8 bronze badges
3431 silver badge8 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.2k4 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.2k4 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.2k4 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.2k4 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.2k4 gold badges34 silver badges61 bronze badges
edited Oct 18 at 14:40
answered Oct 16 at 15:28
kelalakakelalaka
13.2k4 gold badges34 silver badges61 bronze badges
answered Oct 16 at 15:28
kelalakakelalaka
13.2k4 gold badges34 silver badges61 bronze badges
answered Oct 16 at 15:28
kelalakakelalaka
13.2k4 gold badges34 silver badges61 bronze badges
13.2k4 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