IND-CCA insecurity of modified CBC encrypt + MAC scheme I've been puzzling over the following proof for the past couple of days.

Since a block cipher in CBC mode can be used to build both an IND-CPA secure
encryption scheme and a EUF-CMA secure block, a common mistake made in “roll-your-own”
cryptosystems is to try to use the last ciphertext block to compute a MAC on the plaintext,
e.g. to encrypt the message m, we compute the ciphertext $c = \verb|CBCEncrypt|^E
_K(m)$, let $c^∗$ be
the last block, compute tag $\tau = E_K(c^*)$. and use $⟨c, τ⟩$ as an “authenticated encryption”
scheme. Prove that this scheme fails to provide chosen-ciphertext security.

I'm making the assumption that an encryption oracle for $\verb|CBCEncrypt|^{E}_K(m)$ uniformly chooses an IV and then makes it public after encryption. Also, $E_K$ is the block function.
One security issue that comes to mind is that the tag of a message in this scheme relies only on the last block of ciphertext, not the rest of the message. However, since each IV is random and unpredictable, I don't see how an adversary could exploit this.
Another thought I had was if an adversary could compute a valid tag $\tau_{\tau}$, then they could decrypt $⟨\tau, \tau_{\tau}⟩$ and check whether or not the resultant decryption (with IV=0) is equal to the last block of the corresponding ciphertext $\tau$ was generated from. But again, I can't see how an adversary could compute $\tau_{\tau}$.
Any help would be appreciated.

One security issue that comes to mind is that the tag of a message in this scheme relies only on the last block of ciphertext, not the rest of the message.

So, what would happen if the adversary took a valid $⟨c, \tau⟩$ pair and modified $c$ by repeating the last block, that is, converting it into the pair $⟨c || c^*, \tau⟩$ and forwarding that to the decryptor?
Would the modified ciphertext pass the integrity check?
Bonus question (to make the attack even worse): if it did, what would the resulting plaintext look like?


How can we prove that the scrambled G matrix in McEliece cryptosystem preserves the minimum distance properties of G matrix? In McEliece cryptosystem, G matrix is scrambled using S and P so that scrambled G matrix is G' = SGP. Here G is the generator matrix of a linear code and after scrambling it is converted into another matrix G' of the same size. How can we ensure that G' is another possible G matrix of the code with same distance properties? Is there any proof for that? If G' satisfies all the properties of G, will this hold any linear code other than Goppa code also?

edit

Encryption

c = mSGP + e

Here mS will give you another k element vector which forms the message for the permuted version of the G matrix, GP.
Now my question is whether the permuted G matrix results in another valid G matrix.
Are there any properties to be satisfied by P matrix?

$P$ is required to be a permutation matrix. Thus, the effect $P$ has on $G$ is simply to reorder its columns. Crucially, this does not change the weight of any of the codewords. Note that this holds irregardless of the code; be it Goppa or something else.

More concretely, suppose $G$ is any $(n,k,d)$ code. This means that $G$ can correct up to $\frac{\lfloor d \rfloor}{2}$ errors. So let $d' \leq \frac{\lfloor d \rfloor}{2} $ be the weight of $e$. Now suppose
$$c = mSGP + e.$$
On decrypting $c$ we first apply $P^{-1}$ to $c$ to get
$$ c' = cP^{-1} = (mSGP + e)P^{-1} = mSGPP^{-1} + eP^{-1} = mSG + e'. \tag{1}$$
You see that the r.h.v. in (1) is simply a codeword in the code generated by $G$ with an added error of $e'$.
But the inverse of a permutation matrix is also a permutation matrix, so the vector $e'$ also has weight $d' \leq \frac{\lfloor d \rfloor}{2} $.  Consequently, we can apply the decoding procedure of the code to get rid of $e'$ and obtain $mS$. Since $S$ is invertible, we can obtain $m$ by multiplying with $S^{-1}$ on the right.


PSI protocol reveals only one element of the intersection of two sets So let Alice has a set of integers, says, $A = \{a_1,\dots, a_n\}$, similarly, Bob has a set of integers $B=\{b_1,\dots, b_n\}$.

is there any protocol that allows Alice and Bob to randomly learn exactly one element from the intersection, $A\cap B$? I am aware of few private set intersection algorithms, but all of them reveal the whole intersection.

In fact, one possibility is to use the generic garbled circuit protocol that implements a PSI circuit + a filter circuit such that the result (intersection) from the PSI is filtered and only one randomly chosen element in the intersection is output at the end of the protocol. However, I cannot say much except this is feasible.

Below is a custom protocol for your purpose, assuming $|A\cap B|$ can be leaked and semi-honest adversaries. It can be further optimized.

You need 3 building blocks:

A PSI with data transfer protocol (see below references [1,2, 3]). A PSI with data transfer protocol is a PSI protocol such that at the end of the execution, Bob gets nothing and Alice gets for each element $a_i$ in her set, a piece of data $d_i$. If we just want PSI, then if $a_i$ is not in the intersection $d_i$ is a random string, otherwise if $a_i$ is in the intersection $d_i$ is $a_i$ itself. So that after running the protocol, Alice gets the intersection. The trick we will use relies on the fact that it is entirely possible to let $d_i$ convey other information than just the set element.
A semantically secure encryption scheme $(\mathcal{G},\mathcal{E},\mathcal{D})$ in which the ciphertext can be efficiently re-randomized. Here $\mathcal{G},\mathcal{E},\mathcal{D}$ are the key generation, encryption, decryption algorithms. One example is Paillier. For any ciphertext $\mathcal{E}_{pk}(m)$, one can re-randomize it by generating a fresh encryption of 0, $\mathcal{E}_{pk}(0)$, and use the homomorphic property to get a new ciphertext $\mathcal{E}_{pk}(m)*\mathcal{E}_{pk}(0) = \mathcal{E}_{pk}(m+0)= \mathcal{E}_{pk}(m)$. The new ciphertxt encrypts the same plaintext but looks totally different.
A sementically secure symmetric block cipher $(G,E,D)$.

In the protocol, Alice has a set $A$, Bob has a set $B$. Bob also generates a key pair $(pk,sk)=\mathcal{G}(\lambda)$ ($\lambda$ is a security paramter). Bob gives $pk$ to Alice. Then they do the following:

Bob generates a random key $k_1=G(\lambda)$, then use the block cipher to encrypt all his elements $E_{k_1}(b_1),\ldots,E_{k_1}(b_n)$.
Bob and Alice run the PSI with data transfer protocol, such that Alice uses her set as input, and Bob for each his element $b_i$, send a data payload $(\mathcal{E}_{pk}(1),E_{k_1}(b_i))$,  -- note that each $\mathcal{E}_{pk}(1)$ must be generated using fresh randomness.
In total, Alice will receive $n$ pieces of data in the form of $(c_1^i,c_2^i)$. If Alice has an element $a_i =b_j$ (i.e. $a_i =b_j$ is in the intersection), Alice will receive the payload $(\mathcal{E}_{pk}(1),E_{k_1}(b_j))$, otherwise, Alice will receive a piece of random data which can be parsed as $(\mathcal{E}_{pk}(r_1),E_{k_1}(r_2))$ where $r_1,r_2$ are random. However, Alice cannot tell whether each $(c_1^i,c_2^i)$ she received is "good" or random because it is a pair of ciphertexts.
Alice generates a new key $k_2=G(\lambda)$. For each $(c_1^i,c_2^i)$ pair, Alice re-randomizes $c_1^i$ to get a new ciphertext $(c^i_1)'$, and encrypts $c_2^i$ to get $(c^i_2)'=E_{k_2}(c_2^i)$. Alice puts all pairs $((c^i_1)',(c^i_2)')$ in a set $A'$, randomly permutes $A'$, and then sends $A'$ to Bob.
Bob generates a new key $k_3=G(\lambda)$. For each element $((c^i_1)',(c^i_2)')$ in $A'$, decrypts $(c^i_1)'$, if the result $\mathcal{D}_{sk}((c^i_1)')=1$, puts $E_{k3}((c^i_2)')$ in a set $B'$. After all pairs have been processed, permute $B'$ and send $B'$ to Alice. (If $B'$ is empty then stop because the intersection is empty).
Alice randomly chooses one element $e \in B'$, sends $e$ to Bob. Bob decrypts and sends $e' =D_{k_3}(e)$ to Alice. Alice decrypts and sends $e''= D_{k_2}(e')$ to Bob. Bob decrypts and sends $e'''=D_{k_1}(e'')$ to Alice. Now $e'''=D_{k_1}(D_{k_2}(D_{k_3}(E_{k_3}(E_{k_2}(E_{k_1}(b_l))))))$ is a random element in $A\cap B$.

1 Efficient Private Matching and Set Intersection, Michael J. Freedman, Kobbi Nissim, Benny Pinkas, EUROCRYPT 2004 (link)

2 Practical Private Set Intersection Protocols with Linear Computational and Bandwidth Complexity, Emiliano De Cristofaro and Gene Tsudik, FC2010 (link)

3 When Private Set Intersection Meets Big Data: An Efficient and Scalable Protocol, Changyu Dong, Liqun Chen, Zikai Wen, CCS 2013 (link)


What is batching in homomorphic encryption? I have been reading journals about FHE schemes and I keep encountering the term "batching". What does it mean to batch in homomorphic encryption in a simple way?

In simple terms, batching means "encrypt many messages into a single ciphertext so that one homomorphic operation acts on many messages simultaneously".
This is typically done by representing the message space in a "tuple" format (via an isomorphism).
For instance, by the Chinese remainder theorem (CRT), we know that any tuple
$(m_1, m_2, m_3) \in \mathbb Z_2 \times \mathbb Z_3 \times \mathbb Z_5$
can be written as a single integer $m \in \mathbb Z_{30}$.
Thus, if you have a homomorphic scheme whose message space is $\mathbb Z_{30}$,
we can encrypt tuples
$(m_1, m_2, m_3)$
and each homomorphic operation will actually operate on three values.
In this scenario, you would start from $(m_{1,i}, m_{2,i}, m_{3,i})$,
then obtain $m_i$ via CRT, then encrypt $m_i$ into $c_i$.
Now, if you multiply two ciphertexts $c_1$ and $c_2$ homomorphically,
you obtain an encryption of
$m_1 \cdot m_2 \bmod 30$,
but this is actually equivalent to
$$(m_{1,1}\cdot m_{1,2}\bmod 2,
 \,m_{2,1}\cdot m_{2,2}\bmod 3,
 \,m_{3,1}\cdot m_{3,2}\bmod 5).$$
So, one homomorphic multiplication is multiplying three messages in parallel. Of course, instead of 3, you want a tuple with many entries.
Things work essentially in the same way for polynomials, i.e., you represent a tuple of polynomials of low degree as a single polynomial of high degree, then you encrypt it...


AES-128 (CBC) brute force given 90+ rightmost bits of key, known IV and Ciphertext? Given:
Known ciphertext (in hex) (ciphertext is the exact length of the message (i.e. non-padded). It is known that the cipher was developed using CBC. There is one and only one ciphertext message that was grabbed.  The exact ASCII range of the plaintext is known.

Known IV in Hex

Known partial key! (in binary) 91 bits (rightmost) of the key--meaning the first 37 bits are unknown.
This key is: XXXXXXXX.XXXXXXXX.XXXXXXXX.XXXXXXXX.XXXX1100.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000000.00000011

This should translate to 00000000_0C000000_00000000_00000003 in hex  unless I've done something wrong.  In the translation the 0's to the left of the "C" should be unknown (so F's in keymask).  The zeros between the x and the 3 are known "0s" and should be there.

Key mask to search this should be something like "FFFFFFFF_F0000000_00000000_00000000"

What would a method try to brute this? Is this even realistic?  Is there software already developed (open source) that already has the ability to plug in a known portion of a key, the cipher, and IV to try to brute without re-inventing the wheel?

As for complexity, wouldn't the complexity be something like $n^{37}$. since the other 91 of the key are known? Or is there another mathematical factor that I am missing here?

We can say that you need to search 37-bit keyspace that is $2^{37}$.

Brute-forcing:

You will set up a counter starting from 0 to $2^{37}$. With the given key part at each step concatenate them givenKeyPart||counter before the key schedule.

Run the key schedule, then perform the encryption to see that the ciphertexts are matching. You don't need to perform the x-or with the IV for every encryption. Do it once.

You can easily reach $2^{37}$ encryption, or say the key search for AES. You have multiple options;

You can parallelize the search over the cores or PC's
You can use AES-NI if available.
Also, if available you can use GPU's

Here a benchmark for 32-bit search with AES-NI. It takes 40.3497s to search $2^{32}$.

In my test computer the 32-bit search with AES-NI took 14.1762s with 8 core.

Performances:
    1477815830 AES128 operations done in 14.282s
    9ns per AES128 operation
    103.47 million keys per second

Therefore the expected seconds for $2^{37}$ key space is $$2^{37}/2^{32} \times 14s = 448s$$

How to identify the plaintext: One general rule when only ciphertexts are given; one can check the result is valid (English) language. Looking at the ASCII range and/or using a function similar to string can enable to eliminate the candidates. However, there might be still many candidates to eliminate. To reach the solution one may need more than one ciphertext blocks (not a new message). There was a historical RSA challanges that gave more information than these contestants. However, your case still achievable in a very short time.

Update for the comment

Given 4 Bytes, IV and 3 Ciphertext blocks, exactly 16*3-byte plaintext with no padding and ASCII range is known.

For each of the candidate key check

All characters of the first decrypted plaintex are in ASCII range
If so check the second and if so check the last.
If all in the range then it is a good candidate.
Otherwise, skip the next key.

You can use a string search mechanism or select by your eyes. If you prefer your eyes better to write all of the candidates into a file with the key information.


What's wrong with this curve (generation algorithm)? In this tweet, Paulo Barreto proposes the following elliptic curve over $\mathbb{F}_{2^{255}-19}$:

$$
E_\mathrm{PB} : y^2 = x^3 - 3x + 13318
$$

with $G_\mathrm{PB} = (-7, 114)$. Now I would like to try to verify the curve by trying to generate it over some sensible domain. For this I am using this algorithm from this website.

I also require that $n$ (the order of $E_\mathrm{PB}$) is prime, and that the cofactor $h$ is 1. After programming for some time I have come up with the following algorithm for generating elliptic curves:

#!/usr/bin/env sage

F = GF(2^255 - 19)
for i in range(15000):
    if i % 100 == 0:
        print('Progress: {}'.format(i))
    try:
        E = EllipticCurve(F, [-3, i])
    except ArithmeticError:
        # Curve probably has a singularity
        continue
    n = E.order()

    # Only accept curves of prime order
    if not is_prime(n): continue

    # Start selecting random points for the rest of the search
    for x in range(-256, 256):
        for y in range(256):
            try:
                G = E(x, y)
            except TypeError: # (x, y) is not a valid point
                continue
            t = G.order()
            # Cofactor MUST be 1
            if n == t:
                bits = int(log(float(E.order()))/log(2.0))
                print('Found prime order for a_6 = {} ({} bits)'.format(i, bits))
                print('Generator G = {}'.format(G))

After a short time it gives me the following curve:

$$
E_{DS} : y^2 = x^3 - 3x + 101
$$

with $G_\mathrm{DS} = (-4, 7)$, which is not Paulo's curve. I expect that Paulo did not make a mistake, so my question is:

What is wrong with my generated elliptic curve $E_\mathrm{DS}$?

As a lone curve, yours is not bad. But Barreto's proposal offers an extra property, which is that the quadratic twist also has prime order.

In general, in a given finite field $K$, if you have a non-quadratic residue $d$ (i.e. a field element which is not a square), then, for the curve $E$:
$$ E: Y^2 = X^3 + aX + b $$
then you can define another curve called its "quadratic twist":
$$ E^d:Y^2 = X^3 + ad^2X + bd^3 $$
It can be seen that if $X$ is a valid first coordinate for one curve, then it is not for the other, and vice versa. It implies that that if field $K$ has cardinal $q$ (in your case, $q = 2^{255}-19$), curve $E$ has order $n_1$, and $E^d$ has order $n_2$, then $n_1 + n_2 = 2(q + 1)$. It also implies that the exact choice of $d$ does not matter much, in that all twisted curves you may get all have the same order, hence they are all "the same curve" in some sense (they are isomorphic to each other). This is why we talk of the quadratic twist.

(When $p = 3 \pmod 4$, it is convenient to use $d = -1$, but in your case, $-1$ is a quadratic residue because $2^{255}-19 = 1 \pmod 4$.)

Note that the quadratic twist of the quadratic twist is the original curve (or something isomorphic to it).

Quadratic twists may matter because in some cases they allow to avoid point validation. If you consider normal ECDH with point compression, both parties will send the $X$ coordinates of their public points to each other. Normally, each receiving party would then rebuild $Y$ from the received $X$, and check that indeed they got a point on the curve. That process would go thus: receive $X$, compute $X^3+aX+b = Y^2$, then apply a square root algorithm to get $Y$. If the received $X$ does not correspond to a point on the curve, then the recomputed $Y^2$ is not a square: this is where point validation happens.

Historically, a number of implementations have got validation wrong and blindly kept on computing with whatever point they had. In practice, if you get an $X$ that does not map to a point on the curve, then you are really computing on the quadratic twist. Therefore, it seems to be a good idea if the curve and its quadratic twist both have a prime order.

In Barreto's proposed curve, both the curve and its twist have prime order. In your curve, the twist's order is not prime. That's what is "wrong" with your curve.

In my opinion, the issue about validation is overrated. Point validation is not hard; it uses up negligible CPU compared to the actual computations you are about to do, and the code size overhead is small. Implementations that do not point validation are basically sloppy, and sloppiness, like love, knows no limit. However, if you can have some extra protection against sloppiness at low cost, then why not?


AES key from encrypted text and IV So I'm trying to figure out if it's possible to extract the private key if you have the ciphertext and the IV corresponding to that ciphertext.
It's for some kind of a challenge, and can't really seem to figure it out.

No, that's not really possible without blatant flaws of the implementation. Modern modes of operation of ciphers are resistent to attacks even if you know many pairs of plaintext and ciphertext - and the IV is public knowledge. Knowing it is the normal case. You also didn't mention what operation mode was used.

Well, of course you could brute force the key, but that would take more time and computational power than you can ever muster.

Oh, and a small note: AES is a symmetric cipher, so there's just one key, which is normally not called private key. It may be true, but this term is generally reserved for asymmetric encryption.


Why is SHA256/SHA512 not broken for shortish passwords I don't get why SHA-256/SHA-512 hasn't been broken, at least for shortish (10-12 character) passwords
It is perfectly plausible to pre-compute a password/hash-pair table using numerous very fast computers (thereby significantly increasing the speed at which this is done).
Clearly I am misunderstanding, so I would appreciate some input as to why this would not be considered breaking SHA256/SHA512 especially as most people use passwords shorter than 10-12 characters

SHA-256 and SHA-512 were designed to be very fast. Their primary goal ist to verify the integrity of long messages or files. Long means not 10-12 bytes but some megabytes and greater. It is not a good idea, to use hash function that is fast by design for password hashing. Instead, for password hashing should be used functions that need essentially more resources for brute-forcing, e.g. that require relatively much RAM, prevent or limit essentially parallelization and thus limit optimization of brute-forcing. For instance, Argon2, Lyra2, scrypt.
Compare it to cars. Ferrari is good for the cases when the speed is important. It is not correct to say that Ferrari is weak because it cannot carry big load. If you need to move a big load, you better use huge trucks. It is just a matter of choosing a proper tool for the task.


In textbook RSA with low public exponent, how big does a random message needs to be? Assume RSA with a public modulus $N$ of $n$ bits, a small odd public exponent $e$, plaintext $M$ a random non-negative integer less than $2^m$ for some integer parameter $m$, with $M\mapsto C=M^e\bmod N$ (textbook RSA) used for encryption. Inasmuch as it matters, assume there are $2^r$ ciphertexts available to the attacker, and her goal is to recover one plaintext with odds better than $2^{-k}$. If necessary also assume $n\ge1024$, $e\le2^{16}+1$, $r\le30$, $k\ge40$, or/and $M$ is of exactly (rather than at least) $m$ bits.

If $M^e<N$, then $M^e\bmod N=M^e$ and thus $M=C^{1/e}$, making decryption trivial by $e$th root extraction. $m\ge n/e+k+r$ makes us safe from trying that for each available ciphertext; but not necessarily against improvements, or other attacks.

Up to what bound for $m$ do we know an attack better than factoring $N$ using GNFS?

As an aside: starting with what bound for $m$ (if any) is there a positive security argument?

Updates (main question, now highlighted, remains without an answer proposing a bound):

As rightly pointed by D.W.'s in this answer, regardless of $e$, we must also have $m$ big enough to resist being found by "square-root" attack, a "meet-in-the-middle" search using a space/time tradeoff. To be safe from that we can make $m\ge a+b+k$ where the adversary is powerful enough to make $a$ accesses to a memory system of $b$ bits, say $m\ge 90+70+k$.

There is a simple extension to the $e$th root attack: the adversary hopes that an $M$ is divisible by some small integer $s$ of her choice, computes $C'=C\cdot s^{-e}\bmod N=(M/s)^e\bmod N$, then applies the $e$th root attack to $C'$. Perhaps she chooses $s$ as the successive primes, or some better method. This considerably extends the range of vulnerable $m$ (to, uh..).

Note: I assume all plaintext is random and independent, and the adversary has no access to a decryption oracle (even limited to revealing messages other than the originals and with at most $m$ bits).

Another simple extension to the $e$th root attack: the adversary hopes that $k=\lfloor M^e/N\rfloor$ is small enough to be enumerable, and tests if $C+k\cdot N$ is an $e$th root for small $k$. That's independent, but only marginally extends the range of vulnerable $m$, as far as I can tell.

Related messages. If you have (the encryptions of) a pair of messages that differ by a known fixed difference, then the Franklin-Reiter related message attack can be used to recover both messages.  The running time of the attack is something like $O(e^2 n^2)$.  This does not apply if the messages are independent and there are no known relationships between them.

Coppersmith's theorem. Coppersmith's theorem might be relevant.  Roughly speaking, it says that if you have a monic polynomial $f(x)$ of degree e, then you can find all solutions to $f(x)=0 \pmod N$ satisfying $0 \le x < X=N^{1/e}$ in polynomial time, using a lattice technique.  By defining $f(x)=x^e-C$, this can be used to recover $M$ if it is known that $M<N^{1/e}$.  Therefore, it looks like this does not improve upon the trivial $e^{\textrm{th}}$ root extraction root method.  I don't know if the attack can be improved by continuing to use his lattice methods even for a larger value of $X$.

Square-root attack. There is also a meet-in-the-middle style attack whose running time is $O(2^{m/2})$.  If $e=3$ it will be dominated by other attacks, but it may be more relevant for larger values of $e$.  The meet-in-the-middle attack is described by Boneh et al. (see below); basically, we hope that $M$ can be written as $M=M_1 M_2$ where $M_1,M_2 \le 2^{m/2}$, and we try to find $M_1,M_2$.  To find them, we build a table of $C/M_1^e \bmod N$ for all candidate $M_1$ values, then for each candidate at $M_2$, we look up $M_2^e$ to see if it is present in the table.

This is described in Section 5 of the following paper:

Textbook ElGamal and RSA Encryption are Insecure, Dan Boneh, Antoine Joux, Phong Q. Nguyen, ASIACRYPT 2000.

Published work. A good summary of the above attacks can be found in this paper:

Twenty years of attacks on the RSA cryptosystem, Dan Boneh, Notices of the AMS, vol 46 no 2, pp.203-213, 1999.


Hide a weakness in ECC by choosing the prime or one of the curve coefficients Suppose you are given a value $c$.  Can you find a prime $p$ and an integer $b$ such that the elliptic curve

$$E: y^2 \equiv x^3 -3x + b \pmod p$$

is cryptographically weak?  You need to choose $p,b$ so that all of the following restrictions also hold:

$p$ has some desired size (say, 256 bits)
$1 < b < p$ and $1 < c < p$
$b^2 c \equiv -27 \pmod p$
the order $n$ of the curve is a prime number

By cryptographically weak, I mean that the discrete log problem is easy on the curve (or that some other standard cryptographic assumption is false).

Is there any known way to do this?  Is there a procedure to find $p,b$ (as a function of $c$) satisfying all these conditions, where the procedure succeeds with non-negligible probability (say, probability $\ge 1/10^{12}$)?  Or, is there a proof or heuristic argument that doing so is likely to be impossible?

Basically, this amounts to asking whether there's any way to ensure that the resulting elliptic curve has a non-trivial probability of being cryptographically weak, given ability to choose some (but not all) of the curve parameters.

(For instance, maybe you could choose $b$ however you like, factor $b^2c+27$, select an appropriate divisor as $p$, and hope that the resulting curve is vulnerable to some particular attack; or who knows what.  Your choice of strategy.)

Motivation: If this problem has a solution, then it means that the NSA could have hidden a backdoor in the NIST-recommended elliptic curves (specifically, the P-xxx curves).  Thus, it has implications for how much trust we can put in the those standard curves.

Bernstein and Lange says that there has been no progress for prime-field elliptic curves since about 1999, when the NIST curves were chosen. No large class of weak curves were known then, and no large class is known now.

Some small classes are known, (as Neves says) the curves with small embedding degree and the anomalous curves (order $n$ equals the prime $p$), but all of these were known back then (though not all of them by everyone in 1985, the MOV attack was a real attack, and the anomalous curves were an attempt to block the MOV attack, I think). So these classes are hard to hit at random, and are easily detected anyway.

The problem of embedding trapdoors in elliptic curves has been studied by Edlyn Teske, but she uses curves over extension fields, not prime fields. (Her techniques rely on it being hard to find isogenies between curves, but it is possible to find curves with isogenies. You choose one curve over an extension field that is secure, another that is not secure, and an isogeny between them. The isogeny is the trapdoor and allows you to move the DLOG instance from one curve to the other. The extension field attacks this relies on do not apply to NIST's extension field curves, as far as I know.)


Hashing list: concatenation vs prepending In Schnorr's NIZK proof there is an interesting remark:

  Within the hash function, there must be a clear boundary between any
  two concatenated items. It is RECOMMENDED that one should always
  prepend each item with a 4-byte integer that represents the byte
  length of that item.

I know, that it's generally a good practice for preventing length-extension attacks.
But, look closely at the challenge:

  $c = H(g \Vert V \Vert A \Vert \mathsf{UserID} \Vert \mathsf{OtherInfo})$

$A$ is a valid public key ->  fixed length

$g$  is a a generator -> fixed length

Suppose both $\mathsf{UserID}$ & $\mathsf{OtherInfo}$ have fixed length as well.

It seems that in this particular case, Plain concatenation can be safe because all but one of the inputs have a fixed length.

Is it so? How vulnerable is Plain concatenation when all (or all but one) inputs have a fixed length compared to Prepending the length?

The whole issue comes from the fact that regular collision resistant hash functions are defined over binary strings. What you are trying to construct is a collision resistant hash function over a different domain, namely a set of tuples.

To construct a collision resistant hash function for some domain $D$ from a collision resistant hash function for $\{0,1\}^*$ what is necessary is to encode elements of $D$ as elements of $\{0,1\}^*$.
If $\mathsf{H} : \{0,1\}^* \to \{0,1\}^n$ is the original hash function and $\mathsf{E} : D \to \{0,1\}^*$ is an efficient encoding function then $\mathsf{H} \circ \mathsf{E} : D \to \{0,1\}^n$ is a hash function for domain $D$.

However, if it is easy to find collisions in $\mathsf{E}$, then $\mathsf{H} \circ \mathsf{E}$ is not collision resistant, since any collision in $\mathsf{E}$ directly implies a collision in $\mathsf{H} \circ \mathsf{E}$. So to show that $\mathsf{H} \circ \mathsf{E}$ is collision resistant we need that $\mathsf{E}$ is also collision resistant. Since $\mathsf{E}$ does not need to be compressing, the easiest way to ensure that it is collision resistant is to ensure that it is collision free by ensuring that it is a unique encoding.

If $\mathsf{E}$ is a unique encoding, then it is easy to show that $\mathsf{H'} = \mathsf{H} \circ \mathsf{E}$ is collision resistant whenever $\mathsf{H}$ is. Assume towards contradiction that there exists an efficient algorithm $\mathcal{A}$ capable of finding collisions in $\mathsf{H'}$. I.e., $\mathcal{A}$ outputs $x,x' \in D^2$ such that $x \neq x'$ and $\mathsf{H'}(x) = \mathsf{H'}(x')$. By definition of $\mathsf{H'}$ this implies that there are encodings $e := \mathsf{E}(x)$ and $e':= \mathsf{E}(x')$ such that $\mathsf{H}(e)=\mathsf{H}(e')$. And by the fact that the encoding is unique and $x \neq x'$ we have that $e \neq e'$. Therefore an algorithm $\mathcal{B}$ that simply runs $\mathcal{A}$ and encodes the outputs finds collisions in $\mathsf{H}$ with the same probability with which $\mathcal{A}$ finds collisions in $\mathsf{H'}$. Therefore, since $\mathsf{H}$ is collision resistant, so must be $\mathsf{H'}$.

It thus follows that all you need is a unique encoding of your tuples into binary strings. And as correctly observed, if all (or all but one) of the constituent parts of the tuple are of fixed length then simple concatenation is in fact a unique encoding.

However, it should be stressed that this requires all participants to always check that all elements of the tuple they are encoding actually have the required length and rejecting them otherwise. This a check that is easily missed (or maybe even skipped for "efficiency").
Whereas prepending the length -- even for fixed length elements -- ensures that even unchecked malformed tuples will not be able to cause collisions.


openSSL created CSR signature size of 73 bytes but should't it be 70 bytes after creating CSR using openSSL with secp256r1 curve
inspecting the file using openssl asn1parse -i -in ecTest.csr
the size of the signature is 73 bytes, why?
I think the ASN.1 of the signature is
ECDSA-Sig-Value ::= SEQUENCE { r  INTEGER, s  INTEGER }

and for secp256r1 that r and s are 32 bytes each which means
   1+1    +  1+1+32   +  1+1+32  = 70bytes
SEQUENCE     INTEGER     INTEGER

The "extra" octet is needed because ASN.1 uses two's complement notation for integers, per section 8.3.3 of X.690:

The contents octets shall be a two's complement binary number equal to
the integer value

In two's complement, the highest bit indicates a negative number. Since none of our numbers are actually negative, the correct notation needs to have leading zeros.
We can see this in action on the following signature:
$ openssl asn1parse -i -in foo.csr -strparse 126 -out raw
    0:d=0  hl=2 l=  69 cons: SEQUENCE
    2:d=1  hl=2 l=  32 prim:  INTEGER           :1937197C689C3E511CCB830E5F3677D3FA18F045EBA969739B622B95FEB619C1
   36:d=1  hl=2 l=  33 prim:  INTEGER           :BA1B75CEE9714860639A20B50125C20224CBBEBE01F4CCBFA46731706F55D171

You'll notice that my first integer has length 32 but the second has length 33.
Dumping the raw contents, we get:
$ hd raw
00000000  30 45 02 20 19 37 19 7c  68 9c 3e 51 1c cb 83 0e  |0E. .7.|h.>Q....|
00000010  5f 36 77 d3 fa 18 f0 45  eb a9 69 73 9b 62 2b 95  |_6w....E..is.b+.|
00000020  fe b6 19 c1 02 21 00 ba  1b 75 ce e9 71 48 60 63  |.....!...u..qH`c|
00000030  9a 20 b5 01 25 c2 02 24  cb be be 01 f4 cc bf a4  |. ..%..$........|
00000040  67 31 70 6f 55 d1 71                              |g1poU.q|

Let's break it down into the various components:

30 45: SEQUENCE of length 69
02 20: INTEGER of length 32
19 37 19 7c ... 19 c1: the INTEGER contents (32 bytes)
02 21: INTEGER of length 33
00 ba 1b 75 ... d1 71: the INTEGER contents (33 bytes)

This matches exactly what asn1parse tells us. Notice the difference between the first integer (encoded to a length of 32 bytes) and the second (encoded to a length of 33 bytes).
The first one begins with 19 which is 00011001 in binary. Because it does not have a high bit set, this is indeed a positive number.
But the second one begins with BA which is 10111010 in binary. The high bit is set which would be negative if we decoded it as is. Since it isn't negative, the correct two's complement notation has leading zeros.
In your case, both numbers have the high bit set, so they both get 00 prepended.
You end up with a total size of: $2 + 2 + 32+1 + 2 + 32+1 = 72$.
Oops, we're still one short of 73. This is part of the BITSTRING encoding which is defined in the spec, section 8.6.2.2 as:

The initial octet shall encode, as an unsigned binary integer with bit
1 as the least significant bit, the number of unused bits in the final
subsequent octet. The number shall be in the range zero to seven.

This is because a BITSTRING can represent a number of bits that is not a multiple of 8. In our case, we're making use of all bits, so the initial octet for the bitstring is 00.
We now have the right length: $72 + 1 = 73$.


Pseudo-random permutation of a range I have this set: {0,1,2,3,...,15}.

I would like to create a pseudo-random permutation from elements of this set, for example {10,2,15,0,7,5,9,4,3,13,11,1,6,12,8,14}.

Which method could I use to obtain the permutation?

The problem is small enough that the desired PRP can be implemented as a small array of 16 values initialized using the Fisher-Yates shuffle, with a pseudo-random generator deciding the indexes of the shuffles. That's probably the simplest, thus the best except perhaps when side channels (such as cache-induced timing variations) are a consideration.

Something NOT suitable is using a Feistel cipher with many rounds and a large random key defining the round functions: this is bound to generate an even permutation, thus only half of the $16!$ permutations would be obtainable. However this defect can be fixed by using 2-bit modular addition instead of 2-bit XOR to mix the output of the round functions: $R_{i+1}=((L_i+F(R_i,K_i))\bmod 4)$. This can be made constant-time, and also works nicely for permutations of $2^k$ elements with $k$ large enough to preclude the Fisher-Yates approach, which requires about $k\,2^k$ bits of memory.

The problem is well studied in Format Preserving Encryption, which offers a number of other techniques that remain suitable for much larger sets (contrary to Fisher-Yates), including some that exactly balance the odds of the resulting permutations (contrary to Feistel cipher with mixing by modular addition).


How are isogeny graphs made and how are they helpful to crypto? I don't understand how the shapes of isogeny graphs are determined. While Alice and Bob do walk on it and don't backtrack, are they actually relevant to crypto?

Also, I was told that supersingular isogeny graphs are expander graphs. Similarly, how is the shape of an expander graph determined

Let an elliptic curve $E(F_p)$ have the Frobenius discriminant $D_\pi$, and $\left(\frac{D_\pi}{l}\right)$ be a Kronecker symbol for some $l$-degree isogeny. If $\left(\frac{D_\pi}{l}\right)=-1$, then there are no
$l$-degree isogenies; if $\left(\frac{D_\pi}{l}\right)=1$, then two
$l$-degree isogenies exist; if $\left(\frac{D_\pi}{l}\right)=0$, then $1$ or $l+1$ $l$-degree isogenies exist.

  Therefore, if $\left(\frac{D_\pi}{l}\right)=1$. then $l$-degree isogenies of elliptic curves form branchless cycles, and changing
  direction in a cycle means switching to dual isogenies.

This is a Theorem2 of "PUBLIC-KEY CRYPTOSYSTEM BASED ON ISOGENIES", by Alexander Rostovtsev and Anton Stolbunov.
With this theorem, you can determine the shape of isogeny graphs.


A (current or soon-to-be) NIST-recommended alternative to ECC? So this comes from the professional rumor-mill, and I'm wondering if anyone might either debunk or shed light on this.

My understanding is ECC is generally now preferred over RSA simply due to how much more efficiently it operates.  After a 2048 key length, RSA simply doesn't return as much value for a longer key length. whereas ECC can offer greater levels of protection for much less processing overhead.

Is there discussion about a more efficient/powerful alternative to ECC which NIST is preparing to favor (if not already) ahead of ECC?  And if so, what might that be?

To my knowledge, NIST has not really decided or announced anything about successors to ECC. However, they do run workshops and such on post-quantum cryptography, so when the time is right something will probably move towards standardization.

NSA, on the other hand, recently announced that they will soon push for a post-quantum system, going so far as to say that moving from RSA to ECC may be unnecessary in the mean time.

The reason here is not performance or efficiency, however. By many measures the possible candidates for the successor are less efficient. Instead, they want something that remains secure even if quantum computers become practical (known as post-quantum security). Neither ECC nor RSA has that property.

But no, no specific alternative has yet been chosen. Because of this and the above mentioned recommendation to skip ECC, some have even wondered whether post-quantum security is the actual reason for the announcement.


Does perfect forward secrecy (using DH or ECDH) imply quantum resistance? Does perfect forwarding secrecy, as used for e.g. the DHE_ and ECDHE_ TLS ciphersuites make it impossible for quantum analysis to retrieve the plaintext data within the connection?

No it does not.

Perfect forward secrecy implies that even if you retrieve the private key of the asymmetric key pair that you cannot read any of the past or future messages within a connection. It is only possible to derive the secret session keys of the session that you've retrieved the private key for.

Perfect forward secrecy - or forward secrecy for short - is obtained because the private key of all the parties of a connection regenerate the public/private key pair for each connection; authentication of the entities within the connection will be performed by other means (if at all). These key pairs are called ephemeral key pairs and the key agreement is called ephemeral-ephemeral key agreement or just ephemeral key agreement for short.

Perfect forward secrecy however doesn't make it impossible to break DH or ECDH. It just means that you would have to perform an attack for each separate connection as you'd have to attack each separate key pair of one of the parties to retrieve the secret value. It doesn't make DH or ECDH a perfect cipher, equivalent to an asymmetric one-time-pad.

So regardless of (perfect) forward secrecy, the only way to make a transport protocol secure (against analysis with a quantum computer) is to use quantum resistant cryptography - that is, post-quantum algorithms that cannot be analyzed using quantum computers.


Gentry-Halevi’s Fully-Homomorphic Encryption and hermite factor In section 7.2, page 18 in Chen-Nguyen paper regarding BKZ 2.0, they point out different Hermite factors related to Gentry-Halevi FHE.

More precisely, it is said that the critical Hermite factor for the "large" challenge with lattice dimension $n=32768$ is $\delta = 1.0081^n$.

How is this Hermite factor computed ?

It is computed like that:
L is lattice with dimension i. B is BKZ reduction of lattice L.

$$Root Hermite Factor=( B[0].norm() / ( L.volume() )^{(1/i)})^{(1/i)}$$

If you want to calculate RHF, you can use Sage Math.


In NIST modulus and key size recommendations is `group` equivalent to modulus and `key` equivalent to exponent? Looking at the following NIST recommendations for a discrete logarithm, for 2016-2030 and beyond they list 3072-bit number for the group and 256-bit for the key.

If using Diffie-Hellman, does group equal the recommended size of the prime modulus and key equal the recommended size of the private key exponent?

Yes, when using cryptosystems based on the difficulty of the Discrete Logarithm in $\Bbb Z_p^*$ or a subgroup thereof, a key size recommendation of a 3072-bit group means that the modulus $p$ is 3072-bit, and a 256-bit key implies that a private exponent (a key) is 256-bit.

In some (as far as I know: all) NIST contexts, a 256-bit key additionally implies that the order of the public generator $g$ is a 256-bit prime $q$, and (thus) that $p-1$ has that 256-bit prime factor $q$, and public keys belong to a subgroup of $\Bbb Z_p^*$ having order $q$. The generation of $p$ and $q$ is described in FIPS 186-4 appendix A (Dave Thompson's comment explains that's for various sizes including 3072/256).

In all contexts, a private exponent should be at least twice as wide as the security level in bits, which guards against Baby-step giant-step and Pollard's rho. It is good and customary that $p-1$ has a large prime factor $q$, and that the order of the generator $g$ is a multiple of that $q$. That $q$ should be at least twice as wide as the security level in bits, which guards against Pohlig-Hellman.

The width of $p$ is dictated by resistance to a Discrete-Log extension of GNFS, which is why recommendations for this parameters match those for RSA public moduli.

In Diffie-Hellman, it can (but need not) be chosen $p$ such that $q=(p-1)/2$ is prime, and thus $g$ of order $(p-1)/2$ or $p-1$, even when the key is narrower.


How reassuring is 64-bit (in)security? In Feb 2017, CWI and Google announced SHAttered hash collision attack on SHA1, which took $2^{63.1}$ work estimated 6500 CPU years, to achieve. Therefore, 64-bit should be considered now an insecurity.

However, that's on the cloud computers of one of the largest tech company in the world, possibly taking hours if not days to find the collision. So 64-bit assurance may still be meaningful in some scenario (e.g. hash table in the implementation of associative arrays) assuming it can be correctly achieved (e.g. Gimli permutation in Sponge mode of capacity of at least 128-bit).

Also, $2^{-64}$ seems to be small enough a probability, that it's not uncommon that some protocols happily truncate their MAC to 64 bits, and some PQC KEMs take that as quite comfortable a margin of encryption failure probability.

So my question is: How reassuring is 64-bit security in terms of the fastest (classical) supercomputer in 2018, the IBM Summit (used in Oak Ridge National Laboratory).

TL;DR; Just give me the numbers;
\begin{array} {|l|c|c|c|c|}\hline
 & \text{in a second} & \text{in an hour} & \text{in a day} &  \text{in a year} \\ \hline
\text{Summit on SHA-1} & \approx 2^{49.7} & \approx 2^{61.5}  & \approx 2^{66.1}  & \approx 2^{74.6} \\ \hline
\text{Titan on SHA-1} & \approx 2^{49.1}& \approx 2^{61.0}   & \approx 2^{65.5} & \approx 2^{74.1} \\ \hline
\text{Bitcoin Miner on SHA-256D} & \approx 2^{67.1} & \approx 2^{78.9} & \approx 2^{83.5} & \approx 2^{92.09} \\ \hline
\end{array}

Summit can reach $\approx 2^{63}$ SHA-1 hashes around 3 hours, $\approx 2^{74.6}$ hashes in one year.
Titan can reach $\approx 2^{63}$ SHA-1 hashes around 4 hours, $\approx 2^{74.1}$ hashes in one year.
Bitcoin miners reached $\approx 2^{92.09}$ SHA-256D hashes per year in 7 February 2021 ( or $\approx 2^{93.09}$ SHA-256)

Performance Results of some GPU's

On Amazon AWS P2, up to 16 Nvidia Tesla K80 GPUs has total $31,664.7$ MH/s SHA-1 calculations on average per board $\approx 1,992$ MH/s with hashcat-3.10
on 8x Nvidia GTX 1080 Hashcat Benchmarks has total $68,771.0$ MH/s SHA-1 calculations and on averageper board $8,596.4$ MH/s with hashcat 3.00
Tesla V-100 has $17,225$ MH/s with hashcat 4.0, ( very big? see comparison of NVdia's)

The below tables is constructed from various web-sites [1][2][3] and not taken on average.
\begin{array}{|l|c|}\hline
Device & MH/s \\ \hline
\text{GTX 1080 TI} & 12098.4 \\ \hline
\text{RTX 2070S}   & 11283.1 \\ \hline
\text{RTX 2080 TI} & 16823.6 \\ \hline
\text{RTX 3090}    & 22220.5 \\ \hline
\text{Tesla T4}    &  5428.3 \\ \hline
\text{Tesla P100}  &  9653.8 \\ \hline
\text{Tesla V100}  & 17535.9 \\ \hline
\text{Tesla K80}   & 31664.7 \\ \hline
\end{array}
Calculation based on Tesla V-100
This answer based on the 3rd GPU, Tesla V-100. Tesla V-100 has listed price as $10,664 and has 250 W power consumption. This is closest to
$ 17,225\;MH/s  \approx 2^{35} H/s$
If you run the Tesla V-100 for one hour;
$2^{35}\cdot 2^{12} \approx 2^{47} H/h$ calculations.
OCLF's Summit
The Summit contains  27,648 ($\approx 2^{16}$) NVIDIA Volta architecture GPUs.  According to Oak Ridge Library's news the GPU's are Tesla V100. From the picture of the server board, it is Tesla V100 SXM2, ~10% faster than Tesla V100 PCle and consumes 300W.
Total SHA-1 calculations of Summit in one hour $ \approx 2^{47}*2^{16}= 2^{63}$

The SHAttered hash collision attack on SHA1 can be executed in a little more than 1 hour with Summit.

OCLF's Titan
The Titan contains $18,688 \approx 2^{15}$  physical nodes each contains an NVIDIA Kepler™ accelerator (GPU)1. Assuming that Kepler = Tesla V-100
Total SHA-1 calculations of Titan in one hour $ \approx 2^{47}*2^{15}= 2^{62}$

The SHAttered hash collision attack on SHA1 can be executed in 2 hours with Titan.

Cost
Here I will only talk about the initial cost of GPUs and their runtime cost by power consumption.

Titan :The initial cost of GPUs : $27,648 * 10,664 \approx \\\$300M$
Summit :The initial cost of GPUs : $18,688 * 10,664 \approx \\\$200M$
Titan : Each VT-100 requires $250W*18,688 = 4.67MW$, and taking 12 cents per kilowatt-hour is an average in US, one year cost is \$4,896,256
Summit : Each VT-100 requires $300W*27,648 = 8.29MW$, and taking 12 cents per kilowatt-hour is an average in US, one year cost is \$8,709,120
And, if you rent AWS using p3.16xlarge instance the $2^{64}$  SHA1 evaluations cost about 1M USD.SEjPM's comment

security
There are two question on this site answer the practicability of the shattered;

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?
After Google's collision attack, is RSA-SHA1 signature still safe?

tl;dr; for this answers;

But it is not safe, regardless of Google's attack. Before Google attacked, we knew that SHA-1 is not the best choice.
You are already too late. Migrate away from SHA-1 now.

notes;
1 This calculation is based only GPUs and CPUs are slower in magnitude order. Only Titan has GPU on the Summit of Oak Ridge National Laboratory. rhea has only 9. Eos and ARM don't have any.


primitive root of a very big prime number (Elgamal DS) For encryption methods there is a need for (very large) prime numbers. So for Elgamal digital signature there is the problem of finding a primitive root of $(p)$ where $p$ must be very large prime number (1024) or (2048) bits length.

My question is: how does the encrypter solve this problem?

I presume a loop to check all the possibilities is an option.

When considering a big prime $p$, the group of invertible integers modulo $p$ are all integers from $1$ to $p-1$. There are $p-1$ of them. The order of an integer $g$ modulo $p$ is the smallest integer $k > 0$ such that $g^k = 1 \pmod p$. Group theory states that the powers of an element $g$, i.e. $1$, $g$, $g^2$... are collectively a subgroup of the group of invertible integers modulo $p$, and the order of $g$ is really the size of that subgroup (called "the subgroup generated by $g$"). The cardinal of a subgroup is always a divisor of the cardinal of the group that contains it. Thus, $k$ divides $p-1$.

A primitive element $g$ is one such that the subgroup it generates really is all of the invertible integers modulo $p$, not just some of them. Therefore, to verify whether an integer $g$ is primitive or not, all you have to do is check that its order is $p-1$ but not one of the other possible subgroup orders. That is, you check that $g^{k'} \neq 1 \pmod p$ for all $k' < p - 1$ such that $k'$ divides $p-1$.

The problem can be simplified as follows: suppose that there is a $k' < p-1$, such that $k'$ divides $p-1$, and $g^{k'} = 1 \pmod p$. We can consider $\alpha = (p-1)/k'$, which is an integer greater than 1, and thus a product of some prime integers (since every integer can be decomposed as a product of prime factors). Let's call $r$ one of the prime factors of $\alpha$ (i.e. we write $\alpha = r\beta$ for some integer $\beta$). Since $\alpha$ divides $p-1$, so does $r$, and we can compute:
$$ k'' = (p-1)/r = \beta k' $$
Thus:
$$ g^{k''} = (g^{k'})^\beta = 1^\beta = 1 \pmod p $$

In other words, if $g$ is not primitive, then there must be a prime integer $r$ that divides $p-1$ such that $g^{(p-1)/r} = 1 \pmod p$.

This means that in order to test whether a given $g$ is primitive, then it suffices to apply the following test:

  Let $p$ be a prime, and $g$ a non-zero integer modulo $p$. If, for all primes $r$ that divide $p-1$, $g^{(p-1)/r} \neq 1 \pmod p$, then $g$ is primitive, i.e. its order modulo $p$ is exactly $p-1$.

Now comes the actual difficulty: you must somehow know the list of prime factors of $p-1$. This is easy if you generate $p$ "specially", as a so-called "safe prime" (the terminology "safe" here is traditional and does not actually imply that the prime is inherently "safer" than any other, but it makes our problem easier). A "safe prime" is an integer $p$ which is such that both $p$ and $(p-1)/2$ are prime. If you generate your modulus for ElGamal signatures are a "safe prime", then there are only two prime factors of $p-1$: these are $2$, and $(p-1)/2$. The test above now becomes the following:

Get a random non-zero $g$ modulo $p$.
Check that $g^2 \neq 1 \pmod p$. Note that there are only two integers $g$ modulo $p$ such that $g^2 = 1 \pmod p$, and these are $1$ and $p-1$. Thus, it suffices to choose $g$ greater than $1$ and lower than $p-1$ to fulfill that condition.
Check that $g^{(p-1)/2} \neq 1 \pmod p$. If that condition is not met, then you must start over with another $g$. Otherwise, that's it, you have a primitive $g$.

No specific value of $g$ is better than any other with regards to resistance to discrete logarithm, so you might just as well try small values of $g$, that offer a small performance boost; you start with $g = 2$ and simply increment it until you reach a primitive value. Exactly half of the integers from $2$ to $p-2$ are primitives, so you do not have to try many times before reaching such a value.

IMPORTANT: Take care that the test above is for a "safe prime". In the general case, if given a prime $p$ without any knowledge of how it was generated, you would have to factorize $p-1$ into its prime factors, a problem which is, in all generality, quite hard to solve for large integers.

While the ElGamal scheme is nominally defined with a primitive root that generates all invertible integers modulo $p$, it can also be applied to a subgroup, at which point it becomes mostly the same thing as DSA. In DSA, it is customary to generate $p$ as follows:

Let $q$ be a random medium-sized prime (e.g. 256 bits).
Let $p$ be a random large prime (e.g. 2048 bits) such that $q$ divides $p-1$. In practice, this means that random integers $z$ are produced, and, for each, $p$ is computed as $p = qz+1$, until a prime $p$ is obtained.
To make an element $g$ of order exactly $q$, a random integer $m$ modulo $p$ is generated, and we set $g = m^{(p-1)/q} \bmod p$. It is easily shown that $g^q = 1 \pmod p$, which means that the order of $g$ is a divisor of $q$. Since $q$ has been chosen to be prime, the order of $g$ can be either $1$ or $q$. If $g \neq 1$, then its order cannot be $1$. Therefore, $g$ will have order exactly $q$ as long as it is not equal to $1$. Probability of $g$ being equal to $1$ is very very small, but even if that happened, then you would just have to start again with another value $m$.

Summary: to get a primitive element modulo $p$, you get random values and then check whether you obtained a primitive element. Primitive elements are not rare, so this works well in practice. However, to do the check, you have to know the factorization of $p-1$, and that is difficult in the general case. Thus, the usual method is to produce the modulus $p$ with a generation method that also lets you know the factorization of $p-1$, e.g. you make $p$ as a "safe prime". Alternatively, you do not look for a primitive element, but for the generator of a subgroup of known prime size (as is done in DSA).


Full encryption of IDs, partial decryption with customer specific key I am looking for a "partial" encryption/decryption algorithm.

Let's say I am encrypting the following List of IDs (long values) $[1,2,3,4]$ (with a secret key) to an encrypted string $e$, I would like to produce several keys $k_1,k_2,...,k_n$, which can decrypt just a subset (some IDs).

For example:

val rawIds = [1,2,3,4,8]                         # Array of Long
val e = encrypt(rawIds, secretKey)               # An encrypted String

decrypt(k1, e) = [1]                             # Decryption of e with key k1
decrypt(k2, e) = [2,3]                           # Decryption of e with key k2

Both the encryption and decryption must be very fast in terms of computation time (<1ms). We want to produce keys, which can decrypt the value $e$ in way that only a subset of IDs can be decrypted.

$k_1$ for example is able to decrypt $e$ (but only retrieves $ID_1$) where $k_2$ can decrypt the same encrypted value but retrieves $ID_2$ and $ID_3$. He might even get $ID_5$, but this was not in the raw string.

When creating the keys, we could add the IDs which can be extracted somehow to the decryption key.

Update:

The possible values of the IDs are known, there is a predefined set (let's call them $ID_1,ID_2,...,ID_n$).

The business purpose is the following:

I have 2 customers, where I know that customer1 is only allowed to see $ID_1$, therefore I create a key $k_1$ (and add the meta information $ID_1$).
The second customer is allowed to see $ID_2$, $ID_3$ and $ID_5$ (therefore I create a special key $k_2$ for him).
Both customers will get the same encrypted value e, and both can decrypt it but will get back a list of IDs, where every element is allowed to be extracted by that customer).

This was meant by: I add the IDs to the decryption key.

Some additional information:

It's only one entity which is encrypting, don't need to decrypt with the secret key
No need to check authenticity of the encrypted value (always trust)
When creating keys, the actual IDs (Long values) which can be extracted can be added to the actual key.

Where to start? Has anybody an idea of a similar existing approach?

So lets assume a few things:

just symmetric primitives suffice;
a symmetric key derivation function and single block encrypt with a 64 bit block cipher is sufficiently fast;
the ID's are unique and not related to customers;
we're not afraid of customers sharing ID's;
there is protection against customers simply guessing ID's;

Scheme:

establish a master key $k_m$
derive customer keys and distribute to customers: $k_{c,name} = KDF(k_m, name)$
derive a data key for each ID with index $i$: $k_{id, i} = KDF(k_m, i)$
create and distribute the encrypted array where each entry $C_i = E(k_{id, i}, ID_i)$

Now comes the tricky part:

when a customer wants to get the ID's he sends you the set of indices to the ID's;
you calculate the customer key and a customer specific data key for each entry: $k_{c,name} = KDF(k_m, name)$ and $k_{c,name,i} = KDF(k_{c,name}, i)$
you calculate the difference between the data key and customer specific data key for each entry: $k_{x,i} = XOR(k_{c,name,i}, k_{id, i})$
you send a map consisting of elements $(i, k_{x, i})$ back to the customer
the customer can now perform $k_{id,i} = XOR(k_{c,name,i}, k_{x, i})$ for each entry
and of course calculate $ID_i = D(k_{id, i}, C_i)$


If classical ciphers are used with compressed plaintext, how much does it make frequency analysis attack harder? Classical ciphers, such as the Vigenère cipher, are weak and no longer used. They can be broken by using frequency analysis, which is a well-known fact.
However, frequency analysis often depends on the number of captured ciphertexts and/or their duplication. What if the ciphertext was compressed by an algorithm such as Huffman encoding，zlib, or lzma before encrypting the plaintext? For better security, assume there is no constant header, magic number, or any identifier in the plaintext.
How much more difficult does compression make attack by frequency analysis?

Compression works by approximating an optimal code—one where if the probability of a given message is $p$, its encoded length is $-log(p)$. This means that the lengths of the encryptions of compressed messages potentially leak information about the plaintexts.

Also, the way a scheme like Huffman coding works is by outputting shorter code words for more frequent source symbols than for less frequent ones. This means that the relative frequencies of Huffman code words will be the same as that of the frequencies of the source symbols. It does nothing to disguise those frequencies.

A good real-life example to consider is attacks tht break the confidentiality of some encrypted voice-over-IP codecs that use variable bit rate encoding (which is a form of compression):

  Despite the rapid adoption of Voice over IP (VoIP), its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that when the audio is encoded using variable bit rate codecs, the lengths of encrypted VoIP packets can be used to identify the phrases spoken within a call. Our results indicate that a passive observer can identify phrases from a standard speech corpus within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases.


ECDSA signature verifiable 1-way transformations Alice signs a message $m$ with her private key, yielding a signature ($r$,$s$).

I want to prove to someone else that I have this signature, but I don't want them to have the knowledge of what ($r$,$s$) is.

Is there a transformation I can apply to ($r$,$s$) to yield a new signature ($r'$,$s'$), such that someone who knows the original message and Alice's public key can see that it was derived from an original signature (without being able to reconstruct it)?

I'm thinking multiplying both the public key and signature components by some large number mod $n$. Am I on the right track or is this a fool's errand?

Use a zero-knowledge proof of knowledge (ZKPoK) of a value $(r,s)$ that is a valid signature.  For instance, you might be able to adapt existing ZKPoKs for proof of knowledge of a discrete logarithm to this problem.  Because it is zero-knowledge, you will know that it reveals nothing about $(r,s)$ and is not transferable.


Difficulty understanding 'random square root' in enhancement to fiat-shamir This was published in 1986 and I'm trying to reproduce it in an assignment. It's a small variation on fiat-shamir, by the original author, which does away with a public key (and supposedly drastically improves performance) by doing:

  Our improvement comes about from choosing the ${v_{i}}'s$ to be the first $k$ prime numbers
  $(v_1=2,v_2=3,v_3=5)$, etc. The ${s_{i}}'s$ will then be set to be a random square root of the corresponding $v_i \bmod n$

In the paper, ${v_{i}}'s$ are the public key, ${s_{i}}'s$ are the private key.

But I'm a bit lost with the wording. It says to set the ${s_{i}}'s$ to the random square root of the corresponding $v_i \bmod n$.

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11*19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?

Obviously this isn't correct, so I'm sure I'm missing an assumption somewhere. Any help would be really appreciated.

Nb. For reference, there's a paper which isn't behind a paywall which looks at this enhancement. There's also a patent for the scheme here.

edit: After poncho's post, I plugged his two example values into the algorithm and the scheme doesn't seem to work.

p=11
q=19
n=p*q # 209

r = 123 # random
e= 1.234 # random challenge

v = 5 # public key
s = 29 # secret key
y = (r)*(s**e) % n

rhs = (y**2)*(v**e) % n
x = r**2 % n
assert x == rhs

So the corresponding $v_i$ for $s_1$ would be 2. If $n=pq=11∗19=209$, then does this mean that $s_i = \sqrt{2} \bmod n$?

What they mean by "square-root of $x$" is the value $y$ that is a solution to $y^2 \equiv x \pmod n$; as there are multiple solutions (in the cases that at least one solution exists), then by a random solution, they mean to pick one randomly.

Now, in the case of $n=209$, it turns out that there isn't a solution for $v_i = 2$ or $3$.  However, there are four solutions for $v_i = 5$, namely 29, 48, 161, 180 (and for $n$ which is a product of two distinct odd primes and with $v_i$ nonzero and small (that is, $< p, q$), there will always be either zero or four solutions); the algorithm is to set $s_i$ to one of the four randomly.

As for how to compute the square root of $x$, the procedure is:

Compute $x_p = x \bmod p$ and $x_q = x \bmod q$
Compute the values $y_p$ that satisfies $y_p^2 \equiv x_p \bmod p$ and the values $y_q$ that satisfies $y_q^2 \equiv x_q \bmod q$; and if there doesn't exist either a $y_p$ or a $y_q$ that satisfies the above equations, then there doesn't exist such a $y$.  This computation can be done in the general case by the Tonelli–Shanks algorithm (and with simpler algorithms in the case that $p, q \not\equiv 1 \pmod 8$)
Usually, the above will give two possible values for $y_p, y_q$; pick one randomly (this will perform the 'random selection' logic specified.
Use the Chinese remainder theorem to find the value $y$ with $y \equiv y_p \pmod p$ and $y \equiv y_q \pmod q$; you're done


Apply visual cryptography to a video stream? I read that there are different ways to apply visual cryptography. One is to generate two images that when overlapped provide the original image. The main issue of using this approach with a video is that I would need to generate those two images for each frame. Is there a way to generate a single decryption image for the entire video?

In that case such image would act as a symmetric key and so all the encrypted frames could be decrypted with such key.

The simplest form of visual cryptography use transparencies that each individually convey no recognizable information, but reveal a meaningful image when precisely aligned

The basic approach for doing the same with video is using such visual cryptography to encipher each frame. That works, but (as stated in the question) requires generating two images for each frame, and playing these in perfect synchronization. Also, the decoding won't be easy: the eye is good at averaging luminous intensity, and projection on an ordinary screen, even if perfertly superimposed, will lack contrast. Further, lossy video compression (as most video compression schemes are) will tend to prevent decoding.

It is tempting to make the image in one of the two video streams still, which in particular allows decoding with fair contrast simply by projecting on a screen that serves as key. But that's very insecure! What's moving in the original video will be distinguishable to the naked eye; and XORing each frame with the previous one will make that even more apparent: the XOR of two consecutive frame in the ciphertext is also the XOR of two consecutive frame in the plaintext, and is very revealing; in particular, that shows the left and right contour of something moving horizontally.

I see no secure fix.


Sigma protocol to prove that the prover knows how open a commitment Sigma protocol to prove that the prover knows how open a commitment.

Consider the unconditionally hiding commitment scheme based on discrete log, i.e., the public key $p_k = (p,g,y)$, where $\langle g \rangle = Z_p^*$ is a generator and $y \in Z_p^*$.

To commit to a bit $b$, we proceed as follows: $c = \text{commit}(r,b)_{p_k} = y^bg^r \bmod p$.

Now, I want to design a $\Sigma$-protocol to prove that the prover knows how to open $c$, where the challenge should be a single bit $e$.

Here the witness $w=(b,r)$ is input only to $P$, while $x = (p,g,y,z)$ is input to both $V$ and $P$.

Recall that conversations in a $\Sigma$-protocol are $(a,e,z)$.

My initial attempt is to make $P$ send a random commitment as $a$, and then ,depending on whether $e=0$ (or $e=1$), send some $z$ back to $V$.

However, I've trouble determining the $z$ and prove soundness.

Let $a \gets y^{u}g^{v}$, where $(u,v)$ are uniformly random exponents. $P$ sends a in the first flow, then receives a bit $e$ from $V$.

If $e = 0$, $P$ reveals $(u,v)$ and $V$ checks that $a$ is indeed $y^{u}g^{v}$ (hence that $P$ knows how to open $a$). If $e = 1$, $P$ reveals $z_0 = r + u \bmod q$ and $z_1 = b + v \bmod q$ ($q$ being the order of the group generated by $g$), and the verifier checks that $a\cdot c = y^{z_0}g^{z_1}$.

The intuition is the following: when $e=0$, $P$ proves that he can open $a$, and when $e=1$, he proves that he can open $a\cdot c$. As $P$ cannot anticipate the $e$ in advance, if this step is repeated many times, then $V$ is convinced that $P$ knows how to open $c$ with overwhelming probability. In other words, the protocol has soundness $1/2$.

To prove the soundness, you have to exhibit an extractor, id est, a simulator that will play the role of $V$, interacting with $P$, and that can extract $(r,b)$ from this interaction. This is what it means to "know" something: it can be learned from you. Of course, this simulator cannot just play as an honest verifier, because an honest verifier cannot learn the witness. The common method is to use rewinding: the simulator can run the prover, and rewind it to some intermediate step. By doing so, the simulator will ensure that the same first flow $a$ is the same in, say, two different executions, one with challenge $0$ and one with challenge $1$. From then it's easy to recover $r$ and $b$.

Things get slightly more complicated when you interact with a prover that succeeds with some noticeable probability $\varepsilon$, and not "always", but the same ideas work right, you just have to figure out the probability that $P$ succeeds twice in two runs of the protocol that are not really independent (as they share the same $a$); you can get the probability from standard probability lemmas (see the splitting lemma, for example).


Would this hash functionality fall under pre-image resistance or collision resistance? I understand that there are three main security requirements for hash functions, pre-image resistance, second pre-image resistance and collision resistance.

I need to write about a hash function that allows the user to identify if the original hashed items are identical, but I am a little confused to which security feature this falls under. I understand that its best that no hashed items create the same digest, but in this case its a requirement.

Would this fall under pre-image resistance, since often this is when the random salt is added? Or simple collision resistance? As collision resistance stops hashed values from equaling the same value.

I am a little confused since I do not want different inputs equaling the same output, only identical ones.

I do not want different inputs equalling the same output, only identical ones.

That is pretty much the definition of collision resistance:

  a hash function H is collision resistant if it is hard to find two inputs that hash to the same output; that is, two inputs a and b such that H(a) = H(b), and a ≠ b.

Of course, no hash function can guarantee that the same hash values means the same input. Consider the case where you are hashing files up to 2 gb into 256-bit hash strings. So there are $2^{8000000000}$ possible inputs and only $2^{256}$ possible outputs. Many many possible files will map to each hash string.

So you can never guarantee that identical hashes means identical inputs, but you can rest easy that with a good cryptographic hash function, it is computationally infeasible for an attacker to build two inputs with the same hash (collision resistance), or to take a given input and find a second input with the same hash value (second pre-image resistance).


How to generate safe primes in a verifiable way? FIPS 186-3 (APPENDIX A: Generation and Validation of FFC Domain Parameters)
specifies how to generate Finite Field Cryptography Domain parameters and how to perform an explicit domain parameter validation. These parameters consist of the set of values: (p, q, g {, domain_parameter_seed, counter}).
The Standard specifies the following bit lengths of p and q:

p: 1024, q: 160

p: 2048, q: 224

p: 2048, q: 256

p: 3072, q: 256

I would like to generate FFC Domain parameters when p is 2048 and q is 2047 bits (p=2q+1). Is there any way to adapt the methodology proposed in FIPS 186-3 to these bit lengths? or is there any way to generate safe primes in a verifiable way?

Here's a very simple method: Find the largest number below $2^n$ that is a safe prime.  Use standard primality tests for $p$ and $q = (p - 1)/2$.  For example, $2^{2048} - 1942289$ is the largest safe prime below $2^{2048}$.

But you didn't specify what you want this for.  If you want to use this with Diffie–Hellman to resist discrete logarithms, then that won't be a good option.  The bit lengths you describe are designed for DSA, which has different security requirements.

For an $n$-bit safe prime to use with Diffie–Hellman, you want few small subgroups and you want to destroy the structure that the SNFS exploits, so you can pick the smallest $c$ such that $$p = 2^n - 2^{n - 64} - 1 + 2^{64} (\lfloor 2^{n - 130} \pi \rfloor + c)$$ is a safe prime and congruent to 7 modulo 8.  The latter condition ensures that 2 generates the subgroup of quadratic residues in $(\mathbb Z/p\mathbb Z)^\times$, of prime order $(p - 1)/2$.  This is the technique used by RFC 3526 to pick standard groups at sizes from 1536 to 8192; the technique is described in RFC 2412, Appendix E.

This technique is sometimes called NUMS, for nothing-up-my-sleeves, because it uses the conventional transcendental constant $\pi$ instead of some inexplicable string of 1920 bits.  There's no security significance to $\pi$ except that it destroys some structure the SNFS could exploit—you could use $e$ instead, or $e^\pi$, or $\cos 1$, or all manner of other options to get a result you want if you knew of a small, say one in a million, fraction of primes that admitted a back door.  For this reason, may I interest you in doing Diffie–Hellman over rigidly selected elliptic-curve groups free of magic constants instead?  As a bonus, you get higher performance, smaller keys, easier defense against timing side channels, a number of high-quality implementations, and cooler names like X25519.

I'm not sure offhand what all the security requirements for Elgamal encryption: approximately nobody uses Elgamal encryption these days.  Naively, if the recipient given $(c, d)$ yields $d \cdot c^{-x}$ where $x$ is the secret exponent, then the adversary can apply the Lim–Lee active small-subgroup attack by supplying $d = 1$ and $c$ of small orders $n_0$, $n_1$, $n_2$, etc., to learn points ${g_0}^x$, ${g_1}^x$, etc., to which they can apply discrete logarithms in small subgroups to recover $x \bmod n_0$, $x \bmod n_1$, etc., and reconstruct $x$ with the Chinese remainder theorem.

Could I interest you in replacing your use of Elgamal encryption by X25519 in a NaCl crypto_box or libsodium crypto_box_seal, which have none of these finicky considerations and run much faster with fewer side channels and have smaller ciphertext expansion and are widely implemented and understood?


What is "spinal-tap grade" security? As stated here Ed448 is different from Ed25519 because of "spinal-tap grade" security. What does this mean?

It is security on a 0-10 scale that goes to 11.

The cost of cryptanalysis to break a cryptosystem with a 128-bit security level, like Ed25519, is out of reach for humanity already.  A higher security level like Ed448's doesn't have any actual meaning with current understanding of cryptanalytic attacks.  The only purpose it serves is to hedge against potential modest future advances in cryptanalysis—a radical advance like a cheap quantum computer would devastate Ed25519 and Ed448 alike, of course.

P.S.  I see you tagged this jwt and jwe.  JWT and JWE, and JOSE generally, provide a different sense of ‘spinal-tap grade’ security, which is that they are a parody of security.


How do people know decryption is successful? Decryption is simply a process of transforming one byte string into another with an input argument private_key. However, if people have no knowledge about the plaintext, how do they know the decryption is successful?

For example, suppose the plaintext is a byte string abcd, and transformed into ciphertext whatever in the encryption process. Then let's assume the decryption process transforms whatever into abcd with one private key, and wxyz with another private key, how do people know which result is the original plaintext?

It depends on the encryption scheme if the correctness of the result is verified or not.

For instance, the output of an asymmetric scheme such as raw RSA decryption (just modular exponentiation) is just a number; you cannot directly distinguish between a correct and incorrect answer.

However a secure padding scheme such as OAEP then a possible output of OAEP can be "decoding error". Decoding error shows that something went wrong when removing the padding, which would happen if the resulting (padded) plaintext message contains is not encoded correctly. And that situation would arise (with high certainty) if either the ciphertext or the private key was incorrect.

The same goes for symmetric decryption. Decryption with AES-CTR always succeeds, the result is just a bit string. AES-GCM is however an authenticated cipher and will result in an error if the key is incorrect.

There are schemes in which the result does sometimes result in an error and sometimes it doesn't. A perfect example of this is AES in CBC mode with PKCS#7 padding and PKCS#1 v1.5 padding for RSA encryption. In that case the scheme sometimes results in an error and sometimes it doesn't. This leaks information about the plaintext which can be exploited by a padding oracle attack.

If your scheme doesn't return an error (with high certainty) then you can protect it with a signature (for asymmetric crypto) or MAC (for symmetric crypto). Usually sign-then-encrypt is used for asymmetric crypto and encrypt-then-MAC for symmetric crypto.

As an attacker you can use any information about the (padded) plaintext to see if the result is (partially) correct. This could include information about padding, formats of data structures (and therefore files), frequency analyzes of text etc. etc. etc.

An attacker may also use errors returned from the decrypting party to obtain information. This is called a plaintext oracle attack (a padding oracle attack is usually seen as a specific plaintext oracle attack).

Notes:

an error is often indicated as $\bot$ in scientific papers on cryptography (falsum)


How can I add more rounds to AES? I'd like to understand a bit more about the AES key schedule if anyone would mind explaining that. For instance, why is the way the schedule generated (with recursive xors and occasional substitutions) more secure than say, using pbkdf2 on the key, then using it on the result, and on until there is enough data?

The reason I ask is because I'd like to experiment with an extended AES implementations, with more rounds, but need to devise a way to generate the extra sub keys.

The AES key schedule isn't more secure than using PBKDF2 on the data -- but it is a lot faster, and requires many fewer gates in silicon.  Performance is important.

As far as devising your own variant of AES, with more rounds: don't do that.  There's no good reason to do that (it is exceptionally unlikely that AES is the weakest link in your system), and you can easily introduce subtle security vulnerabilities.  Whatever problem you have that you think motivates this, modifying AES isn't the solution.


Where to apply Montgomery Multiplication in GF(2^n) I'm optimizing a Reed Solomon decoding library for several polynomials in $\operatorname{GF}(2^k)$, $k\in\{8,10,12\}$.
Reading about the Montgomery Multiplication from Çetin K. Koç & Tolga Acar's Montgomery Multiplication in $\operatorname{GF}(2^k)$ (in Designs, Codes and Cryptography, 1998), I'm wondering if and how the method could help in polynomial reduction after carry free multiplication.

$t(x) = a(x)b(x)$ is a full length (2k-1) polynomial from carryless multiplication
$u(x) = t(x)n'(x) \bmod r(x)$  returns lower half of the $\operatorname{GF}$ multiplication
$(u(x)n(x) + t(x)) / r(x)$ corresponds to the higher half of one $\operatorname{GF}$ multiplication and one XOR

Instead of calculating $a(x)b(x) \bmod n(x)$, I have now $a(x)b(x)r^{-1}(x) \bmod n(x)$, and there's just one place where I can imagine using it. In inversion by modular exponentiation, where instead of calculating $a(x)^{254}$, I can calculate $(a(x)r^{-1}(x))^{254}$ and multiply that with a constant $r^{254}(x)$.
But can it be used e.g. in polynomial evaluation (used e.g. in syndrome calculation) or for modular reduction after $\operatorname{GF}$ multiplication?

The usual motivation for using Montgomery multiplication is that it significantly reduces the cost of modular reduction by changing the representation of elements. In the Montgomery ring the polynomial $A(x)$ is instead represented by $a(x)=A(x)r(x)\pmod{n(x)}$ where $r(x)$ is a fixed element of the same degree as $n(x)$, but for which division is very efficient (e.g. $x^k$). If likewise we have $B(x)$ represented by $b(x)=B(x)r(x)$ then $a(x)b(x)r^{-1}(x)\equiv A(x)B(x)r(x)\pmod{n(x)}$ which is the representation that we would choose for $A(x)B(x)$ and so your algorithm is way of implementing modular multiplication of polynomials in this representation without having to do a modular reduction. Addition and subtraction do not need new algorithms. If you have an algorithm involving many modular multiplies, it can be worthwhile converting to Montgomery ring representation, using Montgomery arithmetic and then converting back.
To convert $a(x)$ back to $A(x)$ we need to multiply by $r^{-1}(x)$, so it can be useful to precompute and save $r^{-1}(x)\pmod{n(x)}$. I don't know of any way to avoid modular reduction in this final conversion.
Evaluating using the Montgomery representation is possible, but requires a little extra work: to evaluate $A(x)\pmod{n(x)}$ given its representation $a(x)$ we have to evaluate $a(x)\pmod{n(x)}$ and $r^{-1}(x)\pmod{n(x)}$ and multiply the two answers together. However, if many evaluations are needed for the same input $m$, the value $r^{-1}(m)$ can be reused and the overhead is not as great.


Post-quantum SNARGs with near-constant verification? We're building a private computation platform similar to Zexe, where nested proofs are used to preserve the privacy of the programs being computed. We may use different proof systems for the inner and outer proofs. For the inner proofs, we're searching for a system with these properties:

Conjectured post-quantum security, which rules out Groth16 etc.
Constant or near-constant verification time. Logarithmic would be okay, but polylogarithmic (like STARKs) would be undesirable. If verification was polylogarithmic, we'd probably want multiple verification programs to handle different ranges of proof sizes, and the verification program being used for a computation would leak some information about the kind of computation being done.
Non-interactivity.

We don't need a zero knowledge property; that would be redundant since privacy is already protected by the outer proof system.

I believe the PCP theorem implies that it's at least possible to get logarithmic proof sizes (in the QROM), by transforming a PCP scheme into a sigma protocol, then applying Unruh's transform for non-interactivity. If we used a Merkle accumulator for commitments in the sigma protocol, the SNARG would consist of a constant number of log-sized Merkle paths.

Is this reasoning correct? Are there any practical proof systems with these properties?

There exists as of today two candidate SNARGs satisfying all your criteria. The first one is a recent proposal by Boneh, Ishai, Sahai, and Wu, which was presented last year at Eurocrypt. They achieve this construction by building upon the notion of linear-only encryption, which had been developed in previous works of some of the authors.

The second one, by Gennaro, Minelli, Nitulescu, and Orrù, is even more recent, it was presented at CCS this year. It generalizes square span programs, which were previously used to build SNARGs under pairing-based assumptions, to the lattice setting. It also comes with a proof-of-concept (unoptimized) implementation.

Both approach suffer from a common downside: they are designated-verifier, which means that a secret verification key is required to check the proof. If you crucially want public verifiability, even though it's theoretically feasible in a quantum-safe setting (as you mentioned, applying the random-oracle-based Fiat-Shamir transform to Kilian's succinct PCP-based proof system does the trick, and leads to logarithmic proof size and verification time), we do unfortunately not yet know of any concretely efficient construction that would meet all of your criteria.


Why do some key derivation functions (like PBKDF2) use a salt? Let me start by explaining my understanding of the various concepts involved in this question:

Salt: Random bytes of data used as secondary input for a password hashing function, like so:

hashfunc(<password>, <salt>) -> <hash>

And both the <hash> as well as the <salt> that was used are then stored (in a database, for example).

This prevents attacks using rainbow tables, making it more difficult for an attacker who has access to the output of the hash function (<salt> + <hash>) to deduce the original <password>.
Key derivation function: A function that takes a password <password> and an integer <size> as input, and generates arbitrary bytes of the desired <size> as output, like so:

kdf(<password>, <size>) -> <bytes of length <size>>

This allows us to turn a plain-text password like "admin123" into a key of a certain size that can be used by other cryptographic functions (like AES encryption, which requires a key of size 32).

So if my understanding is correct, then key derivation functions have no use for a salt. After all, the derived key isn't intended to be stored - it'll be used as input for another cryptographic function, and then it'll simply be discarded. Unless someone steals the derived key from the computer's memory in this short time frame, there is no risk of a rainbow table attack.

And yet, according to wikipedia, the PBKDF2 key derivation function takes a salt as input:

  The PBKDF2 key derivation function has five input parameters:

  DK = PBKDF2(PRF, Password, Salt, c, dkLen)

What purpose does this salt serve? Did I misunderstand the purpose of key derivation functions?

Related questions:

PBKDF2 and salt does not answer my question because the answers seem to assume that the derived key will be stored, which, according to my understanding of key derivation functions, should never happen.

PBKDF2, like most password-based key derivation functions, has a salt input because that is often useful. Two examples:

When using PBKDF2 as a key derivation function, the salt allows to re-use the same master key for multiple derived keys, e.g. a confidentiality key and integrity keys, with a different salt per use. In the same vein, PBKDF2 could be used to generate per-site passwords from a master password and the site name as salt.
When using PBKDF2 for storage of access-control password tokens, salt will make brute-force attack impossible to carry before the salt is known, defeating rainbow tables. That's noted in the question.


Simple proof of work example? Can anyone show me a simple proof of work algorithm that I can use to stop spammers? I've looked at hashcat, but i think there's a bit too much specialized hardware for bitcoin mining.

That is, the time required to calculate one proof of work on a mobile device cpu is way too long compared to a bitcoin mining rig using asic-miners.

Bitcoin ASIC miners are specialized hardware, which is capable of computing SHA-256 only. If you change almost any parameter in the Bitcoin proof-of-work, the existing miners will be useless. For instance, you could just change SHA-256 to SHA-1 or SHA-3.

To be more efficient against spammers equipped with GPU, you might want to employ a hash function that requires a certain amount of memory to compute hash. Scrypt is a reasonable choice with hundreds MBytes of RAM as a parameter, and the ongoing Password Hashing Competition will likely to produce better and faster candidates.


How to encypt/decrypt messages after ECDH key agreement I am using Diffie-Helman key exchange to generate the shared secret. But how will can a message be encrypted using this shared key?

You can't encrypt a message with ECDH alone, because all it gives you is a shared secret that you can't really control. Rather, you use that secret in a symmetric scheme like AES (generally after passing it through a KBKDF to convert from an ECDH result to a proper-length and less-structured symmetric key, which you then use as the key for symmetric crypto).


Ensuring integrity of a client side script I want a script that is running on the client to compute a collision resistant hash and send it to a server. I need to ensure that the script which performs this hash is not altered in any malicious way. Is there any protocol that exists which can ensure that the client script that calculates the hash has not been altered.

I have an idea whereby the script sends back an HMAC signature of itself, but on second thoughts, this would not stop an attacker from fooling the server if the code is altered.

In short any proposed solution to this problem would be a violation of CWE-602: Client Side Enforcement of Server Side Security.

Even if what you are suggesting where possible in some bizzaro universe it would be insecure.  A client (or an attacker) doesn't just execute scripts,  they are able to view and modify everything in memory,  as well as intercept,  modify and create any request transmitted over the network.  Thus checking the integrity of the script doesn't even close to solving the root of the problem.  In short this proposal is a fundamental violation of modern security and there never will be a solution to this problem. (And no one should need to do this)


How can we prove that the following theorem is valid for almost perfect secrecy? We have the following theorem:

  Let $\Pi$ be a perfectly-secret scheme over message space $M$, and let $K$ be determined by $Gen$. Then $|K| ≥ |M|$.

How can we prove that the above theorem is valid for almost perfect secrecy? The definition for almost perfect secrecy is as follows:

  The encryption scheme $\Pi = (Gen,Enc,Dec)$ over a message space $M$
  is almost perfectly secret or $\varepsilon$-perfectly secret
  if for every probability distribution over $M$, $\forall m \in M$ and
  $\forall c \in C$ for which $Pr[C = c] > 0$ and for a constant
  $\varepsilon < 1$:

  $$|Pr[M = m|C = c] - Pr[M = m]| < \varepsilon$$

EDIT

You cannot prove that because it is not true.

Chapter two of the book Introduction to Modern Cryptography explains about perfect secrecy and defines this $\varepsilon$-perfectly secret notion. In exercise 2.12 you are asked exactly to

  [...] Show that $\varepsilon$-perfect secrecy can be achieved with $|K| < |M|$
  when $\varepsilon > 0$.


Is this the correct procedure for cycle walking using an FPE? To encrypt a value from a set (say a range of years from 1001 to 2001)

Rank the set

{0 = 1001, 1 = 1002, 2 = 1003...999 = 2001}
Take the value you want to encrypt from the set (year = 1995) and determine the ranked value = 996
convert this to binary 996 = 1111100100
Encrypt binary value using FPE(1111100100) = En where n is the iteration
If En lands outside desired maximum of 999, take En and encrypt again FPE(En) = En+1
Stop when En+1 is inside range 0 - 999, else repeat step 5

Questions,

Is this the correct way to perform cycle walking using any FPE?
What is the smallest probability of landing outside the desired range? What is the largest?

Note:  In my case I'm using BPS as my FPE which has the restriction of at least two 'characters' as input so for binary number the smallest input values possible would be 00, 01, 10, or 11.  In decimal this is 0, 1, 2, 3.  Therefore the smallest range you can create from these values is 0 - 1.  So the probability of landing outside those two values would be 50%.  Is this correct?

Would 50% be the max probability of landing outside the smallest range - with the probability getting smaller as the range increases?

Yes, what you're describing is the correct way to cycle walk with FPE.

In your case, the value you're encrypting is ten bits, so the largest possible ciphertext is 1024. You'll only need to cycle walk if the ciphertext is from 1000-1024, so 24 of the possible 1024 values will cause an iteration. This means your probability of cycle walking for any particular value is $\frac{24}{1024} \approx \frac{1}{40}$, which is pretty small.


Advantages of using intermediate hash over full hash in digital signature application Description of intermediate hashes

Intermediate (or partial) hashes are canonical forms of digest state that can be transferred from one hash implementation to another, so that the other, limited device (e.g. a smart card chip) can finish the hash calculation with the remaining data. This scheme is used to create a signature generation system consisting of the devices performing the calculations.

So:

Terminal generates intermediate hash by processing the first i blocks of the message;
Terminal sends intermediate hash to the smart card;
Smart card finishes the hash with the last (N - i) blocks of data;
Smart card creates the signature and sends it back to the terminal;
Sends back the signature.

instead of:

Terminal creates full hash;
Terminal sends full hash to the smart card;
Smart card creates the signature and sends it back to the terminal;
Sends back the signature.

Obviously letting the smart card generate a full hash has drawbacks with regards to performance if the data to be hashed is large. This can still be an option, e.g. when the signature is generated over signed attributes instead of the content itself.

Intermediate hashes are not specified in the SHA-1, SHA-2 or SHA-3 standards.

Possible reason for using intermediate hashes

In my previous question I've already asked about if other protocols use partial hashes. Due to the limited amount of feedback there I'll probably have to conclude that they are not often used.

I've mused there that intermediate hashes could possibly be used to avoid covert channels, i.e. the insertion of data other than a hash into the signature generation. I'm not sure that this would pose a significant threat though (as the provider of the hash could also provide a hash over anything else).

Question

What cryptographic rationale is there to use intermediate/partial hashes instead of full hashes provided by the terminal?

There are two points I can imagine where partial hashes in a protocol can be useful.
Massively parallel computing from the same start
Using an intermediate state as the base for the PoW seems to be standard practice with Bitcoin ASICs these days and give a few dozen per cent of a speed-up. Technically you can pre-compute what you want in the next block and then send this to the ASICs for them to do the final compression function call and looking for the right property.
Regulatory Restrictions / Trusted-Signed Data Displayment
There may be regulatory restrictions along the lines of "the trusted computing device must have seen the actual transaction data", where the signature is over the sender, the recipient and the amount. Now the standard requires you to display the recipient and the amount on a card- / card-reader-controlled trusted display, however you could maybe save a bit of computation time by pre-computing the hash for the parts that do not need extra evaluation. Here the security gain would be in the fact that the card actually knows what it signed and not just some random blob (which could also have been a malicious transaction!).


Instantiating a random oracle I am studying about RO model and just got this question that what are the factors that make it not possible to instantiate a RO with a Hash function. To give a reference on how far I know about them and other specification, I've followed this series of blog posts, so far. So, e.g. I know that one factor is that a RO size is exponentially grows on input but is this the only factor that one cannot instantiate it in the real world?

(hash functions are deterministic functions whereas RO is a random one, is this the most significant factor?)

Well the idea of a cryptographically secure hash function (and often functions within them), is to mimic the Random Oracle model as closely as we can. Now, short of a little gremlin (perhaps?), some perfectly unbiased dice, a magical orb and a magic way to store all the possible outcomes from each input, we need these functions. I'm going to assume you know this and what you're asking is why do we need, "magic"?

Some points worth bearing on the Random Oracle:

The Oracle, would need infinite memory to memorise every query it
ever received (as well as the truly-random reply).
The Oracle is truly random, this is enough of a challenge already.
The Oracle would not only need the infinite memory, previously referenced but eventually infinite power, both ideas, violate some physical constants.
The Oracle ... is already debunked. (it's a useful model but it is magic)

So the next best thing to see is Crypto-Secure-DRBGs. - They and the hash functions based around are at the heart of everything the RO attempts to recreate... apart from we should note, with a computer algorithm anyone with access to the algorithm, can query "the oracle" (this isn't really a problem, though and to expect differently is ludicrous).

  (hash functions are deterministic functions whereas RO is a random
  one, is this the most significant factor?)

Basically, no: the most significant is the first one you mentioned, you can't memorise the outcome of every input, this is a physics issue or a maths issue, either-way, I don't think it needs dragging out.


Practical Key exchange for Internet In section 3.2 (page 10) of Vikram Singh's paper A practical Key Exchange for the internet using Lattice Cryptography, he gives the number of elements in each set for odd $q$. However, the results do not match my calculation of the number of elements in each set for odd $q$.

For example, given an odd prime $q=17$, you can see that calculated result does not match. Can anyone explain this discrepancy?

$\textbf{Randomized Rounding Procedure:}$

Let $q=17$. Thus $q\bmod 4 = 17\bmod 4 = 1 \implies q \equiv 1 \pmod4$

Now,

$$I_0 = \mathbb{Z}_q \cap \left[0,\tfrac{q}4\right) = \mathbb{Z}_q \cap \left[0,\tfrac{17}4\right) = \left[0,4\right)$$
$$I^{\prime}_1 = \mathbb{Z}_q \cap \left[\tfrac{q}4,\tfrac{q}2\right) = \left[\tfrac{17}4,\tfrac{17}2\right) = \left[4,8\right)$$
$$I^{\prime}_0 = \mathbb{Z}_q \cap \left[\tfrac{q}2,\tfrac{3q}4\right) = \left[\tfrac{17}2,\tfrac{51}4\right) = \left[8,12\right)$$
$$I_1 = \mathbb{Z}_q \cap \left[\tfrac{3q}4,q\right) = \left[\tfrac{51}4,17\right) = \left[12,17\right)$$

For odd $q$ the number of elements in each set is:

$$\left(\begin{array}{cc}\#I_1 & \#I_0 \\ \#I^{\prime}_0 & \#I^{\prime}_1\end{array}\right) = \left(\begin{array}{cc}\tfrac{q-1}4 & \tfrac{q+3}4 \\ \tfrac{q-1}4 & \tfrac{q-1}4\end{array}\right) \textrm{ for } q \equiv 1\pmod4$$
$$= \left(\begin{array}{cc}\tfrac{16}4 & \tfrac{20}4 \\ \tfrac{16}4 & \tfrac{16}4\end{array}\right)$$
$$= \left(\begin{array}{cc}4 & 5 \\ 4 & 4\end{array}\right)$$

But $I_0 = \left[0,4\right) = \left\{0,1,2,3\right\}$ (No. of elements is not 5), and $I_1 = \left[12,17\right) = \left\{12,13,14,15,16\right\}$ (No. of elements is not 4)

So, the number of elements in $I_0$ is not 5. Why?