Must the order of the groups in a bilinear map be the same? I've been reading up on bilinear maps and their application to cryptography and one thing I keep seeing hasn't yet clicked.

If $e:G_1\times G_2\to G_n$ is a bilinear map, $G_1,G_2,G_n$ are always defined as having the same order.

It seems to me, however, that $ord(G_n)$ should be $ord(G_1)\cdot ord(G_2)$. Is there a reason that I always see the groups having the same order by definition? Must that be the case?

If both $G_1$ and $G_2$ have prime order $r$, then this means that there are generators $g_1$ and $g_2$; thus, for every $u_1 \in G_1$, there is an integer $x_1$ modulo $r$ such that $u_1 = g_1^{x_1}$. Therefore, every pairing value $e(u_1, u_2)$ is equal to $e(g_1^{x_1},g_2^{x_2}) = e(g_1, g_2)^{x_1x_2}$ by bilinearity. It follows that $e(g_1,g_2)$ is a generator of all the possible pairing values, and the bilinearity implies that $e(g_1,g_2)^r = e(g_1^r, g_2) = 1$. Hence, the group of possible pairing values also has prime order $r$.

Now you can imagine $G_n$ as being larger, with possible pairing values being only a strict subset of $G_n$, but that's just cheating.

Note that bilinearity and non-degeneracy imply that if a prime $p$ divides the order of $G_1$, then $1 = e(u_1^p,u_2) = e(u_1,u_2^p)$, from which we can conclude that $p$ also divides the order of $G_2$, and the order of $G_n$ as well. So we cannot have pairings over just any groups.

It is possible, however, that $G_1$ and/or $G_2$ are larger than $G_n$. In practice, the currently known efficient pairings are all derived from Weil or Tate pairings, which work over elliptic curves. From now on, I will denote operations in $G_1$ and $G_2$ additively, because Tradition requires that we talk about point additions. The basic setup of Weil and Tate pairings goes thus:

Let $\mathbb{F}_q$ be a finite field of order $q$. Let $E$ be an elliptic curve over $\mathbb{F}_q$. Let $r$ be a prime divisor of the order of $E$, such that $r^2$ does not divide the order of $E$, and $r$ is not equal to the field characteristic (this is to avoid a lot of degenerate cases). We denote $E[r](\mathbb{F}_q)$ the subgroup of points of $r$-torsion: these are the points which yield $0$ (the "point at infinity") when multiplied by $r$, and there are $r$ of them.

Then there is an embedding degree which is the lowest integer $k \geq 2$ such that $r$ divides $q^k-1$. It so happens (theorem of Balasubramanian-Koblitz) that $E[r](\mathbb{F}_{q^k})$ (the group of $r$-torsion points over the curve $E$, this time considering point coordinates over the field $\mathbb{F}_{q^k}$) contains $r^2$ points.

In that situation, both Weil and Tate pairings become non-trivial; they take as input $r$-torsion points in $E[r](\mathbb{F}_{q^k})$, and yield as output values in $\mathbb{F}_{q^k}^*$, and more specifically $r$-th roots of $1$ in that extended field. This is a subgroup of size exactly $r$ of the invertible elements in the field. This is our group $G_n$.

So we have the following situation:

$G_1$ and $G_2$ are both subgroups of $E[r](\mathbb{F}_{q^k})$, and thus may have order $r$ or $r^2$.
$G_n$ has always order $r$, no more, no less.

At that point, we must choose our groups so that we get some desirable properties:

$G_1$ and $G_2$ both have order $r$.
It is easy to hash arbitrary data messages into elements of $G_2$ (i.e. we can "randomly" generate elements of $G_2$ without knowing the discrete logarithm of the resulting point with regards to a given generator of $G_2$).
There exists a one-way non-trivial morphism from $G_2$ to $G_1$: this is a linear function which outputs values in $G_1$, such that values other than 0 are achievable, the function is easy to compute, but its inverse is computationally infeasible.

Unfortunately, we cannot have all three properties simultaneously. We end up with the following usual choices:

We use a supersingular curve of embedding degree $2$. $G_1$ is $E[r](\mathbb{F}_q)$ (the $r$-torsion points on the curve in the base field, not the extended field). $G_2$ is the very same group; to compute the pairing, we first map $G_2$ into another subgroup of $E[r](\mathbb{F}_{q^k})$ through a distortion map (if both operands of Weil or Tate pairing are from the curver over the unextended field, the pairing output is always 1, hence trivial). Easily computable distortion maps are a rarity, but with a supersingular curve, we have some. For that scenario, $G_1$, $G_2$ and $G_n$ all have the same order $r$; it is easy to hash data into elements of $G_2$; an isomorphism between $G_1$ and $G_2$ is easily computed in both directions since they are the same group.
We use a non-supersingular curve. $G_1$ is $E[r](\mathbb{F}_q)$ and $G_2$ is a subgroup of $E[r](\mathbb{F}_{q^k})$ generated by a conventional $r$-torsion point (not one which is in $G_1$); thus, $G_1$ and $G_2$ both have order $r$. We do not know how to hash points into $G_2$. The Trace of Frobenius of a point $P = (X, Y)$ is defined as:

$$ \phi(X,Y) = \sum_{i=0}^{k-1} (X^{q^i}, Y^{q^i}) $$

(it is a sum of elliptic curve points, and each of these points is obtained by taking the coordinates of the input point, raised to power $i$). $\phi$ happens to be an isomorphism from $G_2$ onto $G_1$, and it appears to be difficult to invert.
We use a non-supersingular curve. $G_1$ is $E[r](\mathbb{F}_q)$. $G_2$ is the subset of $E[r](\mathbb{F}_{q^k})$ consisting in points $P$ such that $\phi(P) = 0$ (the set of "points of trace zero"). $G_2$ is a group of order $r$ and we know how to hash points into $G_2$. However, we do not know any easily computable non-trivial morphism from $G_2$ to $G_1$, or from $G_1$ to $G_2$.
We use a non-supersingular curve. $G_2$ is the complete $E[r](\mathbb{F}_{q^k})$; thus, it has order $r^2$. $G_1$ is any subgroup of $G_2$ (of order $r$), possibly $G_2$ itself (of order $r^2$). It is easy to hash into $G_2$.

One way to think of pairings is that a pairing is a product. If we had a group $G$ with an "addition" and we could find a pairing of pairs of elements of $G$ into elements of $G$ itself, then that pairing would behave just as multiplication behaves with regards to addition (it would, by the way, totally break Diffie-Hellman on the group $G$). So the "natural" situation is really that $G_1$, $G_2$ and $G_n$ all have the same order.


How can finding a collision help an attacker with tampering messages with HMAC As stated in the HMAC RFC (RFC 2104):

  The strongest attack known against HMAC is based on the frequency of collisions for the hash function H.

How can a collision benefit an attacker? I would have thought that the strongest attack would be a brute force attack aimed at discovering the secret key.

From that same document:

  In any case the minimal recommended length for K is L bytes (as the hash output length).

So as long as the key is fully randomized, i.e. a cryptographically strong key, the time for brute forcing is at least the same or higher than the time finding a collision. If your key is indeed smaller or not fully randomized, then brute forcing attacks may indeed apply.

If you can find a collision, then you could possibly replace the message. But the hash would still be dependent on the key, so you should see this as a strict lower bound. An attacker would still not break HMAC by only finding a collision (otherwise HMAC with MD5 would be broken by now).

For instance, Wikipedia mentions:

  The cryptographic strength of the HMAC depends upon the size of the secret key that is used. The most common attack against HMACs is brute force to uncover the secret key. HMACs are substantially less affected by collisions than their underlying hashing algorithms alone.Therefore, HMAC-MD5 does not suffer from the same weaknesses that have been found in MD5.


Fast evaluation of polynomials Let $x_1,\dots,x_n$ and $y_1,\dots,y_N$ be some known integers modulo $2^k$, where $n\ll N$.

For each $x_i$, I have the following polynomial:

$$P_i(z)= \prod_{j=0}^{k-1}(z+2^jx_i) \mod 2^k.$$

Note that these polynomials are sparse, because only high powers of $z$ survive the coefficient-wise reduction.

My objective is to find the values of $y_1,\dots,y_N$ that vanish each of these polynomials, i.e., find the zeroes among $P_i(y_j)$ for $i\leq n, j\leq N$.

The naive approach of (perform every evaluation) is obviously on $O(knN)$ products in this ring of integers. Is there any way to do better, considering the form of these polynomials and the fact that they are sparse?

I think you can find the pairs $(i,j)$ with $P_i(y_j)=0$ in time $N\cdot\log(N)$ for preprocessing and $k\cdot n\cdot\log(N)$ for processing, if you can use space $N$ for preprocessing the $y_i$:

Preprocessing consists of generating (1) the list $E$ of all $j$ such that $y_j$ is even, and (2) a tree (or something even faster) that you can query in time $\log(N)$ for a given $y$ to get the list of all $j$ such that $y=y_j$.

Now loop over all $x_i$, adding to the result either (1) all indices $(i, e)$ for $e\in E$ if $x_i$ is even or (2) all $(i, j)$ with $y_j = -x_i\cdot 2^l \bmod 2^k$ for some $l\le k$ (using the precomputed tree) if $x_i$ is odd.

The reason why this gives the correct result is written in my first comment to your question.


AES Mix Columns and Shift Rows Why we use Mix Columns and Shift Rows in AES? FOr example, if i want implement an AES algorithm without Mix Columns and Shift Rows what is the difference in the ciphertext?

Without Mix Columns, every byte of the ciphertext would not depend on every byte of the plaintext, but only on the one byte at the same position. This would fully break AES, because we don't have an avalanche effect on the whole text anymore.

Without the Row shifting, every column of plaintext would only affect the same column of the ciphertext. This would break AES, too.

The question "Consequences of AES without any one of its operations" has some similarities with your question.


Repeated Encryption using same/different Encryption systems I would like to know if there are any security risks/gains from encrypting twice, i.e. $$\text{plaintext}\xrightarrow{encrypt}\text{intermediate text}\xrightarrow{encrypt}\text{ciphertext}.$$
I would like to know if there are known gains/risks to what I'm looking at. Perhaps certain pairs of systems are compatible while others are detrimental. Or perhaps some systems are obviously its own inverse (like the one-time pad).

I would like to hear your thoughts and if there is a survey paper, that would be great as well. Thanks!

I found this information which may be useful for you:

Is encrypting twice good or bad?
Does encrypting twice using the same block cipher produce a security weakness?
Is there any benefit to encrypting twice with pgp?

The general rule as far as I know, is that encrypting twice (regardless if its using the same cipher or not) is rarely ever going to produce positive side effects. In some cases it completely breaks the cipher:

For example in rot-13, encrypting the plaintext twice simply decrypts it:

E(E(pt)) = pt

I should note that rot-13 is not a cipher you should be using in practice, but I included it here just to show how certain ciphers will exhibit weaker strength when used twice.

Having said all this, it is generally safe to encrypt twice (i.e. wont make the cipher text weaker) as long as different keys are used during each step (see here for a better explanation).


About the Security of PCBC Encryption Mode We are designing an encrypted file system. We plan to use the PCBC (Plaintext Cipher Block Chaining) encryption mode for encryption. This is because we desire the feature ("small changes in the ciphertext would propagate indefinitely when decrypting") in PCBC.

However, to our best knowledge, PCBC is not a good choice from security and privacy perspective. It is a non-standard mode. It suffers from the adjacent swap attack. It has been cryptanalysis for message integrity.

So, I want to ask questions:

Can PCBC provide confidentiality on message? I just find some materials for breaking the integrity of PCBC, and the book Applied Cryptography saying "Although no one has figured out how to exploit this weakness, Kerberos version 5 switched to CBC mode after the flaw was discovered." I am not aware of anything discussing the confidentiality provided by PCBC.
For integrity, we plan to append a message hash with the content of message for PCBC encryption, instead of using an identical block. But from a cryptanalysis paper which says "In fact, even if the final plaintext block is a CRC computed as a function of all the previous plaintext blocks, an attack along similar lines is still probably possible.", it seems it is insecure even using hash for integrity checking. So I want to ask whether it is secure if I apply this hash in the FIRST block, or if you can give any better suggestions for integrity checking.
We want, (a) the decryption succeeds only when both the entire ciphertext and key are used; (b) if the ciphertext is not integrated, even getting the key, any useful information about the message cannot be extracted. Besides PCBC, do you have any better suggestions on choosing a standard and secure mode to achieve our goal?

PCBC is provably secure for confidentiality, assuming you use a random IV like with CBC. The attacks you mention are all on the integrity rather than confidentiality of PCBC.
No, you probably cannot construct secure authentication with PCBC and an unkeyed hash. For that you should instead use an actual MAC.
While PCBC propagates errors, it only propagates them towards the end of the message. It sounds like you would want the file to be completely undecryptable if modified. What would work is an all-or-nothing transform. Such schemes are typically unkeyed, but if you encrypt the result of the AONT, the whole thing needs to be correctly decrypted to reveal the plaintext.

So what I would recommend is:

Use an all-or-nothing transform on the plaintext.
Encrypt that using some standard authenticated encryption algorithm. Like AES-GCM or AES-CTR + HMAC.

Note that nonce uniqueness is critical with these encryption algorithms, especially the former where you lose both authentication and confidentiality if nonces are reused.


Sage Vs C++(with NTL) for implementing cryptosystems Is Sage a better alternative to C++(with NTL), for programming that involves math objects like polynomial rings in cryptosystems? I hear that Sage is an open source alternative to Magma. I have used Magma before for such programming and it was easier than using C++ because it had built in keywords for defining such structures and to work with them.

I also found that I can make use of the NTL lib in Sage. Is there any advantage to using C++ in terms of efficiency?

Sage can actually use NTL under the hood, so if you are more comfortable with sage (or that style of coding) and can implement things using the ntl wrapper, then there is likely no advantage to using NTL directly in C++.


How to calculate complexity of ElGamal cryptosystem? How to calculate time and space complexity of ElGamal encryption and decryption as there are two exponentiation operation during encryption and one during decryption? Here is my code for encryption:

for i=1:d
    pow=pow*g;
    y=pow%p;
for j=1:r
    pow1=pow1*g;
    C1=pow1*g;
    pow2=pow2*y;
    C2=(M*pow2)%p;

I think the first for loop will execute $O(d)$ times and second for loop will execute $O(r)$ so total time complexity of this is $O(d)+O(r)$ as it is not known which is bigger among $r$ and $d$.

Well, there are some major problems with your code.  Technically, the time estimate of your code is correct (that is, if you insert modulo operations when you update pow1 and pow2), however no one would actually use that algorithm to do ElGamal.

Lets hit some of the issues:

You use an $O(N)$ algorithm to compute $x^N$; in real usage, exponents are huge (perhaps around $2^{256}$), and an algorithm that takes $O(2^{256})$ iterations is utterly infeasible.  In practice, we use an algorithm that performs in $O(\log N)$ operations (modular multiplications), such as this one; this reduces the amount of work to something that can be implemented in practice.
On the less drastic, but still real issue: your code appears to assume that you have the private key $d$ when doing encryption; in practice, you'll start with the public key (which I believe in your code is $y$.
Also, while I'm listing nits, you also need to perform a modular reduction when you compute C1 as well.  Furthermore, you don't need to recompute C1 and C2 in the loop; you're interesting only in the final values, and so you can compute those after you have the final values of pow1 and pow2.

I'm sure there are other issues I missed.  However, the bottom line is that if you really want to compute the time complexity of ElGamal, you need to use the algorithm that we actually implement in practice.


Hash then Sign approaches I am learning about digital signature. For performance, we normally do hash then sign.

One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but under chosen message attack, this approach only has security level of $n/2$ because of birthday attack.

Another approach is to sign $H(m \oplus r)$ where $H(\cdot)$ is  a second-preimage resistant hash function and send $r$ along with the signature, but this is not efficient.

is there a different approach? can we do better on the second approach?

One approach is to sign $H(m)$ where $H(\cdot)$ is collision resistant, but this approach only has security level of $n/2$ because of birthday attack.

I would argue that this is not susceptible to the birthday attack but requires a second preimage attack. The adversary may be able to use the birthday attack to find two messages such that $H(m_1) = H(m_2)$ but this is not sufficient to break a digital signature. The adversary must also know the corresponding signature for either $m_1$ or $m_2$, and if it can generate these for arbitrary messages (as would be required for the birthday attack) then using a collision to forge a signature is moot (it can already generate arbitrary signatures).

Thus a reasonable assumption is the adversary can only intercept valid message / signature pairs (which is generally a fair model to use) and has to be able to find a collision for a fixed message (i.e. the message that was intercepted), which would require a second preimage attack. So I would argue that $H(m)$ is fine in this context (note that this is what schemes like ECDSA do).


Performing simple arithmetic operations on compressed, and both compressed and encrypted data We all know it is possible to perform addition and multiplication operations on encrypted data by means of homomorphic encryption methods. My questions are:

Is there any cryptosystem that is able to perform these operations on

compressed data
first-encrypted then-compressed data
first-compressed then-encrypted data

without any decryption or decompression?

Using generic homomorphic encryption the answer for all three is essentially yes. Although 3. in general is probably mainly of theoretical interest as it would be impractically slow.

For simply compressed data this is simple since compression should not do anything to hide the data. Just decompress, do the operation and possibly compress the result if needed.
For encrypted-then-compressed data this is also easy. Simply decompress and do the operation using the homomorphic encryption and compress the resulting ciphertext. However, you should note that ciphertexts rarely compress very well so it is not often you gain anything from doing this.
For compress-then-encrypt things get a little more difficult. However, in principle fully homomorphic encryption allows you to compute any function on a ciphertext. This includes decompression of your compression function. So what you could do is to run the decompression algorithm using the homomorphic encryption to get an encryption of the decompressed message, then apply any operation needed and finally apply the compress function using the homomorphic encryption to get an encryption of the compressed result. The problem here is that fully homomorphic encryption is really not practically efficient for anything but very simple computations. So doing compression and decompression would probably be completely impractical.


How to provide secure "vanity" bitcoin address service? Bitcoin addresses are RIPEMD-160 hashes of the public portion of a public/private ECDSA keypair (along with an abbreviated hash of the hash to provide a check code, as @pulpspy notes in a comment).  They are generally base-58-encoded.  See Address - Bitcoin

In Vanity bitcoin addresses: a new way to keep your CPU busy, user "ByteCoin" says he can create and sell "vanity" bitcoin addresses (like 1ByteCoinsUNJun4KL3HSt1NfFdXpzoRTy) for people.  Furthermore, he states he can use a handshake algorithm to do so without actually getting access to the associated private key (and thus without being able to spend bitcoins which are sent to the address).

What is a fast algorithm for creating vanity bitcoin addresses?  Can they in fact be created and sold in a secure way?

I don't believe that there's any way to generate the vanity hashes without iterating. In base 58, there's $\log_2(58) \approx 5.858$ bits per letter, so fixing 8 letters would need in average $58^8/2 = 2^{\log_2(58)·8}/2 \approx 2^{46}$ iterations. Note that Bitcoin addresses always start with a 1 by convention (this comes from the version field), and the next character in the base 58 representation is usually among "23456789ABCDEFGHJKLMNPQR" (not the full 58 character set), which halves the number of tries once more (if your wished starting character is in this set, otherwise it gets impossible). If you allow your vanity string to appear anywhere in the hash, you can divide this number again by 25, leading to $2^{40.5}$ iterations (on average) (which also are quite good parallelizable).

Also, the actual example he gave had an "s" rather than an "i" in the vanity "ByteCoins" part, so the odds of that are a bit greater (i.e. the needed time is even smaller).

However, you can do it securely (i.e. without the service gaining access to your private key):

Let the user generate a private key, $a$, and submit the corresponding public key, $a·B$ (where $B$ is the base point of the group). The service can then generate public keys as $a·B + x·B$, where $x$ is incremented to generate different public keys.

Actually, if you have $a·B +x·B$, then $a·B + (x+1)·B = (a·B + x·B)+B$, i.e. you need only one EC point addition (of the base point) and the necessary hashes for each try.

Then, by telling the user x, the user has private key $a+x$ with public key $(a+x)·B$ and $H((a+x)·B)$ has the required property, if the service did its job.


Security proof in the Malicious Model According to the above protocol(Efficient Secure Two-Pary Protocols-Hazay-Lindell-page 27), the authors proved the security of this protocol according to the two paragraphs below:

  We separately consider the case where P1 is corrupted and the case where P2 is corrupted. If P1 is corrupted, then the simulator S receives from A the bit that it sends to P2 in the protocol. This bit fully determines the input of P1 to the function and so S just sends it to the trusted party, thereby completing the simulation. In the case where P2 is corrupted, S sends input 1 to the trusted party and receives back an output bit b. By the observation above, b is the input of the honest P1 in the ideal model. Thus, the simulator S just hands A the bit x = b as the value that A expects to receive from the honest P1 in a real execution. It is immediate that the simulation here is perfect.

  We stress that the above works because P2 is the only party to receive output. If P1 also were to receive output, then S ’s simulation in the case of a corrupted P2 would not work. In order to see this, consider an adversary who corrupts P2, uses input y = 0 and outputs its view in the protocol, including the bit x that it receives from P1. In this case, S cannot send y = 1 to the trusted party because P1’s output would not be correctly distributed. Thus, it must end y = 0, in which case the view that it generates for A cannot always be correct because it does not know the input bit x of P1.

According to the above definition, I understand why it is important that the outputs in the real and ideal model should be indistinguishable, but I do not know why it is important that simulator S should know the input bit x of P1!!!
As I highlighted in the above authors' proof, why the simulator should know the input bit x; If it should know this, please explain to me how the above definition 2.3.1(in the mentioned book) tells us that the simulator should simulate the inputs of the party(P1 in the above protocol).

To sum up, is it important that the simulator simulates the inputs of the corrupted party? would you please explain it to me, according to the definition 2.3.1?

According to the definition 2.3.1, I know that the outputs pair's distribution of the honest and corrupted party in the ideal and real model should be indistinguishable, but it does not make sense to me that the simulation of parties' inputs is mandatory.

In order for a protocol to be secure, the output of any adversary must be simulatable, including that of an adversary that just outputs its input.

Moreover, note that in this case the protocol instructs that $P_1$ send its input bit $x$ to $P_2$, so in the case where $P_2$ is corrupted, it can output the input of $P_1$, so that must be simulatable as well.


Can zkSNARK or other zero-knowledge proofs be used to proof message authenticity without revealing private key? The situation:

Alice and Bob are exchanging messages encrypted by some known asymmetric encryption protocol. All their encrypted messages, as well as public keys are intercepted by Charlie.

Can Alice reveal decrypted messages to Charlie and provide him a zero-knowledge proof (for example zkSNARK) that deciphered text of the messages are indeed decrypted messages which he intercepted?

Can she do it without revealing her private key?

If so, can this method be used in any asymmetric cryptographic protocol without any special modifications to that protocol?

What about symmetric encryption, and passphrase revealing?

In a "fair trade" paper at Bitcoin workshop Financial Crypto 2016, a snark-proof was introduced to assure that a message (a Sudoku solution) could be properly decrypted.


If $G'(s)=G(s0^{|s|})$ and $G$ is a PRNG, is $G'$ necessarily a PRNG? I argue it is because there should be no more correlation between the outputs $G(s0^{|s|})$ than between the outputs $G(s)$. Thus we can say the $G'(s)$ is a PRNG that satisfies $|G'(s)| \geq 4|s|$. If we let $s' = s0^{|s|}$ and denote the set of all $s'$ by $S'$, then $s'$ should be chosen uniformly at random from $S'$. Since, as I stated there should be no correlation between $G'(s')$ for any $s'$, then effectively we are only increasing the expansion factor $l$.

Disagree? Please tell me why.

Suppose g is a PRNG. $\:$ Define G by the following pseudocode:

def G(w):
 m = length(w)
 n = ceiling(m/2)
 set x equal to the n leftmost bits of w
 set y equal to the m-n rightmost bits of w
 z = concatenate(g(x),y)
 output z

In this case, G is a PRNG and G' is not a PRNG.


SHA algorithim with different hash value I am new in hash cryptography. I am trying to build the sha256 hardware accelerator. I am thinking about using the different hash value to optimize the performance. I am trying to fetch custom hash initial value which already computed sometime ago. Does this approach valid and what problem i would get.

Thanks

I'll assume that you are thinking this way:

I am hashing a series of values that share the same prefix $X$ (which is a multiple of 64 bytes in length), that is, you are computing:

\begin{gather*}
\operatorname{SHA256}(X \mathbin\Vert A) \\
\operatorname{SHA256}(X \mathbin\Vert B) \\
\vdots \\
\operatorname{SHA256}(X \mathbin\Vert B)
\end{gather*}

and you are wondering "can I just compute the internal SHA256 state immediately after X, and then just use that as the "initial SHA256 state" when I process the strings $A, B, \dots, Z$?

Answer: yes, absolutely.  In fact, this is fairly common practice when these sorts of hashes are needed (which happens more than you'd expect; for example, when computing HMAC's).

  What problem I would get?

One thing you need to be careful is in the length field in the SHA-256 padding at the end; it needs to include the length of the entire message (including $X$), not just the message you just processed.


Block cipher not resistant to collisions If we have the following block cipher, $E(k,m)$,  which is a permutation, why is $f_2 (x,y)$ not collision resistant?

$$f_2(x, y) = E(x, x \oplus y)$$

First since E is an encryption algorithm, it has a Decryption counterpart, lets name it D.

From the correcntess equation we get that $E(x,D(x,c)) = c$ for every $x$. Then we can easily see that if

$$y= x \oplus D(x,c)$$
then
$$f_2(x,y) = E(x, y \oplus x) = E(x, x \oplus D(x,c) \oplus x) = E(x,D(x,c)) = c$$

Again this holds for every $x$. So we have just shown that a collision exists for all pairs of the form $\langle x, x \oplus D(x,c) \rangle$


How are the functions used in cryptographic hash functions chosen? I'm learning about cryptographic hash functions and I have some questions about the functions used in the compression function.

MD5 uses the following functions:

$f_{1}(B,C,D)=(B\wedge C)\lor(D\wedge \lnot B)$

$f_{2}(B,C,D)=(B\wedge D)\lor(C\wedge\lnot D)$

$f_{3}(B,C,D)=B\oplus C\oplus D$

$f_{4}(B,C,D)=C\oplus(B\lor\lnot D)$

SHA-1 uses these functions:

$f_{1}(B,C,D)=(B\wedge C)\lor(D\wedge \lnot B)$

$f_{2}(B,C,D)=B\oplus C\oplus D$

$f_{3}(B,C,D)=(B\wedge C)\lor(B\wedge D)\lor(C\wedge D)$

$f_{4}(B,C,D)=B\oplus C\oplus D$

SHA-2 uses these functions:

$f_{1}(B,C,D)=(B\wedge C)\lor(D\wedge \lnot B)$

$f_{2}(B,C,D)=(B\wedge C)\oplus(B\wedge D)\oplus(C\wedge D)$

I am wondering how these functions were chosen.

I know that XOR is very effective at mixing the bits of input, but I don't know why a function like $(B\wedge C)\oplus(B\wedge D)\oplus(C\wedge D)$ (SHA-2) is more effective than $(B\wedge C)\lor(B\wedge D)\lor(C\wedge D)$ (SHA-1).

Could someone clarify why certain functions perform better? And how the specific functions were chosen.

The functions considered are binary functions of 3 bits to 1 bit (extended to bit vectors, that is bitwise functions). There are $2^{(2^3)}=256$ such functions.

All the functions considered are balanced; that is, there is an equal number of input combinations for which the function outputs 0 and for which the function outputs 1. That reduces the number of functions to $8!/(4!)^2=70$.

Aggregating balanced functions identical within the $3!=6$ orders and the $2^3=8$ polarities of the $3$ inputs leaves only $6$ classes (see final section); keeping the lexicographically first function in each class:

    z   y   x           g0      g1      g2      g3      g4      g5
    0   0   0           0       0       0       0       0       0
    0   0   1           0       0       0       0       0       1
    0   1   0           0       0       0       0       1       1
    0   1   1           0       1       1       1       1       0
    1   0   0           1       0       1       1       1       1
    1   0   1           1       1       0       1       1       0
    1   1   0           1       1       1       1       0       0
    1   1   1           1       1       1       0       0       1

Of these, it is excluded g0 and g4 since at least one of their input has no influence on the output. The other four functions exhibit properties that tend to be good for diffusion:

for any of their input fixed to either polarity, the output is non-constant when we vary the other inputs;
any of their input influences the output for at least two of the four combinations of the other inputs.

These surviving functions are:

g1 Majority, used for $f_3$ of SHA-1 and $f_2$ of SHA-2 (which turn out to be identical)
g2 Choice, used for $f_1$ and $f_2$ of MD5, $f_1$ of SHA-1, $f_1$ of SHA-2; this function is also called Select, or Digital Multiplexer (input x being 1 or 0 chooses which of y or z is the output);
g3, used (within order and inversion of inputs) for $f_4$ of MD5; as noted in comment, that function $(x\wedge y)\oplus z$ is also the Toffoli gate's third output;
g5 Parity, used for $f_3$ of MD5, $f_2$ and $f_4$ of SHA-1.

Addition per comment: g1 and g2 additionally have the property that any of their input influences the output for at most three of the four combinations of the other inputs; or, in other words, are not fully linear w.r.t. any of their input. This is desirable in some sense, as too much linearity opens to some differential attacks. This might be why g1 and g2 are preferred to g3 and g5 in SHA-2.

A comment asks for the derivation of classes of balanced functions of 3 bits to 1 identical within order and polarity of inputs. We'll represent a function by an 8-bit value $b_{000}\,b_{001}\,b_{010}\,b_{011}\,b_{100}\,b_{101}\,b_{110}\,b_{111}$ giving the output $b_{zyx}$ for the 8 combinations of the 3 inputs $z\,y\,x$.

Balanced functions have $b_{000}+b_{001}+b_{010}+b_{011}+b_{100}+b_{101}+b_{110}+b_{111}=4$. We scan them in lexicographic order (equivalently, numerical order when using big-endian convention); if not excluded, that's the function representative of a new class, and we exclude the functions obtainable from that by permutation of inputs, or changing the polarity of inputs. We can do this by considering any of the 6 following transformations applied, or not (there's some redundancy in applying the 64 combinations and many functions are excluded multiple times, but it does not harm):

turning output to $b_{000}\,b_{010}\,b_{001}\,b_{011}\,b_{100}\,b_{110}\,b_{101}\,b_{111}$ (exchanging $x$ and $y$)
turning output to $b_{000}\,b_{001}\,b_{100}\,b_{101}\,b_{010}\,b_{011}\,b_{110}\,b_{111}$ (exchanging $y$ and $z$)
turning output to $b_{000}\,b_{100}\,b_{010}\,b_{110}\,b_{001}\,b_{101}\,b_{011}\,b_{111}$ (exchanging $z$ and $x$)
turning output to $b_{001}\,b_{000}\,b_{011}\,b_{010}\,b_{101}\,b_{100}\,b_{111}\,b_{110}$ (complementing $x$)
turning output to $b_{010}\,b_{011}\,b_{000}\,b_{001}\,b_{110}\,b_{111}\,b_{100}\,b_{101}$ (complementing $y$)
turning output to $b_{100}\,b_{101}\,b_{110}\,b_{111}\,b_{000}\,b_{001}\,b_{010}\,b_{011}$ (complementing $z$)

We first get 00001111 = g0, and exclude 00110011, 01010101, 10101010, 11001100, 11110000; then get 00010111 = g1, and exclude 00101011, 01001101, 01110001, 10001110, 10110010, 11010100, 11101000; and so on. In the end, there are only 6 classes.


Is Convergent Encryption really secure? Recently a company called Bitcasa demonstrated a product of cloud storage. they indicated that they would use "Convergent Encryption" to secure your data and de-duplicate, essentially one copy of the same file between users.

From what I can read on a university paper about Secure Data Duplication which makes mention of "Convergent Encryption" and assuming this is what this is referring too.

My question is, what security implications of using this technology and is it truly secure that you cannot get the key based on chunk data being used to generate different keys between users.

Reference interview on Washington post

If it's implemented properly, it is as secure as any other form of encryption in preventing those who don't know the data from obtaining it from the encrypted data. However, it does have one fundamental limitation that, so far as we know, is inherent in the technology -- Anyone who has the same file you have can potentially prove that you have that file.

The general way such algorithms work is as follows:

The object to be encrypted is validated to ensure it is suitable for this type of encryption. This generally means, at a minimum, the the file is sufficiently long. (There is no point in encrypting, say, 3 bytes this way. Someone could trivially encrypt every 3-byte combination to create a reversing table.)
Some kind of hash of the decrypted data is created. Usually a specialized function just for this purpose is used, not a generic one like SHA-1. (For example, HMAC-SHA1 can be used with a specially-selected HMAC key not used for any other purpose.)
This hash is called the 'key'. The data is encrypted with the key (using any symmetric encryption function such as AES-CBC).
The encrypted data is then hashed (a standard hash function can be used for this purpose). This hash is called the 'locator'.
The client sends the locator to the server to store the data. If the server already has the data, it can increment the reference count if desired. If the server does not, the client uploads it. The client need not send the key to the server. (The server can validate the locator without knowing the key simply by checking the hash of the encrypted data.)
A client who needs access to this data stores the key and the locator. They send the locator to the server so the server can lookup the data for them, then they decrypt it with the key. This function is 100% deterministic, so any clients encrypting the same data will generate the same key, locator, and encrypted data.


RSA calculate public exponent Suppose I have two messages $m_1$ and $m_2$ as well as $c_1$ and $n$. It's standard RSA so $c_1 = m_1^e \ mod \ n$, $c_2 = m_2^e \ mod \ n$. Further assume the only information we have about e is that it is smaller than $2^{2048}$. Is there a way to find it? (According to this it is not)

No, it is not possible.

If it were, then RSA would be insecure; the same way to recover $e$ from $m_1, m_1^e \bmod n$ would be able to recover the private key $d$ from $c_1, c_1^d \bmod n$ (as that's the same problem, only using different symbols).


Affine Cipher Keys that map plaintext to a given ciphertext We first need to show that for each pair of plaintext-ciphertext
  letters ( x,y ), there are exactly 12 keys that encrypt x to y .  For
  each choice of a , the key ( a,y − ax ) encrypts the plaintext letter
  x to the ciphertext letter y , since ax
  + ( y − ax ) = y .  There are twelve possible choices for a so there are exactly twelve keys that map a given plaintext letter to a given
  ciphertext letter.

This is an easy question, I'm just trying to make sense of this statement found on page three here www.maths.uq.edu.au/courses/MATH3302/2010/files/cryptotute2.pdf

In the affine cipher how is their only 12 keys that map a given plaintext x to a given ciphertext y? I learned that the affinecipher has 286 nontrivial keys. So if thats the case how can only 12 of them map a given plaintext x to a given ciphertext y.

Assuming plaintext and ciphertext alphabets are $U=\{0,\ldots,25\}$, taken to be the ring of integers modulo 26, and the keyspace is $U^2$ with $$(a,b)\in U^2,$$ it is clear that for plaintext $x=2t$ corresponding to even numbers,  $(a,b)$ and $(a+13,b)$ give the same $y$ violating the invertibility of the encryption. Moreover, if $b=0$ $a$ can't be zero for the same reason.

So we allow all $b$ but only $12$ nonzero $a$'s and can choose either $a$ or $a+13$ as $a$ ranges over $\{1,2,\ldots,12\}$.


Publicly Verifiable Authenticator I am working on a Block Storage system, where I have the need to encrypt and authenticate blocks by a client, but also want the server to be able to detect bit corruption while minimizing the work done on the data. The storage blocks are roughly 1MB segments.

One option is to let the client use a AE(AD) cipher (like AES/GCM) and afterwards add a strong checksum. Since AES/GCM is not yet the most optimized cipher (in my Java world), an alternative would be to use a more traditional encrypt-then-HMAC. However, with a normal HMAC, this could not serve as a publicly verifiable checksum. And calculating both, a HMAC and a checksum would double the amount of work which needs to be done (over the message). What about only calculating the checksum over the message, and using a HMAC on this reduced data set?

encrypted = AESCBC(IV, plaintext-1MB)
checksum = SHA224(ID | IV | len | encrypted)
sig = HMAC(ID | len | checksum)
message = ID | IV | len | encrypted | checksum | sig

In this case I calculate a publicly verifiable checksum over the data (so I can detect corruption on the server) and only the client could check in addition to that the HMAC authenticator added. The HMAC does not need to run over all the encrypted data, but uses the checksum as a shortcut. The ID is unique for each segment.

In my case the protocol can't be used as an anonymous oracle and the plaintext length can not be extended boundlessly, however a hash which is more resistant against extension attacks is intentionally used.

I haven't seen much analysis on using ordinary hashes for content authentication. Can anyone can give me a pointer on whether this is safe? (I haven't yet done performance analysis yet; I might simply go with AES/GCM+SHA if that is fast enough). Or is there a more standard construction for generating a publicly verifiable and authenticating tag?

I haven't seen much analysis on using ordinary hashes for content authentication. Can anyone can give me a pointer on whether this is safe?

With good choice of primitives it is. Public key signatures use a hash function in a similar way to identify the message signed.

However, where a MAC only needs what amounts to second preimage resistance, a hash function also typically needs collision resistance, since an attacker can calculate an arbitrary amount on their own. (This is why SHA-1 is being deprecated in signatures even though there's no indication it isn't preimage resistant.)

HMAC is also stronger than the hash function it uses. So while SHA-224 is strong, you will have lower security with it than with HMAC-SHA-2. Technically, it may mean you don't even have 128-bit security – "only" 112-bit.

You don't actually need to use the checksum itself in the HMAC. You can instead use a full SHA-256 (or SHA-512, which may be faster). If you want to truncate – length extension attacks aren't an issue because of the HMAC – only truncate it when writing the checksum, but not when calculating the HMAC. Assuming you don't need as much confidence when detecting corruption, you could even truncate the checksum to only a few bytes and save some space.

I.e.

hash = SHA-NNN(ID | IV | len | encrypted)
checksum = truncate(hash)
sig = HMAC(ID | len | hash)
message = ID | IV | len | encrypted | checksum | sig

(Having ID and len in the HMAC seems unnecessary, but doesn't hurt.)


How often do I need to rotate AES 256 keys I'm trying to design a protocol for a resource constrained environment. The device has to communicate with a server through an insecure node. My plan is to use AES 256 end to end for all communications. From what I understand, keys carry a risk factor that increases with use and time.

From reading this post: How much data can I encrypt with AES before I need to change the key in CBC mode? there is an equation for determining the maximum amount of data it is safe to send given an acceptable risk factor.

My question is two fold:

Is it necessary to factor time into this equation for devices that communicate infrequently with the same key?
How does one determine an acceptable risk factor?

Is it necessary to factor time into this equation for devices that communicate infrequently with the same key?

No. Time would only matter for attacks that require a lot of processing by the attacker. Basically, key recovery attacks, through either brute force (impossible with AES key size) or maybe weaknesses in the cipher (even known related key attacks aren't feasible either).

In comparison, the attack here only needs to store all the used ciphertext in a data structure so that duplicates are detected. If you use a hash table, that's $O(1)$ time per block.

  How does one determine an acceptable risk factor?

You have to understand the risk first.

The attack here is related to the block size of AES, i.e. 128 bits (even with your 256-bit keys the block size is 128). The risk factor essentially indicates the probability that a duplicate would be observed with a PRF after that many blocks. The advantage gained by the adversary is some information about the plaintext of some encrypted blocks. It does not allow key recovery.

What it means depends on the cipher mode used. For example:

If you are using CBC, like in the linked question, the risk is that two blocks of ciphertext are equal, leaking the xor of the corresponding plaintext blocks.
With CFB, if two ciphertext blocks are equal, it leaks the xor of the blocks following them.
With CTR, if counters remain unique, the risk is that two ciphertext blocks are equal. Here it only leaks the fact that the two plaintext blocks are different.
With OFB, a collision results in the rest of the key stream being equal, leaking the xor of the rest of the messages.

You have to decide how important it is that the attacker not learn that information.


The Gimli non-linear operator NORX replaces all the additions of the Chacha20 quarter-round function with the non-linear $x \oplus y \oplus ((x \land y) \ll 1)$ operation. Gimli supposedly improves on it with $x \oplus y \oplus ((z \land y) \ll 1)$, adding a third input $z$ because as they claim it removes the need for the additional xor that NORX has. In addition the Gimli paper says "Gimli varies the 1-bit shift distance, improving diffusion compared to NORX and possibly even compared to ARX".
So we end up with
$$
  a \gets z \oplus y        \oplus ((x \land y) \ll 3) \\
  b \gets y \oplus x        \oplus ((x \lor z) \ll 1) \\
  c \gets x \oplus (z \ll 1) \oplus ((y \land z) \ll 2)
$$

My issue with this is that nowhere in the Gimli specification (as far as I could tell anyway) it explains why they did $z \ll 1$ or why they used bitwise or in $x \lor z$ nor does it explain the exact parameter choices for the non-linear operation (why $a \gets z \oplus y        \oplus ((x \land y) \ll 3)$ rather than $a \gets z \oplus x        \oplus ((z \land y) \ll 3)$ for example).

Is there any justification for these changes that I might have missed?

a bit late, if I had been pinged on this, I could have answered earlier.

$x \vee z$ was chosen for the following reason:

$a \wedge b$ is biased towards 0. As a result if we only used $\wedge$ the linear weight of the equation would have a strong bias towards 0.
As $a \vee b$ is biased towards 1, this aims to compensate.

The $z ≪ 1$ instead of just $z$ in the equation is necessary to ensure that this is a permutation, otherwise the equations do not have an inverse and we really wanted a permutation and not a transformation.

As for the why $⊕⊕((∧)≪3)$, if you remove the $x \leftrightarrow z$ swap, you realize that the shape of the expression is:
$x \leftarrow x \oplus z' \oplus EXPR$
$y \leftarrow y \oplus x \oplus EXPR$
$z \leftarrow z \oplus y \oplus EXPR$
We already discussed why $z'$ is $z ≪ 1$, now if you look at $EXPR$ you notice that in all cases, the destination is not included in the non-linear binary expression, as a result, this increase the complexity of linear trails as you have to track more variables.


Hash functions and polynomial division I understand that a CRC verifies data integrity by producing a checksum, which is the result of polynomial long division. I've heard hash values referred to as hash checksums, so my question is whether hash functions use some sort of polynomial division as well? I know they break the data up into block ciphers, so my guess would be that the hash functions create some relationship between the polynomial check value and how it's divided into the different blocks. Can someone let me know if I'm way off base here? I'm a crypto newbie so apologies if I'm way off.

I've heard hash values referred to as hash checksums, so my question is whether hash functions use some sort of polynomial division as well?

No, they do not.

Actually, the original meaning of "checksum" has nothing to do with polynomial division at all; instead, it was just a simple sum used to detect errors.  The usage has been generalized to mean anything added to the data to detect random errors; a CRC does that, and a hash of the data could be used as well.

These both work well about detecting random errors.  However, since we're in crypto stack exchange, we also get to worry about deliberate changes made by an intelligent attacker; in that case, neither CRCs nor hashes help (as the attacker can easily compute the CRC/hash of the modified data).  If this is the problem space you're in, you need to use either a Message Authentication Code or a Signature; they both depend on secret information that the attacker does not know.


How long does it take to crack RSA 1024 with a PC? Using an Intel Core i5 CPU, how long does it take to crack RSA using a key size of 1024 bit (generated using a secure key pair generation function)?

Suppose for instance that we have thousands of zombies or a big network of computers. To calculate all the combinations or possibilities, can we distribute the process through a big network of computers?

RSA-768 took 2000 years of 2.2Ghz single-core Opteron from the year 2009.

DJB et al wrote in 2013 (see page 30) (see also: 29C3: FactHacks (EN); slide 87/112; about 10 minutes) that RSA-1024 would take $2^{70}$ differences with $2^{24}$ per machine per second in 2009, so 2 million years. Hardware improved since then, and GNFS can use GPUs, so maybe better, but about a million years I guess.

Absolutely the computation can be parallelized to use many devices, for example to use a botnet, which is what DJB recommends. Whether one can have a botnet with a million devices with strong CPU/GPU that uses up a lot of power and not get noticed for a year, is another matter entirely.


Requiring a "supervisor" key pair and a "user" key pair to decrypt multiple-recipient messages I've been toying with some encryption scenarios recently. One of the hard ones I came across is a multi-party system.

So we have

Bob -- The person who sends the message (and knows it's recipients)
Jim -- The person who supervises who is capable of decrypting the message(but can not decrypt the message himself)
Alice -- The person who wants to receive the message
Mark -- The person who also wanted to receive the message, but after Bob sent the message his private key was compromised

For example sake, Bob must post his encrypted message on a public message board. Ideally, Alice and Mark would see the message and know it's intended for them, but they can't decrypt it by themselves. They must ask Jim to apply his decryption skills on the public data first. Jim trusts who is asking for the message because he knows their public keys(and asks for a dynamic signed piece of data or some such). Of course though, Jim won't apply his magic for Mark because he was notified that Mark had been compromised. So, Mark is left in the dark with an undecipherable message

Also, Jim is minimally trustable. So, if Jim wanted to hand the message to some untrusted party, it'd still be fairly useless, unless they themselves learned of one of it's intended recipient's private key as well.

I'm trying to work out the best way to actually do this. Here is one idea:

Bob encrypts his message with a symmetric algorithm.
Bob encrypts the symmetric key against Alice's and Mark's public key using his private key (two separate "key messages" are thus made)
Finally Bob encrypts both of the key-messages against Jim's public key using his private key

I think this would work. However, I have some concerns

I'm double-encrypting things, which sounds like trouble
I'd have to be encrypting basically the same piece of data against two different keys. Does this leave me vulnerable to cryptoanalysis? What about padding?

Ideally, the first algorithms that came to mind for symmetric encryption is AES. For asymmetric encryption, I was thinking RSA. Is there a better choice?

Is there any better way of managing such a scenario where you have a "supervisor" which mitigates the risks of a private-key compromise for messages sent to multiple recipients?

Have you considered using Shamir's Secret Sharing algorithm?

First, Bob encrypts the message with a symmetric algorithm.  Then, he divides the secret key into four parts using SSA such that it requires three parts to decrypt (a $(3,4)$ threshold).  Bob then distributes one part each to Alice and Mark, and two parts to Jim.

When Alice wants to decrypt, she needs has to have both of Jim's parts plus her part.  If Mark wants to decrypt, he similarly needs both of Jim's parts plus his part.

Alice and Mark cannot collude to cut Jim out of the middle, because they have only two parts between them, and decryption requires three.  And because Jim has only two parts himself, he cannot decrypt the message unless Alice or Mark shares their part it with him.

Finally, Jim can withhold his parts from anyone he no longer trusts.


How to do a frequency analysis? I don't quite get frequency analysis..

I see percentages and else, when I tried to do a frequency analysis on a pictogram cipher, the only letter I was able to analyze was the letter A.

Any step-by-step tutorial on this?

I did count, but why are there decimal numbers for certain frequencies?

Like this picture, downloaded from the Wikipedia page.

Do mathematics have anything to do in this, such as dividing?

Any course material or book with a title like introduction to cryptography (or similar) will address this topic and provide examples. Alternatives are: Frequency analysis and substitution cipher.

The basic steps are:

Decide on what you want to count: Usually first you look at single symbols first. And then bigrams. But there are other possibilities (bascially any pattern you can imagine)
Count the appearances
Put them into relation of the possible maximum count. That's a frequency.

The expression "pictogram cipher" doesn't say anything about the actual encryption mechanism. Using arbitrary symbols or pictures instead of numbers is just a form of encoding, and pretty much irrelevant, as long as you can distinguish them somehow.

However, in general we assume that it is known what kind of cipher we have. And based on that, there are different ways to do frequency analysis. Under the tag classical-cipher you can find a lot of questions to this topic. For example Possible ways to crack simple hand ciphers might be interesting to read.


Is there any theory to measures and determine the strength of an encryption protocol? To determine the strength of an encryption protocol, there are elements like key size, Strength of an algorithm, Performance of an algorithm or etc, I have studied these topics but I could not find the answer I am looking for.
Is there any mathematical explanation in this topic, like a "theory of everything" that makes it possible for every encryption protocol.

Is there any mathematical explanation in this topic, like a "theory of everything" that makes it possible for every encryption protocol.

Sure. It's called concrete security proofs.

With these, you define a model that seems reasonable for your attacker (usually someone already did this), then you go ahead and model your protocol as close as possible to reality as possible while staying compatible with the definitional framework.
Finally you show that the protocol satisfies the definition.
As this usually involves the kind of implication "if you can break the security of the protocol, you can break <insert assumption>" you get security results of the form

  For any efficient adversary $\mathcal A$ against AKE security of
  Example, there exists adversaries $\mathcal B_1,\mathcal B_2$ such
  that

  $$\mathbf{Adv}^{\text{AKE}}_{\text{Example}}(\mathcal A)\leq \mathbf{Adv}^{\text{CCA}}_{E}(\mathcal
 B_1)+3\mathbf{Adv}^{\text{EUF-CMA}}_{S}(\mathcal B_2)$$

for some made-up protocol "Example" that achieves "Authenticated Key Exchange" security if the used encryption scheme is CCA-secure and the used signature scheme is EUF-CMA secure.

You can then research the security bounds for the advantages of your favourite encryption scheme and your favourite signature scheme and insert the expressions to come up with a bound on the security of the protocol.


How to compute the attacker's probability? Given a random bit string $R=r_1r_2\cdots r_n$, let us encrypt each bit $c_i=E(r_i,k_i)$ where $k_i$ is taken from the stream of encryption keys. Suppose that an attacker can guess the correct $r_i$ from $c_i$ with probability $p>1/2$. Then, the probability that the attacker can recover correct $R$ from $C=(c_1,\cdots,c_n)$ is $p^n$.

Now, suppose that we use the following encryption diagram (given below).  Is the attacker's probability of recovering the correct $R$ from $C'=(c'_1,\cdots,c'_n)$ still $p^n$?

Let $r'_i=r_1\oplus r_2\oplus\cdots\oplus r_{i-1}\oplus r_i$.
Let $c'_i=E(r'_i,k_i)$.

The probability of recovering the string $R$ is the same with both of your scheme. The reason is that your second scheme can be separated into two independent parts. In the first part, you just transform $R$ into $R'$ using only your step 1 (this is invertible and from $R'$ you can recover $R$).

In the second part, you just encrypt $R'$ with the previous scheme. As a consequence, the probability of recovering $R'$ is the same as in the first scheme and due to the invertibility of the first part, this is equivalent to recovering $R$.

I am wondering about why you want to use this scheme. Did you consider (in your context) attacks that would approximate $R$ instead of predicting it exactly ? I ask this because this would greatly increase the probability of success.


How do I find out whether a message in CBC has padding? When a program is decrypting a message encrypted by CBC mode, what does it find out, whether the last bytes of the last block is part of the padding or part of the plaintext?

Example: Use CBC mode with 4 Byte blocksize and encrypt the following two messages:

m1 = ABCDEF
m2 = ABCDEF22

M1 gets padding and will be "ABCDEF22". How do I find out, whether the original plaintext was ABCDEF, or ABCDEF22?

Actually, that is depending on the padding applied. Maybe there is no padding at all. The implementation defines the padding applied. Check the code or documentation!
The last 22, at first, indicates that might be PKCS#5 or PKCS#7 since PKCS#7 most common with CBC implementations. While PKCS#5 is limited to 8 bytes like DES, PKCS#7 works from 1 to 256 bytes. PKCS#7 appends octets like

For such algorithms, the method shall be to pad the input at the trailing end with $k - (l \bmod k)$ octets all having value $k - (l \bmod k)$, where $l$ is the length of the input.

However, that is 0x02,0x02. The 2s in your last 22 is the character 2 that is in hex 0x32.
To see that has PKCS#7 padding check the last octet and maker sure that the value $k$ of the last octet repeat $k$-times. Example for a 16-byte block cipher where each position is a byte. 1 means 0x01, 2 means 0x02, etc.
xxxxxxxxxxxxxxx1
xxxxxxxxxxxxxx22
xxxxxxxxxxxxx333
...
xFFFFFFFFFFFFFFF
xxxxxxxxxxxxxxxx full block append a new block that contains 16 times 0x10

To see other padding candidates see Padding in Wikipedia


How is a ciphertext encrypted using random numbers decrypted using a symmetric key algorithm We use true random number generators as a source of keys for encryption. What I can not wrap my head around is: How is this cipher text decrypted in case of symmetric key algorithm as we need the same random number to decrypt the cipher text.

What I could guess is:

Is this random number used as a session key and transmitted using any asymmetric key algorithm?
Are PRNGs and true random number generators used as a seed?

Usually the symmetric key is exchanged with Public-key cryptography (which is asymmetric).

Quote from Wikipedia:

  Because of the computational complexity of asymmetric encryption, it is usually used only for small blocks of data, typically the transfer of a symmetric encryption key (e.g. a session key). This symmetric key is then used to encrypt the rest of the potentially long message sequence. The symmetric encryption/decryption is based on simpler algorithms and is much faster.

Concerning random-number-generators in cryptography:

Cryptographically secure pseudorandom number generators are typically used when the design of a cryptographic scheme needs a random number. These include i.e:

One-time pad
Elliptic Curve Digital Signature Algorithm
Cryptographic nonce


Which encodings have |encoding key| >> |decoding key|? I'm looking for an encoding scheme that requires a very large encoding key E (>10MB)  and suffices with a relatively small decoding key D (<4kB). One should be able to prove some lower bound on |E| using only knowledge about the scheme, the encoded message and D.

It would be great if the proposed scheme has computationally efficient primitives.

EDIT: A use case for this can be to encourage voluntary disposal of E after encoding a smallish (~1MB) file.
EDIT 2: Ideally, it should not be possible to infer E from D.

Generate a random 2048-bit RSA key.
Generate a random RC4 key.
Seed an RC4 engine with the key generated in step 2. Throw away the first 128 bytes. Output 10MB of data from the RC4 engine (XOR with 0 or don't XOR at all).
E consists of the corresponding public key to the private key generated in step 1 and the first 10MB of data from the RC4 engine in step 3.
D consists of the RSA public key and the RC4 key.
Encryption proceeds by XORing the data to be encrypted (padded to a multiple of 10MB) with the 10MB RC4 output and then encrypting that with the RSA public key.
Decryption proceeds by regenerating the 10MB of RC4 data from the seed and reversing the encryption process.

There are numerous variations on this scheme. The idea is to make the 10MB pseudo-random (so the decryptors don't have to store it) and don't give anyone else the key needed to generate it, so they have to store the full 10MB. (You could also just pad the data up to 10MB and XOR the final output with the 10MB of data. Same idea.)


Are there security issues with adding plaintext length to TLS packets? I have quite a big problem, because of a software implementation of TLS I had to adapt I had to create something which is now biting me.
It all comes down to this: I need to know the length of the plaintext when I want to decrypt it and the length of the ciphertext when I want to encrypt it. For the 2nd one I've made a (not so nice) workaround.
I have a workaround for the first problem, simply using TLS to encrypt the plaintext and then add a few bytes for the plaintext length and send this over.
So my question is: how big is the security risk if an attacker can see the plaintext length if i would send it in the clear together with the TLS protocol packet?
(more details here)

Not so high, the size of the plaintext should be known in advance. For all the stream cipher based cipher suites, including the ones with the newer authenticated ciphers the size of the plaintext can be directly derived from the ciphertext.

CBC mode only hides the plaintext length in the bounds of the block size - if that. You can however possibly abuse this to create a covert channel. Furthermore, you would be working out of spec - your scheme would not be compatible with TLS. You would only save up to the block size in bytes in your implementation at most, so the returns would be very small.

You may be better off choosing a cipher suite that uses a stream cipher instead. In that case the plaintext and ciphertext have the same length. Currently however that means RC4 or GCM mode encryption in TLS 1.2. In case of GCM you may have to subtract the size of the tag from your calculations of course.


How to generate a random polynomial of degree $m$? I am trying to do a homework in which implement a variation of this paper and I don't know how to generate a polynomial of degree $m-1$. This polynomial is used to generate the $y_0$ and $y_1$ values.

I am using JCE for doing the coding. What do I need to do to achieve this?

I assume you're referring to section 5 of the paper you linked to, which reads:

5 An instance using polynomials
In this section, we describe an instance of the technique of
Section 4 using Shamir's secret sharing scheme [25]. In this
scheme, $\mathrm{hpwd}_a$ is shared by choosing a random polynomial
$f_a \in \mathbb Z_q[x]$ of degree $m - 1$ such that $f_a(0) = \mathrm{hpwd}_a$. The
shares are points on this polynomial. We present the method
in two steps, by first describing a simpler variation and then
extending it in Section 5.4 to be more secure against an
offline attack.

To choose a random polynomial $f(x) = c_k x^k + \dotsb + c_1 x + c_0$ of degree $k$ in the polynomial ring $\mathbb Z_q[x]$ simply means choosing $k+1$ random coefficients $c_0, c_1, \dotsb, c_k$ uniformly from the finite field $\mathbb Z_q$.  However, the additional constraint that $f(0) = c_0$ should take a particular fixed value means that, in fact, only the $k$ coefficients $c_1, \dotsc, c_k$ can be chosen randomly, while the constant coefficient $c_0$ is fixed.
(Note that, using this procedure, there's a one in $q$ chance that $f$ will actually be of a degree lower than $k$, because $c_k = 0$ by chance.  However, in the context of Shamir's secret sharing that's exactly what you want: the polynomial really should be randomly chosen from the set of polynomials of degree at most $k$ in $\mathbb Z_q[x]$ whose lowest coefficient has the desired secret value.)

Ps. A note on notation: $\mathbb Z_q$ here denotes the ring of integers modulo $q$, which is a field if and only if $q$ is prime.  However, Shamir's secret sharing actually works in any finite field $\mathbb F_q$, which exist for all prime powers $q = p^n$.  In particular, the characteristic-2 fields $\mathbb F_{2^n}$ are often convenient to work in, since their elements correspond naturally with $n$-bit bitstrings.  The downside, of course, is that multiplication in finite fields of non-prime order is slightly trickier to implement (or, rather, that you're somewhat less likely to find an existing built-in implementation of it). For more details, see e.g. Galois fields in cryptography.


CMAC for messages shorter than 128bit RFC4493 describes the generation of AES-CMAC and padding for messages with length > sizeof(aes128_key). However I need to generate the CMAC for a series of messages shorter than 16 byte.

So I'd like to ask if it is viable to:

Pad M0 with 0 up to 16 bytes
Pad M_last with the proposed padding (first bit 1, others 0)

As the message always will be M0 || M1 with a fixed size, is the subkey generation still required? Or can it be replaced by a fixed value?

Kind regards

AES-CMAC is defined for messages of any length.

The algorithm can be reduced to the following, if you have non-empty messages smaller than the block size:

(K1,K2) := Generate_Subkey(K);
n := ceil(len/const_Bsize);
M_last := padding(M_n) XOR K2;
X := const_Zero;
Y := M_last XOR X;
T := AES-128(K,Y);
return T;

You don't need to derive some non-standard way of padding your messages.

You should note that len/const_Bsize in the RFC is floating point division. The C implementation does this little trick to not use floating point division: n = (length+15) / 16;.

Shameless plug: I have a JavaScript implementation of AES-CMAC that you can play around in: Online AES-CMAC calculator


Hardness assumption: Extracting $g^y$ from $g^x, g^{x+y}$? I am new in cryptography and I wonder whether there is any hardness assumption in cryptography where computation of $g^y$ is hard given $g^x, g^{x+y}$ ($g$ is group generator, $x$ is selected randomly while no restriction is on $y$).

No, this is (nearly) never hard.

To recover $g^y$ from $g^x,g^{x+y}$ all you need is a fast (ie polynomial-time) group operation (which is a given, because otherwise you'd have a hard time to come up with either value) and the ability to inverse fast (ie in polynomial time).

This follows from: $$g^y=g^{x+y-x}=g^{x+y}\cdot g^{-x}=g^{x+y}\cdot (g^x)^{-1}$$, where on the right you only have known values and fast operations and on the left you have your desired value.

Also note:

If you know the group order $q$, you can efficiently inverse as $a^{q-1}=a^{-1}$.
If you don't know the group order you likely still can invert quickly. For example you can still quickly find $a^{-1}\bmod n$ for composite $n$ (as is the case for RSA).
Inverting (finding $b$ such that $g^x\cdot b=1$) is not the same as computing the discrete logarithm (finding $b$ such that $g^b=X$).


Why did replicated secret sharing use correlated randomness? When I read the AFL16 paper by Araki, each party's share is adding a correlated randomness, like  r1 = (a1b1−x1y1+α)/3 ,  r2 = (a2b2−x2y2+β)/3, r3 = (a3b3−x3y3+γ)/3 with α+β+γ=0, and use AES to generate that.
Also in the ABY3 paper they add the similiar randomness to each party in arithmetic operations.
I wonder why this is necessary. I notice that even without that randomness, the protocol is still correct. Did this miss any security guarantee?
The full name of the paper is "High-Throughput Semi-Honest Secure Three-Party
Computation with an Honest Majority", can anybody help to explain it?

The multiplication is indeed correct without adding the randomness, but it is no longer private (i.e., it leaks information). By adding the correlated randomness, it ensures that what any single party sees during the computation is just uniformly distributed and reveals nothing.


What algorithm could/should be used to encrypt files for storage on untrusted servers? I need an encryption algorithm that works fast on large files and doesn't increase the file size. It should use a key to encrypt/decrypt data. The files will be sent using REST and over HTTPS, but a good encryption/decryption method with a key is mandatory (to be used in a website).

The files will be saved on a 3rd party servers, and although the files are sent through HTTPS, they must be stored encrypted on the remote servers and decrypted when retrieved. The key will not be distributed. The key will be stored on my trusted server, as it is also the receiver! I want to encrypt the file, put it on the 3rd party server, then when I need it I can retrieve it and decrypt it.

The question still lacks detail, so this answer will be equally vague and hand-waving.

Any modern cipher exceeds consumer disk/network IO speeds by a significant margin, you can pair any modern block cipher (AES is probably the best choice here) with a streaming mode of operation such that the file size is left intact, such as CTR or CFB. However, you still need integrity on top, so you also want a fast and strong hash function to use as a HMAC (or use AES in an authentication-capable mode, but such modes are not very widespread yet). A good hash function would be SHA256 (reasonably fast).

There is no "best" algorithm, there are only those that meet your needs and those that don't. Your needs are security and speed - choose accordingly. I gave some fairly generic suggestions above.

Of course, the better choice would still be to use something that's already production-ready, such as OpenSSL. This way you don't need to implement it yourself and just have to learn the API and make a few function calls at either end of your network sockets, and you don't have to worry about security problems (or at least, not as much).

Again, you should not be implementing cryptography if you don't know what you are doing, so your comments such as "I wish I could know that by my self" are worrying to say the least...


Other than brute force, are there any attacks on Threefish-512 using only a single known plaintext block? As per title, other than brute force, are there any attacks on Threefish-512 using only a single plaintext block? Are there any attacks like this in any other cipher?

According to Schneier,
there is an attack on 42 rounds of ThreeFish-512, but if you check out the analysis, it relies on multiple plaintext values.

Wikipedia lists no singular known plaintext attack, only a boomerang attack, which also depends on multiple known plaintexts.

So given these sources, it would seem there is not a well known and effective attack on three fish 512 with only one plaintext block.

Generally speaking, given only an encryption of a single plaintext block it would be difficult to use cryptanalysis to break a cipher. Even block cipher modes of operation which are deprecated, such as ECB, will operate securely for single block-key encryptions.

The Known-Plaintext-Attack seems to utilize single blocks of plaintext in some situations. That wiki site lists its usage on a cipher used during WWII, so technically Yes, there do exist ciphers which have been susceptible to a single known plaintext block at some points in history. But for modern ciphers, No, it does not seem to be an effective means of attack


How much data can I encrypt with RSA before I need to change the key How much data can be encrypted with the same RSA key before it has to be changed?

I looking for the total amount of data that can be encrypted for a single key pair, not the maximum length of data per iteration.

As an example, let's take a 2048-bit RSA key with a PKCS#1 "v1.5 padding". We can compute that the the maximum size of data which can be encrypted per iteration is 245 bytes (2048 bits - 88 bits). How many times can I reuse that key assuming that it encrypts 245 bytes each time?

I find a lot of information on this for AES but almost nothing for RSA.

The reason that you won't find much is that RSA is generally not used for bulk encryption, instead hybrid encryption is used.

For RSA using PKCS #1 v1.5 padding you generally don't want to go above $2^{31}$ but hopefully significantly fewer iterations. This is because of the birthday bound on the random padding used. If the random padding is identical to an earlier random padding then you can distinguish if a message is identical to a previous message.

Of course, this would assume you use all the 245 bytes of the possible payload, leaving you with significantly less than 1TB to encrypt. How much less depends on the risk you want to take with regard to duplicate ciphertext values. Note that if you would use less then 245 bytes for payload, then the number of padding bytes increases. If you would use only 237 bytes of payload then the random padding is about 128 bits and you would not have any problems with repeated ciphertext anymore.

If you just use hybrid encryption: encrypt an random AES data key with full padding then the amount of times RSA can be used is virtually without limit. To be more secure you should look at hybrid encryption with OAEP padding and preferably an authenticated mode for AES such as AES-GCM. For larger messages this will be more efficient (regarding CPU and ciphertext expansion - not to mention the taxation of the RNG) as well as more secure.


What part of an RSA key is referred to by the number of bits? When we speak about 4096- or 2048-bit RSA keys, what part of the key is this number of bits? The public key comprises both the modulus and the public exponent, and the strength of the key can also be seen as depending on the length of the prime factors. Which of these is the "4096-bit" part?

See https://en.wikipedia.org/wiki/RSA_%28cryptosystem%29

Under Key Generation:

Compute n = pq.
    n is used as the modulus for both the public and private keys. Its length, usually expressed in bits, is the key length.


Is there any function that does not suffers birthday problem? I am eager to know that if there is any function that does not suffer birthday problem and how to prove it formally that the function is not suffering the birthday problem.

If $f:\{0,1\}^m\rightarrow \{0,1\}^n$ with $n\geq m,$ then of course there are, the set of one-to-one functions, but such a function is not a cryptographic hash function, since it lacks the compression property. If $n<m,$ (or more generally if $|X|>|Y|$ for $f:X\rightarrow Y$), collisions will happen.


Is PBKDF2 with 1 iteration acceptable for a simple random key expansion? I have a 128 bit randomly generated key. I need to expand this key to 512 bits to use with an existing encryption library that does AES-256 encryption in CBC mode with HMAC-SHA256 authentication.
The encryption library I am using also has PBKDF2-SHA512 available. Is it acceptable to use PBKDF2 with just 1 iteration to do the simple key expansion that I need? I would also need a salt, for which I suppose I could just use a hardcoded value for.
Example:
generated_key = crypto_safe_rand(128)
derived_key = pbkdf2(password: generated_key, salt: 'hardcoded_salt',
                     iterations: 1, algorithm: 'SHA-512')

My thought is that the iteration count isn't really a factor since the original "password" is randomly generated and 128 bits long.
Or would it be better to use something like HKDF?

Or would it be better to use something like HKDF?

Generally? Yes. Using HKDF is preferred, if only to communicate clearer what you're actually doing here.

Is it acceptable to use PBKDF2 with just 1 iteration to do the simple key expansion that I need?

Yes.
To explain this, we first need to understand how PBKDF2 works. First, note that it compute $\ell$ from the input as the number of PRF (HMAC) invocations needed to get the desired key length. The key is then $T_1\|T_2\|\ldots\|T_\ell$. The $T_i$ are defined as $T_i=F(P,S,c,i)$ - with $P$ being the password, $S$ the salt and $c$ the iteration count. If we now look at $F$ we get $F(P,S,c,i)=U_1\oplus U_2\oplus\ldots\oplus U_c$ which simplifies to $U_1$ for our purposes. Finally we look at the definition of $U_1=\operatorname{PRF}(P,S\|\operatorname{INT}(i))$ - with $\operatorname{INT}(i)$ being a fixed-length 32-bit integer encoding.
Putting all of this together we see that PBKDF2 with 1 iteration yields
$$\operatorname{PRF}(P,S\|\operatorname{INT}(1))\|\operatorname{PRF}(P,S\|\operatorname{INT}(2))\|\ldots\|\operatorname{PRF}(P,S\|\operatorname{INT}(\ell))$$
which can be easily proven to be a variable output-length PRF with the same argument that is used to prove Counter-mode secure.
Finally, a variable output-length PRF keyed with a uniformly random key yields an output that is indistinguishable from a random string. The only assumption we need to make here is that HMAC-SHA512 is actually a secure fixed-length PRF but that one shouldn't worry you.


Need some understanding on RSA public key exponent I am new in cryptography domain and try to build some understanding on RSA key pair generation.

My doubt is on RSA public key exponent value . Can exponent be any value (prime or non prime numbers)? i am not getting proper answer for this.

if someone has useful link for this please help to share.

Regards
Nikhil

The exponent and the totient of the modulus should be coprime. (i.e. $\gcd(\varphi(p\cdot q),e)=1$) The easiest way to reduce the chances of them sharing factors is to make the exponent prime. There is a tiny chance that the totient of the modulus will have the exponent as a factor, making them not coprime, but it's a simple check for $\varphi(p\cdot q)\equiv 0\pmod e$ (should be false). I'm not fully keen on the details as to why exactly, but I believe it's due to biases that are present if the exponent and the totient share factors.

Though this is easy to get around, as the exponent doesn't need to be unique to each key. It's common practice to simply use a fixed value of 65537 and perform the check mentioned above.


Why does "gpg --export-secret-keys" ask for a password? What is it about the architecture of GPG that requires me to enter the password of the secret key when I export it with "gpg --export-secret-keys"?

I would expect that gpg can just copy the relevant part out of the keyring and dump it into a file, without a password prompt. After all, the exported form is still encrypted with my password.

man gpg...

  GnuPG  may ask you to enter the passphrase for the key.  This is required because the internal protection method of the secret key is different from the one specified by the OpenPGP protocol.

I guess that answers it.  Though if anybody knows more, feel free to share.


Create a TOTP for machines using HMAC or AES I'm trying to create a sort of Time-based One Time Password (TOTP) where machines are involved (not humans). In this kind of TOTP the step is 15 minutes between one code to the next one and both server and client share the same 256 bit secret key (k).
The message (m) is the current unix timestamp that is known by an attacker so suppose the text plain message m is known.
The key k is always the same and the attacker also knows the algorithm used for cryptography.
I think about two possible solutions for this problem:

HMAC(k,m) using sha256 as base algorithm client side, send the result and check server side that the hash is the same, then ok.
AES(k,m) and send crypted message as base 64 to the server. The server decrypt the message and check the time. If the time is included in accepted range then ok.

Possible scenario:
An attacker knows the plain text (time) and the crypted message (that can be the HMAC hashed text for option 1 or the crypted text after AES for option 2) and have maybe 500 possible combination of textplain plus related encrypted text.
Questions:
Q1: is it possible for the attacker to know the key k before a time range of 5 years for both of options with current computational power?
Q2: Which is the most secure option to use? Option 1 or option 2?
I'm studying these algorithms for days but I haven't find an answer to my questions yet.
Note: I studied TOTP in RFC 6238 too but it seems more related to Machine-human than machine-machine TOTP. For machines, with a 15 minutes step, seems more insecure than the 2 options proposed.
Thanks for everyone can help me in these questions, are making me crazy.

Be reassured: both $\text{HMAC}(k,m)$ [instantiated with a strong hash function, e.g. SHA-512; even SHA-256 would do] and $\text{AES}(k,m)$ [understood as direct encryption of 128-bit $m$ with the block cipher] are believed to be computationally secure Message Authentication Codes for the foreseeable future when the key is 256-bit, irrespective of how many message/cryptogram pairs are available. Both can be truncated: 64-bit would be ample if the verifier limits the attack rate.
$\text{HMAC}$ has the security advantage of being less susceptible to cache-based side channel attacks than $\text{AES}(k,m)$ is, for implementations in software without AES-NI on CPUs with caches.
From a functional perspective, $\text{AES}(k,m)$ has the slight advantage that (if kept 128-bit) it conveys the timestamp $m$, which can be recovered by decryption. Otherwise  we may need to transfer or guess some low bit(s) of the timestamp to fix any drift there may be, especially at startup.
Whatever the MAC, one operational vulnerability is likely to be the establishment and storage of the long-term 256-bit key $k$. There might be other attacks on the protocol, which is not described.


Publicly verifiable secret sharing scheme In https://www.win.tue.nl/~berry/papers/crypto99.pdf, Schoenmakers proposes a publicly verifiable secret sharing scheme, that uses a non-interactive DLEQ proof to allow any participant to verify the shares of the secret (section 3.1 of the paper).

In "Distribution of the shares", it says "Applying Fiat-Shamir’s technique, the challenge $c$ for the protocol is computed as a cryptographic hash of $X_i , Y_i , a_{1i} , a_{2i} , 1 ≤ i ≤ n$."

And later, "Using $y_i , X_i , Y_i , r_i , 1 ≤ i ≤ n$ and $c$ as input, the verifier computes $a_{1i} , a_{2i}$ as

$$a_{1i} = g^{ri} X_i^c,$$ $$a_{2i} = y_i^{ri} Y_i^c ,$$

and checks that the hash of $X_i , Y_i , a_{1i} , a_{2i} , 1 ≤ i ≤ n$, matches $c$."

My question is: how can the challenge $c$ be used as input of the hash that computes itself (the challenge $c$), or am I misunderstanding?

Here's my understanding:

The input of the hash is $x_i,y_i,a_{1i},a_{2i}$.
The output of the hash is $c$.

The wording is '$c$ is computed as ...'

And later the verifier checks if $c$ matches the Output of the hash function used on the same input variables. If different values were used in the original run, the hash would differ.

So yes, you misunderstood the statement.


How to fairly select a random number for a game without trusting a third party? Several people are playing a game with random events and require a way to produce a random number. (Such as dice rolls or a lottery.)

Can this be done such that each player has the power to be reasonably sure that the random number was fairly selected, without having to trust anyone else?

This question stems from a discussion in comments to my answer on the Bitcoin SE. I came up with a protocol but someone else spotted a flaw. This site seems more appropriate.
Please feel free to make use of my answer to that question.

The answer you posted is actually correct (more or less, see below): have each participant commit to their random number $r_i$ by publishing, e.g., $\mathcal{H}(r_i)$ in the first round. And then in the second round, each participant opens the commitment by publishing $r_i$ and everyone checks that it matches the committed value by hashing it. The final random number is the XOR of each $r_i$.

The commenter there suggested an attack if there is a collision. However the definition of a secure hash function is that its collision-resistant. For a good modern hash function like SHA256, that is the case.

There are two subtleties.

The first is that your scheme only works for large random number, large enough that an attacker couldn't try every possible value for $r_i$, hash it, and see if it matches. For committing to small values, you need a randomized commitment function. Good randomized commitments are based on discrete logarithms but you could construct one (with reasonable safeness) using a hash function by generating a large random value $a_i$ and then computing your commitment as $\mathcal{H}(r_i||a_i)$. To open, reveal both $r_i$ and $a_i$. To change $r_i$, you'd have to find a different $a_i$ so that the hash is the same: this is hard based on collision resistance. The bitlength of both $r_i$ and $a_i$ must be predetermined so it is clear from $r_i||a_i$ where to split the value into $r_i$ and $a_i$ (otherwise you could open it to different values by simply splitting in a different spot).

The second subtlety is that the last participant to reveal his value will learn the accumulated random number before he reveals his number (he can see everyone else's number and he knows his own). This may cause him to abort if he doesn't like the result. You can do more complicated things to provide fairness, but generally if any participant refuses to open their commitment, the protocol should be restarted from the beginning with that participant excluded.

Also read this answer from @D.W. on a different question where (s)he explains the same protocol.


Dishonest verifier running a concurrent zero-knowledge protocol Suppose Alice and Bob are engaged in the graph 3-colorability Zero-knowledge protocol in which Alice permutes a coloring $\varphi:V\rightarrow \{1,2,3\}$ for a graph $G(V,E)$, and then sends a commitment of each vertex $v$, $\{\pi(\varphi(v))\}_k$ to Bob.  Bob then randomly selects an edge of this graph to which Alice opens the commitment for the corresponding vertices.  Finally Bob verifies that for edge $(i,j)$, $\pi(\varphi(i))\neq\pi(\varphi(j))$.  They then iterate this process $|E|^2$ times until Bob is convinced with high probability that Alice indeed knows a 3-coloring of the graph.
This is shown in Goldreich, Micali, and Wigderson [1991] to satisfy Completeness, Soundness, and Zero-Knowledge.  However, what is to stop a dishonest verifier from running a concurrent protocol much like a man-in-the-middle attack to convince some third-party that they know the coloring?
Suppose Alice is convincing Bob that she knows a 3-coloring, and Bob is convincing Charlie that he knows the same 3-coloring.  Bob simply passes on each message received from Alice to Charlie and vice versa.
The actions in order will look like:

$A\rightarrow B: \{\pi(\varphi(v_1)\}_{k_1},...,\{\pi(\varphi(v_n)\}_{k_n}$
$B\rightarrow C: \{\pi(\varphi(v_1)\}_{k_1},...,\{\pi(\varphi(v_n)\}_{k_n}$
$C\rightarrow B: (i,j)$
$B\rightarrow A: (i,j)$
$A\rightarrow B: (k_i,k_j)$
$B\rightarrow C: (k_i,k_j)$

So how is this not a violation of Soundness? Since Bob does not know a 3-coloring for $G(V,E)$ yet he is able to convince Charlie with high probability that he does. My thought is that zero-knowledge protocols should work like Deniable Authentication signatures, but I'm having difficulty finding literature addressing this type of attack on ZK protocols.  If it's not a violation of Soundness, an explanation or citation as to why would be very helpful.

The definition of soundness for an interactive (zero-knowledge) proof says that no prover can convince a verifier of a false statement (i.e., one not in the language in question), except with tiny probability. In your “Bob in the middle” scenario the statement is true—the graph is 3-colorable—so there is no violation of soundness if “Bob” proves it by relaying messages (or any other strategy).
A separate but related property is proof of knowledge, which informally says that any prover that succeeds in convincing the verifier (with large enough probability) must “know” a witness for the statement being proved—in this case, a 3-coloring for the graph in question. (This “knowing” is formalized by designing an extractor for the prover.) Importantly, in the formalization of this property, the prover can interact only with the verifier; it can’t “phone a friend” for help. So, Bob alone would not be considered a prover that on its own can convince the verifier, and therefore there is no requirement on what we can extract from Bob. By contrast, Bob together with Alice as a “joint entity” would qualify as a successful prover, but that joint entity does indeed know a witness, so there is no contradiction with the definition.
There are stronger notions of soundness and proof of knowledge that allow provers to have more powers, e.g., the ability to interact with other entities about other statements, the ability to “reset” the verifier, etc. These go by various names like concurrency, non-malleability, and resettable soundness. Your scenario is most related to non-malleability, except that Bob isn’t changing the relayed messages at all, which is something we can never prevent. Non-malleability basically says that such direct copying is the only way an adversary can succeed.


Stream cipher example for an introductory cryptography course I am looking for an easily defined stream cipher to illustrate two basic principles in an undergraduate cryptography course:

  not every bit of the internal state should be used in the keystream;
  some non-linear operations should be used to step the internal state.

So far, my only candidate is the Geffe generator. But this is a bit too easily broken. My ideal example would be a stream cipher showing (1) and (2) that was a bit stronger than the Geffe generator, but still easily defined, and still breakable by a correlation attack.

If there are no candidates then I'd welcome suggestions for a simple design meeting my requirements.

The shrinking generator (open to divide and conquer) or self-shrinking generators are possibilities.

If you use a nonlinear combination generator with 3 relatively prime length primitive LFSRs and a nonlinear boolean function $f(x_1,x_2,x_3)$ you can also illustrate the tradeoff between nonlinearity and the degree of the function (Xiao-Massey lemma) as well as have some room for divide and conquer. You can spend 10 minutes on Geffe and show how its weaknesses can be ameliorated with this generator.

It also enables you to explicitly compute the nonlinearity via $f(L_1, L_2, L_3)$ over the integers.


Understanding Baby-Step Giant-Step Algorithm and discrete logarithm Studying the Baby-Step/Giant-Step Algorithm, I have some questions:

In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$?
(a) The time complexity is $O(\sqrt{p})$. If we make sufficient large $p$, then why is it difficult for compute the discrete logarithm computation in group $G$ of such order $p$?
(b) It is said that the discrete logarithm computation is hard in group of prime order, particularly in subgroup (order $q$) of group of strong prime order (like order $p = 2*q + 1$, $q$ and $p$ is prime); why is that?

In the algorithm, $p$ is the order of group, $x$ is solution. We rewrite $x = i * m + k $, but why do we make $m =\lfloor\sqrt{p}\rfloor$, rather than something else like $\lfloor {p/2}\rfloor$?

The time taken by Big Step-Little Step is $O( m + p/m )$ (the $O(m)$ term comes from the time taken iterating through the various $k$ values, the $O(p/m)$ term comes from the time taken iterating through the various $i$ values.

It should be easy to see that that time is minimized if $m \approx \sqrt{p}$

  (a) The time complexity is $O(\sqrt{p})$. If we make sufficient large $p$, then why is it difficult for compute the discrete logarithm computation in group $G$ of such order $p$?

If $p$ is quite large, then $\sqrt{p}$ is also large (even if it isn't as large as $p$); for example, if we want $\sqrt{p} \ge 2^{128}$ so that the number of steps that Big Step-Little Step takes is infeasibly large, we just take $p \ge 2^{256}$.

Just one note: if we're working in the group $\mathbb{Z}^*_p$, then there are other attacks against the Discrete Log problem other than the generic Big Step-Little Step (and Rho) algorithms; hence we generally need a much larger $p$

  (b) It is said that the discrete logarithm computation is hard in group of prime order, particularly in subgroup (order $q$) of group of strong prime order (like order $p = 2*q + 1$, $q$ and $p$ is prime); why is that?

If we are working in the group $\mathbb{Z}^*_p$ (that is, the multiplicative group modulo $p$), well, that group has a size $p-1$; any prime subgroup will have a size $q$ which is a divisor of $p-1$.  One way (but not the only way) to make sure that there is a good $q$ is to make $p$ a "safe prime", that is, a prime such that $q = (p-1)/2$ is also prime.

On the other hand, that applies only to the group $\mathbb{Z}^*_p$; if you go to (say) Elliptic Curve groups, there is no corresponding reason to prefer safe primes (either for the characteristic or the group size).


What quality of randomness is needed for randomized side channel countermeasures? Using per-operation randomness is a popular and effective way to protect cryptographic implementations against side-channel attacks, e.g. using Shuffling (randomizing the processing order eg for AES bytes) and Masking (aka blinding).
Now I wondered about where symmetric cryptographic implementations, e.g. a 4-shared masked and shuffled AES implementation, get their randomness from given that "proper" cryptographic randomness strategies would require computing (something like) AES again which gives us a circular dependency (?).
So my question is:
What quality of randomness is needed to secure a proper randomized cryptographic implementation and how is that randomness generated (usually)?
An optional follow-up (if not answered I will simply ask a new question): Does the randomness generator need to have the same level of protection as the main protected implementation (and thus also requires per-run randomness)?

What quality of randomness is needed to secure a proper randomized cryptographic implementation?

It is essential that the random source used is unpredictable, including under attack. If it could be predicted, or made predictable (e.g. by pouring some liquefied gaz literally freezing the random source) the countermeasure could be neutralized or even become counterproductive.
It is important that the values produced are at least about uniform and independent. A marked bias could enable an attack. How uniform and independent depends on circumstances and attacker's skill.
It is important that the source is fast, because customers hate to wait, and a lot of randomness is typically used.

How is that randomness generated (usually)?

In modern security devices, by a physical True Random Number Generator complemented by some level of monitoring and/or post-conditioning. For a typical general description of what that hardware does, see e.g. items 151 and 152 in this public Target Of Evaluation. Details are usually secret, because knowing them could help attacks. More generally, resistance to side channels is a hide and seek game, and competitive practitioners of such game don't reveals their hides.  I am told that in Common Criteria evaluation schemes, there are points for how tightly the code is kept secret.