I don't understand lookup tables












1















I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:



For Brute Force:




  • Preparation time: $O(1)$


  • Disk space requirement: $O(1)$


  • Time required to crack the password: $O(2^n)$



Full lookup table:




  • Preparation time: $O(2^n)$


  • Disk space requirement: $O(2^n)$


  • Time required to crack the password: $O(1)$



I'm not sure I'm understanding this correctly.



As far as I understand, for Brute Force:



$O(1)$ is the time required to look up the password in my table of all possible passwords.
The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well



My questions:



Why is the time needed to crack the password $O(2^n)$? How is it determined?



It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster?



I think I'm missing something crucial here. Any help will be appreciated.






brute-force-attack complexity







share|improve this question









New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1





    n-bit input so you need to look for $2^n$ possible passwords.

    – kelalaka
    1 hour ago













  • @kelalaka: Thanks! I can follow that, at least.

    – Fang
    1 hour ago
















1















I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:



For Brute Force:




  • Preparation time: $O(1)$


  • Disk space requirement: $O(1)$


  • Time required to crack the password: $O(2^n)$



Full lookup table:




  • Preparation time: $O(2^n)$


  • Disk space requirement: $O(2^n)$


  • Time required to crack the password: $O(1)$



I'm not sure I'm understanding this correctly.



As far as I understand, for Brute Force:



$O(1)$ is the time required to look up the password in my table of all possible passwords.
The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well



My questions:



Why is the time needed to crack the password $O(2^n)$? How is it determined?



It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster?



I think I'm missing something crucial here. Any help will be appreciated.






brute-force-attack complexity







share|improve this question









New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
















  • 1





    n-bit input so you need to look for $2^n$ possible passwords.

    – kelalaka
    1 hour ago













  • @kelalaka: Thanks! I can follow that, at least.

    – Fang
    1 hour ago














1












1








1








I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:



For Brute Force:




  • Preparation time: $O(1)$


  • Disk space requirement: $O(1)$


  • Time required to crack the password: $O(2^n)$



Full lookup table:




  • Preparation time: $O(2^n)$


  • Disk space requirement: $O(2^n)$


  • Time required to crack the password: $O(1)$



I'm not sure I'm understanding this correctly.



As far as I understand, for Brute Force:



$O(1)$ is the time required to look up the password in my table of all possible passwords.
The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well



My questions:



Why is the time needed to crack the password $O(2^n)$? How is it determined?



It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster?



I think I'm missing something crucial here. Any help will be appreciated.






brute-force-attack complexity







share|improve this question









New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.












I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:



For Brute Force:




  • Preparation time: $O(1)$


  • Disk space requirement: $O(1)$


  • Time required to crack the password: $O(2^n)$



Full lookup table:




  • Preparation time: $O(2^n)$


  • Disk space requirement: $O(2^n)$


  • Time required to crack the password: $O(1)$



I'm not sure I'm understanding this correctly.



As far as I understand, for Brute Force:



$O(1)$ is the time required to look up the password in my table of all possible passwords.
The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well



My questions:



Why is the time needed to crack the password $O(2^n)$? How is it determined?



It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster?



I think I'm missing something crucial here. Any help will be appreciated.






brute-force-attack complexity




brute-force-attack complexity






share|improve this question









New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.











share|improve this question









New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









share|improve this question




share|improve this question








edited 1 hour ago









AleksanderRas

1,9311628




1,9311628






New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.









asked 2 hours ago









FangFang

1085




1085




New contributor




Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.





New contributor





Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.






Fang is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.








  • 1





    n-bit input so you need to look for $2^n$ possible passwords.

    – kelalaka
    1 hour ago













  • @kelalaka: Thanks! I can follow that, at least.

    – Fang
    1 hour ago














  • 1





    n-bit input so you need to look for $2^n$ possible passwords.

    – kelalaka
    1 hour ago













  • @kelalaka: Thanks! I can follow that, at least.

    – Fang
    1 hour ago








1




1





n-bit input so you need to look for $2^n$ possible passwords.

– kelalaka
1 hour ago







n-bit input so you need to look for $2^n$ possible passwords.

– kelalaka
1 hour ago















@kelalaka: Thanks! I can follow that, at least.

– Fang
1 hour ago





@kelalaka: Thanks! I can follow that, at least.

– Fang
1 hour ago










1 Answer
1






active

oldest

votes


















2














Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.



Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $kgets F(k)$. This will take $mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $mathcal O(1)$ the entire calculation takes $mathcal O(2^n)$.



Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.






share|improve this answer





















  • 1





    Interesting way to explain. There is a typo at the end. I would like to add this

    – kelalaka
    49 mins ago













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
});


}
});






Fang is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66461%2fi-dont-understand-lookup-tables%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









2














Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.



Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $kgets F(k)$. This will take $mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $mathcal O(1)$ the entire calculation takes $mathcal O(2^n)$.



Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.






share|improve this answer





















  • 1





    Interesting way to explain. There is a typo at the end. I would like to add this

    – kelalaka
    49 mins ago


















2














Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.



Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $kgets F(k)$. This will take $mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $mathcal O(1)$ the entire calculation takes $mathcal O(2^n)$.



Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.






share|improve this answer





















  • 1





    Interesting way to explain. There is a typo at the end. I would like to add this

    – kelalaka
    49 mins ago
















2












2








2







Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.



Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $kgets F(k)$. This will take $mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $mathcal O(1)$ the entire calculation takes $mathcal O(2^n)$.



Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.






share|improve this answer















Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.



Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $kgets F(k)$. This will take $mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $mathcal O(1)$ the entire calculation takes $mathcal O(2^n)$.



Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.







share|improve this answer














share|improve this answer



share|improve this answer








edited 15 mins ago









kelalaka

6,17522142




6,17522142










answered 59 mins ago









SEJPM♦SEJPM

28.6k554132




28.6k554132








  • 1





    Interesting way to explain. There is a typo at the end. I would like to add this

    – kelalaka
    49 mins ago
















  • 1





    Interesting way to explain. There is a typo at the end. I would like to add this

    – kelalaka
    49 mins ago










1




1





Interesting way to explain. There is a typo at the end. I would like to add this

– kelalaka
49 mins ago







Interesting way to explain. There is a typo at the end. I would like to add this

– kelalaka
49 mins ago












Fang is a new contributor. Be nice, and check out our Code of Conduct.










draft saved

draft discarded


















Fang is a new contributor. Be nice, and check out our Code of Conduct.













Fang is a new contributor. Be nice, and check out our Code of Conduct.












Fang is a new contributor. Be nice, and check out our Code of Conduct.
















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.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66461%2fi-dont-understand-lookup-tables%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







-

Popular posts from this blog

Liste der Baudenkmale in Friedland (Mecklenburg)

Image
In der Liste der Baudenkmale in Friedland sind alle denkmalgeschützten Bauten der Stadt Friedland (Mecklenburg-Vorpommern) und ihrer Ortsteile aufgelistet. Grundlage ist die Veröffentlichung der Denkmalliste des Landkreises Mecklenburgische Seenplatte (Auszug) vom 28. September 2016. Inhaltsverzeichnis 1 Baudenkmale nach Ortsteilen 1.1 Friedland 1.2 Bresewitz 1.3 Brohm 1.4 Cosa 1.5 Dishley 1.6 Dishley-Ausbau 1.7 Eichhorst 1.8 Glienke 1.9 Heinrichshöh 1.10 Heinrichswalde 1.11 Jatzke 1.12 Jatzke-Meierei 1.13 Liepen 1.14 Ramelow 1.15 Schwanbeck 2 Vorgesehener Denkmalbereich 3 Quelle 4 Weblinks Baudenkmale nach Ortsteilen | Friedland | ID Lage Bezeichnung Beschreibung Bild 281 An der Kleinbahn 2 Windmühle mit Umgang 282 Anklamer Straße alter Friedhof mit Portalwand 282 Anklamer Straße drei Erbbegräbnissen und Gräbern u. a. H.A. Riemann 284
Read more

Single-Malt-Whisky

Image
Fünf verschiedene schottische Single-Malt-Whiskys Als Single-Malt-Whisky oder kürzer Single Malt werden Whiskys bezeichnet, die zwei besondere Bedingungen erfüllen: Sie stammen zum ersten aus einer einzigen Brennerei, sind also kein Verschnitt aus mehreren Whiskysorten (daher Single , deutsch: einzeln). Zum zweiten wird als Getreide ausschließlich gemälzte Gerste verwendet (deswegen Malt , deutsch: Malz). Der Zusatz Single Malt wird als Prädikat verstanden, die so ausgezeichneten Whiskys sind in aller Regel besonders hochwertig. Hinzu kommt ihre besonders lange Lagerung, die Reifungszeit währt oft ein Jahrzehnt und länger. Inhaltsverzeichnis 1 Allgemeines 2 Herkunftsländer 2.1 Schottland 2.2 Irland 2.3 Japan 2.4 Kontinentaleuropa 3 Produktionsschritte 3.1 Mälzen 3.2 Brauen 3.3 Brennen 3.4 Reifung und Finish 3.5 Abfüllung 4 Altersangaben 5 Lagerung von Whiskyflaschen 6 Geschmacksklassifikation 7 Sonstig
Read more

Czorneboh

Image
Dieser Artikel erläutert den Berg Czorneboh, für die Gottheit siehe Czorneboh (Gottheit). Czorneboh Čornobóh Berggasthof mit Turm Höhe 555,7  m ü. NHN [1] Lage Freistaat Sachsen, Deutschland Gebirge Lausitzer Bergland Dominanz 15,4 km →  Kottmar Koordinaten 51° 7′ 11″  N , 14° 31′ 31″  O 51.119722222222 14.525194444444 555.7 Koordinaten: 51° 7′ 11″  N , 14° 31′ 31″  O Gestein Granodiorit Besonderheiten Aussichtsturm Czorneboh Der Czorneboh , obersorbisch Čornobóh , ist ein Berg zwischen Hochkirch und Cunewalde in der Oberlausitz. Er gehört zu der südöstlich von Bautzen gelegenen Czorneboh-Bergkette und ist mit einer Höhe von 555,7  m ü. NHN [1] der höchste Punkt dieses Ausläufers des Lausitzer Berglandes. Er leitet als Landschaftselement die wellige Granitlandschaft der Lausitzer Vorbergzone ein. Der Gipfel des Czorneboh liegt in der Gemarkung Meschwitz (Gemeinde Hochkirch), die Czornebohbaude jedoch
Read more