MPC and Secret Sharing in not Fully-Connected Network I have an interest in applications of MPC and Secret Sharing.
My point of view is from fields of distributed computing and Game Theory.

I want to generalize some results to arbitrary network topologies. I couldn't find any results on MPC in not fully-connected networks.

Is anyone familiar with such works?

Secure computation over incomplete networks has been the subject of several works in the past. However, as far as I am aware of, none of these works uses the model of rational cryptography, where the agents are modeled in a game-theoretic way as rational players rather than computationally-bounded machines.

The most classical setting of secure computation considers security with aborts (adversaries may prevent the completion of the protocol, but they cannot compromise security or correctness of the computation), with computational security guarantees. In this setting, it is relatively easy to see that secure computation over an incomplete but strongly connected network can be reduced to secure computation over a complete point-to-point network. Indeed, assuming for simplicity that a public-key setup has been made, each party will simply compile the complete point-to-point MPC protocol as follows: each time a party $A$ must sends a message $m$ to a party $B$, she encrypts $m$ with the public key of $B$, signs it to guarantee integrity and authenticity, and sends the message to all parties she is connected to. Each time $A$ receives a message for which she is not the target receiver, she broadcasts it back to the parties she is connected to (unless she already broadcasted this message in the past, of course). This guarantees that, unless a cheating party prevents a message from passing (which is equivalent to aborting and preventing completion of the protocol), the correct message will eventually securely reach it's target receiver, hence one can implement an arbitrary MPC protocol this way. The same strategy can be used to execute a key exchange over an incomplete network, removing the need for a public key infrastructure in the first place (but one must still be able to authenticate himself).

Now, there are many questions that the above naive solution does not address: can we get something more efficient? Especially, what if we are willing to assume a bit more than just "the network is strongly connected"? Much more efficient protocols are likely to exist on some more specific types of graphs. What if we want unconditional security (with honest majority)? What if we want to hide the topology of the network? What if we want fairness, or guaranteed output delivery? What if the structure of the graph is not fixed before the protocol, but determined dynamically?

Not all of these questions have been considered. What has been looked at in the literature includes (see also additional references in the linked papers):

Information-theoretic secure computation with private and reliable channels in an incomplete network was addressed in this paper.
The more specific case of secure aggregation over incomplete networks was addressed here.
This very cool recent paper addresses the challenging case of secure computation over an incomplete and dynamic network (whose connectivity is determined dynamically). I also suggest, for more references on MPC over incomplete network, that you look at their introduction; page 1 contains a bunch of references.
This recent paper provides further insights regarding the characterization of information-theoretic secure computation over incomplete networks.
Eventually, there has been a lot of work on topology hiding computation, where the goal is to securely compute a function over an incomplete graph, while at the same time hiding the topology of the graph. See e.g. 1, 2, 3, 4 and references therein.


Wrong Miller's Weil Pairing implementation? I tried to implement the Miller's Weil Pairing algorithm in python using the book "An introduction to mathematical cryptography" by Hoffstein, Pipher and Silverman.

I tried my code with the example given in the book and I get the correct response.

I tried with another example but I have problems with it.
It is stated in the book that we must choose a random point S $\notin$ {0, P, -Q, P-Q}. I took the following elliptic curve $E : Y² = X³ + 3X + 8$ over the field $\mathbb{F}_{13}$.

$E(\mathbb{F}_{13}) = \{0, (1,5), (1,8),(2,3),(2,10),(9,6),(9,7),(12,2),(12,11)\}$

I tried to compute $e(P,Q)$ with $P = (1,5)$ and $Q = (12,2)$. As $-Q = (12,11)$ and $P-Q = (9,6)$, I tried with all the other points but I always have an error at some points in the computations because I end up with zeros at both numerator and denominator in this function.

There is probably something that I didn't understand or something wrong with my implementation. Could someone explain to me what is the problem ?
Here is my code with the first example that works and the second that causes the problem : http://tpcg.io/GZNfns

The reason your implementation fails is most likely because the result of the Weil pairing is 1 in this case, which is the most degenerate case and the one most likely to encounter division by zero errors.

Your elliptic curve $y^2 = x^3 + 3x + 8$ over $\mathbb{F}_{13}$ is cyclic. In this case, $P$ is a generator of $E$ (as is $Q$), and $P$ and $Q$ satisfy the relationship $Q = 4P$, so the Weil pairing is trivial:
$$
e(P,Q) = e(P,4P) = e(P,P)^4 = 1^4 = 1
$$
(The second-to-last equality above follows from the antisymmetry property of the Weil pairing.)

If you want a non-trivial Weil pairing, you need a non-cyclic elliptic curve group, such as the curve from the first example. In cryptography one usually uses an elliptic curve defined over an extension of a prime field instead of a curve defined over a prime field, in order to guarantee that the group is non-cyclic.


DSA: why using mod p mod q and not just mod p I'd like to know, in DSA we compute several values modulo $p$ and modulo $q$, like $r = (g^k \bmod p) \bmod q$ or $v = (g^{u_1}h^{u_2} \bmod p) \bmod q$.

As far as I understand, we want to use two different primes $p$ and $q$ instead of just one to make sure that $g$ is of prime order $q$ in order to be able to invert elements (let me know if my understanding is wrong). But once we make sure to have $g^q = 1 \bmod p$, why do we add on top of that another modulo q? After a quick look, all the equations seems to hold if we just work modulo $p$...

The only reason for me that could explain it would be that because $s$ is computed modulo $q$, it's not really useful to store $r \bmod p$, and for "optimization" one can store directly $(r \bmod p) \bmod q$... Is it the reason or did I miss something?

Thanks!

Consider the function $f\colon \mathbb Z \to \mathbb Z$ given by $f(x) = g^x \bmod p$ where $g$ has order $q$ modulo $p$.  If $x \equiv y \pmod q$, then necessarily $f(x) = f(y)$, since by hypothesis $x = y + \ell q$ for some $\ell$, so

\begin{equation}
  g^x \equiv g^{y + \ell q} \equiv g^y g^{\ell q}
  \equiv g^y (g^q)^\ell \equiv g^y 1^\ell \equiv g^y
  \pmod p.
\end{equation}

Note that $f$ is merely a function from integers to integers, but this proposition shows that there is additional periodic structure to its input: $f(x) = f(x + \ell q)$ for any $\ell$.  So if we consider the coset $\overline x = x + q\mathbb Z = \{\dots, x - 2q, x - q, x, x + q, x + 2q, x + 3q, \dots\}$ of $q \mathbb Z$, $f$ is the same on every element of $\overline x$.  Thus we can think of $f$ as being defined on the quotient $\mathbb Z/q\mathbb Z$, the set of all cosets of $q\mathbb Z$, rather than on $\mathbb Z$.  More jargomatically: there is a unique natural $\overline f\colon \mathbb Z/q\mathbb Z \to \mathbb Z$ defined in the quotient $\mathbb Z/q\mathbb Z$ so that $f = \overline f \circ \phi_q$, where $\phi_q\colon \mathbb Z \to \mathbb Z/q\mathbb Z$ is the natural projection $\phi_q(x) = x + q\mathbb Z = \overline x$ onto $\mathbb Z/q\mathbb Z$.

In other words, even if we treat $x \mapsto g^x \bmod p$ as a function on integers, we can always break it down into two steps, the first of which is reduction modulo $q$.  So, whether you like it or not, if you are computing $g^x$ for integers outside $0 \leq x < q$, the function can still always be defined in terms of doing $x \bmod q$ first.

What's much weirder is not reduction modulo $q$—which as above is necessary if you're going to use the result as an exponent—but the chain of reduction modulo $p$ and then modulo $q$.  This was a point of contention in the provable security literature on DSA and ECDSA.  You could imagine computing $g^k \bmod q$ directly, but it wouldn't make a functioning signature scheme.  What you really want is a uniform random map from $\mathbb Z/p\mathbb Z$ to $\mathbb Z/q\mathbb Z$ which has no properties that an adversary could exploit.

It just happens that $h \mapsto (h \bmod p) \bmod q$ sorta kinda seems to work but as far as I know nobody has a good handle on why even in recent analyses like Fersch–Kiltz–Poettering 2016 (paywall-free), which models it roughly as a random oracle while tidying up nearly everything else about the long and sordid history of attempts to prove DSA and ECDSA security.


(How) Is DDH generally broken in groups of composite order? In a somewhat recent lecture a claim was made that I couldn't back up myself but it got me curious whether it actually holds:

  If the order of the group is not prime, then the DDH assumption does not hold.

So my question would simply be:
How does one break DDH in general assuming only that the group order is composite? Or is there a group with composite order where DDH is conjectured to hold?

My research only lead to the special case of $\mathbb Z^*_p$ which has composite order as $p-1$ is even which leads to exploitable attacks on ElGamal thanks to the Legendre Symbol containing useful information which breaks DDH because ElGamal is proven CPA-secure iff DDH holds.

The claim is completely false.

The security of DDH over appropriate composite-order elliptic curves is not only believed to hold, the assumption that it holds has been widely used in cryptography. To give a single famous example, the BGN cryptosystem was initially defined over composite-order elliptic curves (with a pairing), before being generalized a few years later to prime order curves. More generally, relying on composite order elliptic curves is actually the standard approach in various subfields of pairing-based cryptography when a feasibility result must be established (see e.g. this IBE), since it is usually much simpler to get feasibility results there. The choice of prime-order elliptic curves is not motivated by security, but by efficiency, since a composite-order modulus must be huge in general.

Even outside of elliptic curves, DDH can be fine over a composite order group - for example, one of my paper proves, in the appendix, that DDH holds over the subgroup of $\mathbb{Z}^*_n$ of elements whose Jacobi symbol is one, which is a composite order group, assuming that DDH holds over the subgroups of squares of both $\mathbb{Z}^*_p$ and $\mathbb{Z}^*_q$ ($q$ and $p$ are the prime factors of $n$) together with the quadratic residuosity assumption. This is one of many examples, it is in fact very easy to build many composite order groups in which DDH holds, assuming DDH in prime-order subgroups of this group.

I have no idea why this claim was made in your lecture; the only things that comes to mind is that if the modulus contains small factors, then there is a straightforward CRT attack where you project onto the small groups. For example, DDH does not hold over $\mathbb{Z}^*_p$ itself, since it's a group of even order, so you can project a DDH instance to a subgroup isomorphic to $\{-1,+1\}$ (this is equivalent to distinguishing by computing the Legendre symbol, as you correctly observe).


Importance of salt when deriving an encryption key I'm very curious to know this and a bit confuses too:

Suppose, I have two files encrypted using AES-128bit with keys PBKDF2-derived from the same password and the same salt. If an attacker does brute force attack (imagining that he finishes this)
to crack the keys, I'm guessing he needs to run the attack once to get those 2 keys.
Now, if I encrypt the files using AES-128bit with keys PBKDF2-derived from the same password and a different salt, will it make the attacker run brute force twice? If the answer is yes, then why? Changing the salt doesn't change the number of possible keys $2^{128}$.

If the answer is no then, in both cases the number of possible keys are $2^{128}$. So, what difference does it make if the salt is different?

There are two ways to attack encryption that uses a derived key:

You can attack the encryption algorithm. In the case of correctly used* 128-bit AES, that essentially amounts to a brute force attack on the 128-bit keyspace.

This would succeed after on average $2^{127}$ tries (if it were practical). If you knew that two files had used the same password salt, you could brute force the key of one, then check if it also decrypts the other, meaning you'd find both with about $2^{127}$ tries when they share a password. If they had a different salt, there would be nothing special about the first key with respect to the other file – you would need a total of $2 \cdot 2^{127}$ tries.

The difference here is fairly meaningless, since both are impossible to break if AES is secure.
You can try to derive the same key. This means guessing the original password, deriving your own key, then trying whether it's the correct key by using it to decrypt.

The time the latter takes depends on the chosen password. Most ways humans generate passwords have much less than 128 bits of entropy, so a dictionary type attack could be faster than breaking the encryption. RFC 2898, i.e. PBKDF2 adds computational complexity to each password guess, by default making you use 1000 HMAC (2000 hash function) iterations in addition to the AES decryption. Call it $2^{b+11}$, where b is the entropy of the password.

Here, if you could find one password, you could try the same password with other files regardless of the salt. So if you knew the the same password was used for all files, salts would add ~no extra protection (just one extra key derivation per file at the end).

The situation where salts do matter is where each key is derived from a separate password. Finding one password (2. above) doesn't give you significantly more information to break others in that case. The best attack is to try the most common password for each, then the next most common password, etc. However, you need to only derive a key-guess once for any number of files that share a salt, meaning the complexity is related to the number of files with unique salts rather than all files.

* Per file AES keys do make correct implementation a bit simpler, since you don't have to worry about IV collisions or e.g. running into a per key data cap, but the fact that you then have to worry about salt collisions may outweigh any benefit.


SHAKE-128/256 or SHA3-256/512 Would it be better to use SHAKE-128/256 or SHA3-256/512? In what situation should I chose one over the other?

And in which case would it be more interesting to use one or another?

So SHA3-$n$ offers $n$ bits of security against preimage and second-preimage attacks and $n/2$ bits of security against collision attacks.
On the other side SHAKE-$n$ offers at $n$ bits of security against preimage and second-preimage attacks and also $n$ bits of security against collision attacks (assuming the digest is at least $2n$ bits long). So when to use which?

When you are forced to use "an approved hash function", you use SHA3, because SHAKE doesn't qualify.
When you need a really long hash output (or an XOF in general), you use SHAKE.
When you really need more than 256 bits of security against preimage or second-preimage attacks you use SHA3.
When you want to be compatible with more other systems, you probably want to use SHA3.
When speed matters to you (and you still want to use SHA3 / SHAKE) and you are happy with an all-arond $n$-bit security level (for $n\in\{128,256\}$), you use SHAKE.

This last point follows from the fact that the higher preimage resistance in SHA3 is paid for with lower rate (=number of new bits processed per internal permutation invocation) which is usually higher in SHAKE than in SHA3 (SHAKE256 has the same as SHA3-256).


Is MAC better than digital signature? MACs differ from digital signatures in the sense that MAC values are both generated and verified using a shares secret key. Does this in any way put MAC on a disadvantage as compared to digital signatures? How is one of them better than the other?

Was, as you stated, a MAC "are both generated and verified using a shared secret key", while with a digital signature, the signatures are generated with one key, and are verified with another (and it is infeasible to sign anything with the verifier key alone).

So, with digital signatures, we can give someone the ability to verify signatures, but not generate them; with a MAC, we cannot do so.

Is this difference important?  Well, that depends entirely on what we're doing, and whether we can whether someone who can verify messages can also create them.

For example, consider the case of Alice sending messages to Bob.  Bob wants to make sure those messages really come from Alice, and so they share keys; Alice signs/MACs the messages, and Bob verifies those messages.  If that's the only what that key is used, we don't mind if Bob can also use his key to generate messages, because we can trust that he won't.  After all, the only one who will ever validate a message is, in fact, Bob.  If Bob does generate his own message, well, the only one he would be able to fool with it would be himself, and there's no point to that.

For an example in the other direction, consider the example of distributed stock quotes, where (say) the New York Stock Exchange publishes the current price of stocks.  Now, people will need to be able to determine if these quotes came from NYSE, and so they need to be verifiable somehow.  If these quotes were MACed, that means that NYSE would need to distribute the MAC secret key (so people can verify quotes); that would mean that someone could generate a fake stock quote (one that says that, say the price of GM just went drastically down); because he has the MAC secret key, he can compute the correct MAC, and that would fool someone else, causing them to dump all their GM stock.  To prevent this, any such system would need to use a signature method, with the NYSE signature key being distributed.  That way, anyone could validate a stock quote, but they wouldn't be able to generate fake quotes of their own.

Now, the next obvious question is "if a digital signature can do everything a MAC can do, why would we ever use a MAC"?  Well, the answer is that while a digital signature could be used where we currently use a MAC, it is also much more expensive; a MAC is much (several orders of magnitude) cheaper to compute and verify, and is also somewhat shorter.  No one uses a digital signature when a considerably cheaper MAC would do the job.


Is the last step of an iterated cryptographic hash still as resistant to preimage attacks as the original hash? Considering a cryptographic hash, such as MD5 or SHA2, denoted by the function $H(m)$ where $m$ is an arbitrary binary string, there is a lot of material available that deals with potential weakness to preimage attack. I am interested in resistance to preimage attack where the cryptographic hash is applied recursively a number of times.

A classical first-preimage attack asks to determine a message $m$ for a given hash $h$ such that $h=H(m)$.

A related question considers a known value for $H(H(m))$ and asks if $H(m)$ can be determined more easily than $m$ from $H(m)$. The extension asks if $H^{(n+1)}(m)$ is more vulnerable to preimage attacks to determine $H^n(m)$ than it is to first preimage attacks... and, if resistance deteriorates as $n$ increases, how many times can $H(·)$ be applied while it is safe to remain confident the last application of $H(·)$ remains non-invertible - i.e. how many times is it safe to chain this non-invertible function without significantly weakening its resistance to inversion?

I'm also interested to establish if different hashes have different strengths relative to this scenario of repeated application.

If the hash function is any good, then it should behave as a "random function" (i.e. a function chosen randomly and uniformly among all possible functions). For a random function with output size $n$ bits, it is expected that nested application will follow a "rho" pattern: the sequence of successive values ultimately enters a cycle with an expected size of $2^{n/2}$; and the length of the "queue" (the values before entering the cycle) should also be close to $2^{n/2}$.

So, theoretically, recursive application weakens the function with regards to preimage resistance, but the weakening is low-bounded by $2^{n/2}$, a boundary which requires an awfully big number of invocations to be reached.

Moreover, when we select a hash function, we want to have decent resistance to collisions, and collisions can be found with effort $2^{n/2}$. So we already choose hash functions such that $2^{n/2}$ is unreachable (e.g. we use SHA-256, because $2^{128}$ is far beyond what can be realistically achieved with Earth-bound technology; see this answer for a discussion on the subject). In short words, the weakening through recursive application has no practical consequence (while the time taken to compute all the hashes improves things greatly with regards to dictionary attacks).


Efficient Aggregate Signatures With Same Key Suppose Alice has a set of messages $\mathcal M$ and generates signature pairs for each message $(m_1,s_1)$, $(m_2,s_2)$, ... $(m_n,s_n)$ using the same key. She then transfers these signature pairs to Bob, who knows Alice's public key.

Can Bob, without interacting with Alice, generate a new aggregate signature for the entire message set, i.e. ($\mathcal M, s')$, that validates with Alice's public key?

If I understand it correctly, this is achievable using BLS signatures, but I was wondering if there is a simpler and more efficient method available if there is only one signer. I am mainly concerned with validation speed.

Thanks in advance.

Can Bob, without interacting with Alice, generate a new aggregate signature for the entire message set, i.e. (M,s′), that validates with Alice's public key?

That would be troubling if Bob could sign anything verifiable by Alice's key (on behalf Alice).

  if there is a simpler and more efficient method available if there is only one signer. I am mainly concerned with validation speed.

I am not sure if it's the most efficient way, however, I may disclose how it was done in reality.  At one of the public sector publishers, the publisher is mandatory to digitally sign a set of publications and all their translations.  So the system generates a new message consisting of a list of publications and their hashes and then the whole list is signed. However - in this case, the concern here was signing speed (so the signing person doesn't need to enter her PIN into HSM for every single publication).


Application level encryption and key renewal (I had posted this question on stackoverflow and been asked to move it to crypto.)

I have a question related to encrypting data in the database, at the application level.

The application will encrypt the data (e.g. using AES) when persisting it to the database and decrypt the data once they have been retrieved from the database.

Is there any good technic to renew the encryption key?

If for example a company has a policy to renew the encryption key every two years we would end up in a position where we have to decrypt the overall database with the old key, and reencrypt it with the new one every two years.

Is there any technic to avoid such an issue?

I had the following answers: https://stackoverflow.com/questions/37172931/application-level-encryption-and-key-renewal

I mentionned AES because it is an industry standard. Would Paillier be fit for the industry?

DEK (data encryption key): The key that encrypts the actual content.
The DEK gets changed less often than the KEK (see below).

KEK (key encryption key): The key that encrypts the DEK.
The KEK gets changed ("rotated") at regular intervals according to best practices and company security policies.

As the volume of content grows, the more arduous it will be to rotate the DEK. You still might actually rotate a DEK from time to time, but doing so would mean re-encrypting all of your content with a new key.

It is much easier to simply use a new key to re-encrypt the DEK, rather than re-encrypting the content that was encrypted by the DEK, since encryption keys are tiny compared to the content that they encrypt.

You should rotate the KEK as you go, over time, whenever its expiration date passes, or incidentally, such as in the event of a breach or a suspected breach.


how does BearSSL's GCM modular reduction work? BearSSL (in src/hash/ghash_ctmul.c) seems to be doing a modular reduction that I don't completely understand. Here's the code:

/*
 * GHASH specification has the bits "reversed" (most
 * significant is in fact least significant), which does
 * not matter for a carryless multiplication, except that
 * the 255-bit result must be shifted by 1 bit.
 */
zw[0] = c0 << 1;
zw[1] = (c1 << 1) | (c0 >> 31);
zw[2] = (c2 << 1) | (c1 >> 31);
zw[3] = (c3 << 1) | (c2 >> 31);
zw[4] = (d0 << 1) | (c3 >> 31);
zw[5] = (d1 << 1) | (d0 >> 31);
zw[6] = (d2 << 1) | (d1 >> 31);
zw[7] = (d3 << 1) | (d2 >> 31);

/*
 * We now do the reduction modulo the field polynomial
 * to get back to 128 bits.
 */
for (i = 0; i < 4; i ++) {
    uint32_t lw;

    lw = zw[i];
    zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
    zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
}

How does this reduction work?

There are three important points here to consider.

1. We work in $\mathbb{F}_2[X]$. This means that we do additions and multiplications of binary polynomials, i.e. polynomials whose coefficients are 0 or 1. The addition of two polynomials is then a bitwise XOR; there is no carry propagation. Similarly, the multiplication is called a "carry-less" multiplication. There are some explanations about that here.

In particular, the "modular reduction" is about divisions of polynomials, not integers. The modulus is the binary polynomial $X^{128} + X^7 + X^2 + X + 1$ (it is an irreducible polynomial over $\mathbb{F}_2$, which implies that when computing stuff modulo that polynomial, we work in a finite field).

2. There is a fair amount of confusion about encoding. This is a problem from the GCM specification. The input bytes are to be interpreted as bits, i.e. the coefficients of a binary polynomial. "Endianness" is about how to map chunks of an element (e.g. bits in a byte) to their mathematical value. For instance, if you consider a byte of numerical value 0xC9 (201 in decimal) and write it down as a sequence of bits, you normally use big-endian notation, i.e. you write it as "11001001": the leftmost bit is the one with the highest value ($2^7 = 128$), the rightmost is the one with the lowest value ($2^0 = 1$). This is what happens with integers; with binary polynomials, the big-endian interpretation of a byte is to map the leftmost bit to the coefficient of $X^7$, and the rightmost to the coefficient of $X^0$; hence, "11001001" would be decoded as $X^7 + X^6 + X^3 + 1$.

The concept of endianness works at all levels; i.e. not only bits within bytes, but also for bytes within a sequence of bytes. The "pure big-endian" interpretation of a sequence of 16 bytes would be to decode each byte in big-endian (as above), then assemble all bytes with the most significant byte coming first, i.e. the first byte in the sequence corresponding to binary coefficients $X^{127}$ to $X^{120}$, the second byte being for coefficients $X^{119}$ to $X^{112}$, and so on. BearSSL decodes input values in pure big-endian interpretation; internally, it stores them not into bytes, but into 32-bit words:

            /*
             * Decode the block. The GHASH standard mandates
             * big-endian encoding.
             */
            yw[3] ^= br_dec32be(src);
            yw[2] ^= br_dec32be(src + 4);
            yw[1] ^= br_dec32be(src + 8);
            yw[0] ^= br_dec32be(src + 12);

Here, yw[0] will contain coefficients $X^0$ to $X^{31}$, yw[1] coefficients $X^{32}$ to $X^{63}$, and so on.

Now there is a lie here. The GHASH standard does not really mandate big-endian encoding. It, in fact, mandates the complete opposite, which is pure little-endian encoding, i.e. not only the first byte should be for coefficients $X^0$ to $X^7$, but the bits within that byte are interpreted in "unnatural" order, i.e. the most significant bit (of numerical value 128) is for coefficient $X^0$, not $X^7$. This little-endian convention of bits within bytes is very inconvenient for computations, especially since BearSSL implements the carryless multiplication by way of multiplications on plain integers (i.e. multiplications with carries, but using masks and holes to remove these carries where necessary). If BearSSL were to use pure little-endian convention, it would then have to swap bits around within bytes, a cumbersome operation which would degrade performance and increase code size.

Instead, BearSSL uses a trick, which works on binary polynomials. Namely, if you define bit reversal:
$$ \mathrm{rev}_n \Big(\sum_{i=0}^{n-1} a_i X^i\Big) = \sum_{i=0}^{n-1} a_{n-1-i} X^i $$
then, when multiplying two polynomials $A$ and $B$ of degree less than $n$ (i.e. that fit on $n$ bits):
$$ \mathrm{rev}_n(A) \times \mathrm{rev}_n(B) = \mathrm{rev}_{2n-1}(A \times B) $$
i.e. if you reverse the two operands, you get the reverse of the product. This does not work at all on plain integers, because additions on plain integers have carries, and carries propagate in a definite direction (right-to-left, in the usual notations), and that does not work "in a mirror". But with carryless multiplication, there are no carries, and everything can be mirrored.

What that means here is that, by decoding 16 bytes with pure big-endian notations, BearSSL does not get the expected polynomial $A$, but $\mathrm{rev}_{128}(A)$. The product is then computed over reversed operands, and yields the reverse of the expected value. If that result is to be reencoded back with pure big-endian notation, then everything works fine! The compatibility of operations with bit reversal ("mirroring") means that you can really choose the encoding convention you want, and you get the right result, provided that you stick to your convention throughout.

... Except for one small detail. If you look at the equation above, the product of two bit-reversed 128-bit polynomials yields the bit-reversed result over 255 bits, not 256. The BearSSL code ends up with a 256-bit result in zw[], and that value is shifted by one bit, because of that reversed convention issue. Thus, the code must include a shifting step to put it back where it should, and this is the first half of the code you reproduce in your question:

           /*
             * GHASH specification has the bits "reversed" (most
             * significant is in fact least significant), which does
             * not matter for a carryless multiplication, except that
             * the 255-bit result must be shifted by 1 bit.
             */
            zw[0] = c0 << 1;
            zw[1] = (c1 << 1) | (c0 >> 31);
            zw[2] = (c2 << 1) | (c1 >> 31);
            zw[3] = (c3 << 1) | (c2 >> 31);
            zw[4] = (d0 << 1) | (c3 >> 31);
            zw[5] = (d1 << 1) | (d0 >> 31);
            zw[6] = (d2 << 1) | (d1 >> 31);
            zw[7] = (d3 << 1) | (d2 >> 31);

Thus, these lines are really about making it as if everything had been done in pure little-endian convention, whereas it was done in pure big-endian convention.

3. Modular reduction is over binary polynomials. We work modulo polynomial $M = X^{128} + X^7 + X^2 + X + 1$. This means that for any polynomial $P$, we can add (or subtract, but in $\mathbb{F}_2[X]$, addition and subtraction are the same thing, i.e. a XOR) arbitrary multiples of $M$. The "modular reduction" of the 255-bit result $P$ really is an addition of multiples of $M$ until we get something that fits on 128 bits.

Write the polynomial to reduce $P = \sum_{i=0}^{254} p_i X^i$. Take one coefficient $p_i$ for some $i \ge 128$; we want to "cancel that bit", in case it as value $1$; the trick is to add $M\times X^{i-128}$. In other words, we add:
$$ p_i M \times X^{i-128} = p_i X^i + p_i X^{i-121} + p_i X^{i-126} + p_i X^{i-127} + p_i X^{i-128} $$

The first part ($p_i X^i$) merely clears the bit at position $i$ (it's a XOR of $p_i$ with itself), but the other parts "inject" (XOR) bit $p_i$ at other places down the sequence of coefficients. Crucially, these are relatively far (121 or more bits down the sequence), which allows us to process bits by large chunks (this is the reason the modulus was chosen with that value). Consider the first iteration of that loop:

            /*
             * We now do the reduction modulo the field polynomial
             * to get back to 128 bits.
             */
            for (i = 0; i < 4; i ++) {
                    uint32_t lw;

                    lw = zw[i];
                    zw[i + 4] ^= lw ^ (lw >> 1) ^ (lw >> 2) ^ (lw >> 7);
                    zw[i + 3] ^= (lw << 31) ^ (lw << 30) ^ (lw << 25);
            }

The word zw[0] contains the coefficients $X^{255}$ to $X^{224}$. Since the coefficients for $X^i$ must be injected at positions $X^{i-121}$, $X^{i-126}$, $X^{i-127}$ and $X^{i-128}$, these 32 bits end up being injected in various positions in zw[3] and zw[4]. In the line that updates zw[i+4] (i.e. zw[4] during the first iteration), we see the XOR with lw, which is the injection of bits at positions $X^{i-128}$; the lw >> 1 is the injection of bits at positions $X^{i-127}$; and so on.

Nominally, we should clear the high bits (zw[0] to zw[3]) but this is optimized out, since we don't look at these bits again; the useful result, after reduction, is in words zw[4] to zw[7]:

            memcpy(yw, zw + 4, sizeof yw);

And that's the complete modular reduction.


Can we design a block cipher based on SP-network without loss of E/D similarity theoretically? I understand what SP-network (Substitution-Permutation Network) and Feistel Network look like. And those ciphers based on Feistel (e.g. DES) often achieve so called E/D similarity, which indicates that the cipher itself follows the same pattern during either encryption or decryption.
SPN, comparing with Feistel Network, can bring more "confusion" into the cipher indeed. But the ciphers deriving from SPN (e.g. AES) may not be able to realize this E/D similarity. For instance, we have to put the inverse SBOX into the AES decryption process.
Thus, can we design a block cipher based on SP-network without loss of E/D similarity theoretically? Thanks!

Actually, to deal with the conflict between the inverse SBOX and E/D similarity, we can just expand the original SP network into something like "$S$->$P$->(entangled with key)->$P^{-1}$->$S^{-1}$". Then we can have a E/D similar block cipher. Some standard ciphers like PRINCE were designed this way.
However, it seems that we still can not make SPN itself to be of E/D similarity so we have to place extra components in it.


Implementing CBC Encryption Using Decryption I've implemented this algorithm, which, working from the end of the message backwards, creates a valid CBC ciphertext from any plaintext, using the block cipher's decryption operation instead of the encryption operation.

I bet this is described in the literature, somewhere. Possibly as a bad idea.

My questions:

What is this method/algorithm/construction called?
Is it as secure as CBC implemented the normal way?
Do the normal rules for CBC IV apply to the last ciphertext block or not?

For those wondering why I would want to encrypt my message from the end, this is an exercise in exploiting a padding oracle attack (against my own dummy code running on my own server).

Your mode is essentially equivalent to CFB mode, except that:

you've reversed the order of the blocks in the message, and
you're using the block cipher in the opposite direction than usual.

Neither of those differences should have any direct security implications (since all standard block ciphers have the same security properties in both directions), so your scheme should be just as secure as CFB mode.


Is XORing a random stream of bytes a secure way to obscure a file? Long ago I created a very simple program that used the C library's rand method to generate bytes to XOR with the bytes of a file. This was a reversible (just run it through again) method to make a file unreadable.

In my simple implementation, I did not change the seed, so it always created the same "random" stream, but if I had given a seed as a command line argument, would this be a reasonable way to obscure a file?

This question is not about the merits of any particular pseudo-random number generator, just assume a good one. The point is: does it provide a sound obscuration using a very simple algorithm?

XORing a plaintext with a random stream of the same size is a secure way to encrypt it. A stream cipher works in this way.

The issue in your design is the random source. If the random stream does not have the security properties one expects, the systems is not secure.
In your implementation, the seed has the role of the key (and potentially the initialization value) of a regular stream cipher.

If someone can encrypt something with your method (or recover a couple plaintext/ciphertext) he will be able to decrypt every past/present/future encryption generated with the same key. Only for messages shorter than known one (but the remaining part could be guessed if the file is, e.g.:, an english text).


What security do digital signatures provide (like used when signing PDFs)? I want to ask you one question about digital signatures as they are (for example) used when digitally signing PDFs.

We know that if our document has a digital signature, we can detect if the original document has been altered or not. And if we want to prove owner identity, we use digital signatures.

On the other hand, it's very simple to remove a certificate from the document, and change it (because the document itself will not be altered, due to the certificate not being in the byte range of which the hash is encrypted as a digital signature).

So, what security do digital signatures provide (to - for example - PDFs)? Or am I missing something?

You've stumbled on the requirement for authentication.

Recall that signature schemes have a private key and a public key. The private key is used to sign the document in question, and the public key is given to the verifying party so that they can verify that the signature is correct.

You're correct that it is possible to strip a digital signature and replace it with a fake one from, say, a different key. To defeat this, the verifying party needs to check that it has the correct public key to verify the signature. For example, the signer might coordinate with the verifying party a week ahead of time, in real life, and exchange keys physically (here, you could use some form of ID as authentication, since IDs include pictures). Or they might take the SSL route and use third-party certificate authorities. At any rate, they need some way to obtain the correct public key.

Then, if a man-in-the-middle attacker has replaced the signature with a fake one from the wrong key, when the verifying party attempts to verify the signature against their known-good public key, the verification will fail. The point here is that only the (proper) signing party knows the private key associated with the known-good public key, so only the signing party can generate an authenticate signature that will match that public key.

Thus, simply checking that a digital signature is present is not enough; one needs to computationally verify that the signature is correct using an authenticated public key, i.e. one that the verifying party knows for sure is "owned" by the alleged signer.


Homomorphic Encryption or not I am a beginner to homomorphic encryption scheme.
As far as I think, it is just a kind of concealing real value without using standard encryption algorithms such as AES,DES or RSA.
For example , for concealing value of $3$, it expresses $6$ where ($6=2 \times 3$).
Decryption is done successfully if user knows $2$ (secret value).
Is it correct or not?

Homomorphic encryption allows you to perform operations on the ciphertext that are reflected in the plaintext. These operations are not used to keep the plaintext confidential, that's performed by the homomorphic encryption itself.

Homomorphic encryption usually has little to do with obfuscation techniques, which is probably what you're looking for. "just looking for a light version" as you explain in your comments probably rules out homomorphic encryption techniques to accomplish obfuscation.


SHA256 and RIPEMD160 collisions H = ripemd160(sha256(ECMultiply(A,G)))

A - 32-byte number,

H - 20-byte number,

G - generator point,

ECMultiply - elliptic curve point multiplication.

Is it true that there is many A that have the same H?

There are close to $2^{256}$ ECC keys while there are only $2^{160}$ 20-byte hashes, so the pidgeonhole principle shows that there exist collisions. On average there there are $2^{96}$ keys for each 20-byte hash.

Since SHA-256 is a strong hash function, the only way to find a collision is brute force, which involves $2^{80}$ hash computations. But collisions are not a relevant attack for bitcoin addresses, since stealing your own money is rather pointless.

What an attacker needs to do is a multi-target preimage attack, which is ridiculously more expensive than the expected rewards ($2^{160}$ hash computations to steal 67 billion USD, which means more than $2^{120}$ hash computations for each dollar you steal).

It's clearly better for the attacker to attack the address with a known ECC public key and the highest balance, since that costs $2^{128}$ operations, but reaps all bitcoins from that address.


Fully homomorphic encryption (over addition and multiplication) library in python I was wondering if there is a commonly used library in Python (or another common language such as Java, C++, etc.) for fully homomorphic encryption over multiplication and addition that also supports floating point numbers. This means that if our encryption function is $f$ and our decryption function is $g$ and we have to plaintext messages $m_1,m_2$, then both the following hold:

$g(f(m_1)+f(m_2))=m_1+m_2$
$g(f(m_1)\cdot f(m_2))=m_1\cdot m_2$

Python-paillier implementing a Paillier cryptosystem seems to be pretty well documented and it actually does support floats (does so by fixing a precision and scaling all floats up to be integers), but unfortunately it is not fully homomorphic over multiplication (it does not support the multiplication of cipher texts, but rather has a weaker multiplicative property).

I've done a quick search and it seems that there's a lot of such cryptosystems (I don't care too much about runtime as of now), but I've been unable to find a library with concrete implementations.

Thanks in advance!

Most of the homomorphic encryption schemes work

over integers modulo some value, say n
or over bits.

In the first case, you can try to simulate floating-point numbers by first scaling all your original data to integers and keeping tracking of the scaling factors during homomorphic evaluation so that you can divide by the correct value after decryption. But this is generally not efficient.

In the second case, you can encrypt each bit of the floating-point numbers and implement circuits to add, multiply, etc, floating-point numbers using the homomorphic binary gates provided by the scheme, but this is very laborious.

The only scheme that I am aware of which works natively on (something very close to) floating-point numbers is this scheme by Cheon et al, which is implemented in this Github reposiroty.


How can I be sure the RNGCryptoServiceProvider is able to produce 12 bytes that can have 2^96 values? I am writing code that needs to produce a truly random number of 96 bits. The requirements are:

The code must be able to produce all $2^{96}$ values.
The likelihood for any value to come up must be the same for all values.
It must be impossible to predict the next $96$-bit number that will come up.

So, using RNGCryptoServiceProvider, I have the following implementation:

  Public Function GetRandom96BitNumber() As BigInteger
        Dim random96BitNumber As BigInteger
        'We need 12 bytes, but take 13 in order to ensure a positive number.
        Dim bytesFor96BitNumber(12) As Byte
        Dim cryptoProvider = New RNGCryptoServiceProvider
        cryptoProvider.GetBytes(bytesFor96BitNumber)
        'Set the thirteenth byte to zero to ensure that we get a positive BigInteger.
        bytesFor96BitNumber(12) = 0
        random96BitNumber = New BigInteger(bytesFor96BitNumber)

        Return random96BitNumber
    End Function

Question:

This code (assuming it employs the RNGCryptoServiceProvider correctly) is only as good as the quality of randomness of the RNGCryptoServiceProvider. How can I convince myself and my clients that the three criteria stated above are met? I found this document that compares cryptographic random number generation between Windows and Linux and I think I read there that the entropy used to seed the RNGCryptoServiceProvider is at least 256 bits.

Does this mean that the three requirements stated above are met? If yes: why? If not: why not?

Any further guidance for getting enlightenment are very much appreciated.

RNGCryptoServiceProvider - according to many sites including the following Wikipedia link itself - uses the CryptGenRandom functionality of the operating system. You therefore need to convince your clients that the OS functionality is sufficient.

The Wikipedia article contains references to FIPS and Common Criteria EAL4 evaluations of the operating systems containing the RNG. That should normally be sufficient - although I must admit that I cannot find the actual FIPS validation certificate of the RNG.

The best reference is probably the documentation of BCryptGenRandom which states:

  The default random number provider implements an algorithm for generating random numbers that complies with the NIST SP800-90 standard, specifically the CTR_DRBG portion of that standard.

This is for Windows versions after Windows Vista. Before that an RC4 based algorithm seems to have been used.


Is it possible to choose which point will have the public key of a given Elliptic Curve? I am wondering if there is a feasible way that, given a specific elliptic curve (such as secp256r1), I could create a keypair where the public key has a given $x$-coordinate. If it is not possible, is there a way to choose the most significant digits of that coordinate?

For example, is there a way to make a secp256r1 ECC keypair with the $x$-coordinate of the public key having the form 04 0000....1234?

Thank you.

If that were possible, that is, if you could take an x-coordinate, and find the private key $k$ such that $kG$ has that x-coordinate, well, you've just solved the discrete log problem. If you can do that, you've just shown that the curve is insecure.

If you're thinking "I'm not specifying the y-coordinate; doesn't this make it easier than the discrete log problem", actually, no it doesn't.  There are at most two points that have a specific x-coordinate, and those two points are inverses of each other.  If you known the discrete log of one of the points, you immediately know the discrete log of the other.

As for choosing the most significant digits of the coordinate, I don't know of any easier way that brute force (that is, start at an arbitrary place $kG$ and test $kG, (k+1)G, (k+2)G, ...$ until you stumble across a point that meets the condition.


The real-life meaning of proving over a group that doesn't support the oracle? If I proved a scheme's security under GDH assumption, in real-life, if this DDH oracle does exist, then it's good, but what about  other side ? In real-life, if this DDH oracle doesn't exist, then what's the meaning of proving?

One might imagine that the object of a security proof is to know that if someone breaks your system, that means they have (essentially) found a way to do some computation that you couldn't do before. Sort of a consolation prize.

However, it is better to consider it as a statement of beliefs and consequences of those beliefs. We believe factoring is hard. If a practical attacker against a cryptosystem leads to easy factoring, we must believe that such a practical attacker cannot exist. We must believe that our cryptosystem is secure.

And from this point of view Gap Diffie-Hellman makes sense. We do not believe that CDH reduces to DDH, ergo we must also believe that cryptosystems based on GDH are sound.


How to calculate Enc(-m) from Enc(m) in Paillier cryptosystem? The encryption in Paillier cryptosystem is like this according to Wikipedia:

Let $m$ be a message to be encrypted where $m \in \mathbb{Z}_n$
Select random $r$ where $r \in \mathbb{Z}_n^*$
Compute ciphertext as: $c = g^m \cdot r^n \bmod n^2 $

So just calculating the inverse of ciphertext $c$ (i.e enc($m$)) will not work, because enc($m$)*enc($-m$) is equal to $r^{2n} \bmod n^2$, not $1 \bmod n^2$.

Actually, computing the inverse modulo $n^2$ using (say) the Extended Euclidean method is exactly what you do.  If $c = g^m r^n \bmod n^2$ is an encrypted version of $m$, then $c^{-1} = (g^m r^n)^{-1} = g^{-m} (r^{-1})^n$ is a representation of $-m$ (because if $r \in \mathbb{Z}^*_n$, so is $r^{-1}$)

That $enc(m) * enc(-m)$ isn't precisely 1 isn't relevant; however if we use different randomness $r$ and $s$ during the separate encryptions (as we're supposed to), it'll actually be $r^ns^n = (rs)^n$.  However, there is lots of encrypted representations of 0; while 1 is such a valid representation, $(rs)^n$ is as well.


Developing algorithm for detecting plain text via frequency analysis I'm currently attempting the Matasano Crypto Challenges as a basic intro to cryptography. For solving some of the earlier challenges I utilised n-grams to determine which is going to be the most likely English plain text. It has been quite successful.

I'm up to attempting to break repeating XOR, which involves grouping bytes in their suspected single byte XOR group, and cracking them in this fashion. As this will be disjointed text, it appears I will need to use frequency analysis as opposed to n-grams.

I implemented a basic scoring system (similar to the below source code) source.

function getEntropy(str) {
    var sum = 0;
    var ignored = 0;
    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if      (c >= 65 && c <=  90) sum += Math.log(ENGLISH_FREQS[c - 65]);  // Uppercase
        else if (c >= 97 && c <= 122) sum += Math.log(ENGLISH_FREQS[c - 97]);  // Lowercase
        else ignored++;
    }
    return -sum / Math.log(2) / (str.length - ignored);
}

With short cipher texts though I've had the issue that garbled text with more printable ASCII has scored higher than correctly formed English. I.e. FKDASDOFD may score higher than THE RIVER, as it's got a space which isn't counted towards its score.

From this, I've been trying to come up with a way of perhaps scoring the letter count against it's expected frequency, while penalising the score for each letter the further it is away from it's expected value according to normal distribution.

For example, a very rough though process of algorithm I'm trying to implement.

1) "a" has a frequency of 8.167%.
2) Evaluate the frequency in the candidate plain text and compare that      against the expected value (8.167%).
3) Penalise the 'score' by multiplying it by [1-(std dev cumulative prob)]. For example if it was 1 std dev away from expected, multiply the score by [1-0.68], 3 std deviations, [1-0.997], etc.
4) Add the cumulative score for each letter to evaluate the most likely plain text.

My questions are.

Is there a better, established, algorithm out there for performing frequency analysis?
Is it simply the nature of short cipher / plain texts that there will be inherent inaccuracy in evaluating the probability of English plain text?
Is my proposed method ridiculous / naive / stupid in some way?

Thanks folks, attempting to learn so sorry if there are trivial mistakes or invalid assumptions in this question.

As otus suggests in the comments, it's better to first calculate the frequency of each letter in the decrypted message, and then compare the frequency distribution to what would be expected for English text.

For the comparison, you can use chi-squared ($\chi^2$) testing.  (Actually, for just comparing the likelihoods of different decryptions, you don't even need the complete test.)  To do this, start by comparing the actual observed number of occurrences $N_{\rm obs}(c)$ of each character $c$ in the decrypted message with the expected number of occurrences $N_{\rm exp}(c)$ of that character in a piece of English text of the same length (i.e. its expected frequency times the length of the message), and calculate the test statistic $$\chi^2 = \sum_c \frac{\left( N_{\rm obs}(c) - N_{\rm exp}(c) \right)^2}{N_{\rm exp}(c)},$$ i.e. the sum of the squared differences between the observed and the expected frequency, divided by the expected frequency.  The smaller this $\chi^2$ is, the more closely the decrypted message resembles English.*

Here's some basic JS code to calculate $\chi^2$ for English ASCII text:

// http://en.algoritmy.net/article/40379/Letter-frequency-English
var english_freq = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,  // A-G
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,  // H-N
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,  // O-U
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074                     // V-Z
];

function getChi2 (str) {
    var count = [], ignored = 0;
    for (var i = 0; i < 26; i++) count[i] = 0;

    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if (c >= 65 && c <= 90) count[c - 65]++;        // uppercase A-Z
        else if (c >= 97 && c <= 122) count[c - 97]++;  // lowercase a-z
        else if (c >= 32 && c <= 126) ignored++;        // numbers and punct.
        else if (c == 9 || c == 10 || c == 13) ignored++;  // TAB, CR, LF
        else return Infinity;  // not printable ASCII = impossible(?)
    }

    var chi2 = 0, len = str.length - ignored;
    for (var i = 0; i < 26; i++) {
        var observed = count[i], expected = len * english_freq[i];
        var difference = observed - expected;
        chi2 += difference*difference / expected;
    }
    return chi2;
}

If you're only interested in finding the most likely decryption(s), that's all you need to do.  Just sort the decryptions (and corresponding candidate keys) by $\chi^2$ in increasing order, and print out the first few entries.

If you also wish to estimate the actual likelihood of the message being English (or, rather, the likelihood that picking random letters with frequencies matching English text could yield such a message), you'll also need to determine the number of degrees of freedom $k$ for the model (which, for a simple model like this, is simply the size of the plaintext alphabet minus one**) and then integrate the chi-squared distribution for $k$ degrees of freedom up to $\chi^2$ (or just compare it to a precalculated table).  But just for comparing the likelihood of different decryptions, the raw $\chi^2$ value is enough.

*) You have to calculate this sum over all the letters in the alphabet, including those that don't actually occur in the message, for which $N_{\rm obs}(c)$ simply equals $0$.  Conversely, any characters that don't occur in your frequency table would, in principle, have $N_{\rm exp}(c) = 0$, and thus yield $\chi^2 = \infty$ if they occur in the message.  In practice, to avoid such infinite results, you may wish to either ignore such characters or assign them some more or less arbitrary small frequency.  One reasonable choice, if you're compiling your own frequency tables from a corpus of text, is to use additive smoothing by incrementing the observed count of each character in the corpus by one.

**) The one degree of freedom is lost because the sum of the character counts must obviously equal the length of the message, which is fixed a priori.  Thus, we're not completely free to choose how many times each character occurs in the message; having chosen all but one of the counts, the last count is unique determined by the others.


What kind of multiparty computation is this? The classic multiparty computation protocols are defined around " Untrusted parties trying to compute something together".

But is there a cryptographic abstraction for, "Trusted parties trying to compute together in presence of untrusted server"?

Basically, I am looking for something like multi-player homomorphic encryption for cloud based services. Current homomorphic encryption schemes are two player setup (just a client and server), where client wants to outsource her computation to an untrusted server , but this abstraction does not stretch for most of the cloud based applications, say privacy preserving Facebook or tax processing cloud application where multiple people are involved using a cloud server.

There is a surge in research of functional encryption and its variants (IBE,PBE,ABE, etc.), but they reveal the end-result in plain text.

There are roughly two common techniques for multi-party computation, garbled circuits and secret sharing. Either may work for your situation, so I've detailed some info and recommendations about each below.

Garbled Circuits
GC is most often applied to the 2 party case. It can be made to be secure against malicious adversaries and can be fairly efficient (a single execution of AES in 1 sec on a massively parallel machine). Against a semi-honest (or honest-but-curious) adversary, a single execution of AES takes about 0.2 seconds (this is on a single thread/process).

Secret Sharing
There are many secret sharing based protocols out there. They typically aim for as many parties as desired (with a cost of extra communication & computation per party). They also can be made to work in the malicious model. Any secret sharing technique can theoretically be used, but the most efficient protocols have used (somewhat) homomorphic encryption.

The SPDZ protocol was recently used to compute an execution of AES in less than half a second with up to 10 parties. The timing result only takes into account the online phase. There is a preprocessing phase which takes more time (haven't been able to find exact numbers), but still appears to be manageable.

Fully Homomorphic Encryption
Fully-homomorphic encryption can easily be used to compute on encrypted data, in the malicious model. But, it comes with its tradeoffs. The communication complexity is much less than any of the other protocols, but (currently) the computation complexities are too large to be practical. For example, homomorphic evaluation of AES was shown to take a few days using the best of the best available FHE systems.


Split encryption into two steps Are there two step encryption systems that - given the same plain text - support choosing two keys ($k_{A_1}, k_{A_2}$) for a first encryption so, that you can calculate another pair of keys ($k_{B_1}, k_{B_2}$) resulting in equal cipher texts?

$E(k_{B_1}, E(k_{A_1}, m)) = E(k_{B_2}, E(k_{A_2}, m))$ with $k_{A_1} \neq k_{A_2}$

A one-time-pad encryption is one of these systems, if you choose the keys like this $k = k_{A_1} \oplus k_{B_1} = k_{A_2} \oplus k_{B_2}$. Are there other systems that don't suffer from key re-usage?

There's always the old Polig-Hellman system, with:

$$C = M^k \bmod p$$

where $M$ is the message, $C$ is the ciphertext, $k$ is a (secret) key (any integer relatively prime to $p-1$), and $p$ is a large public prime.

Decryption can be done as:

$$M = C^{k^{-1} \bmod p-1} \bmod p$$

To address your requirement, given $k_{A_1}, k_{A_2}$, you can select a random $k_{B_1}$ (relatively prime to $p-1$), and then compute $k_{B_2} = k_{A_1} k_{B_1} k_{A_2}^{-1} \bmod p-1$, and Bob's your uncle.


Can (EC)DH keys be used as the signed content in X.509 certificates? From Wikipedia's article on ECDH:

  The public keys are either static (and trusted, say via a certificate)…

Also see this question on this very site.

These indicate to me that a certificate (maybe an X.509 certificate) can have a(n) (elliptic curve) Diffie-Hellman public key as the data that is authenticated by it. Is this true?

Yes, but it isn't that common and you may therefore have trouble finding implementations of it. Dave already pointed out in the other answer that you may need to use the OpenSSL API (which is a lower level crypto-API, not just SSL/TLS) rather than using the command line.

Please look at the following in the X509 RFC 5280:

  4.1.2.7.  Subject Public Key Info

  This field is used to carry the public key and identify the algorithm
     with which the key is used (e.g., RSA, DSA, or Diffie-Hellman) (emphasis mine).

When used with TLS:

With a static DH key you would be using ephemeral-static Diffie-Hellman. That means that such a key is normally only used to authenticate the key agreement protocol. That also means that this protocol won't be providing forward secrecy.


Comparing two values without revealing them Suppose Alice wants to prove to Bob that t1 is less than t2. t1 and t2 represent timestamps. Alice does not want to reveal t1 and t2. However, she needs to receive Bob’s confirmation that t1 < t2. In order to prevent Bob from performing a brute-force attack to find t1 and t2, Alice wants to use some salt with the timestamps.

Any idea how to use cryptographic algorithms in order to solve this problem?

From the last part of your question, I understand that you need order preserving hash function or encryption. Look into this thread
How does order-preserving encryption work?


Byte At A time ECB Attack This is my first post on stack overflow/stack exchange so please excuse me if I asked the question in a bad way or the format is bad.
I am currently working through the cryptopals challenges and I got stuck on this one: https://cryptopals.com/sets/2/challenges/12 where you basically need to figure out a secret by extracting one byte a time exploiting AES-ECB (You are given a function which encrypts usertext + secret and encrypts it with AES-ECB). I understand why this attack works but what I don't understand is how we can extract more than one block size worth of bytes of the secret. Because let's say for block size = 8. We do the attack and discover the first eight bytes of secret, how can we get all the other bytes of secret as whatever amount of bytes we will enter now only parts of the first block size of secret will get discovered.

You have and oracle call of
$$O(\texttt{your-string}) = (\operatorname{AES-128-ECB}(\texttt{your-string} || \texttt{unknown-string})$$
Since you know that the AES has 16-byte block cipher and it uses CBC, request;
$$C = O(\texttt{AAAAAAAAAAAAAAAx})$$ from oracle, where $\texttt{x}$ is the first byte of the random key.
Now ask to oracle  these encryptions $$C = O(\texttt{AAAAAAAAAAAAAAA[a..zA..Z]})$$ and see which character is equal to $\texttt{x}$, sat $1$
Now once we determine the $\texttt{x}$, we can move to the next one. Request from Oracle;
$$C = O(\texttt{AAAAAAAAAAAAAAxy})$$
Now ask to oracle these encryptions $$C = O(\texttt{AAAAAAAAAAAAAAx[a..zA..Z]})$$ and see which character is equal to the second byte $\texttt{y}$ of the string, say $2$
With this method, we can get 16 bytes of the secret. What about if there are more. Request
$$C = O(\texttt{AAAAAAAAAAAAAAA1})$$
then request this will provide the next block's encryption as the input
$$\texttt{234567890abcdef}$$, where you know $\texttt{234567890abcde}$ but not $\texttt{f}$, but you got the encryption of this block. Now ask the oracle
$$C = O(\texttt{234567890abcde[a..zA..Z]})$$
to determine the 17th byte $\texttt{f}$, the rest is similar.


Searchable Symmetric Encryption VS Deterministic encryption? I am a beginner learning about encryption. The Searchable Symmetric Encryption is better than Deterministic encryption? When I say better I mean smaller leakage.

Comparision is not possible between Searchable Symmetric Encryption (SSE) and Deterministic Encryption (DE). The reason is given below:

DE is an encryption scheme with the property that it always generates the same ciphertext for the same message. Hence, this is more prone to Guessing Attacks.
Examples of DE are Unpadded RSA, AES with ECB mode, and Order Preserving Encryption etc.

SSE is Crypto paradigm that facilitates searching over the encrypted data. You can use DE as an encryption scheme in SSE for encrypting the data and then make it searchable with the help of searchable indexes. However, the output of this SSE could be more prone to Guessing Attacks because DE was used in SSE.


Low entropy - how does it compromise the crypto One of the often pointed out mistake in dealing with crypto is not having enough entropy in the system. Without enough entropy the random numbers generated are not random enough.

But what I am not able to piece together is how exactly the lack of randomness can lead to less secure systems. In what does a key generation on a low entropy system make it vulnerable for attacks ?

If the adversary can guess the key, then they can do all the things that a legitimate user can do: decrypt secret messages, sign statements transferring money to their accounts, etc.  The min-entropy of the process used to generate keys must be high enough that the adversary has no hope of guessing the generated keys by chance.


Is it safe to store initial counter value for AES-CTR alongside with ciphertext? The initial counter value can actually be thought of as a sort of IV, which I assume is safe to transmit with the ciphertext, but I really want to be sure that this is indeed safe.

It is an IV and it is safe to transmit with the ciphertext (if it wasn't, we would call it a key).


Where does the range of possible values in Bleichenbacher's attack against PKCS #1 come from? In Bleichenbacher's paper on his attack against PKCS #1, we find:

If the oracle says that $c'$ is PKCS conforming, then the attacker
knows that the  first two bytes of $ms$ are $\mathtt{00}$ and $\mathtt{02}$. For
convenience, let $$B = 2^{8(k−2)}.$$
Recall that $k$ is the length of $n$ in bytes. Hence, that $ms$ is
PKCS conforming implies that
$$2B \ \leq\  ms \bmod n \ <\ 3B$$

I know that if $c'$ is PKCS conforming, that means that $2 \times 16^{k-2} \leq c' < 3 \times 16^{k-2}$ (because the two most significant bytes of $c'$ are $\mathtt{00}$ and $\mathtt{02}$). I clearly understand why the size of the range from above is $2^{8(k−2)}$, but I don't see where the lower bound come from. Can someone please explain?

if $c'$ is PKCS conforming, that means that $2 \times 16^{k-2} \leq c' < 3 \times 16^{k-2}$

Uh, no. $k$ is the number of bytes, not hexadecimal nibbles. That must be made
$$2 \times 256^{k-2} \leq c' < 3 \times 256^{k-2}$$
where $256=2^8$ because a byte holds 8 bits. And then it comes
$$2 \times {(2^8)}^{k-2} \leq c' < 3 \times {(2^8)}^{k-2}$$
and from that
$$2\times2^{8(k-2)} \leq c' < 3\times2^{8(k-2)}$$
Finally, with $B\ =\ 2^{8(k−2)}$ and $c'\ =\ ms\bmod n$ it comes
$$2\times B \ \leq\  ms \bmod n \ <\ 3\times B$$
which is the intended meaning of
$$2B \ \leq\  ms \bmod n \ <\ 3B$$


How can I follow the validation and verification recommendations of the NaCl (sodium) secretbox library? I was advised to use crypto_secretbox_xsalsa20poly1305 due to its simplicity and because it's safe against timing attacks. I'm reading the secretbox tutorial, and there's a link to Validation and Verification regarding message length. In that, in the last paragraph, it says the following:

  Tests are currently limited to 4096-byte messages. This is one of several reasons that callers should (1) split all data into packets sent through the network; (2) put a small global limit on packet length; and (3) separately encrypt and authenticate each packet.

Now I don't understand who's the "caller" here. Is it me in my application or the NaCl library? From requirement (1) it seems it's me. From requirement (3) it seems it's NaCl, because I don't have control on separating encryption and implementation, because both happen in one call of crypto_secretbox_xsalsa20poly1305.

So I guess my question is: If I have a message whose length is longer than 4096 bytes, should I manually split it when using crypto_secretbox_xsalsa20poly1305, encrypt and authenticate each, then combine them together in a certain way as my final cipher?

This is advice to you, the application protocol designer, on how to use the cryptography.  The word ‘separately’ applies to the packets, not to encrypt and authenticate: use crypto_secretbox_xsalsa20poly1305 for one ≤4096-byte packet at a time.

You should split longer messages into ≤4096-byte packets with sequence numbers.  This way:

The most memory an adversary can force the receiver to waste at a time by sending forgeries is 4096 bytes.
The least bandwidth that the sender needs in order to make progress during a denial of service attack is 4096 bytes.


Definition of a distinguisher In Introduction to Modern Cryptography by Katz and Lindell, p. 70, they define a pseudorandom generator by:

  Let $l(\cdot)$ be a polynomial and let $G$ be a deterministic
  poly-time alg. s.t. for any input $s \in \{0,1\}^n,$ algo $G$ outputs
  a string of length $l(n).$ We say $G$ is a pseudorandom generator if
  the following conditions hold:

  (Expansion) For every $n$ we have $l(n)>n$

  (Pseudorandomness) For all probabilistic poly-time distinguishers $D,$
  there exists a negligible function $negl$ s.t. $$\left| P[D(r)=1] - P[D(G(s))=1] \le negl(n) \right|,$$ where $r$ is chosen unif. at random
  from $\{0,1\}^{l(n)}, $ the seed $s$ is chosen unif. at random from
  $\{0,1\}^n,$ and the probabilities are taken over the random coins
  used by $D$ and the choice of $r$ and $s.$

I would like to clarify how we should be thinking about the distinguisher, $D$. I understand that it is typically any polynomial-time algorithm, but how do we interpret its output? Do we assume that when $D$ "thinks" its input is truly random then it outputs a $1$, and otherwise outputs a $0$?

I think of it this way: think of a distinguisher as an adversarially-chosen statistical experiment that attempts to support or refute some hypothesis, that again is adversarially selected.  This means that the honest party doesn't get to assume what meaning the adversary assigns to $0$ or $1$; their PRG has to behave like a random distribution no matter what the adversary does (with the proviso that the adversary's experiment must complete within polynomial time).

For example, a distinguisher could be an algorithm that takes the output of the PRG, chooses a random position in the bit string, tests whether the bits starting from this location are equal to some ASCII representation of the Gettysburg Address, and outputs $0$ if they are, $1$ otherwise.  If that's the statistical test the adversary wants to use, they can do it.


What is "witness encryption"? I recently skimmed over tho papers on time-lock encryption:

“Time-release Protocol from Bitcoin and Witness Encryption for SAT” by Liu, Garcia, and Ryan
“How to Build Time-Lock Encryption” by Jager

To get the data released on a specific point in time they'd extract some information from the blockchain, which can only be obtained if the blockchain has reached a certain size) and use this as a witness for witness encryption:

Is there any "easy" instance of witness encryption or can it be otherwise "simply" explained or visualized?

Requested level and amount of detail: Enough to understand how easy versions work and what they actually do. Knowledge of cryptographic standard primitives (hash, cipher, AE, …) can be assumed if neccessary.

In very short:

Assume you have an NP problem, stated as some condition to be met. Since it is a NP condition, the computational complexity to find a satisfying input (called the witness for the language) grows quite fast.

The setup of such an encryption scheme is based on a multilinear map (a generalization of a bilinear map, but with arbitrary many inputs). And then you only need to know the NP statement to encrypt something, but you need a witness of the according length to decrypt the ciphertext again.

The actual construction is really complex, and I don't think you can explain that in easy terms. But it is based on multilinear maps, and look at DrLecters answer in "What are Cryptographic Multi-linear Maps?" for more information on that. Current constructions build on fully homomorphic encryption.


EdDSA point encoding difference between documentation and implementation The RFC 8032 describes the point encoding like this :

A curve point (x,y), with coordinates in the range 0 <= x,y < p, is
coded as follows.  First, encode the y-coordinate as a little-endian
string of 32 octets.  The most significant bit of the final octet is
always zero.  To form the encoding of the point, copy the least
significant bit of the x-coordinate to the most significant bit of
the final octet.

And implements it like this :
def point_compress(P):
    zinv = modp_inv(P[2])
    x = P[0] * zinv % p
    y = P[1] * zinv % p
    return int.to_bytes(y | ((x & 1) << 255), 32, "little")

Could you explain the meaning of the word "copy" in this sentence "copy the least significant bit of the x-coordinate to the most significant bit of the final octet" ? Why isn't the bit copied in the code ? Why is it just a bitwise OR ?

Could you explain the meaning of the word "copy" in this sentence "copy the least significant bit of the x-coordinate to the most significant bit of the final octet" ? Why isn't the bit copied in the code ? Why is it just a bitwise OR ?

First of all note that;

# Points are represented as tuples (X, Y, Z, T) of extended
# coordinates, with x = X/Z, y = Y/Z, x*y = T/Z

So the zinv comes from there and

x = P[0] * zinv % p
y = P[1] * zinv % p

Uses to find x and y
Now the last line does what the RFC describes in a simple way.

int.to_bytes(y | ((x & 1) << 255), 32, "little")

The code is just a demonstration of the result. In your programming environment, you can use copy bit by bit, and it will be way slower.
A bitwise or operation is much faster than bit by bit copy. Also, as you can see there are no range check or if to check boundaries. Since the formula is fixed you can use whatever optimization is needed as longs as your code doesn't leak information.
Final note: you restrict yourself with the bit-by-bit copy. Doesn't the result copy the values into the return value?


What are the steps for decryption of RC4? I've seen a lot of algorithms posted everywhere about how to encrypt using RC4. For example, this wiki article https://en.wikipedia.org/wiki/RC4 explains the KSA and PRGA steps.

After it generates bytes, they are XOR'd with a message to encrypt the message. What are the steps for decrypting the message when it is received by the intended entity?

It's probably the inverse of KSA / PGRA, but can someone write out the steps for it? I've tried looking online and can't find an article on it, and I'm trying to fully understand the decryption part of it.

What I'm guessing is, the entity receiving the message generates the same bytes using the key as well (with the KSA / PRGA algorithm), then XORs the encrypted message with the bytes?

Your guess is correct. RC4 basically generates a very long key to fit your message. Encryption and decryption is simply xoring with the output of RC4 for that particular position in the key stream.

In general, most stream ciphers work that way. The complex part is that the algorithm should generate a very long key that is not susceptible to attack (the ideal being a one-time pad of the same length as the message).

So once you understand encryption using RC4, switch "plaintext" and "ciphertext" in the explanation to give you decryption.

edit: you probably know this already but it doesn't hurt to reiterate: don't use RC4.  It is not secure and can be broken.


For WinRar, how long should a password be to make up for a lack of complexity? Assuming that the best alternative to complexity is length, how long do you recommend a password or phrase to be when using WinRar?

Note that I'm aware that it's not always that simple, but I would like to get this right.

how long do you recommend a password or phrase to be when using
  WinRar?

This very much depends on how you choose your passwords. The "right" answer can be anything from 11 characters to 200 characters.

So assuming fgrieu's research is correct (it usually is), the PBKDF uses at least $2^{15}$ rounds of hashing, giving us effectively 15 bits of security "for free". Now with the target being 100-bit security (which is reasonably secure for most intents and purposes), this leaves 85-bits to go. Now assuming you use the full ASCII-Range and good cryptographic randomness, this is about 11 bytes, or 11 characters. However assuming humans being humans, you will get much less randomness from short passwords. A conservative estimate would be 40 characters (with a bit more than 2 bits of entropy per character) and a more aggressive estimate would be 16 characters (assuming nearly fully random pick from upper- and lower-case latin letters).


What is total key space in transposition algorithms How we can measure key space in transposition algorithms? Should we specify the method, like rail fence?

Measuring the size of the key space in transposition algorithms is not important, because their security is far less than the size of the key space would suggest.  Therefore, any measure of effective key length will be misleading and will not give an accurate picture of the true security of the scheme.

In general the standard way to compute the effective key length of a cryptographic algorithm is as follows: we let $K$ denote the set of all possible keys for that algorithm; then the effective key length is $\lg |K|$, where $|K|$ denotes the size of the set $K$ and $\lg$ denotes the logarithm to base 2.


Can the knowledge of the inverse of $p$ modulo $q$ help factor $n=pq$? With the RSA algorithm implemented using the Chinese Remainder Theorem (CRT), the private key has to be provided with not only $p$, $q$ and the private exponent $d$, but often also with the pre-computed value $q^{-1} \bmod p$ for a faster recombination using the CRT.

Assuming that $q^{-1} \bmod p$ is leaked to the adversary (but not $d$, $p$ and $q$ themselves), does that help factor $n = pq$? And if so, how?

This question was already answered in this not-so-great titled question.

($p$ and $q$ being "safe primes" does not matter in this context, but $q$ shouldn't be (much) longer than $p$, as the methods works for $q<p$, but can be adapted by "guessing" the top bits of $q$ otherwise).


Supersingular Isogeny Key Exchange broken? Found this report detailing a quantum algorithm for computing isogenies
between supersingular elliptic curves.

http://cacr.uwaterloo.ca/techreports/2014/cacr2014-24.pdf

with the quote "recommendation
to avoid using base curves defined over Fp in De Feo-Jao-Plut type
schemes".

Is it correct then that 'Supersingular Isogeny Key Exchange' of De Feo is broken?

If so, as this is a fast moving field, are there any recommendations for alternate post quantum key exchange with reasonably good key size and speed?

Thank you.

Sorry I will have to answer my own question.

I received a mail from Luca De Feo a moment ago.
"Nope, I discussed this at length with Jean-François Biasse, and we couldn't find a way to apply this kind of attack to SSIKE."

I'll leave this question around for reference for the next person who wonders.


Stream cipher malleability Considering a stream cipher that produces a ciphertext $c$ from a message $m$ and a key $k$ is it possible to apply operations (multiplication and/or addition) directly to $c$ without knowing the key ?

Example : $m$ > encrypt > $c$ > $c+5$ > decrypt > $m+5$

I can not manage to get a valid $m$ at the end. I tried to work with hex values, binary data… no success so far. Could you please confirm if this kind of operation is possible on AES-ctr / Xsalsa20 (this one uses nonces) and how to properly do it? Thanks !

AES in counter mode works by XORing the output of an encrypted counter against the plain-text. This easily allows you to flip bits in the ciphertext and have that bit flip in the plain-text.

The easiest way to get the kind of behaviour you're looking for is rather than XORing the encrypted counter against the plain-text, add it mod $2^{128}$. Decryption proceeds by subtracting the encrypted value mod $2^{128}$.

Then if you deduct $5\mod 2^{128}$ from the ciphertext, that deduction will also affect the plain-text.

This is because:

$c = m + AES(counter,k) \mod 2^{128}$

$m = c - AES(counter,k) \mod 2^{128}$

So:

$c+5 = (m + AES(counter,k))+5 \mod 2^{128}$

$c+5 = (m + AES(counter, k)+5) \mod 2^{128}$

$c+5 - AES(counter, k) = (M+ AES(counter, k) - AES(counter,k) + 5) \mod 2^{128}$

$c+5 - AES(counter, k) = m+5 \mod 2^{128}$

$(c - AES(counter, k)) + 5 = m+5 \mod 2^{128}$

We can then clearly see that the left hand side is the decryption equation + 5 and this five is carried through in to the plain-text.


How does the birthday paradox apply to random keys? I'm developing a web app where I wish to use pseudorandom keys for items, perhaps akin to Imgur. I was thinking about how many combinations I need to reduce the chance of someone guessing any random item in the database (by checking the associated URL) to x. On the performance side, it would seem to be the same (similar?) problem when I'm generating new keys randomly to avoid an excessive hit from repeated collisions.

From the birthday attack article, roughly, the number of options there needs to be (H) for a 50% chance of collision is sqrt(H). So, even if I have 10 billion (1010) possible keys, someone only needs to guess 100 thousand (105) to get a collision...

Something seems severely off with my understanding of the math: if I only have a couple thousand keys used (or lets say 1) out of billions possible, it seems like the chance to randomly find it would be one in a billion.

What's relevant for me I suppose is given the number of entries I expect, and some tolerance for a possible attacker to randomly find one of said entries, how many choices do I need? Naively I'd just say it's

  num_possible_key_values >= expected_entries / max_probability_to_randomly_find_one

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys.

So if I plan to accommodate in the ballpark of 10,000 entries, and want it to take a million random guesses to get lucky and find one, I should only need 10,000 * 1,000,000 keys.

Yes, this is correct.  If you have $n$ (randomly chosen) valid keys out of $N$ total, then the probability of a single key being valid is $p = n/N$, and so the average number of keys one needs to test to find a single valid one is $1/p = N/n$.

Where the birthday paradox comes into play is in key generation.  Specifically, if you have a total of $N$ possible keys, and you independently and randomly pick $n$ of these possible keys to be valid, then there's a risk that some of the keys you pick will be identical.  In particular, the expected average number of duplicate pairs will be $(n^2-n)/(2N)$.  (This is also an upper bound on the probability of there being at least one duplicate; this upper bound is a good approximation of the true probability whenever it is much less than one, i.e. when $n \ll \sqrt N$.)

What this means, in practice, is that if the number of valid keys $n$ is much less (say, less than one thousandth of) the square root of the total keyspace size $N$, then you probably don't need to worry about collisions in key generation at all, since the probability of having even a single collision is less than one in a million.  Once the $n$ gets closer to $\sqrt N$, though, collisions become likely, and you will need to implement a mechanism for dealing with them.

(If you have a centralized database, dealing with collisions is pretty trivial; just pick a new random key and repeat.  This is very efficient unless your keyspace is almost full (say, $n > N/2$), in which case you have bigger problems than slow key generation anyway.  In some crypto schemes, however, one needs to avoid collisions without using any kind of central key database.  In this case, the only possible solution is to increase the keyspace size far above the square of the highest foreseeable number of valid keys, so that having even a single collision becomes extremely unlikely.)


How to encrypt letters less than block n using Hill Cipher I am learning about Hill Cipher and know that it is a block cipher where each block of n letters (considered as an $n$-component vector) is multiplied by an invertible $n \times n$ matrix, again modulus $26$.

The article did not touch on what happens if the the block of letters is less than length $n$.

Eg: Assume I am supposed to encrypt 100 letters – how do I encrypt the last 22 letters?

I was thinking of padding similar to MD5, or are there other methods to resolve this issue? If so, what are those methods?

Since it's a linear cipher, you should be wary about a guessable padding, otherwise if your last block is only one char long, you will reveal almost your whole matrix on this last block. If you're too afraid of mangling the last word, use something like 'Z'+(random chars). But I really would not use any predictable padding with such a cipher.


Adding an IV to an AES implementation I have an embedded project that requires AES, I seem to have found an AES implementation that fits the bill here: http://www.literatecode.com/aes256, but it does not include an IV.

Are there any documents detailing the standard way to implement an IV? I looked up the FIPS 197 spec and there is no mention of an IV.

AES is  a block cipher which actually only "maps" (encrypt) a 128 bit block (plainblock) to a 128 bit block (cipherblock) and vice versa. This "mapping" is key dependent.

To encrypt some data you normally apply an encryption mode like CBC, CTR, GCM etc. using e.g. AES as block cipher within this mode. These modes normally require an IV or Nonce.

So, not the actually AES requires an IV but the mode used to actually en-/decrypt data.


Perl DES PCBC as protection against decryption/crypt analysis Is error propagation in DES PCBC a good method to prevent decryption/crypt analysis by third parties?

If I had a very large file encrypted with Perl's DES with the PCBC option, and then removed the first megabyte of the resulting ciphertext would this render the remaining ciphertext 100% immune to crypt analysis ? Why or why not? Suppose that the missing 1 megabyte file disappeared forever would the ciphertext never be able to be decrypted? I'm assuming that too much information is being lost by not having the first megabyte of the ciphertext for it ever to be decrypted or any further information about the plaintext to be discovered.

What if the data was encrypted first in AES-CBC for more protection and then re-encrypted with DES PCBC for the intended error propagation? Could this weaken it or would it strengthen it slightly?

I am considering using the PERL DES cipher with the PCBC option since this seems to be the easiest and fastest way to implement this.

This is actually a good question, about how a mode of operation will affect analysis of a data stream.

In regards to an implementation of AES-PCBC, if you have AES-ECB you can build a wrapper for PCBC around it with the appropriate block size. It is not too difficult, but unnecessary...

In regards to security analysis, PCBC is no more resistant than CBC with an unknown Initialization Vector, since upon decryption the only difference between the modes is that the previous block input is only 1 value.

This will make decryption slower since it can not be decoded in parallel, but brute forcing the key space CAN be done in parallel. Once the correct combination of mode input and key are found, the entire remaining data stream will be correctly decrypted. The brute force of the IV/prior block is faster than the key, since no key change is required. DES is a 64-bit block, which means it has a small IV, and that makes your Key/IV search combination theoretically feasible with appropriate hardware (not now, but in the future yes).

The error propagation aspect of the mode was desired before widespread use of message authentication codes, modern cryptography sees error propagation through a mode as unnecessary. There are other applications that may prefer error propagation, but data at rest is not one of them. The downsides of error propagating modes (mostly performance) do not make up for any perceived advantage in security.

A bad mode is bad, but a good mode does not make a good cipher any better, and DES just isn't good enough anymore.


Why the exponent is a power of 2 in Ring-LWE? I was reading some papers on Ring-LWE. I found almost all of them talk to choose the polynomial modulo $x^n+1$ where $n$ is a power of $2$. I did not understand why this condition is necessary?

As @Raoul722 pointed out the polynomial should be irreducible.

One should also add the fact that in the original Ring-LWE article security proofs hold by sampling the error with a spherical distribution and the poly $f=x^{2^n}+1$.

In How (Not) to Instantiate Ring-LWE, from Invulnerability instantiations subsection it's specified that you could in fact select any number field and still be a hard problem but then you have to change the error distribution.

To answer your question, the reason is just to make proofs easier.


Finding roots in $\mathbb{Z}_p$ Is there an efficient way (algorihtm) to compute the solutions of the congruence $x^n\equiv a \pmod p$?

$n\in \mathbb{N}$
$a\in\mathbb{Z}_p$
$p$ is a large prime number

Note that:

By efficient I mean computationally efficient even when the given prime $p$ is appropriate for use in cryptographic protocols (hard to find discrete logarithm in $\mathbb{Z}_p$)
We do not know the prime factors of $p-1$.

It’s easy to find one solution when $\gcd(n,p-1)=1$.

I think this should be as hard as finding a Discrete Logarithm or as Factoring. Any ideas ? Thank you for your time.

This is an extended but still partial attempt at an explicit solution.

Since $p$ is prime, Fermat's little theorem tells us that:

$\forall z\in\mathbb Z_p, z^p\equiv z\pmod p$.
$\forall z\in\mathbb Z_p^*, z^{p-1}\equiv1\pmod p$.

We settle some easy cases:

If $n=0$ and $a\equiv 0\pmod p$, our equation $x^n\equiv a\pmod p$ is ill-defined.
If $n>0$ and $a\equiv 0\pmod p$, the solution is $x\equiv0\pmod p$.
If $n\equiv0\pmod{p-1}$ and $a\equiv 1\pmod p$, any $x\not\equiv0\pmod p$ is solution.
If $n\equiv0\pmod{p-1}$, $a\not\equiv 0\pmod p$ and $a\not\equiv 1\pmod p$, there is no solution.
If $n\equiv1\pmod{p-1}$, the solution is $x\equiv a\bmod p$.

In all the other cases, $x\equiv0\pmod p$ will not be a solution, and we can reduce $n$ modulo $p-1$ to obtain an equivalent equation. From then on, we will assume $1<n<p-1$, $a\not\equiv0\pmod p$, $x\not\equiv0\pmod p$, and proceed to solve our equation $x^n\equiv a\pmod p$.

As pointed out in the question, things are easy when $\gcd(n,p-1)=1$: the only solution is $x\equiv a^{n^{-1}\bmod(p-1)}\pmod p$. Proof: For the stated $x$, we have $x^n\equiv a^{(n^{-1}\bmod(p-1))·n}\pmod p$; thus $\exists k\in\mathbb N, x^n\equiv a^{1+k·(p-1)}\pmod p$; thus $x^n\equiv a\pmod p$; thus the stated $x$ is a solution of our equation. The function $z\mapsto z^n$ is thus a surjective function over the finite set $\mathbb Z_p^*$, thus a bijection, thus there is no solution other than the stated one.

If $\gcd(n,p-1)\neq 1$, let it be $m$, with both $n/m$ and $(p-1)/m$ integers. We find $b$ such that $b^{n/m}\equiv a\bmod(p-1)$ by the above method; that is: $b=a^{(n/m)^{-1}\bmod(p-1)}\bmod p$. Solving $x^m\equiv b\pmod p$ is equivalent to our original equation.

By raising to the power $(p-1)/m$, we see that $x^m\equiv b\pmod p\implies 1\equiv b^{(p-1)/m}\pmod p$. Thus if $1\not\equiv b^{(p-1)/m}\pmod p$, which we can check, there is no solution.

This test is quite useful; for example when $p=71$, $n=55$, $a=2$, we have $m=5$, $(n/m)^{-1}\bmod(p-1)=51$, $b=3$, $b^{(p-1)/m}\bmod p=54$, thus no solution, and that's the case for most $a$. But for $a=20$ we get $b=45$, $b^{(p-1)/m}\bmod p=1$, and indeed there are $5$ solutions $\{18,19,24,32,49\}\pmod p$.

We can thus restrict to solving $x^n\equiv a\pmod p$ when $n$ divides $p-1$, $n>1$, and $a^{(p-1)/n}\equiv 1\pmod p$ (we have shown that any other $a$ leaves the equation without solution, except $a\equiv 0\pmod p$; and we have an efficient method to reduce to that case for any other $n$).

That equation has exactly $n$ distinct solutions $\pmod p$. Proof: by the fundamental theorem of algebra, any polynomial of degree $n$ in the field $\mathbb Z_p$ has exactly $n$ roots, counted with multiplicity; applying that to $x^n-a$ we see that $x^n\equiv a\pmod p$ has at most $n$ solutions $\pmod p$; similarly there are at most $(p-1)/n$ solutions in $a$ to the equation $a^{(p-1)/n}\equiv 1\pmod p$; thus the function $z\mapsto z^n$ over the finite set $\mathbb Z_p^*$ maps at most $n$ elements to any element, and at most $(p-1)/n$ elements have a preimage; by a counting argument, every element with a preimage thus has exactly $n$ preimages.

It follows that we can not aim at finding all the solutions in time polynomial w.r.t. $\log p$ for arbitrary $n$: there are too many solutions when $n$ is big, e.g. $n=(p-1)/2$. We can still aim at finding one solution, or perhaps the smallest one.

When $(p-1)/n$ is small, there is an efficient and trivial probabilistic algorithm that finds a solution: pick a random $x$, and check if $x^n\equiv a\pmod p$, until a suitable $x$ is found; that is expected to require $(p-1)/n$ steps. By trying $x$ sequentially starting from $2$, we can find the smallest $x$.

If the exponent $n$ is even, we can change the unknown to $y\equiv x^{n/2}\pmod p$ and first solve $y^2=a\pmod p$, which is the well-studied problem of finding a square root modulo a prime. By applying this recursively, we can remove the powers of $2$ from the factorization of $n$. Assuming a polynomial-time algorithm finding a solution for any odd exponent $n$, our resulting algorithm would find a solution and work for any exponent, while remaining polynomial in $\log p$ after reduction of the exponent $n\pmod p$.

This is studied and generalized by Adleman-Manders-Miller, solving the problem in time polynomial w.r.t. $\log p$ for fixed $n$. Their algorithm is (at worse) linear w.r.t. $n$ (not $\log n$), and as an aside requires the factorization of $n$.

This might be improved by Barreto-Voloch, and perhaps these two re-visitations of Adleman-Manders-Miller and Barreto-Voloch.

[To be continued. Feel free to improve this community wiki, e.g. by including a description of Adleman-Manders-Miller; I'll have no time to do that in the following week.]

An instance of the original problem with random exponent has a fair chance of being solvable with the above techniques. I have the feeling do not know if this is easier than discrete logarithm modulo $p$ even in the harder cases, like $n\cdot k=(p-1)$ with $k\approx\sqrt{p-1}$, and $p$,$k$,$n$ are primes.