Is it possible to find the key for AES ECB if I have a list of plaintext and corresponding ciphertext?












7














Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?



If, how big does the list of plaintext and matching ciphertext have to be to be able to find it in a feasable amount of time (say in 1 or 2 hours)?










share|improve this question




















  • 1




    Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext?
    – ymbirtt
    Nov 12 at 11:26










  • @ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB!
    – Richard Jones
    Nov 12 at 14:24












  • @Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used.
    – Klaws
    Nov 12 at 16:43
















7














Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?



If, how big does the list of plaintext and matching ciphertext have to be to be able to find it in a feasable amount of time (say in 1 or 2 hours)?










share|improve this question




















  • 1




    Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext?
    – ymbirtt
    Nov 12 at 11:26










  • @ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB!
    – Richard Jones
    Nov 12 at 14:24












  • @Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used.
    – Klaws
    Nov 12 at 16:43














7












7








7


1





Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?



If, how big does the list of plaintext and matching ciphertext have to be to be able to find it in a feasable amount of time (say in 1 or 2 hours)?










share|improve this question















Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?



If, how big does the list of plaintext and matching ciphertext have to be to be able to find it in a feasable amount of time (say in 1 or 2 hours)?







aes attack known-plaintext-attack ecb






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 12 at 2:15









e-sushi

13.6k863172




13.6k863172










asked Nov 11 at 18:30









Richard Jones

413




413








  • 1




    Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext?
    – ymbirtt
    Nov 12 at 11:26










  • @ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB!
    – Richard Jones
    Nov 12 at 14:24












  • @Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used.
    – Klaws
    Nov 12 at 16:43














  • 1




    Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext?
    – ymbirtt
    Nov 12 at 11:26










  • @ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB!
    – Richard Jones
    Nov 12 at 14:24












  • @Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used.
    – Klaws
    Nov 12 at 16:43








1




1




Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext?
– ymbirtt
Nov 12 at 11:26




Whilst you can't recover the key, as the other answers have indicated, there are other attacks you can perform in this scenario. What's your actual objective? Are you just interested in key-recovery, or do you have a large corpus of very similar plaintexts, and you're interested in the plaintext corresponding to a new, unknown ciphertext?
– ymbirtt
Nov 12 at 11:26












@ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB!
– Richard Jones
Nov 12 at 14:24






@ymbirtt they gave us this list as homework which has a ciphertext and its corresponding text in it, like 50-60 and somehow we have to decrypt a flag which was encrypted by the same key? i only know its encrypted by AES ECB!
– Richard Jones
Nov 12 at 14:24














@Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used.
– Klaws
Nov 12 at 16:43




@Richard Jones: Quite possibly, the cleartext has been encoded character by character - each character individually, without any internal state or whatever. This reduces the encryption to a simple substitution cipher (like the Caesar Cipher). That way, when character "x" in the cleartext corresponds to character "y" in the ciphertext at one position, a "y" in the ciphertext will always be an "x" in the cleartext. Look here: crypto.stackexchange.com/questions/20941/…. Less obvious when a blocks size != 8 bits is used.
– Klaws
Nov 12 at 16:43










3 Answers
3






active

oldest

votes


















15















Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?




No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.






share|improve this answer























  • So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
    – Richard Jones
    Nov 12 at 21:43










  • Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
    – kiwidrew
    Nov 13 at 1:42



















10














What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour.



In brute-force, the number of elements in your list is not important. The problem is the key-size. You have to check every possible key to match one of your plaintext-ciphertext pair;



for each k in possible keys
if E(k,P1) == C1
testWithSomeOtherPair(k)


Once you found you can verify with the other plaintext-ciphertext pairs.



Note: there are other types of attacks (related-key attacks) faster than the brute-force for AES-192 and AES-256 with $2^{176}$ and $2^{99.5}$-time, respectively. But they are still infeasible to reach. For AES-128, the fastest known is the Biclique attack with $2^{126.2}$ and that is still infeasible and in practice, the brute-force may still beat the Biclique attack which requires $2^{88}$-data and $2^8$-memory. Biclique attack for AES-192 and AES-256 runs with $2^{189.7}$ and $2^{254.4}$ computational complexity, respectively.






share|improve this answer























  • So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
    – Richard Jones
    Nov 11 at 18:59












  • Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
    – kelalaka
    Nov 11 at 19:03










  • @RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
    – Clockwork-Muse
    Nov 12 at 3:29



















3














As the other answers have mentioned, you basically have no hope of executing a key-recovery attack. This does not mean, however, that you should give up and go home. Key recovery is not the only kind of attack, and the information you have available gives you a different attack, which allows you to decrypt some ciphertexts without using the key. The other answers don't mention the fact that this encryption scheme uses ECB-mode.



As you mentioned in a comment, you have a list of valid and related plaintext/ciphertext pairs, and you have another ciphertext, and you want to make an educated guess as to its corresponding plaintext.



The use of ECB mode gives us a credible attack. Recall the operation of ECB:



A diagram showing ECB-mode's operation



Each plaintext block is fed into the block cipher, and the corresponding ciphertext block is just its output. This means that, wherever the plaintext block appears in whichever message, the output ciphertext will always be identical.



AES usually uses a 128-bit block-size, which is 16 bytes. You might have 192- or 256-bit AES, but I don't see these quite so often. This means that if you split your plaintexts and ciphertexts into 16-byte chunks you might see see that in one chunk the plaintext 11 22 33 44 55 66 77 88 99 00 aa bb cc dd ee ff corresponds to the ciphertext 12 34 56 78 90 ab cd ef fe dc ba 09 87 65 43 21. Now, whenever you see that ciphertext in any message ever, you can map it back to that plaintext!



Now, you mentioned that this was a homework question. You should write some software to do this for you, and exactly what that looks like I'm not going to say because we aren't a homework solving service, but hopefully you should be able to use this insight to recover your flag.



Your next lessons are probably going to talk about CTR and CFB encryption modes, which stop this attack from working.






share|improve this answer



















  • 1




    Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
    – Klaws
    Nov 12 at 16:51










  • The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
    – symcbean
    Dec 18 at 0:10










  • @symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
    – ymbirtt
    Dec 18 at 9:17










  • @symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
    – ymbirtt
    Dec 18 at 9:21










  • Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
    – symcbean
    Dec 18 at 10:11











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63883%2fis-it-possible-to-find-the-key-for-aes-ecb-if-i-have-a-list-of-plaintext-and-cor%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























3 Answers
3






active

oldest

votes








3 Answers
3






active

oldest

votes









active

oldest

votes






active

oldest

votes









15















Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?




No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.






share|improve this answer























  • So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
    – Richard Jones
    Nov 12 at 21:43










  • Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
    – kiwidrew
    Nov 13 at 1:42
















15















Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?




No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.






share|improve this answer























  • So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
    – Richard Jones
    Nov 12 at 21:43










  • Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
    – kiwidrew
    Nov 13 at 1:42














15












15








15







Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?




No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.






share|improve this answer















Assume I have a list of plaintext text and its corresponding ciphertext which was created using a specific key with AES in ECB mode.



Can I recover that key?




No. This is what is referred to as a known plaintext attack, and secure block ciphers are designed to prevent exactly this kind of attack. This answer on the Mathematics Stack Exchange goes into more detail about the notion of IND-CPA ("indistinguishability") which AES is conjectured to meet and how that implies that a known plaintext attack is impossible.







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 12 at 2:16









e-sushi

13.6k863172




13.6k863172










answered Nov 11 at 23:50









kiwidrew

4489




4489












  • So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
    – Richard Jones
    Nov 12 at 21:43










  • Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
    – kiwidrew
    Nov 13 at 1:42


















  • So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
    – Richard Jones
    Nov 12 at 21:43










  • Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
    – kiwidrew
    Nov 13 at 1:42
















So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
– Richard Jones
Nov 12 at 21:43




So i can't find the key, but if I'm lucky and most of the texts are the same, i can find the plain text of a ciphertext which was encrypted by the same key, right?
– Richard Jones
Nov 12 at 21:43












Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
– kiwidrew
Nov 13 at 1:42




Have a look at @ymbirtt's excellent answer regarding other attacks against AES that you can do when using ECB mode.
– kiwidrew
Nov 13 at 1:42











10














What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour.



In brute-force, the number of elements in your list is not important. The problem is the key-size. You have to check every possible key to match one of your plaintext-ciphertext pair;



for each k in possible keys
if E(k,P1) == C1
testWithSomeOtherPair(k)


Once you found you can verify with the other plaintext-ciphertext pairs.



Note: there are other types of attacks (related-key attacks) faster than the brute-force for AES-192 and AES-256 with $2^{176}$ and $2^{99.5}$-time, respectively. But they are still infeasible to reach. For AES-128, the fastest known is the Biclique attack with $2^{126.2}$ and that is still infeasible and in practice, the brute-force may still beat the Biclique attack which requires $2^{88}$-data and $2^8$-memory. Biclique attack for AES-192 and AES-256 runs with $2^{189.7}$ and $2^{254.4}$ computational complexity, respectively.






share|improve this answer























  • So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
    – Richard Jones
    Nov 11 at 18:59












  • Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
    – kelalaka
    Nov 11 at 19:03










  • @RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
    – Clockwork-Muse
    Nov 12 at 3:29
















10














What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour.



In brute-force, the number of elements in your list is not important. The problem is the key-size. You have to check every possible key to match one of your plaintext-ciphertext pair;



for each k in possible keys
if E(k,P1) == C1
testWithSomeOtherPair(k)


Once you found you can verify with the other plaintext-ciphertext pairs.



Note: there are other types of attacks (related-key attacks) faster than the brute-force for AES-192 and AES-256 with $2^{176}$ and $2^{99.5}$-time, respectively. But they are still infeasible to reach. For AES-128, the fastest known is the Biclique attack with $2^{126.2}$ and that is still infeasible and in practice, the brute-force may still beat the Biclique attack which requires $2^{88}$-data and $2^8$-memory. Biclique attack for AES-192 and AES-256 runs with $2^{189.7}$ and $2^{254.4}$ computational complexity, respectively.






share|improve this answer























  • So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
    – Richard Jones
    Nov 11 at 18:59












  • Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
    – kelalaka
    Nov 11 at 19:03










  • @RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
    – Clockwork-Muse
    Nov 12 at 3:29














10












10








10






What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour.



In brute-force, the number of elements in your list is not important. The problem is the key-size. You have to check every possible key to match one of your plaintext-ciphertext pair;



for each k in possible keys
if E(k,P1) == C1
testWithSomeOtherPair(k)


Once you found you can verify with the other plaintext-ciphertext pairs.



Note: there are other types of attacks (related-key attacks) faster than the brute-force for AES-192 and AES-256 with $2^{176}$ and $2^{99.5}$-time, respectively. But they are still infeasible to reach. For AES-128, the fastest known is the Biclique attack with $2^{126.2}$ and that is still infeasible and in practice, the brute-force may still beat the Biclique attack which requires $2^{88}$-data and $2^8$-memory. Biclique attack for AES-192 and AES-256 runs with $2^{189.7}$ and $2^{254.4}$ computational complexity, respectively.






share|improve this answer














What is the simplest attack is the Brute Force Attack. However, it is infeasible to brute-force even AES-128 bit, AES also supports 192, and 256-bit keys sizes. To break the AES-128 with brute force, you need to execute $2^{128}$ AES operations, today's top computers can reach $2^{63}$ around one hour.



In brute-force, the number of elements in your list is not important. The problem is the key-size. You have to check every possible key to match one of your plaintext-ciphertext pair;



for each k in possible keys
if E(k,P1) == C1
testWithSomeOtherPair(k)


Once you found you can verify with the other plaintext-ciphertext pairs.



Note: there are other types of attacks (related-key attacks) faster than the brute-force for AES-192 and AES-256 with $2^{176}$ and $2^{99.5}$-time, respectively. But they are still infeasible to reach. For AES-128, the fastest known is the Biclique attack with $2^{126.2}$ and that is still infeasible and in practice, the brute-force may still beat the Biclique attack which requires $2^{88}$-data and $2^8$-memory. Biclique attack for AES-192 and AES-256 runs with $2^{189.7}$ and $2^{254.4}$ computational complexity, respectively.







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 11 at 19:39

























answered Nov 11 at 18:34









kelalaka

5,44322040




5,44322040












  • So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
    – Richard Jones
    Nov 11 at 18:59












  • Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
    – kelalaka
    Nov 11 at 19:03










  • @RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
    – Clockwork-Muse
    Nov 12 at 3:29


















  • So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
    – Richard Jones
    Nov 11 at 18:59












  • Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
    – kelalaka
    Nov 11 at 19:03










  • @RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
    – Clockwork-Muse
    Nov 12 at 3:29
















So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
– Richard Jones
Nov 11 at 18:59






So even if we have millions of texts and their corresponding ciphertext using our key, it wouldn't help us to find the key?
– Richard Jones
Nov 11 at 18:59














Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
– kelalaka
Nov 11 at 19:03




Short answer no. For brute-force, you need only a couple of pairs. There are attacks like biclique attack, but that requires $2^{126.2}$ operations for AES-128. You can find some other attacks at Wikipedia but you will not see they are better than biclique attack.
– kelalaka
Nov 11 at 19:03












@RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
– Clockwork-Muse
Nov 12 at 3:29




@RichardJones - Note that in a straight brute force attack, knowing the plain text is only for verification - that is, knowing the plain text doesn't help in the decryption at all, and probably isn't necessary (an incorrect key is usually going to generate gibberish in at least some part of a sufficient length message).
– Clockwork-Muse
Nov 12 at 3:29











3














As the other answers have mentioned, you basically have no hope of executing a key-recovery attack. This does not mean, however, that you should give up and go home. Key recovery is not the only kind of attack, and the information you have available gives you a different attack, which allows you to decrypt some ciphertexts without using the key. The other answers don't mention the fact that this encryption scheme uses ECB-mode.



As you mentioned in a comment, you have a list of valid and related plaintext/ciphertext pairs, and you have another ciphertext, and you want to make an educated guess as to its corresponding plaintext.



The use of ECB mode gives us a credible attack. Recall the operation of ECB:



A diagram showing ECB-mode's operation



Each plaintext block is fed into the block cipher, and the corresponding ciphertext block is just its output. This means that, wherever the plaintext block appears in whichever message, the output ciphertext will always be identical.



AES usually uses a 128-bit block-size, which is 16 bytes. You might have 192- or 256-bit AES, but I don't see these quite so often. This means that if you split your plaintexts and ciphertexts into 16-byte chunks you might see see that in one chunk the plaintext 11 22 33 44 55 66 77 88 99 00 aa bb cc dd ee ff corresponds to the ciphertext 12 34 56 78 90 ab cd ef fe dc ba 09 87 65 43 21. Now, whenever you see that ciphertext in any message ever, you can map it back to that plaintext!



Now, you mentioned that this was a homework question. You should write some software to do this for you, and exactly what that looks like I'm not going to say because we aren't a homework solving service, but hopefully you should be able to use this insight to recover your flag.



Your next lessons are probably going to talk about CTR and CFB encryption modes, which stop this attack from working.






share|improve this answer



















  • 1




    Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
    – Klaws
    Nov 12 at 16:51










  • The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
    – symcbean
    Dec 18 at 0:10










  • @symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
    – ymbirtt
    Dec 18 at 9:17










  • @symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
    – ymbirtt
    Dec 18 at 9:21










  • Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
    – symcbean
    Dec 18 at 10:11
















3














As the other answers have mentioned, you basically have no hope of executing a key-recovery attack. This does not mean, however, that you should give up and go home. Key recovery is not the only kind of attack, and the information you have available gives you a different attack, which allows you to decrypt some ciphertexts without using the key. The other answers don't mention the fact that this encryption scheme uses ECB-mode.



As you mentioned in a comment, you have a list of valid and related plaintext/ciphertext pairs, and you have another ciphertext, and you want to make an educated guess as to its corresponding plaintext.



The use of ECB mode gives us a credible attack. Recall the operation of ECB:



A diagram showing ECB-mode's operation



Each plaintext block is fed into the block cipher, and the corresponding ciphertext block is just its output. This means that, wherever the plaintext block appears in whichever message, the output ciphertext will always be identical.



AES usually uses a 128-bit block-size, which is 16 bytes. You might have 192- or 256-bit AES, but I don't see these quite so often. This means that if you split your plaintexts and ciphertexts into 16-byte chunks you might see see that in one chunk the plaintext 11 22 33 44 55 66 77 88 99 00 aa bb cc dd ee ff corresponds to the ciphertext 12 34 56 78 90 ab cd ef fe dc ba 09 87 65 43 21. Now, whenever you see that ciphertext in any message ever, you can map it back to that plaintext!



Now, you mentioned that this was a homework question. You should write some software to do this for you, and exactly what that looks like I'm not going to say because we aren't a homework solving service, but hopefully you should be able to use this insight to recover your flag.



Your next lessons are probably going to talk about CTR and CFB encryption modes, which stop this attack from working.






share|improve this answer



















  • 1




    Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
    – Klaws
    Nov 12 at 16:51










  • The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
    – symcbean
    Dec 18 at 0:10










  • @symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
    – ymbirtt
    Dec 18 at 9:17










  • @symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
    – ymbirtt
    Dec 18 at 9:21










  • Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
    – symcbean
    Dec 18 at 10:11














3












3








3






As the other answers have mentioned, you basically have no hope of executing a key-recovery attack. This does not mean, however, that you should give up and go home. Key recovery is not the only kind of attack, and the information you have available gives you a different attack, which allows you to decrypt some ciphertexts without using the key. The other answers don't mention the fact that this encryption scheme uses ECB-mode.



As you mentioned in a comment, you have a list of valid and related plaintext/ciphertext pairs, and you have another ciphertext, and you want to make an educated guess as to its corresponding plaintext.



The use of ECB mode gives us a credible attack. Recall the operation of ECB:



A diagram showing ECB-mode's operation



Each plaintext block is fed into the block cipher, and the corresponding ciphertext block is just its output. This means that, wherever the plaintext block appears in whichever message, the output ciphertext will always be identical.



AES usually uses a 128-bit block-size, which is 16 bytes. You might have 192- or 256-bit AES, but I don't see these quite so often. This means that if you split your plaintexts and ciphertexts into 16-byte chunks you might see see that in one chunk the plaintext 11 22 33 44 55 66 77 88 99 00 aa bb cc dd ee ff corresponds to the ciphertext 12 34 56 78 90 ab cd ef fe dc ba 09 87 65 43 21. Now, whenever you see that ciphertext in any message ever, you can map it back to that plaintext!



Now, you mentioned that this was a homework question. You should write some software to do this for you, and exactly what that looks like I'm not going to say because we aren't a homework solving service, but hopefully you should be able to use this insight to recover your flag.



Your next lessons are probably going to talk about CTR and CFB encryption modes, which stop this attack from working.






share|improve this answer














As the other answers have mentioned, you basically have no hope of executing a key-recovery attack. This does not mean, however, that you should give up and go home. Key recovery is not the only kind of attack, and the information you have available gives you a different attack, which allows you to decrypt some ciphertexts without using the key. The other answers don't mention the fact that this encryption scheme uses ECB-mode.



As you mentioned in a comment, you have a list of valid and related plaintext/ciphertext pairs, and you have another ciphertext, and you want to make an educated guess as to its corresponding plaintext.



The use of ECB mode gives us a credible attack. Recall the operation of ECB:



A diagram showing ECB-mode's operation



Each plaintext block is fed into the block cipher, and the corresponding ciphertext block is just its output. This means that, wherever the plaintext block appears in whichever message, the output ciphertext will always be identical.



AES usually uses a 128-bit block-size, which is 16 bytes. You might have 192- or 256-bit AES, but I don't see these quite so often. This means that if you split your plaintexts and ciphertexts into 16-byte chunks you might see see that in one chunk the plaintext 11 22 33 44 55 66 77 88 99 00 aa bb cc dd ee ff corresponds to the ciphertext 12 34 56 78 90 ab cd ef fe dc ba 09 87 65 43 21. Now, whenever you see that ciphertext in any message ever, you can map it back to that plaintext!



Now, you mentioned that this was a homework question. You should write some software to do this for you, and exactly what that looks like I'm not going to say because we aren't a homework solving service, but hopefully you should be able to use this insight to recover your flag.



Your next lessons are probably going to talk about CTR and CFB encryption modes, which stop this attack from working.







share|improve this answer














share|improve this answer



share|improve this answer








edited Nov 12 at 14:46

























answered Nov 12 at 14:40









ymbirtt

1838




1838








  • 1




    Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
    – Klaws
    Nov 12 at 16:51










  • The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
    – symcbean
    Dec 18 at 0:10










  • @symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
    – ymbirtt
    Dec 18 at 9:17










  • @symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
    – ymbirtt
    Dec 18 at 9:21










  • Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
    – symcbean
    Dec 18 at 10:11














  • 1




    Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
    – Klaws
    Nov 12 at 16:51










  • The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
    – symcbean
    Dec 18 at 0:10










  • @symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
    – ymbirtt
    Dec 18 at 9:17










  • @symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
    – ymbirtt
    Dec 18 at 9:21










  • Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
    – symcbean
    Dec 18 at 10:11








1




1




Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
– Klaws
Nov 12 at 16:51




Some wireless keyboards which boast "AES encryption" actually use AES ECB to encode each keypress separately. No filling the 128 bit (or whatever) block with random noise or whatever, so once you figure which code is transmitted for each key, you are done. Basically, an "advanced" Caesar Cipher, except that it's easier to break, as you have the timing of the keypresses. A user working on the shell will often have a significant pause after a certain keycode....yep, that's the enter/return key.
– Klaws
Nov 12 at 16:51












The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
– symcbean
Dec 18 at 0:10




The ordering of records in the data file is very unlikely to match between the two databases, hence the suggested attack is unlikely to be effective.
– symcbean
Dec 18 at 0:10












@symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
– ymbirtt
Dec 18 at 9:17




@symcbean, I'm not sure I understand your comment. ECB mode is homomorphic under a reordering of the blocks, and OP has specifically said in a comment that they have a set of corresponding plaintext/ciphertext pairs. Moving this into a more "real-world" scenario where this was used for some kind of database file, 16 bytes isn't a lot of data, so it's likely for database records to straddle multiple blocks, and for some amount of that data to repeat itself. Whilst it wouldn't lead to a complete decryption in the real world, it's still likely to leak quite a lot of information.
– ymbirtt
Dec 18 at 9:17












@symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
– ymbirtt
Dec 18 at 9:21




@symcbean, I've noticed that this is linked from security.stackexchange.com/questions/199879/… - if my answer were given to the question in that post, then yes, your criticism makes sense, but OP here has a slightly different problem.
– ymbirtt
Dec 18 at 9:21












Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
– symcbean
Dec 18 at 10:11




Sorry - yes, comment made in relation to that question, where the data might be the same but not the cleartext.
– symcbean
Dec 18 at 10:11


















draft saved

draft discarded




















































Thanks for contributing an answer to Cryptography Stack Exchange!


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

But avoid



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

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


Use MathJax to format equations. MathJax reference.


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





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


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

But avoid



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

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


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




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f63883%2fis-it-possible-to-find-the-key-for-aes-ecb-if-i-have-a-list-of-plaintext-and-cor%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()