Let $\mathcal{M}$ be our message space and $\mathcal{K}$ our key space. Now, let $\mathrm{E} : \mathcal{K} \times \mathcal{M} \to \mathcal{M}$ be a block cipher. Define the block cipher $\mathrm{EX}((k_1, k_2, k_3), m) := k_1 \oplus \mathrm{E}(k_2, m \oplus k_3)$, where $m \in \mathcal{M}$, $k_2 \in \mathcal{K}$, and $k_1$ and $k_3$ are of the same length as the message (I suppose I could write $k_1, k_3 \in \mathcal{M}$).  In the case of DES, we get , giving us a total key size of $64 + 56 + 64 = 184$ bits.  At the end of  (as well as what can be inferred from the Wikipedia entry), prof. Dan Boneh mentions that there is a simple attack on all block ciphers of the form $\mathrm{EX}$ in time $|\mathcal{K}| \cdot |\mathcal{M}|$, meaning a simple attack on DESX in time $2^{120}$.  I finished the course during this summer and generally had no problems, but could not figure this attack out for DESX / the general case. Can anyone explain to me what it is?
124219
The passage said that the computational load to attack DES-X can be reduced to approximately $2^{(56+64)}=2^{120}$ steps,and  the storage of data sets should be $2^{64}$.  But I can't figure why it is time complexity $2^{120}$ and  the (space complexity) of data sets should be $2^{64}$.  Can somebody help?
110421
I am new to crypto and trying to understand if it would be insecure to use a cipher such as AES to encrypt a key with the same key. If it is insecure, then why would it be insecure?  Basically, something like this:  encrypt(key, key)   What happens when both key and message are the same (128 bits)?  The obvious question would be why would I want to do that. If I have a secure channel to send the key, why encrypt it? My question is more for understanding.
37774
Modern stream ciphers usually predicts the usage of a nonce (also termed as IV) in the cryptosystem. The cost of initializing the cipher with the nonce varies from algorithm to algorithm (for instance, this cost seems very high on HC-256 and negligible on Salsa 20). I would like to know the correct usage pattern of a nonce together with the stream cipher in a cryptosystem. The only thing I know for sure is that they must never repeat...   Does it needs to be new for every transmitted message? It must be secret? (Is it assumed to be known by an attacker)?
69464
I know a plaintext - ciphertext couple of length 6 for a hill cipher where its key is a [3x3] matrix.  Based on what I've read and learned, to attack and crack keys of [n x n], if we know a plaintext - ciphertext duo of length $n^2$ then we have our set of n equations with n variables, and this is generally solvable. However in my case there is only length of $6$ instead of $n^2 = 9$ .   My question is, how will I solve this problem and find the key? Or, since this is an obvious homework question, what should be my way of thinking? I cannot think of anything else but matrix multiplications and inverses but they do not help me at all.
617
I understand how for hash functions which are vulnerable to length extension attacks (such as SHA1 and SHA2) it is safer to use a HMAC construction.  What I don't understand is, how or why is $\operatorname{HMAC\_SHA256}_\mathrm{key}(\mathrm{message})$ safer (in terms of resistant against certain attacks) than $\operatorname{SHA256}(\mathrm{key}_1 \mathbin\| \mathrm{message} \mathbin\| \mathrm{key}_2)$, assuming that all key strings are sufficient in length and entropy?
59726
I have read a lot of summaries of block ciphers particularly with regards to the NIST competitions stating that reduced-round block ciphers are – for example – vulnerable to differential cryptanalysis.  I have a general idea that the application of differential cryptanalysis is to look at the difference between inputs;  makes that fairly clear. However, I could take any two inputs for any given block cipher and I am pretty certain I'd be staring at random differences.    I am aware this is the idea of a well written block cipher; however, assuming a broken or vulnerable cipher (feel free to provide simple examples) how do I go about choosing differences to try?  Are there any clues in algorithm design that would inform a decision on which values to choose?  How does being vulnerable to differential cryptanalysis impact a cipher in the wild?  If all I have are differences between known plain-texts and known keys as my analysis and a captured ciphertext as my data to exploit, what can I actually deduce?
115825
Is there any pair of 128-bit strings M and K such that AES$_K$(M) = M?  If yes, how do I go about (efficiently) finding such a pair?
51033
Pre-conditions:  Let the public key be $(n, e)$, and $n=pq$, which $p,q$ are large distinct primes. Let $gcd(e, (p-1)(q-1))=1$, and $d$ is the inverse of $e$ modulo $(p-1)(q-1)$.   And let $M$ be the raw message, $M &lt; pq$, and $C$ represents the encrypted message(i.e. $M^e$).    Proof:  Since $M &lt; pq$, and $p, q$ are prime, $gcd(M, pq) &gt; 1$ implies that $gcd(M, p)=p$ or $gcd(M,q)=q$, but not both.  WLOG, consider the case $gcd(M, p)=p$ and $gcd(M, q)=1$. Let $ed=1+k(p-1)(q-1)$, then we have:   $C^d \equiv (M^e)^d \equiv 0\ (\textrm{mod}\ p) \equiv M\ (\textrm{mod}\ p)$ $C^d \equiv (M^e)^d \equiv M\cdot M^{k(p-1)(q-1)} \equiv M\cdot1^{k(p-1)} \equiv M\ (\textrm{mod}\ q)$   Since $gcd(p,q)=1$, $C^d \equiv M\ (\textrm{mod}\ pq)$ by Chinese Remainder Theorem. $\mathbf{Q.E.D.}$    This is an exercise in my text book Discrete Mathematics and it's Application, Rosen, page 305, section 4.6. And I don't have the solution...
118698
Say I have a simple hash function where $x$ is a sequence of integers:  $$h(x)=(a_1\cdot x_1+...+ a_n\cdot x_n) \bmod N=\sum_i a_i\cdot x_i \bmod N$$  where $a_1,a_2,a_3,...,a_n$ is the coefficient known to the attacker, size of $x$ can be anything smaller than $N$.   How to find 2 different inputs that hashes to the same value, i.e $0$?  I feel like this has something to do with linear combination / euclid algorithm but I'm not sure how to proceed.
120907
Suppose I have a ciphertext that I know is encrypted using an affine cipher in $\mathbb{Z}_{26}$. The plaintext begins with es and the corresponding ciphertext is FX. How can I calculate the key?
41822
I need to generate a 256 bit encryption key described by the adjectives in the title. Currently I intend to create the key using this .  Is this a secure manner of creating the key, given that it has the following properties:   Private key for symmetric encryption Used many times (of course with unique IV's)   And given the following facts:   I will literally just get the RNG to produce 32 random bytes not doing anything with (1) SALT (2) Iterations (3) Anything else   Please note that I am only asking if the key, directly after being generated, is secure. Thanks
114678
I have been trying to understand exactly how a length extension attack works on SHA-1. I'll detail below what I've understood so far, so that I can convey my understanding of the same and hopefully get advice on where I'm going wrong.  Lets assume that for a message $m$, a secret $s$ is appended to it and the SHA-1 hash is calculated. If $\textrm{len}(m) + \textrm{len}(s)$ is not a multiple of the block size, a certain amount of padding is added to it to make it a multiple, and the hash is generated using what is essentially $s || m || \textrm{padding}$.  Now SHA-1 internally uses 5 registers — it takes in an block, generates new register values, turns the crank, takes in another block, generates new register values, turns the crank ... and so on till the end. When all blocks are exhausted, the register values are concatenated and spit out.  Assume that an attacker knows a certain value of $m$, for which he also knows the hashed key. In such a case, he knows the state of the 5 registers when $(s || m || \textrm{padding}$ was processed. Lets also assume that the attacker knows the length of $s$, so that he can predict how much padding was added.  Here is where I get confused. From what I've read so far, the attack involves taking the known hash, adding a certain amount of padding and then the value that we want. However, isn't the padding already used up in creating the hash? Why are we using padding in our attack?
44584
I decided to read the original RSA paper A Method for Obtaining Digital Signatures and Public-Key Cryptosystem because of a question I had about RSA (which is not the question I'm about to ask, but may be a question on here at some time) and came across something I had never seen before in any textbook description of RSA (Note: this comes from the beginning of ).  for any integer (message) $M$ which is relatively prime to $n$, $M^{\phi(n)} \equiv 1\pmod{n}$  The part I don't recall ever hearing in class, or coming across in a text book, or seeing in any description of RSA I've ever read is that $M$ and $n$ must be relatively prime. So, I decided to play around with a toy example of RSA to see what would happen. I use $p=13$, $q=31$, $e=7$ and $M=2p=26$ (for completeness: $d=103$, $\phi(n)=360$, $n=403$). I observed the following using my toy instance of RSA: $M^e\equiv M\pmod{n}$, $M^e\equiv 0\pmod{p}$ and $M^e\equiv M\pmod{q}$. Do these equivalences hold for all $M,p,q$ when $M$ and $n$ are not relatively prime? How would I prove this? What is the real-world effect of this?
95350
The symbol $\mathbb Z/q\mathbb Z$ (given that $q$ is prime) represents the prime field $\mathbb Z_q$. Basically, the elements of this field are represented by $\{0, 1, \dots, q-1\}$, let's call this the "normal representation". However, in lattice based crypto, the elements of the field are represented by $\{-(q-1)/2, \dots, (q-1)/2\}$, let's call this the "lattice representation". What is the difference between these two representations? Why is the second one used in lattice crypto? Would it work if the normal representation was used instead? I would also be very grateful if someone could show an example of how $\mathbb Z_7$'s elements $\{0, 1, 2, \dots, 6\}$ are mapped into the other representation.
59957
In a  a doubt was voiced about my answer, which claims GCM to requires $2^{128}$ for a successful forgery. The doubt was that the square root needs to be taken meaning the security would be $2^{64}$.  So of course I immediately checked the relevant security theorem ():  $$\mathbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm}(n),\tau]}(\mathcal A)\leq \frac{0.5(\sigma+q+q'+1)^2}{2^n}+\frac{q'(\ell_A+1)}{2^\tau}$$  with $\sigma$ being the total plaintext size in blocks, $q$ being the total number of encryption queries, $q'$ being the total number of decryption queries, $n$ being the size in bits of the underlying permutation, $\ell_A$ being maximum authenticated input length in blocks and $\tau$ being the tag size in bits.  Now clearly from this we can see that performing $2^{n/2}=2^{64}$ queries yields a strong enough advantage for a break.  Now my question is: When talking about "n-bits of security" or "needs $2^n$ operations to break", do we usually talk about "online" security, ie queries to an oracle can be done and cost $1$ or "offline" security where no oracles are available or do we need to make this decision depending on the situation?  TL;DR: Does GCM offer 64 or 128 bit security?
17775
My question might appear the same as the question , but actually I did read all the answers and none of them helped me with the details I need.  I am new to cryptography and my problem is with two time pad attacks on OTP. The problem I had in my course was that I have 10 ciphertexts encrypted with the same key $K$. I am then given another ciphertext that I should decrypt.  I know that XOR-ing two ciphers gives me the XOR of their original messages.  My question is what is the correct thing to do after that?  I tried to take 3 ciphertexts $C_1, C_2$ and $C_3$.  Then get $S_1 = C_1 \oplus C_2  \oplus $' ', also get $S_2 = C_1 \oplus C_3 \oplus$ ' '.  After that I compared all corresponding characters in $S_1$ and $S_2$,  and if $S_1[i] = S_2[i]$ then I calculate $S_1[i] \oplus C_2[i]$ to get $K[i]$.  I tried this on paper before coding and it worked, but I might be missing something.  Is this the right approach? Why does it work?
28974
Consider a common practically-collision-resistant hash function $\mathcal{H}$ (e.g. , , , ), perhaps based on the  as are the first three. We define a  $\mathcal{C}$ $$(k,m) \mapsto \mathcal{C}(k,m)=\mathcal{H}(m\mathbin\|k)$$ where $\mathbin\|$ denotes concatenation, $k$ is a secret key (constant, or at least of fixed size), and $m$ is a message (possibly of variable length). Assume that an adversary can (iteratively) submit queries with $m_j$ and obtain $C(k,m_j)$, and wants to obtain $k$ or otherwise compute $C(k,m)$ for some $m\ne m_j$.  That MAC $\mathcal{C}$ is not trivially bad. In particular, if $\mathcal{H}$ was indistinguishable from a random function in the , $\mathcal{C}$ would be secure. And even though $\mathcal{H}$ may have the , it does not turn into a devastating attack on $\mathcal{C}$.  The less impractical generic attack that I see is that if a collision was known for $\mathcal{H}$ with the colliding messages of moderate identical length, it could be deduced countless collisions for $\mathcal{C}$. Hence security is demonstrably not better than collision-resistance of $\mathcal{H}$ (for identical-length messages). We could assume that $k$ is half the size of the result of $\mathcal{H}$, and hope that the security is about  or  or , 280, 2128, 2256 hash rounds for SHA-1, RIPEMD-160, SHA-256, SHA-512.   What are the known attacks against $\mathcal{C}$ (better than the above), and their cost, for each of these common hashes?  Is there hope for an argument that an attack against $\mathcal{C}$ would turn into an attack of similar cost against $\mathcal{H}$, or hint of the contrary?  Update: this  is of interest, but I fail to find that it really answers the present question.  Update 2: I am aware that the construction considered is weaker than , and in particular is vulnerable to collision on $\mathcal H$; I stated that, and that it is thus pointless to have the key wider hopeless to target security against some attacks better than half the hash's size. I'm asking exactly what cryptanalytic attack better than finding a collision on $\mathcal H$ there are. There is room for such an attack only by exploiting a weakness in the structure or/and the round function of a concrete $\mathcal H$.