How to make a collection for the Meet-In-The-Middle attack?












1















I want to create a collection, which can be used to find matches among the values. As you properly know, recovering the key for Double DES takes three steps. Having the plaintext and the ciphertext given:




  1. Encrypting the plaintext with all 2^56 possible keys and storing the results

  2. Decrypting the ciphertext with all 2^56 possible keys and storing the results

  3. Checking where the results match to retrieve the key


What I am trying to do:
I am currently working with Meet-in-the-middle attack on Double DES and I have reached the point where I have to encrypt/decrypt a plaintext/ciphertext 2^56 times and store the results in order to find any matches.



Right now, I have stored the results in two HashMaps where I store the key used and the result from the encryption/decryption. However, I am not able to figure out how I can compare the results from the two HashMaps and then decide which keys have been used.



So, my second idea is maybe to use ListMultimap instead where I can store the results from the encryption/decryption with the key used, but then again, I don't know how to find the matches. The matches are not necessarily on the same row.



EDIT:



I gave it a try with my two HashMaps, but I did not succeed i.e. I was not able to compare the Maps



for (int i = 0; i <  Math.pow(2, 20); i++) {

for (int j = 0; j < Math.pow(2, 20); j++) {

if(hmap1.values().toArray()[i].equals(hmap2.values().toArray()[j]) )
System.out.println(hmap1.keySet().toArray()[i] + " = " + hmap2.keySet().toArray()[i] );
}
}


I forgot to mention that for the sake of testing, I am working with keys that have 20 effective bits. So, there will be 2^20 possible keys



I also forgot to mention what my HashMaps contain of. They contain of two byte arrays static Map<byte, byte> hmap1 = new HashMap<byte, byte>(); where the first byte array contains of the possible key and the second array contains of the result of the encryption/decryption










share|improve this question

























  • You need one loop not double. One loop iterates one hashmap inside search in the second.

    – kelalaka
    Nov 21 '18 at 19:57











  • You do not store the results of #2.

    – James K Polk
    Nov 21 '18 at 19:57











  • Use set intersection as here

    – kelalaka
    Nov 21 '18 at 20:07











  • @JamesKPolk: Then how am I going to find the the key for the decryption?

    – Bab
    Nov 21 '18 at 20:14











  • Unfortunately you have left off critical details on your implementation. You say you have HashMaps but you don't say what is the HashMap lookup key and its value. Since you have DES keys and DES encryption results it matters.

    – James K Polk
    Nov 21 '18 at 20:44
















1















I want to create a collection, which can be used to find matches among the values. As you properly know, recovering the key for Double DES takes three steps. Having the plaintext and the ciphertext given:




  1. Encrypting the plaintext with all 2^56 possible keys and storing the results

  2. Decrypting the ciphertext with all 2^56 possible keys and storing the results

  3. Checking where the results match to retrieve the key


What I am trying to do:
I am currently working with Meet-in-the-middle attack on Double DES and I have reached the point where I have to encrypt/decrypt a plaintext/ciphertext 2^56 times and store the results in order to find any matches.



Right now, I have stored the results in two HashMaps where I store the key used and the result from the encryption/decryption. However, I am not able to figure out how I can compare the results from the two HashMaps and then decide which keys have been used.



So, my second idea is maybe to use ListMultimap instead where I can store the results from the encryption/decryption with the key used, but then again, I don't know how to find the matches. The matches are not necessarily on the same row.



EDIT:



I gave it a try with my two HashMaps, but I did not succeed i.e. I was not able to compare the Maps



for (int i = 0; i <  Math.pow(2, 20); i++) {

for (int j = 0; j < Math.pow(2, 20); j++) {

if(hmap1.values().toArray()[i].equals(hmap2.values().toArray()[j]) )
System.out.println(hmap1.keySet().toArray()[i] + " = " + hmap2.keySet().toArray()[i] );
}
}


I forgot to mention that for the sake of testing, I am working with keys that have 20 effective bits. So, there will be 2^20 possible keys



I also forgot to mention what my HashMaps contain of. They contain of two byte arrays static Map<byte, byte> hmap1 = new HashMap<byte, byte>(); where the first byte array contains of the possible key and the second array contains of the result of the encryption/decryption










share|improve this question

























  • You need one loop not double. One loop iterates one hashmap inside search in the second.

    – kelalaka
    Nov 21 '18 at 19:57











  • You do not store the results of #2.

    – James K Polk
    Nov 21 '18 at 19:57











  • Use set intersection as here

    – kelalaka
    Nov 21 '18 at 20:07











  • @JamesKPolk: Then how am I going to find the the key for the decryption?

    – Bab
    Nov 21 '18 at 20:14











  • Unfortunately you have left off critical details on your implementation. You say you have HashMaps but you don't say what is the HashMap lookup key and its value. Since you have DES keys and DES encryption results it matters.

    – James K Polk
    Nov 21 '18 at 20:44














1












1








1








I want to create a collection, which can be used to find matches among the values. As you properly know, recovering the key for Double DES takes three steps. Having the plaintext and the ciphertext given:




  1. Encrypting the plaintext with all 2^56 possible keys and storing the results

  2. Decrypting the ciphertext with all 2^56 possible keys and storing the results

  3. Checking where the results match to retrieve the key


What I am trying to do:
I am currently working with Meet-in-the-middle attack on Double DES and I have reached the point where I have to encrypt/decrypt a plaintext/ciphertext 2^56 times and store the results in order to find any matches.



Right now, I have stored the results in two HashMaps where I store the key used and the result from the encryption/decryption. However, I am not able to figure out how I can compare the results from the two HashMaps and then decide which keys have been used.



So, my second idea is maybe to use ListMultimap instead where I can store the results from the encryption/decryption with the key used, but then again, I don't know how to find the matches. The matches are not necessarily on the same row.



EDIT:



I gave it a try with my two HashMaps, but I did not succeed i.e. I was not able to compare the Maps



for (int i = 0; i <  Math.pow(2, 20); i++) {

for (int j = 0; j < Math.pow(2, 20); j++) {

if(hmap1.values().toArray()[i].equals(hmap2.values().toArray()[j]) )
System.out.println(hmap1.keySet().toArray()[i] + " = " + hmap2.keySet().toArray()[i] );
}
}


I forgot to mention that for the sake of testing, I am working with keys that have 20 effective bits. So, there will be 2^20 possible keys



I also forgot to mention what my HashMaps contain of. They contain of two byte arrays static Map<byte, byte> hmap1 = new HashMap<byte, byte>(); where the first byte array contains of the possible key and the second array contains of the result of the encryption/decryption










share|improve this question
















I want to create a collection, which can be used to find matches among the values. As you properly know, recovering the key for Double DES takes three steps. Having the plaintext and the ciphertext given:




  1. Encrypting the plaintext with all 2^56 possible keys and storing the results

  2. Decrypting the ciphertext with all 2^56 possible keys and storing the results

  3. Checking where the results match to retrieve the key


What I am trying to do:
I am currently working with Meet-in-the-middle attack on Double DES and I have reached the point where I have to encrypt/decrypt a plaintext/ciphertext 2^56 times and store the results in order to find any matches.



Right now, I have stored the results in two HashMaps where I store the key used and the result from the encryption/decryption. However, I am not able to figure out how I can compare the results from the two HashMaps and then decide which keys have been used.



So, my second idea is maybe to use ListMultimap instead where I can store the results from the encryption/decryption with the key used, but then again, I don't know how to find the matches. The matches are not necessarily on the same row.



EDIT:



I gave it a try with my two HashMaps, but I did not succeed i.e. I was not able to compare the Maps



for (int i = 0; i <  Math.pow(2, 20); i++) {

for (int j = 0; j < Math.pow(2, 20); j++) {

if(hmap1.values().toArray()[i].equals(hmap2.values().toArray()[j]) )
System.out.println(hmap1.keySet().toArray()[i] + " = " + hmap2.keySet().toArray()[i] );
}
}


I forgot to mention that for the sake of testing, I am working with keys that have 20 effective bits. So, there will be 2^20 possible keys



I also forgot to mention what my HashMaps contain of. They contain of two byte arrays static Map<byte, byte> hmap1 = new HashMap<byte, byte>(); where the first byte array contains of the possible key and the second array contains of the result of the encryption/decryption







java encryption collections hashmap






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 21 '18 at 20:52







Bab

















asked Nov 21 '18 at 18:54









BabBab

14810




14810













  • You need one loop not double. One loop iterates one hashmap inside search in the second.

    – kelalaka
    Nov 21 '18 at 19:57











  • You do not store the results of #2.

    – James K Polk
    Nov 21 '18 at 19:57











  • Use set intersection as here

    – kelalaka
    Nov 21 '18 at 20:07











  • @JamesKPolk: Then how am I going to find the the key for the decryption?

    – Bab
    Nov 21 '18 at 20:14











  • Unfortunately you have left off critical details on your implementation. You say you have HashMaps but you don't say what is the HashMap lookup key and its value. Since you have DES keys and DES encryption results it matters.

    – James K Polk
    Nov 21 '18 at 20:44



















  • You need one loop not double. One loop iterates one hashmap inside search in the second.

    – kelalaka
    Nov 21 '18 at 19:57











  • You do not store the results of #2.

    – James K Polk
    Nov 21 '18 at 19:57











  • Use set intersection as here

    – kelalaka
    Nov 21 '18 at 20:07











  • @JamesKPolk: Then how am I going to find the the key for the decryption?

    – Bab
    Nov 21 '18 at 20:14











  • Unfortunately you have left off critical details on your implementation. You say you have HashMaps but you don't say what is the HashMap lookup key and its value. Since you have DES keys and DES encryption results it matters.

    – James K Polk
    Nov 21 '18 at 20:44

















You need one loop not double. One loop iterates one hashmap inside search in the second.

– kelalaka
Nov 21 '18 at 19:57





You need one loop not double. One loop iterates one hashmap inside search in the second.

– kelalaka
Nov 21 '18 at 19:57













You do not store the results of #2.

– James K Polk
Nov 21 '18 at 19:57





You do not store the results of #2.

– James K Polk
Nov 21 '18 at 19:57













Use set intersection as here

– kelalaka
Nov 21 '18 at 20:07





Use set intersection as here

– kelalaka
Nov 21 '18 at 20:07













@JamesKPolk: Then how am I going to find the the key for the decryption?

– Bab
Nov 21 '18 at 20:14





@JamesKPolk: Then how am I going to find the the key for the decryption?

– Bab
Nov 21 '18 at 20:14













Unfortunately you have left off critical details on your implementation. You say you have HashMaps but you don't say what is the HashMap lookup key and its value. Since you have DES keys and DES encryption results it matters.

– James K Polk
Nov 21 '18 at 20:44





Unfortunately you have left off critical details on your implementation. You say you have HashMaps but you don't say what is the HashMap lookup key and its value. Since you have DES keys and DES encryption results it matters.

– James K Polk
Nov 21 '18 at 20:44












1 Answer
1






active

oldest

votes


















1














Here is the basic outline:



You obtain a plaintext and ciphertext pair (P, C) which you know is the result of Double DES:



C = DESk2(DESk1(P))



Now going forward you create, say, a HashMap that maps DES intermediate output to the DES key k1 that created it. So this is important: don't get confused by the HashMap keys and the DES keys, this is just an unfortunate name overload. To avoid confusion I'll call the DES keys cryptokeys. So the HashMap is from 64-bit DES outputs to 56-bit (or 20 bit in the case of your toy) DES cryptokeys.



Java psuedo-code:



Map<Long, CryptoKey> forwardMap = new HashMap();
for (CryptoKey k1=0; k1 < (1 << 20); k1++) {
Long intermediateCipher = DES-Encrypt(k1, P);
forwardMap.put(intermediateCipher, k1);
}


Now to run the attack in Java psuedo-code:



for(CryptoKey k2=0; k2 < (1 << 20); k2++) {
Long intermediateCipher = DES-Decrypt(k2, C);
if (forwardMap.contains(intermediateCipher)) {
k1 = forwardMap.get(intermediateCipher);
System.out.printf("k1=%s, k2=%s work", k1.toString(), k2.toString());
}
}





share|improve this answer


























  • You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

    – Federico Peralta Schaffner
    Nov 21 '18 at 21:26











  • @FedericoPeraltaSchaffner: Thanks, I will change it.

    – James K Polk
    Nov 21 '18 at 23:17











  • @JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

    – Bab
    Nov 24 '18 at 23:45











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
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: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
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
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53418819%2fhow-to-make-a-collection-for-the-meet-in-the-middle-attack%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









1














Here is the basic outline:



You obtain a plaintext and ciphertext pair (P, C) which you know is the result of Double DES:



C = DESk2(DESk1(P))



Now going forward you create, say, a HashMap that maps DES intermediate output to the DES key k1 that created it. So this is important: don't get confused by the HashMap keys and the DES keys, this is just an unfortunate name overload. To avoid confusion I'll call the DES keys cryptokeys. So the HashMap is from 64-bit DES outputs to 56-bit (or 20 bit in the case of your toy) DES cryptokeys.



Java psuedo-code:



Map<Long, CryptoKey> forwardMap = new HashMap();
for (CryptoKey k1=0; k1 < (1 << 20); k1++) {
Long intermediateCipher = DES-Encrypt(k1, P);
forwardMap.put(intermediateCipher, k1);
}


Now to run the attack in Java psuedo-code:



for(CryptoKey k2=0; k2 < (1 << 20); k2++) {
Long intermediateCipher = DES-Decrypt(k2, C);
if (forwardMap.contains(intermediateCipher)) {
k1 = forwardMap.get(intermediateCipher);
System.out.printf("k1=%s, k2=%s work", k1.toString(), k2.toString());
}
}





share|improve this answer


























  • You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

    – Federico Peralta Schaffner
    Nov 21 '18 at 21:26











  • @FedericoPeraltaSchaffner: Thanks, I will change it.

    – James K Polk
    Nov 21 '18 at 23:17











  • @JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

    – Bab
    Nov 24 '18 at 23:45
















1














Here is the basic outline:



You obtain a plaintext and ciphertext pair (P, C) which you know is the result of Double DES:



C = DESk2(DESk1(P))



Now going forward you create, say, a HashMap that maps DES intermediate output to the DES key k1 that created it. So this is important: don't get confused by the HashMap keys and the DES keys, this is just an unfortunate name overload. To avoid confusion I'll call the DES keys cryptokeys. So the HashMap is from 64-bit DES outputs to 56-bit (or 20 bit in the case of your toy) DES cryptokeys.



Java psuedo-code:



Map<Long, CryptoKey> forwardMap = new HashMap();
for (CryptoKey k1=0; k1 < (1 << 20); k1++) {
Long intermediateCipher = DES-Encrypt(k1, P);
forwardMap.put(intermediateCipher, k1);
}


Now to run the attack in Java psuedo-code:



for(CryptoKey k2=0; k2 < (1 << 20); k2++) {
Long intermediateCipher = DES-Decrypt(k2, C);
if (forwardMap.contains(intermediateCipher)) {
k1 = forwardMap.get(intermediateCipher);
System.out.printf("k1=%s, k2=%s work", k1.toString(), k2.toString());
}
}





share|improve this answer


























  • You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

    – Federico Peralta Schaffner
    Nov 21 '18 at 21:26











  • @FedericoPeraltaSchaffner: Thanks, I will change it.

    – James K Polk
    Nov 21 '18 at 23:17











  • @JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

    – Bab
    Nov 24 '18 at 23:45














1












1








1







Here is the basic outline:



You obtain a plaintext and ciphertext pair (P, C) which you know is the result of Double DES:



C = DESk2(DESk1(P))



Now going forward you create, say, a HashMap that maps DES intermediate output to the DES key k1 that created it. So this is important: don't get confused by the HashMap keys and the DES keys, this is just an unfortunate name overload. To avoid confusion I'll call the DES keys cryptokeys. So the HashMap is from 64-bit DES outputs to 56-bit (or 20 bit in the case of your toy) DES cryptokeys.



Java psuedo-code:



Map<Long, CryptoKey> forwardMap = new HashMap();
for (CryptoKey k1=0; k1 < (1 << 20); k1++) {
Long intermediateCipher = DES-Encrypt(k1, P);
forwardMap.put(intermediateCipher, k1);
}


Now to run the attack in Java psuedo-code:



for(CryptoKey k2=0; k2 < (1 << 20); k2++) {
Long intermediateCipher = DES-Decrypt(k2, C);
if (forwardMap.contains(intermediateCipher)) {
k1 = forwardMap.get(intermediateCipher);
System.out.printf("k1=%s, k2=%s work", k1.toString(), k2.toString());
}
}





share|improve this answer















Here is the basic outline:



You obtain a plaintext and ciphertext pair (P, C) which you know is the result of Double DES:



C = DESk2(DESk1(P))



Now going forward you create, say, a HashMap that maps DES intermediate output to the DES key k1 that created it. So this is important: don't get confused by the HashMap keys and the DES keys, this is just an unfortunate name overload. To avoid confusion I'll call the DES keys cryptokeys. So the HashMap is from 64-bit DES outputs to 56-bit (or 20 bit in the case of your toy) DES cryptokeys.



Java psuedo-code:



Map<Long, CryptoKey> forwardMap = new HashMap();
for (CryptoKey k1=0; k1 < (1 << 20); k1++) {
Long intermediateCipher = DES-Encrypt(k1, P);
forwardMap.put(intermediateCipher, k1);
}


Now to run the attack in Java psuedo-code:



for(CryptoKey k2=0; k2 < (1 << 20); k2++) {
Long intermediateCipher = DES-Decrypt(k2, C);
if (forwardMap.contains(intermediateCipher)) {
k1 = forwardMap.get(intermediateCipher);
System.out.printf("k1=%s, k2=%s work", k1.toString(), k2.toString());
}
}






share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 21 '18 at 23:18

























answered Nov 21 '18 at 21:01









James K PolkJames K Polk

30.3k116897




30.3k116897













  • You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

    – Federico Peralta Schaffner
    Nov 21 '18 at 21:26











  • @FedericoPeraltaSchaffner: Thanks, I will change it.

    – James K Polk
    Nov 21 '18 at 23:17











  • @JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

    – Bab
    Nov 24 '18 at 23:45



















  • You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

    – Federico Peralta Schaffner
    Nov 21 '18 at 21:26











  • @FedericoPeraltaSchaffner: Thanks, I will change it.

    – James K Polk
    Nov 21 '18 at 23:17











  • @JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

    – Bab
    Nov 24 '18 at 23:45

















You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

– Federico Peralta Schaffner
Nov 21 '18 at 21:26





You can't use byte as the key, it doesn't implement hashCode and equals, so it won't work, i.e. forwardMap.contains(intermediateCipher) will always return false

– Federico Peralta Schaffner
Nov 21 '18 at 21:26













@FedericoPeraltaSchaffner: Thanks, I will change it.

– James K Polk
Nov 21 '18 at 23:17





@FedericoPeraltaSchaffner: Thanks, I will change it.

– James K Polk
Nov 21 '18 at 23:17













@JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

– Bab
Nov 24 '18 at 23:45





@JamesKPolk; I just want to be sure about something. What is CryptoKeys in the for loop? I read that you have named the DES keys cryptokey, but how do I use them in a for loop?

– Bab
Nov 24 '18 at 23:45




















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53418819%2fhow-to-make-a-collection-for-the-meet-in-the-middle-attack%23new-answer', 'question_page');
}
);

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







這個網誌中的熱門文章

Xamarin.form Move up view when keyboard appear

Post-Redirect-Get with Spring WebFlux and Thymeleaf

Anylogic : not able to use stopDelay()