Disjunctive zero knowledge proof of equality of committed values I have read on ZK proof of equality of committed values, that is for $g^xh^y$ and $g^{x'}h^{y'}$, prove in ZK that $x = x'$ (can also be generalized if generators are different using sigma-protocols).

However I want to do a disjunctive (OR) proof as follows: For $g^{x_1}h^{y_1}$ and $g^{x_{1}'}h^{y_{1}'}$ and $g^{x_2}h^{y_2}$ and $g^{x_{2}'}h^{y_{2}'}$ prove in ZK that either $x_{1} = x_{1}'$ or $x_{2} = x_{2}'$. Any suggestions or ideas?

Upd: As suggested, I should highlight the fact that the generators are the same.

What's special about your question is the "global" use of generators $g,h$ for all the commitments. This allows for a nice shortcut, leading to some potential savings.

Asking for a proof that $x=x'$ for given $C=g^x h^y$ and $C'=g^{x'} h^{y'}$ only makes sense if we actually demand a proof of knowledge of all four exponents as well. Now, the interesting thing is that if some party already proved knowledge of the four exponents, it suffices to prove knowledge of $z=\log_h (C/C')$ to establish that $x=x'$. This latter proof can be done using the Schnorr protocol.

The basic assumption for Pedersen commitments is that nobody knows $\log_g h$, otherwise one cannot even speak about the exponents for a given commitment. So, given all these proofs it follows that we can write $C=g^x h^y=C' h^z=g^{x'} h^{y'+z}$, hence that $x=x'$ must hold (and $y=y'+z$).

The proof that you are asking for then boils down to the OR-composition of two Schnorr proofs, which is pretty efficient. This idea can be applied more generally, and was in fact the basis for an efficient construction of list signatures (see Lemma~1 in List Signature Schemes).

If knowledge of the four exponents has not been proved yet, it is more efficient to prove everything in one go using EQ-composition combined with OR-composition.
Assuming that $x_1=x'_1$, we use an EQ-proof for $C_1,C'_1$ and a simulation of an EQ-proof for $C_2,C'_2$. This yields the following $\Sigma$-protocol:

Prover sends announcement $(a_1,a'_1,a_2,a'_2)\leftarrow(g^{u_1} h^{v_1}, g^{u_1} h^{v'_1}, g^{r_2} h^{s_2} C_2^{-c_2}, g^{r_2} h^{s'_2} C_2'^{-c_2})$ with $u_1,v_1,v'_1,c_2,r_2,s_2,s'_2\in_R\mathbb{Z}_n$.
Verifier sends challenge $c\in_R\mathbb{Z}_n$.
Prover sets $c_1\leftarrow_n c-c_2$ and $(r_1,s_1,s'_1)\leftarrow_n (u_1+c_1\,x_1, v_1+c_1\,y_1,v'_1+c_1\,y'_1)$, and sends response  $(c_1,r_1,s_1,s'_1,r_2,s_2,s'_2)$. Verifier sets $c_2 \leftarrow_n c - c_1$ and accepts if all of $g^{r_1} h^{s_1} = a_1 C_1^{c_1}$, $g^{r_1} h^{s'_1} = a'_1 C_1'^{c_1}$,  $g^{r_2} h^{s_2} = a_2 C_2^{c_2}$, and $g^{r_2} h^{s'_2} = a'_2 C_2'^{c_2}$ hold.


Block Cipher Mode of Operations I am studying for a test and I don't seem to understand the Block Cipher and its different modes of operations especially when it comes to encrypting and decryption. Could anyone please help solve these questions?
Block Cipher Mode of Operations. Please refer to the image attached for a diagram of PCBC, a similar mode of operation to CBC.
Input
000
001
010
011
100
101
110
111
Output
111
110
101
100
011
001
000
010
a. Decrypt Ciphertext 001001001001 without using any mode. Your answer:
b. Decrypt Ciphertext 001001001001 using CFB and IV=000. Your answer:
for (a) I am getting 110 110 110 110
and for (b) I am getting 110 001 110 001
But I am not sure if that is correct. My confusion is do I decrypt the ciphertext with the key, XOR it with the IV giving me the Plaintext(PT1)- and then for the next step; I XOR the Plaintext(PT1) with the first ciphertext which will then be used as the input to be XORed with the decrypted ciphertext2? You then basically repeat the process?

It is a block cipher with block size 3. Therefore for a given known-plaintext, we can build the current key's action table that has $2^3=8$ values. We will use the decryption part $$P_i = D(C_i) \oplus C_{i-1} \oplus P_{i-1}$$ with $C_{0} \oplus P_{0} = IV$ with conversion
$$D(C_i) = P_i \oplus C_{i-1} \oplus P_{i-1}$$
P_i          000 001 010 011 100 101 110 111
P_i-1        ??? 000 001 010 011 100 101 110
C_i-1        ??? 111 110 101 100 011 001 000
--- xor-all
x-ored       ??? 110 101 100 011 010 010 001
C_i          111 110 101 100 011 001 000 010

Now built the decryption table and the encryption table is just the reverse of it.
$$\begin{array}{|c|c|}\hline
\text{input} & \text{output} \\ \hline
\texttt{000} & \color{red}{\texttt{010}}\\ \hline
\texttt{001} & \color{red}{\texttt{010}}\\ \hline
\texttt{010} & \texttt{001}\\ \hline
\texttt{011} & \texttt{011}\\ \hline
\texttt{100} & \texttt{100}\\ \hline
\texttt{101} & \texttt{101}\\ \hline
\texttt{110} & \texttt{110}\\ \hline
\texttt{111} & \texttt{???}\\ \hline
\end{array}$$
With the current information, this question is not solvable since the defined block cipher is not reversible. The PCBC mode requires this.
P.S. Maybe I had a mistake with the simple calculations. If so inform me please;


Is there a point to having a large IV in AES I've always known that the IV should be 128 bits, because that's the block size of AES, regardless of the key.
However, I just saw one vendor advertising AES-256 with a 256 bit IV.
Is there any point to that? Does a 'double' IV bring additional guarantees? For example, reducing the probability of having the same IV with the same key?
Will it even work with standard AES implementations, or they'll reject it? The Java implementation rejects it, for example.
Effectively, it adds another block of plaintext to throw away, but if it works, does it have negative effects (apart from having one more block to process)
Or is it just a marketing mistake...

I've always known that the IV should be 128 bits, because that's the block size of AES, regardless of the key.

The IV depends on the mode of operation. It may well be that the block mode of operation specifies to use the block size, but this is not a given. For instance, AES-GCM defaults to 96 bits.
For CTR mode it is rather common to supply an IV, but in reality that consists of a nonce and a starting counter value; you could have implementations / protocols that only expect the nonce as input, which would then be smaller than 128 bits.

However, I just saw one vendor advertising AES-256 with a 256 bit IV.

Not many modes support that, so I'm wondering how they accomplished that. AES-GCM does support it, but at the expense of additional calculations. Furthermore, it doesn't increase security at all. It doesn't make much sense for AES-CBC mode either, as the second ciphertext block will be the IV, i.e. the effective IV would still be 128 bits.
The other more likely option is that they use Rijndael with a block size of 256 bits. In that case it is not AES (which is Rijndael with a block size of 128 bits and only 3 key sizes with the default number of rounds configured). In that case they really don't know what they are doing.

Is there any point to that? Does a 'double' IV bring additional guarantees? For example, reducing the probability of having the same IV with the same key?

No generally it doesn't bring any benefits. As it is hard to use AES in such a way that the block size of 128 bits isn't a limiting factor (e.g. when it comes to processing a huge amount of blocks), I don't see how a larger IV would alleviate that issue.

Will it even work with standard AES implementations, or they'll reject it? The Java implementation rejects it, for example.

Again, it depends on the mode; GCM may grog it. Java simply keeps to the standards, I've not seen Oracle deviate all that much yet.

Effectively, it adds another block of plaintext to throw away, but if it works, does it have negative effects (apart from having one more block to process)

Again, depends on the mode and how it is configured.

Or is it just a marketing mistake...

I might well be a marketing mistake. That's pretty likely actually. An engineering mistake (AES vs Rijndael) is also likely. It could however also be snake oil although you should not attribute to malice that which is adequately explained by stupidity.
However, definitive statements can only be made after more detailed analysis, and for that we need the source. I'd have them explain it to you.


Does salt size affect password hash security? I use PBKDF2-SHA512 with an iteration count of 128,000 to hash my passwords. I use a CSPRNG to generate a salt per password. However, I am unsure about the ideal size of the salt. I have read a lot of things about the salt size, but I have been unable to find a definitive answer. All of them agree that there is a minimum salt size, but I have found nothing about a maximum salt size.

So, here's my question: is there a point where the salt size doesn't matter anymore in terms of security and where it might even decrease it? If there is no maximum salt size, does it mean that the size we choose is actually a sweet spot among performance/space for salt storage/protection against precomputed tables?

So, here's my question: is there a point where the salt size doesn't matter anymore in terms of security and where it might even decrease it?

The purpose of a salt is to prevent the attacker from targeting multiple users' passwords with the same try or caching common passwords' hashes in a table. You need enough salts that each user has a unique salt. After that, having more won't help, nor will it hurt (within reason).

  If there isn't a maximum salt size, does it mean that the size we choose is actually a sweet spot among performance/space for salt storage/protection against precomputed tables?

Basically, yes, although it's parallel attacks on your whole user database, rather than precomputed tables that I'd worry about.

However, there's definitely diminishing returns. If your salt is 64 bits you'd need a billion users before collisions are remotely likely. Double that to 128 bits and you can be pretty sure no one anywhere will use that same salt. With a sufficient number of users there's still a chance that someone, somewhere has used that salt value, so 256 bits would be an even more conservative choice. No use going beyond that, though.


Parity attack on block cipher My misunderstanding is all about the parity attack mentioned in "Cryptography Engineering by Ferguson, Schneier and Kohno".

Most modern block ciphers have a 128-bit block size, but they operate on 32-bit words. They build the encryption function from many 32-bit operations.This has proved to be a very successful method, but it has one side effect. It is rather hard to build an odd permutation from small operations; as a result,virtually all block ciphers only generate even permutations.

I still do not get in how far a parity attack will be helpful.
Why only ideal ciphers have odd permutations?
Can someone form an example why odd permutations need more operations and why it is hard to realize with the current hardware being able to do 32-bit operations only?
I did not get smart by another thread on this forum exactly on this question.

When dealing with a block cipher of large block size, the text appearing as a quote in the question

Most modern block ciphers have a 128-bit block size, but they operate on 32-bit words. They build the encryption function from many 32-bit operations.This has proved to be a very successful method, but it has one side effect. It is rather hard to build an odd permutation from small operations; as a result,virtually all block ciphers only generate even permutations.

is about a merely theoretical attack. The book's chapter 3 acknowledges it:

This attack has no practical significance whatsoever.

That's because knowing the parity of the permutation implemented by an otherwise ideal block cipher with a $b$-bit block and some fixed key only helps adversaries after they have obtained $2^b-2$ plaintext/ciphertext pairs: the last two plaintext/ciphertext pairs are revealed by that parity. Before that threshold, nothing actionable comes from that one bit of information.
For example, with $b=3$, after an adversary obtained plaintext/ciphertext pairs 0/1, 1/6, 2/5, 3/0, 4/2, 5/7, which we can picture as
      0   1   2   3   4   5   6   7
      1   6   5   0   2   7   ?   ?
and if the permutation is known to be even, then the adversary can determine¹ that the remaining pairs are 6/3, 7/4 (rather than 6/4, 7/3).  But before the adversary obtained the pair 5/7, knowing that the permutation was even was of no help to predict if 5 maps to 3, 4, or 7.
Even if a 128-bit block cipher is known to implement an even permutation for any key, that's not an exploitable weakness. It does allow to build a theoretical distinguisher from an ideal cipher, but only after making so many queries ($2^{128}-1$) to the encryption or decryption oracle² that it does not count as attack against usual or reasonable security definitions.
The quoted text is somewhat exaggerating the difficulty of building an odd permutation from small operations; see these comments by poncho:

The standard trick for small block Feistel ciphers is to use modular addition, rather than xor, in each round; that way, the round, and hence the permutation, has a 0.5 probability of being odd. (…) If the two halves of the Feistel state are $a, b$, then the update $a\gets a+F(k,b)$ can be odd; in fact, it will be if an odd number of the $F(k,b)$ values are odd (fixed $k$, over all possible values of $b$).

¹ Proof: going from 01234567 to 16502734 can be done with an even number of permutations, e.g. 01234567 → 10234567 → 16234507 → 16534207 → 16504237 → 16502437 → 16502734.
² The challenger randomly choose an ideal random cipher or an even random cipher, the distinguisher tries to guess that choice. It needs $2^{128}-1$ queries to determine if the cipher is even or odd, if odd outputs 'ideal', otherwise outputs 'even'. It succeeds with probability $3/4$.


What is the linear complexity of a modified LFSR sequence with a fixed length of zeroes inserted between every pair of successive terms There was a deleted question that asked;

We know that if $n$ zeros are inserted between every pair of successive terms of the sequence in LFSR (variable changed $x$ to $x^n$) then linear complexity (shortest LFSR which produces the given seq) will be $n$ times the original one.
My question is that: in the new sequence what is the period (assume period of original one is $p$)

The period was easy to answer;
Let $m$ be a sequence output from $L$ bit maximal LFSR. Then we know that the period of the sequence $m$ is $2^L-1$
Let $m'$ be the modified sequence of $m$ such that for every two successive elements $n$ zeros are inserted. An example with $n=3$
   m  = 1   1   0   1   1   0   1
   m' = 1000100000001000100000001000

It is obvious that the period of $m'$ is $(2^L-1)\cdot n$. One can prove this with a counter-argument; if the period is smaller, then remove the added zeroes to find a smaller period for $m$.
What about the linear complexity?
I couldn't see a general rule for this; My was example already a counterexample for the multiple; run with SageMath code the online;
[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1
[1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0] has x^8 + x^4 + 1

and for the $n=1$ case;
[1,1,0,1,1,0,1,1] has x^2 + x^1 + 1
[1,0,1,0,0,0,1,0,1,0,0,0,1,0] has x^4 + x^2 + 1

[1,1,0,1,1,1,1,1] has x^4 + x^3
[1,0,1,0,0,0,1,0,1,0,1,0,1,0] has x^7 + x^5

Is there a work or a result on the bounds of the Linear complexity of $m'$ related to $L$ and $n$?

There are no general lower/upper bounds that are not combinatorial in nature.
If you have a sequence $S=(s_0,s_1,\ldots,s_{N-1})$ which has period $N$ over a finite field $\mathbb{F}_q$ there are two related formalisations of the linear complexity $L(S)$ of the sequence. The first one is the classical
$$L(S)=N-\deg(\gcd(S^N(x),x^N-1)),\tag{1}$$
where $S^N(x)=s_0+s_1x+\cdots+s_{N-1} x^{N-1}.$
Now, for $q=2,$ which is what we are interested in, $x^N-1$ has a canonical factorisation as
$$
x^N-1=\prod_{t=1}^h f_t(x)\quad with\quad f_t(x)=\prod_{j \in C_t} (x-\alpha^j)
$$
where $\alpha$ is an element of order $N$ in $\mathbb{F}_{q'}$ which is defined to be the smallest extension field containing an element of that order. Then the degree of the gcd  in (1) can be written as a sum of cardinalities of cyclotomic cosets modulo $N.$
If you insert $k-1$ zeroes between each symbol, for $k\geq 2,$ to obtain a new sequence $S'$ of period $kN,$ it is straightforward to see that the new linear complexity is
$$L(S')=kN-\deg(\gcd(S^N(x^k),x^{kN}-1))\tag{1}$$
A related characterisation can be made using a finite field valued (not complex-valued) DFT. Firstly you need enough points in the finite field $GF(q')$ over which you will define the DFT to make it one-to-one, thus $q'\geq N$ is needed. For the arithmetic operations leading to the DFT to make sense, $\mathbb{F}_q$ must be a subfield of $\mathbb{F}_{q'}.$
If you can find $\mathbb{F}_{q'}$ such that $\gcd(q',N)=1,$ you can define the DFT vector of the sequence $S$ as
$$
A=[a_0,\ldots,a_{N-1}]
$$
where
$$
a_j=\sum_{i=0}^{N-1} s_j \alpha^{ij},\quad j=0,\ldots,N-1
$$
and all arithmetic is in $\mathbb{F}_{q'}.$
A relationship called Blahut's Theorem in coding theory literature states that the Linear Complexity $L(S)$ is equal to the Hamming Weight (over $\mathbb{F}_{q'}$) of the DFT vector $A.$
Note: Some of the algebraic details of this answer can be found for example in Lidl and Niederreiter's Introduction to Finite Fields book.


Are there standards for transport layer security using only symmetric keys? I have an embedded system with AES-128 implemented in hardware. There is very little flash/RAM and the (8-bit) CPU runs relatively slowly. Public key crypto isn't a viable option. This system is connected to the Internet and can have one or more unique AES keys programmed at manufacture.

Are there any standard protocols for securing a TCP socket using pre-shared symmetric keys?

Is it enough to just use a pre-shared key for AES-CBC over TCP?
Is there a benefit to exchanging a unique session key (eg. AKEP2/Needham-Schroeder)

Thanks.

I know of two standard protocols that support AES encryption without public key cryptography getting involved:

With TLS, we have RFC4279, and in particular, the ciphersuite TLS_PSK_WITH_AES_128_CBC_SHA.  Now, the two sides don't literally have preconfigured AES keys; instead, they have preshared premaster secrets; the AES (and HMAC-SHA1) keys are derived from the premaster secret in the standard way.  No public key cryptography is involved.
With IPSec, we have RFC4301, and in particular, "manual keys" (which are exactly that, preconfigured symmetric keys)

If both work for you, I'd advise you to use the TLS option; it is probably more work (as you'll need to deal with the session setup messages); however, support for TLS is more command, and it does mean that the keys actually change over time (while with IPSec manual keys, the keys are fixed; if they are ever leaked, you are dead).

You could, of course, design your own protocol, however I'd strongly advise you to stick with protocols designed by people who knew what they are doing.


Adding dummy bytes to ciphertext I was wondering if interleaving the resulting crypted data with dummy bytes placed at random positions but known in advance by the peers could improve security (no matter the algorithm and strength used, this is just baby step theory here) or do the contrary (and why).
E.g.:
normal: kIolmspJgheydhNud
with dummies: kI9oklmdspJgfheydshNufd
Update:
after Thomas answer, I realized that my question was not clear where the dummy bytes would go.
My mistake.
So I am interested in adding dummies in the ciphertext. After all encryption of the real text occurred. The net result is to make the ciphertext longer and not logical anymore.

If you're using a real encryption scheme then no it cannot weaken or strengthen the system because the encryption scheme's security is supposed to be independent the actual data being encrypted. The plaintext could be random bytes or all zeroes for all it cares, it will be just as secure.

All this modification achieves is lower your encryption scheme's capacity (number of plaintext bytes you can transfer in a given number of ciphertext bytes) and performance (number of plaintext bytes encrypted by second) as well as complicating the algorithm even further for no reason.

This is, of course, if the adversary only has access to the bytes over the wire. Your implementation of this modification may well leak sensitive information through a side channel (don't know how, but it's possible since you need to add code to implement this, and this code may have bugs and security vulnerabilities, as with any code.

Basically, it doesn't really do anything useful and has only cons, so don't do it.


Perfect secrecy of block ciphers Is it right that all block ciphers don't provide perfect secrecy like AES? If it's true, how can we prove that? If it's not true can you tell me a sample? Any reference or guidance would be appreciated.

Perfect secrecy, in the sense defined by Shannon, means that observing the ciphertext does not allow an attacker (who has no knowledge of the key) to learn any new information about the plaintext beyond what they already possess.

(Note that there are no restrictions on what the attacker may already know about the plaintext; for example, they might already know that the plaintext is one of two specific messages, and just want to know which one.  Also, for technical reasons, we generally assume that there's an upper bound on the length of the plaintext, and that this upper bound is public information, i.e. already known to the attacker.  This is because no cipher capable of encrypting arbitrarily long messages can perfectly hide their length.)

Importantly, unlike more modern computational definitions of security (such as semantic security), the definition of perfect secrecy does not assume anything about the amount of computing power available to the attacker.  Thus, for example, the attacker is free to generate any number of candidate keys and to try to decrypt the ciphertext with each of them.

Based on this, it's easy to show that no cipher can possibly provide perfect secrecy unless the number of possible keys is at least as large as the number of possible plaintexts.  If there are $k$ possible keys and $n$ possible plaintexts, then the attacker (who, in this case, is assumed to know nothing about the plaintext in advance except that it's one of the $n$ possibilities) can simply try to decrypt the ciphertext with each of the $k$ keys, and thus obtain (up to) $k$ distinct decrypted messages.  If $k < n$, the attacker has thereby just learned something about the plaintext: namely that it's not one of the $n - k$ possible messages that the ciphertext did not decrypt to using any of the keys.

(We can also extend the same result into a proof that no cipher can provide perfect secrecy if the same key is used to encrypt multiple message, unless the key is at least as long as the combined length of all the messages.)

A block cipher like AES normally has a fixed key length (e.g. 128 bits for AES-128, or 256 bits for AES-256).  While in principle a block cipher like AES could provide perfect secrecy if the messages were no longer than the key, and if each key was only used to encrypt one message, in practice an encryption scheme capable of only encrypting up to 256 bits of plaintext per key would be pretty useless.

Thus, normally, AES is used with a mode of operation that allows it to be used to encrypt multiple messages of (more or less) arbitrary length.  Such modes of operation make AES into a practical general-purpose encryption scheme — but, as an inevitable side effect of allowing longer and/or more messages to be encrypted with the same key, the resulting encryption scheme cannot possibly provide perfect secrecy.

(Fortunately, they do still provide provable practical security against computationally limited real-world attackers who cannot just test every 256 bit AES key by brute force — something which appears to be safely beyond the reach of mankind.)


How are keys mapped to cipher texts in block ciphers with large block sizes? What I understand so far:

For n-bit block size, there are 2n plaintexts (P)
there are P! possible keys
The bits necessary to represent each of the possible mappings is log2(P!) rounded up

Basically, my calculator craps out at a block size of 8 bits because the key length is so massive to map all possible keys for 8-bit block size.
What I am led to understand is that there is some way to use much smaller key sizes (like 128 bits), but from what I have read, there are encryptions that use larger block sizes like 32 bits, 64 bits, etc where there is no feasible way to map every possible ciphertext to a key.
It seems to me that if there was a 32-bit block size being used, for example, then with 128 bits, you can only map a very small chunk of the possible ciphertexts. I'm not even sure how to ask what I'm trying to understand...how does this work? I'm just confused by this. I guess what I'm trying to ask is, if it's impossible to map a specific key to a specific, unique ciphertext value, what does it actually map to if I just pick 32 random bits? It seems that each possible key would have to map to multiple ciphertexts.

A block cipher is a family of permutations.
$$F:\{0,1\}^k\times \{0,1\}^b \to \{0,1\}^b$$
That's it!. A key $k \in \{0,1\}^k$ represents one of the permutations of the family. A permutation is an invertible map $$P:\{0,1\}^b \to \{0,1\}^b.$$ The above is a permutation from $2^b$ elements to itself ( the input space of a block cipher). Therefore every element is mapped. Since a key represents a permutation from the block cipher's permutations, then every plaintext is mapped to some ciphertext.
There are $2^n!$ permutations, however, usually, we have $2^{64},2^{128},2^{256}$ etc. keyspace. With the Stirling formula $$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}.$$ Plug this into AES-256
$$2^{256}! \approx \sqrt{2\pi 2^{126}} \bigl(2^{256}/e\bigr)^{2^{256}} \!=  \sqrt{2\pi 2^{256}} e^{-2^{256}} \bigl(2^{256}\bigr)^{2^{256}} \ggg 2^{256}$$
So, practically there is no way to represent all possible permutations.
What we want that the block cipher must be is indistinguishable from a random permutation. That is not an easy job, since even after 20 years no one yet showed that AES is a PRP, but we believe that it is.

I guess what I'm trying to ask is, if it's impossible to map a specific key to a specific, unique ciphertext value, what does it actually map to if I just pick 32 random bits? It seems that each possible key would have to map to multiple ciphertexts.

If you select a random key or any key of the block cipher, start from encryption the all-zero plaintext to the all-one plaintext. Since the key selects a permutation then each will be a different ciphertext value.
You can see this also in this way

The input of the block cipher is processed regardless of its input value and mapped (encrypted) to a ciphertext. Since the block cipher needs the decryption, i.e. the reverse map, then every ciphertext mapped back to the plaintext that $$m = D_k(E_k(m))$$ under the same key.

Multiple values are not possible since we have a permutation. Even it is not a function, remember a function can have only one value in the range.

An educative example:
Consider the block cipher $$F:\{0,1\}^2\times \{0,1\}^3 \to \{0,1\}^3$$ that has 2-bit keyspace and 3-bit block size. The number of possible permutations is $2^3! =40320$ and note that it is not the power of 2. Consider the below permutation as one of the permutations selected by the one of the keys $k_1,k_2,k_3,k_4$ of the block cipher.
$$P = \begin{pmatrix}0& 1 & 2 & 3 & 4 & 5 & 6 & 7 \\7 & 2 & 4 & 0 & 3 & 5 & 6 & 1 \end{pmatrix} \text{ and }$$
As we can see, with the permutation;

All inputs of the cipher is mapped to one
They are mapped 1-1 by the nature of the permutations that make the inverse permutation possible.


How is Twofish flattening the result of Reed-Solomon MDS matrix multiplication into a 32-bit result? I have trouble understanding how Reed-Solomon coding can produce same number of output bits than the input was.

Twofish uses this technique. I've read the paper, but still can't quite understand how the flattening works. In my understanding, RS should add redundant bits, and the output must be larger than the input. What am I missing?

In addition, how is the MDS matrix constructed from RS coding? It seems that it was constructed using clever heuristics.

In crypto diffusion layer design the MDS matrix is usually used in the following form:

$$ X_{n+1}=M X_n,$$

where the actual codewords are $(X_n | X_{n+1}).$ So it's a rate $1/2$ MDS code. It need not be Reed Solomon, and optimisations with respect to speed and other considerations are made. This is done in Twofish as well.

In particular $X_n$ is made up of the 4 words that are the outputs of sboxes $(S_0,S_1,S_2,S_3)$ and $X_{n+1}$ is the result of multiplying this vector with the MDS matrix $M$.

See the answer to this question as well.


Is it safe to use single-block AES for mutual authentication? I read the question Symmetric mutual authentication with client using a derived secret and its answer which, if I'm not mistaken, assert that it should be safe to use the proposed protocol for mutual authentication between a client A and a server B as follows:

At commissioning, each client A gets a unique identifier $i_A$ and a derived key $k_A$ which is generated from the secret $s$ by HMAC($s$, $i_A$).
To authenticate B, A sends $i_A$ and a random nonce $c_A$ to B.
B calculates the expected derived key $k_A'$ = HMAC($s$, $i_A$) and replies with $r_B$ = HMAC($k_A'$, $c_A$) as well as a random nonce $c_B$.
A can now authenticate B by comparing $r_B$ to HMAC($k_A$, $c_A$).
To enable authentication of A with B, A sends $r_A$ = HMAC($k_A$, $c_B$) to B.
Now B can authenticate A by comparing $r_A$ to HMAC($k_A'$, $c_B$).

Now I would like to use a single-block AES128 for the HMAC calculation in this scheme such that every message item (namely, $i_A$, $c_A$, $r_B$, $c_B$, and $r_A$) between A and B is exactly 128 bits long and the AES128 is used in ECB mode.

Given this answer to a question about AES Message Authentication Vulnerability, I think this should be safe?

If we assume that AES is a pseudorandom permutation (which is a standard model for block ciphers), then AES can replace the HMAC in your construction. Be aware, this only works because you have a fixed message length, i.e. the protocol must not accept nonces $> 128$bit.

Besides, I guess you are aware of this but you have a shared secret key among all users. Hence, your protocol does not authenticate a specific user. Instead, the protocol only verifies that the other side is a user that knows the secret key.

The reason is that any user knowing $s$ can compute $k_A = \text{HMAC}(s, i_A)$. Even if $i_A$ is not made public explicitly. Everyone that communicated once with $A$ will know $i_A$. Besides, this would mean that you have to protect $i_A$ while being transmitted and finally this has the problem that the authenticity of $i_A$ must be verifiable. Otherwise, an attacker could use an arbitrary value as $i_A$.

If you only want to get a proof of membership, this protocol works but is overly complicated as you can omit the key derivation step. You can simply use $\text{HMAC}(s,nonce)$...

As you included the identifiers I guess you wanted something stronger than a proof of membership. In this case, you should switch to some standard mechanism like TLS with a PKI. You will not really be able to omit public key crypto in this setting. The only (impractical) solution in the symmetric setting would be the establishment of one key for each pair of users.


How does this happen in RSA malleability? I don't understand how the $E(m)$ turns into $E(mt)$. I mean, I don't know how does that transformation happen and how does the equation occur.

$$E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)$$

See, $E(m)$ is $m^e \bmod n$, so if you plug in real values, it won't work.

For example:

$c_1 = 17^{23} \bmod 35 = 33$
$c_2 = 2^{23} \bmod 35 = 18$

Now, $c_1 \cdot c_2$ should result in $33 \cdot 18 = 594$, i.e. $E(mt)$.
But if you plug in the values in $(mt)^e \bmod n$, you get $34$ instead of $594$.

How are these equal?

As mikeazo notes in the comments, RSA operates on the ring $\mathbb Z / n\mathbb Z$ of integers modulo $n$, for a given modulus $n = pq$.  In this ring,

$$E(m) \cdot t^e \equiv m^e \cdot t^e \equiv (mt)^e \equiv E(mt)\ \pmod n.$$

In particular, for $n =  35$, $e = 23$,

$$17^{23} \cdot 2^{23} \equiv 33 \cdot 18 \equiv 594 \equiv 34 \equiv 34^{23}\ \pmod{35}.$$

The notation in your question,

  "$E(m) \cdot t^e \bmod n = (mt)^e \bmod n = E(mt)$",

apparently using $\bmod$ as a modulo operator, is somewhat confusing here, although it's technically correct if you interpret the left hand side as "$(E(m) \cdot t^e) \bmod n$".  I would much prefer the notation I've used above, which makes it clear that we're doing all arithmetic in the ring $\mathbb Z / n\mathbb Z$, and that we're thus free to reduce (or not to reduce) intermediate values modulo $n$ any time we want.


Using modulus in one time pad? I would like to know what is the real purpose of using a modulus in the equivalent of a Vernam cipher:

Data $d$, large number $M$.
Assume the key length is $\lambda$ bits. Then $M$ could be $2^\lambda$.
$k$ is picked from $\{0,1\}^\lambda$ using a pseudo random function (PRF)

Encryption: $C = k + d \pmod{M}$
Decryption: $d = C - k \pmod{M}$

What's the purpose of using $M$?

It depends on what you think of as an alternative.

If you think of the scheme where you do not use $M$ as a modulus, but the keys a picked as:
$$
k \leftarrow \{1, \ldots, M-1\}
$$
Encryption:
$$
C = d + k
$$
Decryption:
$$
d = C - k
$$
Then the scheme is insecure. One way to see this is to note that we have $C \geq d$. So the ciphertext communicates the information that $d \leq C$.

You could also think of a scheme where there is no $M$ at all:
$$
k \leftarrow \mathbb{Z}
$$
Encryption:
$$
C = d + k
$$
Decryption:
$$
d = C - k
$$
This would be secure, however, it would be impossible to implement because there is no way to sample $\mathbb{Z}$ (the integers) uniformly at random (think about it, how would you do that?).

So you see $M$ is really quite essential to the scheme.


rolling key with two keyfobs Hy i just saw this Question: How does a rolling code work?

And I just wondered how it is possible that my Vehicle (A 2013 Mazda 6) has two key fobs? As i understand this shuld not be possible. Because there shuldbe only one key that stores n+1.

Are these Vehicle using another form of a Rolling Key Algorithm or are there Keyfobs that do full handshake?(Rx+Tx)

Keyfobs that do a handshake are actually quite common, see the HiTag2 key transponder specifics for how its handshake works.

Even without a handshake, the code can still identify the key if it is long enough, and cars can be programmed to accept multiple keys, but almost certainly there is a handshake involved.

I believe your key probably uses a Ford type transponder chip, probably transmitting at 315MHz for long range commands like door unlock, and a lower freq for engine start (123-134KHz). For engine start, the car tells the key it wants to start and adds a challenge code, then sends to the key. The key encrypts the challenge, resulting in an 80-bit code, then truncates to 40-bits and transits back with its serial number and a checksum. The car then verifies the code, and starts if it is correct.

I am not sure if the high frequency commands use the same cipher, but they are a 1-way transmission. Similar to how a garage door opener can use 2 remotes, the car can use 2 keys to unlock doors without a handshake, as internally the car will see that the code matches a programmed key.


total effective key length of the AESX-192 If I have a AESX-192 be a block cipher which is similar to DESX but has the DES being replaced by AES and the AES key size is 192 bits.

How should I compute the total effective key length of the AESX-192.

The security bound for this construction is (PDF, section 4.7.3 in v4) $$\mathbf{Adv}^{\text{sPRP}}_{\text{AESX-192}}(\mathcal A)\leq \frac{2Q_sQ_{AES}}{2^{192}\cdot 2^{128}}$$ to be a strong PRP assuming AES can be modeled as an ideal cipher (not perfectly accurate but probably "close enough" here), where $Q_s$ is the number of "online" queries against a keyed oracle of the cipher and $Q_{AES}$ is the total number of AES evaluations for this.

So for an off-line brute-force search you actually get a 384-bit security strength, for a "online" security it breaks after $2^{160}$ queries. Therefore it may be easier to "just" use normal AES-192...


Yao's Garbled Circuit with different outputs In a lecture I was told of a a possibility to modify Yao's Garbled Circuit Protocol so that both parties in the end get each a part of the output but not the other part.
This may be achieved by manipulating the Circuit.

Does anybody have some hints how this can be done?

Thanks in advance.

Suppose you want Alice to learn $f_A(x,y)$ and Bob to learn $f_B(x,y)$. Then have Alice choose random string $r_A$ and have Bob choose random string $r_B$. The parties should perform a secure computation where both parties learn $(f_A(x,y) \oplus r_A, f_B(x,y) \oplus r_B)$. Basically each party's designated output is masked by a one-time pad that only that party knows.


Early propagation of carries in the BLAKE hash function The BLAKE paper uses round constants derived from $\pi$ to improve diffusion, even if the additions modulo $2^{32}$ are replaced with bitwise XOR when processing a null message and null initial state:

  The higher weight in the original model is due to the addition carries induced by the constants $c_0,\dots,c_{15}$. A technique to avoid carries at the first round and get a low-weight output difference is to choose a message such that $m_0 = c_0,\dots,m_{15} = c_{15}$. At the subsequent rounds, however, nonzero words are introduced because of the different permutations.

However, the BLAKE2 paper describes changes it made to BLAKE that remove these constants:

  Constants in G initially aimed to guarantee early propagation of carries, but it turned out that the benefits (if any) are not worth the performance penalty.  This change saves two xors and two loads per G, that is, 16% of the total arithmetic (addition and xor) instructions.

This statement was made as part of an argument that reducing the number of constants in BLAKE2 does not weaken it, while simultaneously decreasing RAM and ROM footprint. Unfortunately, unlike many of the other trade-offs it discusses, no further explanation is given. What are the benefits of guaranteeing early propagation of carries that lead to BLAKE's constants, and why are these benefits in doubt?

This is already covered by Ella's response, but in short the added nonlinearity at the start buys you very little in terms of security, compared to its cost in number of operations. It would be more effective, and make for a simpler design, for example, to trade all these constant xors by an extra round. Since that part of BLAKE was not pulling its own weight, as noted by the cryptanalysis of the various weakened versions of BLAKE, it was removed.

But besides the small effect on nonlinearity, there is another reason for the existence of the constants—to eliminate symmetries on the underlying block cipher. BLAKE, as well as BLAKE2, are modes of operation on top of a $\{0,1\}^{1024}\times\{0,1\}^{1024}\to \{0,1\}^{1024}$-bit (or $\{0,1\}^{512}\times\{0,1\}^{512}\to\{0,1\}^{512}$) block cipher $E(k, m)$, inspired by the ChaCha core. And like the ChaCha core, when the message words $m_i$ are all 0, or more generally all equal, if the inputs $x_i$ are also, say, all equal, the output words $y_i$ will also be all equal. For example,
$$
E\left(
\begin{pmatrix}
m & m & m & m \\
m & m & m & m \\
m & m & m & m \\
m & m & m & m \\
\end{pmatrix},
\begin{pmatrix}
x & x & x & x \\
x & x & x & x \\
x & x & x & x \\
x & x & x & x \\
\end{pmatrix}
\right) =
\begin{pmatrix}
y & y & y & y \\
y & y & y & y \\
y & y & y & y \\
y & y & y & y \\
\end{pmatrix}\,,
$$

for some 32- or 64-bit word $m$, $x$, and $y$. This property, often called a symmetry of the round function, makes the underlying block cipher of BLAKE—without the constants—easily distinguished from an ideal cipher. Likewise with BLAKE2. This is even exploited in the "chosen-IV" attacks of a weak variant of BLAKE2.

However, in the actual mode of operation of either BLAKE or BLAKE2, these so-called symmetric states are unreachable by design, via the inclusion of the $IV_0$–$IV_7$ constants in the initial state, so this property is not a security liability.


Attack on LFSR key stream generator Alright this is a question I found on one of my books:

  Given is a stream cipher which uses a single LFSR as key stream
  generator. The LFSR has a degree of 256.

How many plaintext/ciphertext bit pairs are needed to launch a successful attack?
Describe all steps of the attack in detail and develop the formulae that need to be solved.

What I don't understand is how the author came with the answers.

First it seems that one would need 512 consecutive pairs of plaintext/ciphertext to launch an attack, which consists of creating a system of 256 linear equations and solving them, that much I understand.

My question is: why do we need 512 consecutive plaintext/ciphertext pairs if we are going to construct a system of only 256 equations? Shouldn't it be 256 pairs?

The number of consecutive plaintext-ciphertext pairs $(x_i,y_i)$ of bits necessary is 256 if we know the LFSR taps (equivalently: the reduction polynomial) in advance, for the reason explained in the question. 512 is when we do not, because it creates more unknowns: the coefficients of the polynomial, in addition to the initial state.

If we know the LFSR taps, the initial state is all that's unknown, and is directly given by the vector of the first 256 values of $x_i\oplus y_i$ for an LFSR in Fibonnaci form (within a reflection, depending on notation). In Galois form, one option to find the initial state is to solve a system of equations.

If the LFSR taps are unknown, a standard algorithm is Berlekamp-Massey, which reconstructs the shortest LFSR state and feedback polynomial matching a given sequence of $x_i\oplus y_i$ (without taking the degree as input).

PS: I found the solution floating online, and adapted my notation to that. It is assumed that the feedback polynomial is initially unknown (or equivalently part of the key), hence the 512 pairs. The resolution is not explicitly per Berlekamp-Massey. Rather

With the LFSR in Fibonnaci form, the first 256 $x_i\oplus y_i$ give the initial internal state. The only remaining unknowns are the 256 coefficients $p_i$ of the feedback polynomial.
These 256 remaining unknowns are found by solving a system of 256 equations with 256 unknowns, built using the 512 $x_i\oplus y_i$. That system states that the internal state evolves from the first 256 $x_i\oplus y_i$ to the next 256 $x_i\oplus y_i$ after 256 steps with the reduction polynomial defined by the $p_i$.


Integrity protection in wireless sensor networks I have done a lab about wireless sensor nodes and got in touch with encryption for the very first time. There are some questions on my sheet, especially on integrity protection (the attacker wants to tamper our data) which I wanted to ask about. I read some stuff but I don't feel so comfortable:
1) Why is a simple checksum or MD5 sum insufficient?

I guess because they are not secure anymore. In 2004 some researchers found out that there are 2 different messages with the same MD5 value and one can create more. Same is true for the checksum (?)

2) Is CBCMAC a good way to achieve integrity protection?

If I understood the wikipedia article right it is secure for fixed length messages, for arbitrary long messages it is not secure anymore.

3) Block ciphers are often fast and readily available. When comparing HMAC
and CMAC, which do you suspect will work better in a WSN scenario? What
are the differences between them?

The differences are quite crucial: HMAC uses hash functions for encrypting and CMAC block ciphers. But I don't know which one is more suited in a WSN. As we have very limited resources one should maybe choose the one which "costs" less in terms of energy?

4) Is it a good idea to use the same key for both encryption and the MAC
function?

No it is not, in the CBC-MAC article wikipedia shows a big problem if you use the same key.

5) Are there ways to combine encryption and itegrity protection? Name at
least two examples. Is a single key sufficient in these cases? Do different
approaches differ with respect to their performance characteristics? Will
such an approach be usually faster, slower or equal to doing encryption and
MAC calculation as separate steps?

I guess this question is about authenticated encryption. The wikipedia article (http://en.wikipedia.org/wiki/Authenticated_encryption) is quite short and I can't find many information about these questions ...

I am thankful for any help

That's a lot of questions, I'll try and answer in order.

A hash or message digest alone is not secure because anybody can calculate and thus substitute a hash value. If you (correctly) add a key to the mix then you get a HMAC, which can be used.
Nowadays often a HMAC is used, or an authenticated mode of authentication such as GCM, CCM (for packet encryption) or EAX. If you want to use a MAC based on a block cipher you can use AES-CMAC. You'll need a 128 bit block cipher though.
Yes, you should check if hashing or encryption is most efficient on your platform. You could also have a look which one is least vulnerable to side channel (timing / energy usage) attacks. You want to try and find the best crypto library available if you have only just seen crypto for the first time.
You already answered it. Although it is less a worry in HMAC, for AES-CBC-MAC and even AES-CMAC it is considered best practice to use a separate key for encryption and calculation of the authentication tag. Usually deriving an additional key is not that much of a performance issue. Note that it is strongly recommended to use a key for each direction as well, and to make sure your IV is unique (and - for CBC - unpredictable). Your MAC should include the IV, not just the ciphertext.
I think I just named 3 authenticated ciphers in answer 2), all of them use just a single key (externally, anyway) and auto-include the IV within the authentication. GCM and CCM are NIST standardized, EAX is a proposed mode to NIST but - as it simply uses AES-CMAC internally - it's very likely secure.


Addition-only PHE in F# Using homomorphic encryption, I would like to be able to take an encrypted integer and either add 1 or -1 for a new encrypted value.  I do not want the encrypted value to be recoverable - just the following:

$\varepsilon(x) = (\varepsilon(x) \oplus \varepsilon(-1)) \oplus \varepsilon(1) = (\varepsilon(x) \oplus \varepsilon(1)) \oplus \varepsilon(-1),$
$\varepsilon(x+1) = \varepsilon(x) \oplus \varepsilon(1) \ \mathrm{and}$
$\varepsilon(x-1) = \varepsilon(x) \oplus \varepsilon(-1)$
$\forall x \in \mathbb{Z}$

$x$ can never be recovered because the secret key will not be known (an original $\varepsilon(x')$ is chosen as $0$ and it will only be manipulated or used in encrypted form).  It is ok (and perhaps even desirable) if $\varepsilon(x + n)$, computed (only) recursively as a series of single increments or decrements, is worse than $O(n)$ but no worse than about $O(n \log n)$ and there should be no limit on $n$ - that is, the further I go in a direction, it gets a little harder to keep going, but not impractically so.

It seems to me that this is perhaps within practicality for Gentry's scheme if the hints for $\mathrm{sK}$ can be reused forever for $\mathrm{recrypt}()$, but I might be misunderstanding this (or all of it).  Then, Gentry might be overkill, since I don't seem to need multiplication ($\varepsilon(-1)$ does not need to be calculated as $\varepsilon(1) \otimes \varepsilon(-1) $, right?).  I think any PHE supporting unlimited additions is good enough.  Gentry's numbers "stiffen" - but is that the case with all systems?  If they stiffen at about $O(n \log n)$ that's what I'm hoping for worst case.

I'd like to implement this in F# but 1) I need a good choice of algorithm supported by .NET or with an implementation in F#, and 2) How can I disable padding in such a scheme which normally one would be crazy to want to do?

The purpose is to create a dimension whose origin is unknown, but which can be navigated relatively.  I'm below novice at math and latex and formalisms so if my attempts above are totally asinine, I apologize.  Do you recognize an equivalent scheme that doesn't require HE?

You don't need fully homomorphic encryption for this.  In particular, you don't need to use Gentry's scheme.  Any standard scheme for additively homomorphic encryption will be fine.  For instance, Paillier should work fine, as should exponential El Gamal.

Search this site and you can find lots of information on additively homomorphic encryption.    See, e.g., Can Elgamal be made additively homomorphic and how could it be used for E-voting? and https://crypto.stackexchange.com/a/9003/351 and https://crypto.stackexchange.com/a/12704/351 and https://crypto.stackexchange.com/a/9139/351.  Also, search the literature for work on "encrypted counters" and you should find additional stuff that might be helpful.

This is not the site to ask how to implement crypto in F#; ask on StackOverflow for coding questions.  Your questions about padding make no sense to me.  The real question is what algorithm to use.  Once you know what algorithm to use, just implement it (that's just a  straightforward matter of programming).


Statistical Analysis of Cryptographic Hashing Algorithms I was wondering how can I use NIST Statistical Test Suite to check for the randomness of output generated by a cryptographic hashing algorithm, let say SHA-256?

To be specific, how will I generate input for the suite? For block ciphers, we use key avalanche, plaintext and ciphertext avalanche, etc as inputs of the suite. Is same kind of inputs are used while evaluating a cryptographic hash algorithm, as for an S-box or block cipher?

You simply create a hashed counter.  So output = SHA-256(n) whilst incrementing n. You'd make n a large multi-byte variable, say 16 bytes, and seed it at a random value from some PRNG you find lying around. That way you can perform repeat runs to generate different sequences. I find that you need >10MB for some of the template tests to complete fully.

I won't bother repeating  Natanael's comment to you :-)


What does "adaptively secure" mean? In a paper it says "In the generic group model, the PRF is adaptively secure for inputs of $\mathbb{Z}_q^n$". Maybe a stupid question, but what does "adaptively secure" mean exactly?

Well, when we talk about "chosen plaintext attacks", there are two possible flavors for this attack:

The attacker gets to create a list of plaintexts to be encrypted; we'll go through and encrypt them all, and then hand over all the ciphertexts to the attacker.
The attacker gets to ask for a plaintext to be encrypted; we encrypt it and hand over that ciphertext.  Based on what the ciphertext looks like, he can then select another plaintext for us to encrypt (and we'll go through the procedure for a number of plaintext/ciphertext pairs).

This second model is known as "adaptively chosen plaintext attack" model, because the attacker can adapt the plaintext he selects based on previous results.  This is a strictly stronger attack model than the "nonadaptive" attack model, where we insist that the attacker gives us all the plaintext up front before we give him anything.  "Adaptively secure" means that it is secure within this attack model.

Nowadays, this distinction is a bit obscure, mostly because we really don't have much use for a cryptographical primitive that is secure only in the nonadaptive model; hence a "chosen plaintext attack" typically does mean "adaptively chosen plaintext attack".  However, the terminology does turn up when we're being precise.


Differential cryptanalysis in "The Block Cipher Companion" I am practically implementing a differential cryptanalysis on a cipher which can be found in the book "The Block Cipher Companion". Following image shows the cipher:

In Fig. 6.10 (page 126) there are some evaluations to the probabilities of success to correctly restore the bits 4-8 of k5 depending on a given count of choose messages. I try to compare my implementation with the given results. My problem currently is, that my implementation does not really compare good to the given results. For example: In the book they say, with 32 choosen messages, they restore the bits of k5 with a probability of 64% in 100 cases. I get roughly 28% with my implementation. So may be there is some problem with my implementation or the setup of the tests are a bit different. Is here anybody who implemented the differential cryptanalysis for the cipher in the book "The Block Cipher Companion"? Or does somebody has some test vectors?

I haven't studied this in detail, but the authors seem to give quite a comprehensive presentation of the differential attack.

Please note that this cipher is essentially the same as the one in Heys' Tutorial on Linear and Differential Cryptanalysis (easily found online by a google search) but the Sbox is different.

I have had students implement that attack successfully. So you can use that text as an extra reference while you are trying to sort things out.

In fact the authors themselves of the Block Cipher Companion state, on page 121, that

  The probability of
  the characteristic we have identified could be too small to effectively distinguish the
  correct key information.


Undetectable cheater in Shamir's Secret Sharing scheme Consider Shamir's Secret Sharing scheme with $n=5, t=3$ (i.e, there are 5 shares, and when we have 3 of them we can reconstruct our secret $s$). Let $f(x)$ be the dealing function, i.e the secret $s$ is defined as $s = f(0)$.

We assume that given 3 participants who gather together in order to reveal the secret, one of them wants to cheat in the manner of preventing the other 2 participants from revealing the secret. He doesn't care about the secret itself - he just want to sabotage the revealing of $s$.

I want to prove formally that neither of the 2 honest participants can detect who is the cheater.

My current lead is this: in the revealing process - using Lagrange's interpolation - each participant reveals his tuple $\left(x_i, f\left(x_i\right)\right)$ (where WLOG $\forall i : x_i \in \{1,2,3\}$), or perhaps just the unique function for that participant ($f_j(x) = y_j \cdot \prod_{1 \leq i \leq 3, i\neq j}\frac{x-x_i}{x_j - x_i}$ where eventually $\tilde{f}(x) = \sum_{j=1}^3 f_j(x)$ ) - but reconstructing this way only reveals a function $\tilde{f}(x)$ which they find out to be useless (when they try to use $\tilde{s}=\tilde{f}(0) \neq s$). It seems very intuitive that an honest participant cannot tell which $f_j(x)$ messed everything up, but I don't manage to write it formally. would appreciate some help... thanks.

The way to prove this is to follow the same proof that Shamir's secret sharing is perfectly secret. Specifically, given any two points all secrets are possible since there is a polynomial going through every possible secret and the two given points. Since the polynomial is random, all of these polynomials have the same probability. The same thing is happening here: given any set of three points, there is a polynomial going through those three points. Now, assume that you know exactly what the secret is. If you look at any subset of two of the three points, there is a polynomial going through those two points and the secret that you know. Thus, it is impossible to know which of the three parties is cheating, even if you actually know the secret you are supposed to get.


ECDSA vs RSA: Performance on Android platform and surprising results For our privacy-preserving protocol, an encrypted channel is established. In order to protect our system from man-in-the-middle attacks, a signature-based approach is used. After we've implemented it with RSA, we decided to optimize the protocol a bit by using ECDSA. The result was very surprising: on Android, signing and verifying in the case of ECDSA was 10 times slower than for RSA with the corresponding key length!
Any viable explanation for this?
Maybe the android smartphones don't have hardware support for elliptic curves, and for RSA operations they do?
The exact parameters are below:
RSA:   signing: 52ms,  verifying:   6ms
ECDSA: signing: 692ms, verifying: 975ms

Smartphone: Samsung Galaxy S Advance, GT-I9070P with CPU: 1 GHz STE U8500 DualCore
Crypto-lib: SpongyCastle 1.50.0.0
The elliptic curve used: 224 bit, secp224r1
ECC signature: SHA256 with ECDSA
RSA 2048 signature: SHA1 with RSA

BouncyCastle has a really bad ECC implementation. It uses affine coordinates which incur a huge performance hit (factor 20 or so) since it computes a field inversion after every single step. Good implementations use Jacobi coordinates (or a similar approach) where denominators are kept and there is only one field inversion at the end.

It's also potentially vulnerable to side channel attacks since it branches on secret data (only relevant to signing, not verification).

As another ECC benchmark you could look at the the ref10 branch of str4d/ed25519-java. This uses a different elliptic curve, Ed25519, but the main difference is that the implementation has been optimized more than the one you tested. But this is still new and experimental code, so be careful.


AES256 CTR nonce generation I am following a wiki diagram for CTR mode of operation in AES256. The documentation states that for it to work you need a random nonce with 8 bytes and then a counter of 8 bytes. So I guess you can randomly generate nonce for instance: SgVkYp3s. And then you just add a count to it. Then you iterate over all of your plaintext bytes and up the count with every pass of the for a loop. So in the end you get nonce like SgVkYp3s00000000, SgVkYp3s00000001, ... And then you use the same format for decryption. Is this the correct approach?

The counter mode encryption (and similarly the decryption) with AES work as
$$C_i = AES(key,nonce,i) \oplus m[i]$$ where the nonce and index $i$ is used to encrypt the $i$th block with the x-or of the output of the encryption.
The cryptographic algorithms work on bytes and you can consider it as a byte array. Now you need to fill the byte array with your random 8-byte values on the lower index and the rest is set to 0.
If you want to have the random access that CTR enables, you can set the upper bytes to the index $i$ within 64-bit representation.
If you are encrypting sequentially, then after setting the counterpart to zero, you need to implement a byte array incrementer. If we represent in hex then we need two hex char per byte;
1b4fe8364as4a8100000000000000000    //initial
1b4fe8364as4a8100000000000000001    //counter incremented
1b4fe8364as4a8100000000000000002    //counter incremented
1b4fe8364as4a8100000000000000003    //counter incremented
..
1b4fe8364as4a81000000000000000FF    //counter incremented
...

So I guess you can randomly generate nonce

There is a common problem here, 64-bit nonce is vulnerable to collisions. After $2^{32}$ random nonce generation under the same key one will have collisions with 50%. The 50% is not negligible, one must stop way before that. A better way is either

Generate the nonce sequentially, which may some other problems as system failures can cause re-use of the old values were the easiest mitigation is using a fresh key. Or,
Use larger random like AES-GCM uses; 96-bit nonce. This is safer to use randomly. Keep in mind that, this will limit the number of block encryption to $2^{32}$ and this makes $2^{36}$ bytes and that is $\approx 68.71$ GB.

And remember, AES has a 128-bit block size regardless of its key sizes 128, 192, and 256.
Normally, the cryptographic libraries handle those parts for you. You don't need to worry about those like Java's IvParameterSpec.


Is it possible to pick your Ed25519 public key? Is it possible to generate an Ed25519 keypair that has a very similar public key as another keypair (fooling a casual visual comparison) or is this as hard as solving one of SHA-512 or the discrete logarithm problem?

If you can store the private key with some pre-computed work, then you can pick almost any public key you want. So in a way, it depends on the implementation.

Here's a diagram of how Ed25519 works, note how keys are generated:

(Image source.)

A more detailed description (that is simpler than the actual paper) of the process is in these slides (slides 9 - 11).

To recap the image and slides: The secret is hashed and public key is derived from the "left half" of the hash. The left half is manipulated to be value $a$, which is a bit string with a few conditions. Then $a$ is applied to a curve point $B$ to produce the public key $A$.

The critical thing to note is that the seed's hash output is used in key generation. Apparently implementations differ on what they store as the private key, but the algorithm itself does not need the original secret, only the hash from it. This means that if you control the implementation you use, you can just make up any hash that suits your purposes and you don't need to care what the corresponding secret would be. (This prevents the need to finding any sort of SHA-512 pre-image.) We can use this by working backwards from the desired public key value and deciding what hash value we want.

The goal of this attack is to choose the value of $A$, or to at least choose something very similar to it. Call the new target public key we're trying to build $A'$, then if $A'$ is a valid public key there is an $a'$ such that $a'B = A'$. This reduces to finding the inverse on the elliptic curve, $a' = AB^{-1}$, which is actually the Discrete Logarithm problem and certainly non-trivial to calculate. But if you could find a valid $a'$, you would have everything you need.

As an important side-note, not all values of $a$ are valid in the scheme. See the Ed25519 paper for all restrictions for $a$ (I believe they are all listed on pg 6). There aren't very many restrictions, I think the most restrictive one is that $a$ be divisible by 8 (ie, the low three bits are 0). Assuming you can can calculate the $a'$ from a chosen $A'$, you could just pick random $A'$s until you find one that produces a valid $a'$. This step would prevent you from explicitly choosing your public key, because you have no guarantee that the desired value for $A'$ is valid. You can probably find a valid $A'$ after only a few tries, so just flip a bit here and there in the desired $A'$ and you should be able to find one that works and has a small Hamming distance from the original desired $A'$, which is probably good enough to produce keys that look alike.

If you have $a'$ then you have the public key and you can create a corresponding private key. You can make up a random "right-side" of the SHA-512 hash value and incorporate the new $a'$ to construct the private key.

This all assumes you can control the implementation and solve the necessary discrete logarithm. Regarding the implementation, the NaCl project has a high-speed performance-oriented implementation of Ed25519, and as such it stores as much pre-computed data as possible in the private key. It would allow you to perform this sort of manual crafting of the keys. But in general, with other implementations, you may have no such luck. I would think that for most attacks, the attacker should be assumed to be able to choose the implementation they use.

(Hopefully this is all correct, I hadn't looked at Ed25519 before this.)


Is there a secret sharing scheme which allows sharing of a secret (one-out-of-n) Is there a secret sharing scheme where the knowledge of just one share is sufficient to find the secret, in other words a (one-out-of-n) sharing scheme ? Plz I need to know if it is possible to make such operation with secter sharing

Just tell the whole secret to each person.


Could use an explanation of the notation for an oracle adversary In the definition below, what exactly does it mean for the adversary (not even sure that's the correct term?) to equal one?

$$
\underset{K}{Pr} \left [A^{F_k(\cdot)} = 1 \right ]
$$

Source (Page 22/35?)

This represents the probability over all $K$ that $A$ given an oracle access to $F_K(\cdot)$ outputs 1. You usually compare that to the probability of A ouptputting 1 while having oracle access to a random function and the difference tells you how well $A$ does at telling $F_K$ from random


Help understanding lattice-based aggregate signature scheme I came across this paper about aggregate lattice-based signatures, however, I'm not able to fully understand it. Specifically, I'm wondering if someone could help answer the following questions:

In part III. System model of Aggregate Signature, the authors state there is a KeyExtract algorithm where "Given parameters $n$ and $PP$, the KGC provides public/secret key pairs ($pk$; $sk$) for all single signers." - is this to be understood as all key pairs must be generated by some trusted authority?
What are the sizes of public keys, signatures, and aggregated signatures (in bytes)? On the second to last page there are two tables that address this, but I'm not sure how to translate this info into bytes (at ~128 bit security level).

"Given parameters $n$ and $PP$, the KGC provides public/secret key pairs $(pk; sk)$ for all single signers."

Yes, the key generation center (KGC) generate the key pairs $(pk; sk)$ and distributes them. It is also clear from figure 3 of the article.

  What are the sizes of public keys, signatures, and aggregated signatures (in bytes)?

The parameters are used in $TrapGen(n,q,m)$, which actually generates for SIS parameters. You can find example secure paremeters from here or similar work.


Does key authentication in SSH protect from MitM? How do cryptography in SSH(2) work (secure channel establishment, authentication)?

Does key authentication in SSH(2) protect from MitM by providing authentication and integrity and why?

How do cryptography in SSH(2) work?

This is a very broad question. If you're interested in the details, then read the relevant RFCs that describe the SSH protocol. In particular:

RFC 4253 - The Secure Shell (SSH) Transport Protocol
RFC 4252 - The Secure Shell (SSH) Authentication Protocol

  Does key authentication in SSH(2) protect from MitM by providing authentication and integrity and why?

Assuming you're referring to Public Key Authentication (where a client authenticates by proving they hold the private key of a pre-shared public key), then not directly/entirely. Public key authentication is a feature of the SSH Authentication Protocol, which runs on top of the SSH Transport Protocol, and generally assumes that the transport protocol provides confidentiality and integrity.

The Public Key Authentication does provide some protection against mitm attacks (by associating the proof of the private key with the SSH session ID), which will prevent the mitm passing on the private key proof as an authentication credential, but won't prevent an attacker using other credentials to access the target system.

The primary mechanism for man-in-the-middle prevention in the SSH Transport Protocol is the verification of pre-shared (or otherwise verifiable via some trusted channel) host keys.

RFC 4251 - The Secure Shell (SSH) Protocol Architecture discusses potential Man-in-the-middle attacks on the SSH protocol and the approaches taken to prevent them.


How to encrypt a vector $e\in Z^{m}$ using LWE I have a vector $e \in Z^{m}$, now I want to encrypt it by using LWE (Learning With Errors).

Because in LWE, we have to encrypt of a bit $\{0,1\}$. How can I encrypt a vector $e \in Z^{m}$?

I think you will not find any scheme that works over $Z$.

But, if you want to work over $Z_t$, you just have to choose a LWE-based encryption scheme that encrypts non-binary messages, and there is a lot of them!

For example, the paper ML Confidential uses one scheme  like that (non-binary messages) to perform classification algorithms over cipher texts.

The same occurs with this one: Using Homomorphic Encryption for Large Scale Statistical Analysis.

In general, the LWE schemes are presented considering only binary messages because the authors want to extend them to some Fully Homomorphic Encryption (FHE). Since the FHE is able to process functions described as boolean circuits, these schemes just worry about encrypt bits.

But usually, it's easy to change the schemes to work over $Z_t$ if you don't need a FHE, I mean, you don't need to do arbitrary sequences of multiplications and additions.

To do so, you just have to adjust the modules used by the schemes and be aware that you possibly will be able to do less operations than specified on the papers to the same set of parameters.


Security analysis for a extended ElGamal Signature against selective unforgeability Let $H$ is a cryptography hash function and $\Pi=(\mathsf{G}, \mathsf{S}, \mathsf{V})$ is a digital signature, as follows:

$(h_1=g^x,h_2=g^y) \leftarrow \mathsf{G}(1^n)$,  where $x,y$ uniformly random from $\mathbb{Z}^*_q \ .$

$(r=g^k,s=(H(m)-x \cdot r)\cdot k^{-1},z= y^{-1} \cdot k ) \leftarrow \mathsf{s}_{x,y}(m)$, where $k$ uniformly random from $\mathbb{Z}^*_q \ .$

$b:=\mathsf{V}_{h_1,h_2}(m,(r,s,z))$, where $b :=
\begin{cases}
   1 & \text{if } (g^{H(m)} = h_1^r \cdot h_2^{z \cdot s}) \\
   0 & \text{otherwise}
 \end{cases}$
The above construction is similar to ElGamal signature (https://en.wikipedia.org/wiki/ElGamal_signature_scheme).

1- Where can I find proof of existential unforgeability ElGamal signature?

2- Does the above construction is a secure digital signature against existential unforgeability?

The hashed ElGamal signature scheme was shown to be secure by Pointcheval and Stern (see Section 3.3.); i.e., the signature scheme resists adaptive chosen message attacks assuming the discrete logarithm problem is hard. The proof of security is quite remarkable, as this was the first application of the forking lemma. Sometimes they refer to the hashed ElGamal signature scheme as the Pointcheval–Stern signature algorithm.
Note that the original ElGamal scheme (where the message is not hashed) is existentially forgeable, see Theorem 16. in the linked paper above.


Is the Salsa20/ChaCha20 keystream generation one-way? Is it possible to recompute the Salsa20 or ChaCha20 key in a realistic time if the keystream and the nonce are given to an attacker? Or is the keystream generation one-way, like a cryptographic hash function?

Nobody should be able to retrieve the key from the IV + key stream. If that would be possible then the stream cipher would be broken. Both the IV and key stream can be considered public knowledge (by performing a known plaintext attack, for instance using all zero's). Retrieving the key from information that may be known to an attacker constitutes the strongest attack possible, so any stream or block cipher should protect against that situation.

Or, as fgrieu already states without making it an answer:

  A keystream generation algorithm which key, assumed unknown and uniformly random, can realistically be found from the output keystream and input other than key, is broken by definition of key per Kerckhoffs's principles, and/or of the security objectives of a keystream generator/CSPRNG.


Trapdoors of Lattices: SampleD and SamplePre In Trapdoors for Hard Lattices and New Cryptographic Constructions by Gentry et. al, they discuss SamplePre and in Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller by Micciancio et.al, they discuss SampleD.

But still, I cannot understand whether the functionality id same or different. Can you explain?

No, they aren't the same. One of them maps 4 values to a single value, the other maps 2 values to a single value.

But yes, both functions have some similarities. Both compute the inverse of a known function witch can be computed only because a trapdoor is given (t in SamplePre and R in SampleD). We can use SampleD to create different SamplePre functions changing the parameters creating this way different trapdoor schemes.


What is the difference between Shor's algorithm for factoring and Shor's algorithm for logarithms? There is a paper from Peter W. Shor from 1994:  Algorithms for Quantum Computation: Discrete Logarithms and Factoring, and I have a question about it and the algorithms presented.
For integer factoring problem, Shor's algorithm is working as a fast period finder for function f(x) = a^x mod N, where semiprime N is equal to p*q, a is fixed and all possible exponents x are quantumly computed. Then, Shor uses Simon's algorithm to find period r of f(x) such that f(x) = f(x+r) . With 0.5 probability, the output of quantum scheme r will be the even, and a^(r/2) will be the non-trivial square root of 1 mod N. Having such root we can easily crack N to p and q. (If there is something wrong with this description, please comment. The simple quantum circuit is
here.
But how does Shor's algorithm for the discrete logarithm problem work? There is only prime number P (and generator g), so we can't factor it into something having a square root. I'm even not sure that there will be any nontrivial square root in the mod p field.
The task for discrete logarithm is: given some x, equal to x = g^r mod p, with g and p known, find the r.

In fact, the basic idea of Shor's algorithm for the discrete logarithm problem is reasonably simple.

Assume (as in Section 4 Discrete Log: the easy case of Shor's paper) that you have an efficient quantum algorithm for the Fourier transform. Then, applying this Fourier transform twice (once for $a$ and once for $b$) on a quantum superposition of values $g^a\cdot x^{-b}$ and measuring yields a pair $(c,d)$ with $d\equiv -cr\pmod{p-1}$. Thus, you can recover $r$ (if the gcd of $c$ and $p-1$ is $1$) directly with a simple division modulo $p-1$. [If the gcd is a small number it is also easy to conclude]

Unfortunately, doing this Fourier transform directly is only easy when $p-1$ is smooth (which is an uninteresting case since dlogs are easy with a classical computer in that case) and technicalities arise because of this. These technicalities involve replacing the Fourier transform modulo $p-1$ by a Fourier transform modulo $q,$ where $q$ is smooth and not too far from $p-1$.  A similar technique is used for factoring: it is simpler than the general discrete logarithm case because a single application of the Fourier transform is enough in that case.


Sequence output by a Galois type LFSR I have provided a diagram of a Galois type LFSR. I am told it outputs a sequence of period 31.

Find the sequence output by this LFSR.

By applying the shifts I got the seemingly trivial answr of $0,0,0,0,1$ which I know must be wrong since it has a period of 31. Where have I gone wrong?


Does MD5 hash have quasi commutative property? I am implementing a one-way accumulator using MD5 hash, wondering wheather it has quasi commutative property or not.

No it does not. There are only a few cryptographically strong functions that have that quality out there. lattice based methods are promising.


Does a man-in-the-middle attack apply in this scenario? Disclaimer: I am aware that the question's title does not adequately describe what I am asking, but it is the best I could come up with. Any improvement is welcome.
I am a university student studying for an upcoming cryptography exam, and I came across this unsolved exercise. I have various questions that stem from it.  Unfortunately, my professor is unavailable, and I cannot contact her. So I would appreciate some clarification as to whether my approach is correct and whether there are many right answers.
Consider the following system for the communication of a group of nodes. This group has a standard number of M members that each have a unique id. A central entity CE also exists for the facilitation of node communication.
When a member Mi is accepted into the group, they produce a key pair KiPUB and KiPriv, and share their public key and id with the CE.
When a member of the group wishes to communicate with another member, it sends the id of the intended receiving node to the CE and gets back the receiver's public key. The message is then encrypted with said public key and sent.
a.  If you have access to the communication path of Mi with CE or any other node, but cannot meddle with the contents, can you decrypt messages sent by Mi?
My initial answer to that is no. The attack that makes sense to me is the man-in-the-middle attack, and it needs to be able to change the messages sent. However, it is unclear whether the man-in-the-middle has to be an entity "formally" incorporated into the system, into the communication process. If so, then it does not apply, and some other attack would be appropriate for this scenario.
b.  You can now alter the contents of Mi's communication with other nodes and CE. Can you do that without being detected? Can you now decrypt the messages sent?
My answer to that can be easily derived from the one in question a. my problem is if man-in-the-middle does not have an effect here, my whole reasoning falls apart.
c.  How would you change the system so that every node stores every other node's public key to protect from such attacks? What memory demands would that system have compared to the existing one?
It seems unlikely that all that is required as an answer is "have each member send all other members its public key via a secure channel," and at the same time, I'm not sure how much further beyond that I am supposed to go.
As for storage, compared to the $M$ number of keys CE would have to store, $M$ being the number of members, each member now has to store all member public keys, so it changes to $M^2$.
To clarify, this is not an exercise that will be graded, just one that I'm trying to solve to understand the material better and clarify my thinking on the matter. If you downvote my question, please provide a comment with the reason. I am looking for some pointers and explanations, as the theoretical approach doesn't seem to be enough for me to figure this out.

The exercise fails to cover how a sender is supposed to know the Id of an intended recipient, and how the CE is supposed to know that a KiPub it gets is that of the Mi with this Id. If the goal is just to get away with a high mark, ignore the issue or briefly mention we assume sender knows Id; and CE knows Id and KiPubwith, and acts honestly. Never insist that the question is lacking when it could be that the author is the grader!
Then the initial answer to (a) is correct: with only passive eavesdropping, there's no attack to the system proposed. I don't get what's meant by "formally" incorporated, but a Man in the Middle is an adversary assumed to go beyond passive eavesdropping, and that's excluded in (a) by "cannot meddle with the contents".
For (b), there's an attack possible by a MitM. Just describe that attack with enough details, like you are the mastermind explaining how it's done to a novice accomplice. Detail exactly what the MitM changes (and into what) in order to "decrypt the messages sent" [hint: "The message" won't cut it].
For (c), "every node stores every other node's public key" is a solution to the attack in (b) only inasmuch as it gets achieved, and the question asks how. One acceptable answer involves detailing how the CE makes public key certificates, how they are communicated and checked. I recommend to make another assumption explicit: that each member knows the CE's public key.
More hint: the first part of (c) ask how we prevent the attack in (b), and in my reading that requires explaining how we get a member to know another member's KiPub, rather than assuming that it happens [it did not in the attack of (b)]. Among the methods for this allowing new members (as required), matching (c), and close to the practice commonly taught, we'd rather use the one closest to the exercise's existing setup. That seems to be: keep the CE authenticating new members and their KiPub however it does that now, and tweak it's role: from distributing a KiPub on request, to distributing certified KiPub to each existing member as a new member enrolls.
The part of (c) about the storage required may be calling for a comparison with the storage required for secret-key cryptography, and a level of criticism of "every node stores every other node's public key".


Using the output of HKDF directly I am using HKDF with an IKM and salt, the OKM is used as the key for an HMAC operation. The HMAC algorithm is authenticating messages in a communications system

The salt is the concatenation of 2 nonces, 1 drawn drawn by each of the communicating nodes and can be found by any one observing the communications system

Messages are sent as:

message || sequence number || HMAC(key, sequence number || message)

My question is this: Is it safe to use the OKM directly as the key for the message HMAC or should I perform some other operation on the OKM before using it?

The whole idea of a KDF is to use the output of the key material as, well, an unpredictable key to an attacker. So as long as your IKM is secure and preferably your salt is unique, then the output of a KDF should be usable as key.

For HMAC it is best to use the same key size as the output of the hash algorithm used, as per HMAC spec:

  The key for HMAC can be of any length (keys longer than B bytes are
     first hashed using H).  However, less than L bytes is strongly
     discouraged as it would decrease the security strength of the
     function.  Keys longer than L bytes are acceptable but the extra
     length would not significantly increase the function strength. (A
     longer key may be advisable if the randomness of the key is
     considered weak.)

You're correctly concatenating the nonces already to create the salt. Don't use XOR for that.

Um, yeah, I think there is all that there is to it. If you just need one key you can do with just HKDF-Extract which takes the IKM and, indeed, a salt.


Why do we use XTS over CTR for disk encryption? I'm taking Prof. Boneh's crypto class from Coursera, and am unsure on the requirement for XTS mode for disk encryption.

It seems that CTR mode would do exactly what XTS can do, but is simpler to implement? In either mode, I will use the disk sector # to provide randomness to ensure that 2 sectors of same data will end up with different cipher texts. What subtlety have I missed?

Suppose you use the sector number times the number of AES blocks per sector as the initial value for CTR. If you successively store the content $M$ then $M'$ in the same sector $n$ then $E^{CTR}_n(M) \oplus E^{CTR}_n(M') = M \oplus M'$ (where $E^{CTR}_{n}$ is the encryption function with CTR mode and IV started for sector number $n$). CTR mode fails catastrophically when you reuse a counter value, because it's a pure xor stream cipher: xorring two ciphertext blocks that were produced with the same key and counter values cancels out the encryption. For example, if the block started out as all zeroes (which happens pretty often in practice) and an adversary manages to obtain both the initial ciphertext and the updated ciphertext, then the adversary has the confidential plaintext on a platter.

If you use the sector number as the initial counter, it's even worse since the second block of a sector shares a counter with the first block of the next sector and so on. That would enable an adversary to reconstruct a lot of content with even a single snapshot of the disk.

To use CTR safely, you need to generate a fresh counter value each time. You can use the sector number as part of the initial counter value, but there's little value in doing so, because you'll need to store the rest of the counter (some kind of per-block update count, a global counter value, a random value, or any other scheme) anyway.

XTS incorporates the sector number as a tweak. Any change in the plaintext results in a complete change of the content. An adversary who knows the content of a sector at two different times can observe whether the content of the sector has changed, which is unavoidable for deterministic encryption, but if the content has changed, then the adversary obtains no information about the plaintext.

If the only threat is that the disk is stolen, so that an adversary will only ever obtain one version of the ciphertext and no more plaintext will ever be encrypted after that, then I don't think there's any benefit in using XTS over CTR.

If the adversary can observe the ciphertext at different times, XTS does a better job. Not perfect though: you need the extra burden of storing an IV of some kind for that.

If the adversary can modify the ciphertext, then you need to worry about data integrity as well. CTR is extremely malleable: the attacker can flip plaintext bits by simply flipping the corresponding ciphertext bit. XTS is less malleable but still allows the attacker to replace good content with garbage or with older content. Authenticated encryption modes combine encryption with a MAC, and thus provide both confidentiality and authenticity (and if done right, integrity).


Brute force knowing a part of the password So here is the problem, my brother forgot about the eight digit numeric part of his password, he is using Ubuntu 15.04 default whole disk encryption

To make it clear, this was his password (example)

  thiswashispassword12345678

He completely forgot about the 12345678 part, to make things worse it was his working laptop with lot of important documents in it, for "backup" he was using raid 1 so same problem, his boss gave him a month top to recover the data or he is fired, is he screwed?

We solved this problem in just 9 hours 37 minutes.

Here is how to do it.

Tools you need:

sudo apt-get install cryptsetup
sudo apt-get install dh-autoreconf
sudo apt-get install libcryptsetup-dev

1 - Dump the encryption header of your device using cryptsetup toolset, here /dev/sda1 was our device yours could change:

sudo cryptsetup luksHeaderBackup --header-backup-file headerOutput /dev/sda1

2 - Generate a dictionary with all the possible combinations of the part of the passphrase you forgot; We paid a professional solution for this but there are tons of tools and programming language to accomplish this task for free.

3 - Download and compile this free project (https://github.com/glv2/bruteforce-luks)

wget https://github.com//glv2/bruteforce-luks/archive/master.zip
unzip master.zip
cd bruteforce-luks
sh autogen.sh
./configure
./make

4 - Recover your password

./bruteforce-luks -t 6 -f dictionaryYouGenerated yourLUKSHeaderFile

Notice the step "4" will be extremely slow since it utilizes the CPU and the software is not optimized at all, that's why we bought a similar software made for GPU's and we also hired a powerful cloud distributed computing solution (I can't put names here)

In our case the cost of everything was exactly 4400 USD (developer + software + cloud service)
Lesson learned from now on we are storing the passphrase printed in a safe so this never happens again. Thank you and I hope this help someone in the same desperate situation.


What's the point of hiding the key in white box cryptography if the attacker already has full access to the encryption (or decryption) implementation? The attacker doesn't need the key in order to decrypt ciphertexts or encrypt plaintexts since he/she already has the full implementation.

So what's the point of hiding the key?
What advantage would the attacker even have by knowing the key?

Update:
ddddavidee's answer below, in the second paragraph, raises an interesting point: a white-box implementation of a symmetric cipher that exhibits the "one-wayness" property - i.e. it is infeasible to derive the decryption circuit from the encryption circuit, or vice versa - can be used to create an assymetric cipher. That would indeed be useful. Note that key-extraction security - i.e. it is infeasible to derive the key from the encryption (or decryption) circuit - is a necessary but not sufficient condition for achieving one-wayness.

However, I'm still stumped by the tenor of the first paragraph of ddddavidee's answer, which is why I asked this question to begin with. The model for an attacker of a white-box implementation assumes that they have full access to the encryption (or decryption) circuit. In that case (aside from the scenario in the previous paragraph), what is the point of the notion of key-extraction security, or key-extraction itself, for that matter, since the attacker can accomplish any encryption without using the key? Either I am missing something or there is something missing or flawed in the definition of white-box cryptography itself.

The main goal is to, at least, oblige the attacker to use the software to consume the encrypted message and avoid to use it on a different platform.
It is quite easy to understand this reason if one thinks to the DRM (Digital Right Management) model: one vendor sells hardware with the capability to show some media content. If an attacker can decrypt and use the content on her PC the vendor loses some market.
In the mobile payment context one wants to avoid that a malware could steal payment keys and use them in a different platform against the legit user.
A different use is to protect the Intellectual Property from the final user: some piece of firmware or software has to be given to the final user but the vendor wants to keep it protected.
Other examples can be found thinking when, where and why hardware tokens are used. The white-box encryption can be seen as, with some other software security measures, as a cheap replacement for the hardware tokens (or smart cards).

Moreover you can see the white-box encryption as a way to transform a symmetric key algorithm into a asymmetric one. If it is infeasible to reverse the white-box encryption algorithm into a decryption one and it is infeasible to extract the key, only the encryption algorithm is available and the decryption remains infeasible. The same applies in the opposite direction: providing a white-box decryption makes impossible to encrypt something under the same key.

Some other security properties are discussed in this paper White-Box Security Notions for Symmetric Encryption Schemes

In particular the "incompressibility" property says that "should not be possible to output a program smaller than the challenge one doing the same crypto-operation". Some solutions have published achieving a provable incompressibility, the reason motivating such construction is that it is more difficult for a national agency to store (say) 1 terabyte of key per person to decrypt the targeted user data, while would be feasible to store the corresponding 128-bit key.


Result of expressions using modular arithmatic for group signatures I read the following in a paper about group signatures called "A Practical and Provably Secure
Coalition-Resistant Group Signature Scheme".

In the sign part of paper the following expressions can be found:

$$d_2 = T_2^{r_1}/g^{r_3} \bmod N$$
$$s_1 = r_1-c(e_i-2^{\gamma_1})$$
$$s_3 = r_3-c*e_i*w$$

and in the verify part

$$d_2 = T_2^{s_1-c*2^{\gamma_1}}/g^{s_3} \bmod N$$

this is not producing correct result as $d_2$ doesn't verify.

I am confused about the result of these expressions, can you explain if and why the expressions are correct?

The $\text{ mod } N$ is implied in all equations below.

In the signing process we have:

$$d_2 = T_2^{r_1} / g^{r_3}$$

In the verification process we have:

$$d_2 = T_2^{s_1 - c2^{\gamma_1}} / g^{s_3}$$

So we know that we must have the following equivalence:

$$T_2^{r_1} / g^{r_3} = T_2^{s_1 - c2^{\gamma_1}} / g^{s_3}$$

Substituting in the values for $s_1$ and $s_3$ we have:

$$T_2^{r_1} / g^{r_3} = T_2^{r_1 - ce_i + c2^{\gamma_1} - c2^{\gamma_1}} / g^{r_3 - ce_iw}$$
$$T_2^{r_1} / g^{r_3} = T_2^{r_1 - ce_i} / g^{r_3 - ce_iw}$$

From the paper we know that $T_2 = g^w$ and we can also use some exponent laws to simplify:

$$(g^w)^{r_1} / g^{r_3} = (g^w)^{r_1}(g^w)^{-ce_i} / g^{r_3}g^{-ce_iw}$$
$$g^{wr_1} / g^{r_3} = g^{wr_1}g^{-ce_iw} / g^{r_3}g^{-ce_iw}$$
$$g^{wr_1} / g^{r_3} = g^{wr_1} / g^{r_3}$$

Hence the equation provided are correct, and the verify procedure does indeed produce the same $d_2$ as the sign procedure. If you are producing incorrect results one thing to remember is that division $\text{ mod } N$ is equivalent to multiplication by the multiplicative inverse of the denominator.


Why doesn't any cryptographic library apply the Lehman's method? Lehman's method can be described as;
Let $N=pq$. If the ration of $p/q$ is near a ratio of two small numbers $r/s$, then $ps$ and $qr$ are close to $\sqrt{nrs}$. The Fermat's method can be easy applied to $nrs$, and $p=\gcd(ps,n)$, $q=n/p$.
Why doesn't any cryptographic library apply the Lehman's method?

I think the question really is: why don't cryptographic libraries generating RSA keys check if $p$ and $q$ are such that $N$ would be easily to factorize by Lehman's method?
That's because the probability that this stands are negligible. One way to prove this is to establish that Lehman's method overall has cost $O(N^{1/3})$ for random distribution of $p$ and $q$ with whatever limit the generation method has, like $\max(p,q)<2\min(p,q)$. GNFS and Lentra's ECM factorization are more credible ways to factor such $N$, and the later has to an even higher degree than Lehman's method the characteristic of having probability of success grow progressively with effort. So why bother with a test against Lehman's method when a rational adversary would skip Lehman's method in favor of GNFS or ECM?
Then one can ask: so why do some cryptographic libraries generating RSA keys check if $\lvert p–q\rvert$ is above some bound, apparently to protect against Fermat's factorization method? That's because it's a way to check some failure modes of the prime generator, including returning a constant value. And because $\lvert p–q\rvert>2^{(n_\text{len}/2)–100}$ is mandated by FIPS 186-4, section B.3.1, item 2(d).
But why is there this check in FIPS 186-4? I guess that's essentially because it's been in the earlier ANSI X9.31:1988, combined with it's indirect way of checking some horrible RNG failure, and the unlikeliness that it would harm (even in a side-channel attack).
But why is there this check in ANSI X9.31:1988? My understanding is that's bowing to request of some member(s) of the committee, sponsored by bankers, who wanted to show that every reasonable precaution was taken. Based on my memory of what Bob Silverman (who stood at this committee and was instrumental in writing the standard) has reported, the rationale was to make it harder for a lawyer to repudiate an RSA signature in court, by a wrong but superficially credible argument on the tune of: these "RSA signatures" are not admissible evidence! It was not taken reasonable precautions to make the factorization of the modulus $N$ difficult. Look, even some algorithm known to XVIIth century mathematician Pierre de Fermat could have been used to forge that "signature" thing opposed to my client!


Why develop new stream ciphers when block ciphers can be trivally made into streams? I've just been reading about a new drop-in replacement for the RC4 stream cipher, but why develop new stream ciphers when AES can be made into a stream with a little XORing?

The biggest reason is performance. Stream ciphers are generally faster than block ciphers and perform fewer operations. Stream ciphers only need to generate a pseudorandom output while block ciphers need to be pseudorandom permutations. So when you create a steam cipher out of a block cipher, you are doing a lot more work to get the same effect. To get an idea, look at how much more work is required to encrypt 16 bytes with AES than RC4.


Can one group the SHA-256 outputs depending on partial inputs? Is it possible to predict a hash key based on half key?
Let's have some example:

I have 100000000 hash results, and they are generated by either

sha256( "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" . md5(random()) );

or

sha256( "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb" . md5(random()) );

So, when someone generates a new hash (based on method "aa" ou method "bb"), is there any way that I can predict if hash is more a "aa" generated type or more a "bb" one?

I have already tried some type of Bayes classification, because I know that can only be there 2 types of results. But for each result I cannot classify hashes so that I have a good Bayes training.

Is this theoretically possible?

Somewhat simplified, if that were possible, you would have found a vulnerability in SHA-256. The kind of attack you're talking about is called a preimage attack, ie figuring out information on the original message from the hash. There have been some attacks of that kind against a weakened version of SHA-256 but no successful ones against the standard algorithm.

Of course your MD5 only adds 128 bits of entropy and your other data one (either all a or all b), but a brute force attack against 129 bits isn't what you're looking for either.