Get IV from Key, Clear and Cipher text in AES-256 CBC Newbie question here but can I get the IV if I know the Key, plain text and chiper text ?

(I thought that if I encrypt 16 first bytes of clear with the key and 16 first bytes of cipher text as IV it would work to get original IV but it seems that it doesn't)

Thanks.

The IV is XOR'ed with the plaintext before encrypting the first block. You can get the input of the block cipher by decrypting the first block of ciphertext using the block cipher directly.

After that it is a simple operation to get the IV, of course, considering you know the plaintext and - hopefully - the mathematical properties of XOR.


What is special about an entropy count (RNDGETENTCNT) of 160 for libsodium initialization? (Moved from StackOverflow)

In the Usage documentation for libsodium, before calling the initialization function sodium_init, they suggest you check the entropy count of the system's CSPRNG (i.e. use ioctl to query RNDGETENTCNT). That makes sense. In the example code, they check that the entropy is at least 160.

What's special about the 160 value?

The Linux CSPRNG now uses ChaCha20, right? But I would think that would require more than 160 bits of randomness to be initialized (e.g. it looks like the getrandom syscall in more-recent kernels blocks until it gets randomness of at least twice the ChaCha20 keylength, which would be 512 bits).

The internal RNG uses a 256 bit seed, and on Linux, a byte is read from /dev/random to check that the pool is seeded.

The reason for requiring 160 bits to be available without blocking is unrelated.

During initialisation, the library reads and discards 32 bits from the RNG to check that it is available and working.

Shortly after, it will need 128 extra bits for the canary protecting guarded memory allocations.

Hence, if 160 bits are not immediately available, sodium_init() will block. This will happen even if the application doesn't need to generate any keys.


Conditions for a successful Differential Power Analysis attack From this paper, there are two conditions for a successful DPA attack:

i) there exists an intermediate variable in the implementation that is correlated with the power consumption and
ii) this variable exclusively depends on the plaintext (or ciphertext) and a small part of the key.

My question is that, on the condition i), does the variable need to appear on the calculation of the algorithm? Can a variable that is not explicitly computed correlate with the power consumption?

Can a variable that is not explicitly computed correlate with the
  power consumption?

Yes, and this can happen in several ways. When you say "not computed explicitly", I assume you mean that the computation is performed on a masked value or share instead. That is, the secret inputs (referred to as the key by the paper you link to) themselves do not directly appear in any of the computations. Below, I discuss why this condition is not enough.
So "correlation" is used in a very broadway. In fact, for higher-order attacks nonlinear dependencies (i.e. not just linear correlation) can also be problematic.

First, let's consider a traditional boolean masking scheme: add a random mask to the secret input of your combinatorial circuit.
Let's say that you've implemented a very nice masking scheme: operations are never done directly on the unmasked (secret) values and leakage, in general, is carefully avoided. So you made sure to choose the operations with care so that no intermediate values depend on the unmasked values.

(Un)fortunately, it has been shown that hardware glitches can leak information anyway. This paper concludes that this is a general problem for non-linear masked gates:

  It has turned out that masked nonlinear gates, such as AND, NAND, OR
  and NOR gates are susceptible to DPA-attacks, while masked linear
  gates, such as XOR and XNOR gates, are resistant to DPA attacks.

The general idea is that the number of gates affected by a glitch depends on the unmasked input, for example this paper has a nice example of a masked AND gate.
Methods that solve this problem have been proposed since then, though (see below). This is an area of active research.

Higher-order attacks are another possibility. I won't go into detail here, but if information from several points in the implementation can be combined, this (i.e. higher-order statistical moments) may leak information about the unmasked data.

I think my recent answer about threshold implementations is worth mentioning here.
There, mutual information analysis (MIA) can be used to attack the proposed scheme. Hence, it's an example of how, even though each share of the realization is independent of at least one of the input shares, an unshared (secret) value may still be revealed using MIA. Of course, simply observing several shares (also a higher-order attack) would also work. Higher-order threshold implementations attempt to mitigate this problem (but currently don't entirely succeed).

Note: Some comments on the question have also mentioned the influence of memory access. As my knowledge of that subject is relatively limited, I'll leave the discussion to others. So you can take this answer to be mainly about the combinatorial part of an implementation.

The generation of random masks is also an interesting subject by itself, and much could be said about that.
Other types of side-channel attacks, such as fault-attacks, will also lead to several other difficulties. For example, a fault-attack model allows active disruption of the implementation (injecting faults) which may lead to other ways of revealing key bits which do not explicitly occur in any computation. Consider what happens if you sabotage the RNG that provides the masks.


Is this a UC-secure commitment scheme in the ROM? To prove UC-security (universally composable security) of a commitment scheme, we must show that a commitment scheme is extractable and equivocal.

That is, we must construct a simulator that is able to extract the commitment of an adversary corrupting the sender (extractability) and construct a simulator that is able to open anything for an adversary corrupting the receiver given a commitment (equivocal).

Consider this commitment scheme in the Random Oracle Model:

Commit phase: The sender computes $c=\mathsf{RO}(M)$ where $\mathsf{RO}$ is the random oracle and $M$ the message to commit. It sends $c$ to the receiver.
Opening phase: The sender sends $M$ to the receiver. The receiver checks if $c=\mathsf{RO}(M)$.

It seems to me that this protocol is UC-secure since the simulator has control of the random oracle. Thus, it can always know the message $M$ by looking at the calls to the random oracle. The simulator can also open any message $M'$ it wants by returning $c$ to future queries of $M'$ by the adversary corrupting the receiver.

My questions are:

Is this correct?
If so, what is the point of constructing UC-commitment schemes in the ROM like
https://eprint.iacr.org/2014/908.pdf
and
https://link.springer.com/content/pdf/10.1007/978-3-540-24638-1_4.pdf
since this protocol seems much more efficient than the others.

Thank you!

No, your construction is insecure, specifically it fails to be hiding. A receiver who has a guess of $M$ can simply check whether $H(M)=c$ since $H$ is public. You can see that your suggested simulation strategy fails when the adversary has already queried $H$ on $M$ before the simulator learns that the commitment should hold $M$. The argument to $H$ should have high entropy even conditioned on a correct guess of $M$. Change the construction to $H(M\|r)$ for long random $r$ and you have the standard folklore commitment in the random oracle model.
Naively using a random oracle in the UC model is kind of like cheating. You get a totally independent random oracle for each protocol instance. It's not a great model for a supposedly public object. Those papers you reference try to use a random oracle in a less "cheaty" way, so their protocols have to work harder. Also at least the first paper avoids having the simulator program the oracle's outputs (non-programmable random oracle model) which is often seen as more palatable.


Combine two sha512 hashes to a single hash Assume I have two data fragments: $Frag_1$ and $Frag_2$.

I can build sha512 hashes the usual way with $SHA512(Frag_1)$ and $SHA512(Frag_2)$ and then hash the two fragments appended to each other:

$$SHA512(Frag_1 | Frag_2)$$

My question is, is there any way to combine the hashes of those two fragments so that it would be possible to compute the hash of their appended version?

More precise: Is there an operation (denoted here with a red question mark “$\color{red} ?$”), so that

$$SHA512(Frag_1)\ \color{red} ?\ SHA512(Frag_2) == SHA512(Frag_1 | Frag_2)$$

It is possible to create the data fragments with a length of a multiple of the block size of sha512?

Most standard-use iterative hash functions (including SHA-512) are build in a way that these types of operation are not possible (without breaking the hash function).

They work generally in this way:

The message is split in same-size blocks (usually with some padding at the end to fill the last block): $pad(M) = M_0 || M_1 || M_2 ... || M_n$.
There is some internal "state" $S$, initialized to a fixed value $S_0$ at the start
For each block, some internal function $C$ (usually called a "compression function") is applied to the old state and a message block to produce a new state: $S_{i+1} = C(S_i, M_i)$
At the end, either the last state is output directly, or (in more modern hash functions) another function $O$ is applied on that state to produce the final hash output: $h(M) = O(S_{n+1})$

So for example with a 4-block message (after padding) we have $$h(M) =  O(C(C(C(C(S_0, M_0), M_1), M_2), M_3)).$$

The compression functions are usually build in a way that even a minor change in one of the inputs produces a totally different output, and such that there is no easy way to go back from the output to the input. (This is usually formalized as "$C$ is a one-way function".) (Sometimes parts of the state are treated specially and can be easily tracked back, like in Skein, where they contain a counter. This is not the case for SHA-256, and also in Skein this doesn't hurt anything, as the output doesn't include them.)

Even assuming there is no padding, O is the identity and our fragments have both the size of only one block, we get $h(F_1) = C(S_0, F_1)$, $h(F_2) = C(S_0, F_2)$ and
$h(F_1||F_2)) = C(C(S_0, F_1), F_2)$.
While we can write the latter also as $h(F_1||F_2)) = C(h(F1), F_2)$, the one-way property of the compression function doesn't allow us to get any information about this from $C(S_0, F_2)$.

But if you have $F_2$ actually given, not just its hash, you can use this to create the hash of $F_1||F_2$, even without knowing $F_1$. This is known as the length-extension property of iterative hashes with the identity as its output transformation.
In reality it is complicated by the presence of a padding, but you still get to create the hash for something like $F_1 || P || F_2$, where you know $h(F_1)$ (but not $F_1$ itself), $P$ is some padding depending on the length of $F_1$ (and not actually needed to be known by you), and $F_2$ is a string chosen by you).

Using a non-trivial output transformation blocks this – possible ways are to apply some simple truncation (like SHA-384, which is essentially SHA-512 with a different initial state and a truncation of the result), or some other compression-function-like transformation. Or simply apply the whole hash function again on the result (this is used e.g. as SHA-256d in the Bitcoin protocol).

On the other hand, there are hash functions which are specifically designed to allow stuff like that: hashing two (or more) parts of the message separately and create the final hash from the partial hashes.

Have a look at the Merkle tree article in Wikipedia, it explains the basic principles. When used as a simple message hash algorithm (and not a complex structure), for it to have a deterministic result, the size of $F_1$ needs to be one of some few specific values (e.g. powers of two), so the limit between $F_1$ and $F_2$ falls exactly on a border between two subtrees.


Does shift cipher with non-uniform plain text probability have perfect secrecy? I am having a hard time grasping the perfect secrecy concept. (I have already tried solving a couple of similar problems, so please don't think I am trying to get you guys to do my work, I really am stumped on this).

Consider a shift cipher with plaintext, key and cipher-text space is $[0..7]$ i.e.

$$
P = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}\\
K = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}\\
C = \{0, 1, 2, 3, 4, 5, 6, 7, 8\}
$$

plain-text's even alphabets have twice the probability of odd alphabet i.e.

$$
\forall p \in P:
\Pr_P(p) = \begin{cases} \frac{2}{12} & \textrm{ if p = 2(b) for some b $\in$ Z } \\
\frac{1}{12} & \textrm{ if p = 2(b) + 1 for some b $\in$ Z }
\end{cases}\\
\\
\forall k \in K: \Pr_K(k) = \frac{1}{8}
$$

From here I have calculated that $\Pr_C(c) = \frac{1}{8}$.

How do I calculate $\Pr(y|x)$
How do I use Baye's theorem to calculate $\Pr(x|y)$
How do I show whether $\Pr(x|y) = \Pr(x)$ or $\Pr(x|y) \neq \Pr(x)$ (thereby determining whether this cipher has perfect secrecy or not).

For any ciphertext $c \in C$ and message $p \in P$ we have
$$P(c|p) = \frac{P(p\cap c)}{P(p)} = \frac{P(p\cap k)}{P(p)},$$
where $k = c-p$. This is because if the plaintext is $p$, the ciphertext is $c$ if and only if the key is $k$. Now, if the key is chosen independently of the plaintext we have $P(p\cap k) = P(p)\cdot P(k)$, and so finally $P(c|p) = P(k) = 1/8$ if the key is chosen uniformly.


Performance of ECDSA, ECKCDSA and ECGDSA It is proven that ECDSA algorithms are faster in key and signature generation compared to RSA. In addition, the signatures are much shorter.

However, I would like to know the performance difference of the variants ECKCDSA and ECGDSA compared to either ECDSA or RSA. ECGDSA avoids the calculation of the inverse in the signing phase, but is there really a significant performance increase?

In the ECKCDSA algorithm, the public keys are validated by means of certificates. Does this step decrease the performance?

If you want to know practical measurements, which depend not just on the signature scheme family but also on the choice of curve and so on, your best approach will be to submit the software you are considering using to eBATS, unless you are also concerned with specific hardware not represented there in which case you're in a better position to do your own measurements than anyone else.

That said, we can estimate costs of the arithmetic required for straightforward implementations of these signature schemes.  Let $B$ be the standard base point in the curve group in question, $n$ its order, and $A$ another curve point serving as public key, with $A = [a]B$ for secret $a$ known only to the signer.

Verification.
The verification equations for a signature $r, s \in \mathbb Z/n\mathbb Z$ on a message $m$ (and certificate hash $h$ in ECKCDSA) are:

ECDSA: $r \equiv x\bigl([H(m)\,s^{-1}] B + [r s^{-1}] A\bigr) \pmod n$
ECGDSA: $r \equiv x\bigl([r^{-1} H(m)] B + [r^{-1} s] A\bigr) \pmod n$
ECKCDSA: $r = H\bigl(x\bigl([r \oplus H(m, h)]B + [s]A\bigr)\bigr)$

(I'm omitting details of checking the ranges of $r$ and $s$, rejecting zero, etc.  If you run with the scissors included in this post and you stab yourself to security death, it's your fault, not mine!  Consult the standards for what you need to pacify auditors.)

It is hard to imagine that verification performance would be different between comparable implementations of ECDSA and ECGDSA, because you can trivially express one as the other with different parameters.  The ECKCDSA verification equation involves an extra hash, but that is likely to be negligible compared to the cost of the inversion it avoids altogether.

Signing.

Here $k$ is a scalar modulo $n$ chosen uniformly at random.  I'm omitting all the details of fenceposts required by the procedure in the standards, and the additional step of verifying the signature after generation to confirm no faults.

ECDSA: Compute $r = x([k]B)$; $s$ must be a root of $H(m)\,s^{-1} + r s^{-1} a - k$ modulo $n$, so compute $$s \equiv k^{-1} (H(m) + r a) \pmod n.$$  Thus, the cost is

1 elliptic-curve scalar multiplication,
1 inversion modulo $n$ to compute $k^{-1}$,
2 multiplications modulo $n$ to compute $r a$ and $k^{-1} (H(m) + r a)$, and
1 addition modulo $n$ to compute $H(m) + r a$.

ECGDSA: Compute $r = x([k]B)$; $s$ must be a root of $r^{-1} H(m) + r^{-1} s a - k$ modulo $n$, so compute $$s \equiv a^{-1} (k r - H(m)) \pmod n.$$  The substantive difference from ECDSA is that the element we must invert is the long-term secret $a$, so we can just store $a^{-1}$ rather than recompute it, rather than the per-signature secret $k$.  Thus, the cost is

1 elliptic-curve scalar multiplication to compute $[k]B$,
2 multiplications modulo $n$ to compute $k r$ and $a^{-1} (k r - H(m))$, and
1 addition modulo $n$ to compute $k r - H(m)$.

ECKCDSA: Compute $r = H(x([k]B))$; $s$ must be a root of $r \oplus H(m, h) + s a - k$ modulo $n$, so compute $$s \equiv a^{-1} (k - r \oplus H(m, h)) \pmod n.$$  Once again, we invert the long-term secret rather than the per-signature secret, so the cost is

1 elliptic-curve scalar multiplication to compute $[k]B$,
1 multiplication modulo $n$ to compute $a^{-1} (k - r \oplus H(m, h))$, and
1 addition modulo $n$ to compute $k - r \oplus H(m, h)$

(and 1 $\lceil\log_2 n\rceil$-bit xor to compute $r \oplus H(m, h)$, which should be negligible).

Cost of inversions.
How much does an inversion cost versus a multiplication or an addition?  Usually inversion will be computed using Euler's theorem with square-and-multiply exponentiation in Montgomery form.  This costs $\ell + w$ multiplications into $2\ell$-bit integers, $\ell$ squarings into $2\ell$-bit integers, and $2\ell + w$ additions into $\ell$-bit integers for the Montgomery reductions, where $\ell = \lceil\log_2 (n - 2)\rceil$ is the length of $n$ in bits and $w$ is the Hamming weight of $n - 2$, plus a little more to get the Montgomery multiplication started.

So outside the elliptic-curve scalar multiplications, inversions dominate the time spent, and there is probably a measurable difference to be had by avoiding them.  Could you do better than generic square-and-multiply exponentiation using a custom multiplication chain?  Yes, but unless $n$ has a very special form (which is hard to imagine!), inversion would still dominate.  Replacing one multiplication by an xor in ECGDSA vs. ECKCDSA?  Probably not going to matter to you.

Could you do ECDSA without per-signature inversions?
Yes: you could swap the rôles of $r$ and $s$ and effectively get ECGDSA and nobody would be any the wiser, except for the auditors hired to study your software who crash your party wondering why you aren't following the letter of the bureaucratic government standard mandating a wacky bizarro variant of Schnorr signatures with unreasonably slow signing procedures.

Inversion-free alternative.
May I interest you in the Schnorr-based EdDSA, which avoids inversions altogether for signing and verification, and is widely available in high-quality software running in constant time with defense against broken random number generators at signing time?

(Schnorr's patent expired a while ago, so you don't have that excuse to hide behind any more!)


Plain cascade and Xor cascade I have seen in few places (mostly papers) talking about plain cascade and XOR cascade. I know what is cascade cipher is but I am not clear about what these are. Can anyone help to understand using simple words to define what is a XOR cascade? (how XOR is involved in cascade cipher?)

Without more context the answer isn't quite precise. In the following answer $\oplus$ always denotes bit-wise XOR.

First let's quickly revisit "plain" cascade encryption. You encrypt arbitrary messages using the keys $K_1,K_2,K_3$ and the encryption algorithm $E$ as follows: $C=E_{K_1}(D_{K_2}(E_{K_3}(P)))$

Now the first possible XOR-cascading construction (more common) is to use three stream-ciphers (or blockciphers in CTR-mode) as follows: $C=E_{K_1}(Ctr)\oplus E_{K_2}(Ctr)\oplus E_{K_3}(Ctr)\oplus P$. This was already recommended by B. Schneier in his Applied Cryptography.

The mode, I think is most likely the one you're looking for, is proven secure in this paper. First you need again the three previously mentioned keys. Secondly you need four more keys of the same length as the blocksize (128-bit for AES-256). Using these additional four keys $l_i$, you encrypt the plaintext $P$ as follows:
$C= E_{K_3}(E_{K_2}(E_{K_1}(P\oplus l_1)\oplus l_2)\oplus l_3)\oplus l_4$.


What is KEK and how is used for key sharing? i'm trying to understand how the keys are shared on the 10Gbit passive optical network, and i've found that the keys are generated by ONUs or OLT and after shared with AES-ECB with KEK.

What is it this Key Encryption Key, and how is used with AES to share keys?
Thank You

A Key Encryption Key or KEK is simply a key that is solely used to encrypt keys. The keys that are encrypted are usually keys that have a specific meaning such as domain specific keys. It could also be that the encrypted keys have shorter life time such a as session keys.
A KEK may be used in combination with ECB mode as the encrypted key material should be indistinguishable from random. This is one of the few places where ECB encryption does not leak information. Note that it is an extremely bad idea to encrypt structured information with ECB; this includes most asymmetric keys as they generally consist of multiple encoded components.
Currently I would advice a scheme such as AES-SIV or AES-GCM-SIV. This will create a randomized ciphertext if the key only differs by a single bit. The calculated synthetic IV in SIV mode double acts as an authentication tag. This means that any changes (deliberate or not) of the key value can be detected. Beware that it is still possible to e.g. swap encrypted key values though - this is something that the wrapping algorithm itself cannot provide protection for.
Key encryption is sometimes also called wrapping. The KEK is then called a wrapping key and the protected key is of course called the wrapped key.


Which AES modes can decrypt from anywhere in the ciphertext CTR is amenable to parallelization because you can split the message into chunks, each chunk having a range of counter values associated with it, and encrypt (or decrypt) each chunk independently. What I would like to know is if any other modes can do this?

EDIT:

My reason for wanting to know this is that I have a class with and encrypt function, and if you encrypted two plaintexts with CBC mode for example, it encrypts them from scratch. If I'm using a mode in which that doesn't matter, CTR for example, then I won't raise an error if the user tries to encrypt another block.

The practical answer is that you should almost certainly be using authenticated encryption, in which case authenticating an individual encrypted message requires you to process all of it anyway.  Once you throw in this element, random access into encrypted data becomes not a matter of message encryption modes, but rather of how to split your data into a collection of messages that you can encrypt and authenticate individually.

The literal answer is that among the classic confidentiality-only block cipher modes, CBC and CTR can start decrypting from any block, while CFB and OFB cannot.  You can read this pretty straightforwardly from mode diagrams; here's CBC decryption (diagrams from Wikipedia entry):

Neither of the inputs to each block cipher call require the output of any other other block cipher call—there are no arrows going outside of one block cipher decryption box and into another, unlike for example with OFB mode:


RFC6979: error in reference implementation? If I correctly understand RFC 6979, there is an error in the ref implementation section 3.2.

In the step H2, RFC specification says

 2.  While tlen < qlen, do the following:
              V = HMAC_K(V)
              T = T || V

but in Java implementation in the RFC appendix, we found the comparison with rolen

That does not provide the same result.

For example if used with Stark curve with prime field equal to 0x0800000000000011000000000000000000000000000000000000000000000001, qlen is 252 and rolen is 256

As consequence the loop occurs twice with rolen, but only once with qlen. it doesn't change the first k value but the subsequent k change.

The RFC code has been used now from third software.

Any thought about that?

The RFC specifies things in terms of bits. Each call to HMAC outputs hlen bits. tlen is the count of bits obtained so far; when at least qlen bits have been obtained, this step is finished.

The sample code is written in Java in which the elementary unit of information is the octet ("byte" in usual terminology). The supported hash functions always output a given number of bytes, and there is no fractional byte. In other words, within that code, hlen is always a multiple of 8. This implies that tlen is also a multiple of 8.

The rolen value is the length of q in octets; that is, it is equal to qlen/8, rounded up. This is OK in the code, since hlen is a multiple of 8. For instance, with a curve such that qlen is 252, the generation needs 252 bits of output from HMAC; but since hlen is a multiple of 8, you cannot get 252 bits of output without getting at least 256 bits of output. Thus, the code can keep track of things counting octets (hence, rolen) instead of bits. With HMAC/SHA-256, you get 32 bytes of output per HMAC call; and rolen is 32. Thus, one call will be enough to get rolen bytes, and there won't be a second one.


Hash functions and the Avalanche effect Informally, the Avalanche effect says that two similar, but not identical, inputs should produce radically different outputs when fed through a hash function.

I've seen, at least, two formal definitions of the effect. The first is that if we flip one bit of an input, the two respective outcomes should typically be very different and it's guaranteed that they're not the same. The other definition is that if we flip one bit of an input, the outcomes are statistically independent. I find this confusing: the two definitions are contradictory.

What is the proper definition? And practically, does modern hash functions like sha256 have this property?

To set ideas. Let $H(\cdot)$ be some hash function with $N$ possible outputs. Let $X_1$ be an (integer) random variable, uniformly distributed on some interval. (Assume that $\Pr(H(X_1) = x) = N^{-1}$ for each $x$.) Let $X_2$ be a RV such that it differs exactly in one bit with respect to the first RV (i.e., the Hamming distance between $X_1$ and $X_2$ is exactly one). What does the Avalanche effect says about $\Pr(H(X_2) = H(X_1)\,|\, H(X_1))$?

The first definition says that $\Pr(H(X_2) = H(X_1)\,|\, H(X_1)) = 0$. The second says that $\Pr(H(X_2) = H(X_1)\,|\, H(X_1)) = N^{-1}$. Obviously, both cannot be true.

The proper definition of avalanche effect is defined in the paper of Webster, A. F. "On the design of S-boxes". Advances in Cryptology - Crypto '85 as :

  For a given transformation to exhibit the avalanche effect, an average of one half of the output bits should change whenever a single input bit is complemented.

It is also seen as each bit should have 50% chances to change if you change 1 bit of the input.

This basically mean that in order to test an avalanche effect, you have to apply an algorithm similar to the following.

# result array
array res[n] = {0, ..., 0}

# compute all inputs
for each inputs x of size n
   ref_val = H ( x )

   # compute all possible 1 bit change
   for i in 0..n-1
      test_val = H ( X ^ (1 << i) )

      # compute statistics per bit
      for j in 0 .. n-1
         res[j] += ((test_val ^ ref_val) >> j) & 1

# in the end forall k, res[k] / (n * 2**n) should be around 50%.

Due to the size of the inputs, you can test with a relative precision whether or not $\operatorname{SHA256}$ does have a strict avalanche effect. But by doing a sampling over a large number of inputs where you flip each bit once, you can have a measure.But in most cases we usually analyze the components of the primitive in order to assert whether or not the avalanche effect is respected.


Struggling to understand Perfect Forward Secrecy From the definition on Wikipedia:

  In cryptography, forward secrecy (FS), also known as perfect forward secrecy (PFS), is a feature of specific key agreement protocols that gives assurances that session keys will not be compromised even if the private key of the server is compromised.

So, if I am understanding this right, a protocol establishes PFS if the leak of the master key does not enable a calculation of already-used session keys.

But I read a question here that PFS can be achieved by deriving session keys with a hash of an old session key. But if I were to know the master key (the pre-shared key?), I could easily calculate all session keys or am I misunderstanding something?

But I read a question here that PFS can be achieved by deriving session keys with a hash of an old session key. But if I were to know the master key (the pre-shared key?), I could easily calculate all session keys or am I misunderstanding something?

So the idea of PFS is that if the entire (secret) state of an entity at a time point $x$ is leaked and there exists at least one previous session, then there is a time point $x'<x$ where before that you lack knowledge to recover information from ciphertexts.

If we use this more formal definition and the participants do indeed erase old keys upon a key-update, then the scheme from the other question provides forward secrecy. If the initial key is now leaked, the first condition is violated as there is no previous session and the definition doesn't claim post-compromise security (where if you leak state at one point it will recover from passive adversaries). Now if you leak the state at a later point then obviously you cannot recover the key from a previous session because the hash is one-way.


Python library that implements additive homomorphism of Elgamal Encryption on the Elliptic curve i.e X25519 or P-256 I'm trying to find a Python library that implements Elgamal Encryption on the Elliptic curve i.e X25519 or P-256.
My purpose is to use the additive homomorphic property of Elgamal.
I'm using https://github.com/data61/python-paillier
Python library for Paillier to have additive homomorphism.
However, since I'm only encrypting small integers(32bit). Therefore, I think Elgamal will be faster for encryption and will have a shorter key and cipher size than Paillier [If my conceptual understanding is correct].
Hope someone already implemented and using such a library. Looking forward to knowing such a production-grade library.
I found a library that says they implemented Lifted-Elgamal (not sure what Lifted means here)
https://github.com/herumi/mcl
However, it seems they use Type-3 pairing to achieve multiplicative homomorphism in Elgamal. To my understanding pairing operation is expensive since the underlying operations are carried over the extension over the prime field.

We'll say that asymmetric encryption is homomorphic below $\ell$ when, given the public key and ciphertexts $C_i$ obtained from plaintexts assimilated to integers $a_i\in\mathbb N$ such that $\ell>\sum a_i$, it can be efficiently computed ciphertext $C$ that deciphers to $a=\sum a_i$.
The best known example is Pailler encryption, which when the secret primes are 1024‑bit is homomorphic below $2^{2046}$. That's more than ample for many applications, so the limit $\ell$ is typically unstated.
The question asks an equivalent using ElGamal encryption on a standard Elliptic Curve group such as X25519 or P-256, with the stated goals:

reduce the ciphertext size
"improve the encryption operation", which I take as making at least encryption faster.

Both are possible, but as far as I know that comes with a serious limitation: the cost of decryption¹ grows about as $\Theta(\sqrt a)$ where $a$ is the plaintext. That's thus not even a cipher by the modern definition of that, which would require cost polynomial in $\log a$. However the question is "only encrypting small integers (32bit)", thus that might be tolerable.
Using the notation in the definition of P-256 aka secp256r1 in SEC2, that variant of ElGamal encryption goes:

The curve has a generator $G$ forming an Elliptic Curve group of prime order $n$ with $\log_2(n)\approx256$
A point on the curve other than the neutral can be defined by it's $x$ coordinate in $[0,p)$ and the parity of it's $y$ coordinate, and fits 257 bits or 33 bytes.
The private key is a random secret integer $d$ drawn about uniformly randomly in $[1,n)$
The public key is the point $Q$ of the curve computed as $Q\gets d\,G$. Recall that this scalar multiplication on the Elliptic Curve gives the same $Q$ as would computing $\underbrace{G+G+\ldots+G}_{d\text{ terms}}$, but can be performed with $\approx512$ point additions in the Elliptic Curve group (refer to SEC1).
Encryption of integer $a\in [0,n)$ goes:

Draw a random secret integer $k$ about uniformly randomly in $[1,n)$
Compute $R\gets k\,G$ and $S\gets a\,G\,+\,k\,Q$.
Output ciphertext $(R,S)$ (it's like 66 bytes).

Decryption of ciphertext $(R,S)$ goes

Check that $R$ and $S$ are on the curve
Compute $A\gets (n-d)R\,+\,S$
Find integer $a\in [0,n)$ with $a\,G=A$.

It's easy to verify that

decryption (if we can manage it's last step) recovers the plaintext $a$;
if $a_i$ has enciphered to $(R_i,S_i)$, and $n>\sum a_i$, then $(\sum R_i,\sum S_i)$ [where the summations are point additions in the Elliptic Curve group] deciphers to $\sum a_i$ [where the summation is ordinary addition]: our modified ElGamal encryption is homomorphic below $n$.

I think security is somewhat reducible to some well-studied problem (is it DDH?).
The catch is: we don't know how to perform the last decryption step for cost¹ less than $\Theta(\sqrt a)$. For plaintext $a$ limited to 32-bit, Baby-Step/Giant-Step is probably the method of choice: it's simple; has predictable runtime; is straightforward to implement in pure Python on a standard PC if we brush aside resistance to side-channel attacks.
The whole endeavor is a useful exercise, and can be done from scratch in like a day for one with a good understanding of Elliptic Curve Cryptography, programming, and some exposition to Python. About half the work is implementation of the code doing point addition and multiplication, which exists in many open-source projects²
Difficulty grows sharply if we want a secure implementation, or acceptable speed for much larger $a$. For the later, we'd want Pollard's Rho with distinguished points, which can be efficiently distributed and requires little memory; see Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

¹ This is the cost for a single decryption, including precomputations. These precomputations can be performed before the ciphertext is available, and amortized across multiple decryptions, see poncho's comment.
² For NIST's P-256, P-384, P-521 curves, pycryptodome's EccPoint looks like it can be used without re-engineering the interface. This is not a recommendation: I've not used or reviewed that code. And from the perspective of learning crypto (rather than the joys and pitfalls of code reuse), it's better to implement that too.


Why is the re-encryption algorithm in Universal Re-encryption for Mixnets more complicated than apparently necessary? This is the paper.

On page 6, the paper describes a variant of El Gamal and a way of re-encrypting ciphertexts.

I thought an easier way to do encryption is to output $(m(g^x)^y,g^y)$, and universal re-encryption can be done by $(m(g^x)^y(g^x)^z,g^yg^z)$ for randomly chosen $z$. Instead the paper used a ciphertext with four components. Why?

Does it have something to do with CCA security?

Actually no, it is not related to CCA security.

The re-encryptor mix server needs all of the four components for performing a correct re-encryption since it does not know the public key of the receiver $g^x$. Mix server only knows $\alpha_0, \beta_0, \alpha_1, \beta_1$ and two re-encryption factors it generates $k''_0, k''_1$

The encrypted message mix server receives:

$$[(my^{k_0}, g^{k_0}); (y^{k_1}, g^{k_1} )] = [(\alpha_0, \beta_0); (\alpha_1, \beta_1)]$$

The re-encrypted message it sends:

$$[(my^{k'_0}, g^{k'_0}); (y^{k'_1}, g^{k'_1} )]= [(\alpha_0\alpha_1^{k''_0}, \beta_0\beta_1^{k''_0}); (\alpha_1^{k''_1}, \beta_1^{k''_1})]$$

The scheme is designed in a way that not only it does not require the public key, the ciphertexts and the re-encryption procedure do not yield any information about the public key. As a result, it could be used in applications that require "receiver-anonymity" in situations that we have multiple receivers.

Page 2 of the paper:

  The novelty in our proposal is that re-encryption neither requires
  nor yields knowledge of the public key under which a ciphertext was computed.


Cryptography and patents First of all, I've seen a question marked as off topic because OP doesn't cover any issue related to cryptographic work, but the legal aspects, but I'm unsure where to attend to ask the following questions.

I've never thought I was going to ask such a question, since I always thought that cryptography should be an open field, because the majority of information I know is on the public domain. But advices received from partners and relatives encouraged me to experiment with the idea. I know that some schemes were patented in their beginning: DH, RSA, DES, NTRU, some schemes on ECC.

Imagine that I own various schemes that are based on existing ideas, but the construction of these schemes are different from the original description, resulting in a different scheme that is believed to have better security or it is more efficient (optimized). I haven't studied any subject related to patents since I started my career so I'm not very familiarized with the scenarios that can arise:

Can you patent a cryptographic scheme and publish a paper opening your method entirely, which is descriptive enough, so its security can be analyzed by the cryptographic community? Could I provide an implementation of the scheme?

Can you patent a cryptographic scheme based on an scheme/idea that was previously patented but lacks of patent nowadays, considering that this scheme is a modification of the original one?

I just don't want to hit a barrier considering this option. I'd like everyone to read and study the presented schemes, so I can still contribute onward with the community I've always thought that patenting make your idea less interesting or restrictive because you can't disclose any technical secret related to it, but maybe I'm wrong because I'm lacking of information. Thanks in advance.

But advices received from partners and relatives encouraged me to experiment with the idea. I know that some schemes were patented in their beginning: DH, RSA, DES, NTRU, some schemes on ECC.

Note that there is considerable reluctance in significant parts of the community to use any algorithm with any intellectual property claims.  If you patent your algorithm, that pretty much guarantees that no one will use it, unless (or even if) it has very significant advantages over unburdened algorithms. For example, (EC)DSA has extra operations in it to avoid a (now expired) patent. DSA itself was introduced partly due to concerns over patents on RSA. OCB is virtually unused largely because of patents which led to the adoption of the slower CCM. Patents delayed the adoption of elliptic-curve cryptography.

However, to address your questions (and while I am not a lawyer, I do have some familiarity with how patent law works):

  Can you patent a cryptographic scheme and publish a paper opening your method entirely, which is descriptive enough, so its security can be analyzed by the cryptographic community? Could I provide an implementation of the scheme?

Absolutely; a patent (or a pending patent) does not rely on the secrecy of the invention (unlike, say, a trade secret); in fact, the entire point of the patent process is to give you an incentive to publish your invention (by giving you a monopoly on it for a limited period of time).  On the other hand, you have to do things in the correct order.  In the US, you have a year after publishing your invention to file for a patent; in Europe (and, AFAIK, the rest of the world), you don't have any grace period - once you've published, you can't file for a patent.

  Can you patent a cryptographic scheme based on an scheme/idea that was previously patented but lacks of patent nowadays, considering that this scheme is a modification of the original one?

You can, if the modification doesn't itself have prior art, and is sufficiently nonobvious to one "skilled in the art" (and, yes, that is a rather nebulous criteria).

  I've always thought that patenting make your idea less interesting or restrictive because you can't disclose any technical secret related to it, but maybe I'm wrong because I'm lacking of information.

No, after you file for your patent, you can disclose any details you want.  What makes your idea less interesting to other people is that they're concerned about the legal ramifications of using your idea (and you possibly taking them to court for patent infringement).  Now, if you release your patent for general use, that's no longer an issue for them; however it begs the question "why did you file for a patent in the first place?"


Would it be safe to store GCM nonce in the encrypted output? I'm looking to use AES-256 GCM to encrypt and authenticate a file containing sensitive information. I am a bit loss on where to store the nonce that is required for GCM.

Would it be adequate/safe to store the nonce unencrypted at the beginning the the encrypted file?

Yes, and it is quite common to do this. As long as the nonce is unique for the given key you should be all right. Note that it is best to keep the nonce at 12 bytes (the default). No need to store the size.

Note that there is no need to put the nonce in the Additional Authenticated Data (AAD or AD) as it is already included in the calculation of the authentication tag.

Note as well that GCM does have some limitations to the number of bytes that can be encrypted ($2^{32}$ blocks of 16 bytes).

You could store a magic string and version info before encrypting so you can switch to another scheme later on.


If I don't use XOR in Davies–Meyer, does it remain collision resistant? If I don't use XOR in Davies–Meyer construction like in picture 2, does the function remain collision resistant?

Let $h=E_{x_i}(z_{i-1})$ in your suggestion. Let $z'=E^{-1}_{x'}(h)$. This gives a collision between between $(x_i,z_{i-1})$ and $(x',z').$

The XOR makes this attack difficult.


Cryptographically linkable random tokens Are there any algorithms/protocols that let you produce a specific length of random tokens/bits in such a way that you can cryptographically determine which 2 or more tokens/bitstrings where produced using the same seed/key. Is it possible at all?

For example, if I produce these random bits: 12432, 15693, with key A and 57322, 57483 with key B. I want a third party who gets 12432 and 15693 to be able to determine they were both produced under the same key.

I thought of digital signatures as the obvious solution. However digital signatures will be to long for my requirement. I would like the token to be between 10-20 bits long, any pointers will be greatly appreciated.

Requirements:

The third party should be able to verify the tokens are valid.
Ideally, the third party should be unable to forge tokens.
Tokens must be unique to a single key.

I see 2 options that fit the requirement (small, verifiable within some limit).

Because the sizes are small, the probability of the collision of a random value showing linked is high, larger values will obviously help.

Option 1 is to have a random value, and encrypt or hash it, then truncate the result and concatenate to the original value. The size of the value limits the pool of available tokens, and the size of the truncated output limits the probability of a collision. For example:

$A$ is a random or sequential 14-bit value, $B = HMAC_k(A)$ truncated to 16-bits.
$A || B$ is a 30-bit (5 character base64 encoded) token that can be easily verified as being linked to $k$, with a pool of 16384 maximum tokens linkable to $k$

Option 2 is to encrypt the entire value using a block cipher, and limit the inputs to a small subset of the available plaintext space. Upon decryption, only values that fall into that space will be considered valid. The cipher must have a small enough block size for your application, which limits available choices to those designed for low resource systems, like SPECK with a 32-bit block size.


Can authenticated encryption reduce bandwidth overhead of per-packet encryption? I know that authenticated encryption modes of operation like GCM offer certain security advantages, as well as increased performance. (On my laptop with AES-NI, the benchmark performance of AES-128-GCM is about 3.7× faster than AES-128-CBC-SHA1.)

What I'm less certain about is whether authenticated encryption modes offer any advantages in terms of bandwidth overhead, in particular for datagram/UDP-based VPNs.

I've been working recently on supporting a commercial ESP-based VPN in an open-source VPN client, and have been struck by the substantial overhead of wrapping IP packets in ESP:

20 bytes for SHA1 MAC
16 bytes for an AES-128 IV

Including ~17 bytes for padding and a 4-byte SPI), the ESP overhead can be around 5% of the size of an IPv4 packet on a network with a typical MTU around 1500 bytes.

Do authenticated encryption modes offer any possibility to trim the per-packet bandwidth overhead of encryption and authentication, while retaining similar security levels?

My understanding of GCM is that it still uses authentication tags and IVs of similar length to ciphersuites like AES-128-CBC-SHA1, but perhaps there are possibilities that I'm looking here.

GCM supports multiple authentication tag sizes.  To the extent that overhead outweighs security in your application, you perhaps could use GCM with reduced tag size.  You'd be settling for a lower security level, so that needs to be thought through very carefully.

The common requirements on the use of IVs are the following:

The sender and recipient must agree on what the IV is for each encryption/decryption pair.  Even better, they should authenticate the IV.
Other additional requirements that the cipher imposes on IVs.  The two typical ones:

Some ciphers require the IVs to be a nonce—that two encryptions with the same key never reuse the same IV, or otherwise the cipher may fail catastrophically.  CTR and GCM are like this.
Other ciphers require the IVs to be random.  CBC is like this.

Requirement #1 is often achieved by sending the IV along with the ciphertext, but this is just one way of achieving the goal.  The alternative would be to have some protocol where the parties can locally generate the correct IV for each encryption/decryption pair without having to individually transmit them. Many solutions are possible here.  One very simple scheme, suitable for nonce-based ciphers, is to treat the IV as a counter.  The documentation for the NaCl library has an example trick worth quoting:

  Distinct messages between the same {sender, receiver} set are required to have distinct nonces. For example, the lexicographically smaller public key can use nonce 1 for its first message to the other key, nonce 3 for its second message, nonce 5 for its third message, etc., while the lexicographically larger public key uses nonce 2 for its first message to the other key, nonce 4 for its second message, nonce 6 for its third message, etc.

This does require that recipient be able reconstruct the order in which the sender used encrypted the messages.  But there are other ideas that can help if that's a problem:

If your messages carry some plaintext metadata that contains values that offer some uniqueness guarantee, you might be able to use that metadata as an input to compute a unique or pseudorandom nonce.
You could put a variable-length encoding of the counter into the datagrams along with the ciphertexts, and have the recipient expand the counter values to the full IV size for decryption.

Note that these implicit IV techniques stress the importance of authenticating the IV as well as the ciphertext, otherwise active attackers may be able to fool you by reordering, deleting or adulterating packets. (Authenticated encryption modes like GCM implicitly authenticate the IV already, however.)


Why is CBC-MAC with length appended not secure? I've just read about CBC-MAC for the authentication of arbitrary length messages. In particular I cannot figure out why appending the message length before computing the MAC yields a non-secure MAC. I've already read other topics on crypto about this problem, but i did not find a rigorous proof.

I'll give you a hint, and you can work out the details yourself.

Take any $m_1,m_2,m_3$ of length $n$ (where $n$ is the block length), with $m_1\neq m_2$. Query the oracle with $m_1$, then query the oracle with $m_2$, and finally query the oracle with $m_1\|n\|m_3$.

Work through this, and you can find a message and its forgery.


How to turn adversary against encryption of zeroes into adversary against random bits? I recently read the article Nonce-Based Symmetric Encryption by Rogaway, where he presents two different notions of indistinguishability, which he calls ind$ and ind, respectively. Here's the definitions of these to notions:

First, let $A^g$ be an algorithm with access to an oracle $g$, and let $\Pi = (\mathcal{E},\mathcal{D})$ be an encryption scheme with key space $\mathrm{Key}$.

Ind\$ is then defined as follows:
$$ \mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{$}(\cdot)} \Rightarrow 1],$$

where $ \$(\cdot)$ is a random oracle, returning random bits equal to the block size of $\mathcal{E}$. In other words: ind$ asks an adversary to distinguish between messages encrypted by the real encryption scheme and random bits.

Ind is defined as:
$$ \mathbf{Adv}_{\Pi}^{\mathrm{ind}} = \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1].$$

That is, ind asks an adversary, when quarrying the input message $M$ to the oracles, to distinguish between the real encryption of $M$, and the encryption of $0^{|M|}$.

He then claims that

  "It is easy to verify that the ind$-notion of security implies the ind-notion, and by a tight reduction".

My question:

Intuitively, the implication seems easy enough:
If $\Pi$ is ind\$-secure, then encryption of $0^{|M|}$ will be indistinguishable from random, so we just get the "ind\$-game". However, how would you go about showing the tightness of the reduction? Usually I'm used to doing this by a reduction like so: assume you have an ind-adversary that breaks the ind-security, how can you turn this into an (effective) adversary against the ind\$-security of $\Pi$? But I don't really see how an adversary against ind can be turned into an (effective) adversary against ind\$.

It's actually quite simple.
Given your adversary $A$ against ind you construct an adversary $A'$ against ind$ by simply forwarding the queries and answers. (This may seem stupid but please bear with me.)

Consider now, the difference between the advantage of $A$ and $A'$:
$$\mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{$}(\cdot)} \Rightarrow 1]-(\mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(\cdot)} \Rightarrow 1] - \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1])$$
$$= \mathrm{Pr}[K \xleftarrow{$} \mathrm{Key} : A ^{\mathcal{E}_K(0^{|\cdot|})} \Rightarrow 1] - \mathrm{Pr}[A ^{\mathcal{$}(\cdot)} \Rightarrow 1]$$

If this distance were non-negligible, we could build a successful adversary $A''$ against ind$\mathrm{$}$ as follows: Whenever $A$ queries a message, $A''$ queries $0^{|\cdot|}$ instead and returns the answer to $A$.

It's easy to see that the advantage of $A''$ is excactly the difference from above. Therefore you get $$\mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \mathbf{Adv}_{\Pi}^{\mathrm{ind}}  - \mathbf{Adv}_{\Pi}^{\mathrm{ind$}}$$
$$\Rightarrow 2\cdot\mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$
$$\Rightarrow\mathbf{Adv}_{\Pi}^{\mathrm{ind$}} = \frac{1}{2}\cdot\mathbf{Adv}_{\Pi}^{\mathrm{ind}}$$


Multiple levels of encryption Is it feasible to have data encrypted at different levels of hierarchy

I'd like to encrypt an xml database (such as used in www.keepass.info) whereby two or more keys can exist. For example:

Key #1 decrypts the entire database file
Key #2 decrypts a subset of the database file

Is this technically possible/recommended? The reason I'm looking is that I currently use keepass for myself and I repeatedly get family members saying that they've forgotten their password and do I know what it is...so I would like them all stored in a master database file that we can keep on our home network storage

Yes, this is possible. You can create a symmetric key per entry. You can then wrap that key with any key (of any person) you want and store the wrapped keys with each entry.

I strongly suspect that doing so within keypass is not possible.


Secret key and Decryption oracle in the revised Fujisaki-Okamoto transformation Recently, Fujisaki and Okamoto provided a revised version of the Fujisaki-Okamoto transformation [1], a generic transformation for achieving IND-CCA2 security in the Random Oracle model. This new version is slightly different than the original [2] and the security proof does not define a knowledge extractor (the original version actually proved that the transformation satisfies the Plaintext Awareness (PA) notion and used the fact that PA $\Rightarrow$ IND-CCA2 in the random oracle model). Instead, they directly provide an algorithm for the decryption oracle. When describing the decryption oracle construction, they stress that it does not require the secret key (in a similar way than the original version), and it only uses the information from previous random oracle queries.

Is this characteristic (i.e., not using the secret key) relevant in general for proofs for the IND-CCA2 notion, or is it simply something inherited in this particular case from the original transformation, aimed at the Plaintext Awareness notion? In other words, is there any inherent drawback in using the secret key in the decryption oracle when facing a security proof for IND-CCA2? I know that, usually, proofs are constructed as reductions to hard problems, which may force to define the decryption oracle without knowledge of the secret key. However, this does not seem to be the case.

I think I may be overthinking the problem, and that the answer may be a simple "No".

Update: I added some possible explanations in the comments. I'm starting to lean towards the answer "It is important in this particular proof, but not in general".

References:

[1] Fujisaki, E., & Okamoto, T. (2013). Secure integration of asymmetric and symmetric encryption schemes. Journal of Cryptology, 26(1), 80-101.

[2] Fujisaki, E., & Okamoto, T. (1999). Secure integration of asymmetric and symmetric encryption schemes. In Crypto (Vol. 99, No. 32, pp. 537-554). [link]

As you say, CCA proofs are actually reductions to underlying problems. In all CCA proofs that I can think of at the moment, the underlying problem is a weaker security notion for an "embedded" encryption scheme - e.g. Cramer-Shoup and friends use IND-CPA of ElGamal and Fujisaki-Okamoto uses OWE of the contained scheme.

The general proof strategy is to take a public key from your challenger and pass this to the adversary. This lets you use the challenger to process the two challenge messages to get the challenge ciphertext - since the only bit of information that your adversary gives you is which of the two challenge messages he thinks was encrypted, I'd guess that all CCA proofs will somehow have to "embed" the hard problem they're reducing to in the challenge ciphertext. After all, the reduction could compute everything else by itself.

This strategy of getting the public key from the challenger means you don't know the matching secret key, so the interesting bit of the proof is then how you handle decryption queries without it. This is certainly general to all CCA proofs that I can think of at the moment.


Obtaining Diffie-Hellman generator In the Wikipedia article on Diffie-Hellman, the algorithm calls for a large prime modulus, $p$, and a generator, $g$, which is a primitive root of $p$.

As far as my knowledge of number theory goes, to find a primitive root of a prime number, you first need to determine the prime factors of $\phi(p)$, or $p-1$.

Obviously, 2 divides $\phi(p)$, but after that you are left with the problem of factoring a number that is the same bit size as the original $p$.

I was under the impression that the security of the system was dependent upon the difficulty of finding the prime factors of a big number in the first place.

What am I missing?

Diffie Hellman is not dependent on the difficulty of factorisation of large numbers (sort of*).

It relies on the fact that there is no efficient algorithm know to the human race as of today that can efficiently deduce the discrete logarithm of a number. That is given an element $y \in G$ where G is a cyclic group of prime order $q$ , it is not computationally feasible to find a number $x \in Z^*_q$ such that $y = g^x$.

They key point here is that the order of the group needs to be a prime number. This means that the group $Z^*_p$ is not secure for any prime $p$since its order is obviously not prime.

To deal with this trouble one can choose a prime $p$ such that $p= kq + 1$. This means that there exists a unique subgroup (called schnorr group) of $Z^*_p$ of order $q$ since there exists exactly one subgroup for each divisor of $φ(p) = p-1$.

To find a generator for that group is trivial. Choose a random value $1 <h < p$ such that $h^r \mod{p} \neq 1$. If you find such a number then this inequality means that the order of $h$ is greater than $r$. However the only possible order greater than $r$ is $q$. As a result $h$ has order $q$ and can generate a secure subgroup of $Z^*_p$. If $h^r \mod{p} = 1$ then simply generate another random $h$ and try again until you find a generator.

*One can show that if the order of the group has only small prime divisors then the discrete logarithm problem is much easier to solve than other groups. However by selecting a subgroup of a large prime order as we did above by selecting $p= kq + 1$ means that the subgroup we are generating only has one large factor (itself), which in turn means that you need not worry of these factorisation attacks.


Securely computing functions over source code I have been studying multi-party computation and want to start implementing it. I think it would be interesting to do this where one of the inputs (say party 1) is some source code, say a .py file.

If for example I wanted to securely compute the number of lines of code this file had, how would I go about it? The functionality would look something like $$f(code.py, \_) = (\_, \text{number of lines in code.py})$$ where $\_$ represents the empty string.

I think MPC is up to this task but are there any better ways this functionality could be realised?

Also, any pointers to packages that would be good to implement this in would be nice also.

I'd like to divide the problem into semi-honest and malicious adversaries with corrupt the party inputting the source code.

In the semi-honest setting, you assume an adversary which follows the protocol correctly, but tries to learn information from the messages the party corrupted by the adversary. As a result, if you assume the adversary is semi-honest, the problem will be trivial to compute since that party can simply compute the lines of code himself and send the other party the result.

It will be very hard to securely construct a secure multiparty computation protocol in the malicious setting where an adversary may also vary the protocol specification, if there are not additional properties about the code known to both parties, like the length of the code. That is for two reasons:

Some data like the length of the code has to get leaked. As to my knowledge, there is no MPC protocol known which permits inputs of variable length.
Adversaries in the malicious setting may input another input like anothercode.py. You can assume that the input is not changed by the adversary, but then you can just use the semi-honest setting.

My best idea of designing the MPC procotol you desire would be to define and reveal properties about the code and then prove them using zero knowledge protocols such that these properties are fulfilled. The best candidates which come to my mind are Zero-Knowledge Using Garbled Circuits or ZKBoo: Faster Zero-Knowledge for Boolean Circuits (the authors even provided an impmenentation of ZKBoo on Github). These protocols are zero-knowledge protocols which prove generic statements (generic as described using AND/XOR gates) using MPC techniques.


Hash of a ciphertext Would hashing a ciphertext (so $H(Enc(pk,m))$) compromise it in any way if both schemes are secure by themselves? This doesn't seem to be the case but I couldn't find a definitive answer.

No.
Any adversary could simply perform the hash themselves and so you are providing them with no additional resources.


How useful is NIST's Randomness Beacon for cryptographic use? NIST have just launched a new service called the NSANIST Randomness Beacon. It has been met with some initial skepticism. Perhaps the cryptography community would have used it before June 2013 when NIST had a trusted reputation. At first I thought it was a mistimed April Fool's joke, however it actually appears to be an ongoing serious project.

I am intrigued as to the potential uses of this randomness beacon and serious cryptographic applications that this service could legitimately provide, given that this service is potentially hostile and probably under adversarial control. I am assuming that using it for private cryptographic keys is out of the question.

I'll quote a few things from the specification in the Uses section that raised an eyebrow for me:

  First, the Beacon-generated numbers cannot be predicted before they are published. Second, the public, time-bound, and authenticated nature of the Beacon allows a user application to prove to anybody that it used truly random numbers not known before a certain point in time.

However this feature can not be true because:

  The Beacon will broadcast full-entropy bit-strings in blocks of 512 bits every 60 seconds.

So while normal users won't be able to predict the random numbers, in that 60 second window someone with a privileged access inside the NIST (or NSA) could easily have access to the next random bit-string a full 60 seconds before it has been "published". If this adversary with insider access were to become one of the regular users of an application using this beacon they would have knowledge of random numbers before other users providing a significant advantage depending on the type of application.

Given this information, what actual safe, fair and useful cryptographic uses could this potentially compromised beacon provide?

I would characterize the service as similar to a trusted time-stamping service. Except they do not do the time-stamping, but just provide the "key". This allows a user to decide what do to with it, such as using it as a private key to sign something, or an HMAC key, proving the signature is "not older" than the timestamp. If the signature is published to a verifiable record, it can then be proven to be "not newer" than the date of the record. If the gap is short enough, the applications for a signature or hash with a provable time period of creation are numerous. It can also be used an an additional input to a two factor authentication system (I think this is the most useful).

Other sources of true randomness are available, but having one for free is better if you do not need to use it for a cryptographic purpose. Having a way to prove or audit your random source is beneficial from a business or political perspective, as in the examples for the Unpredictable Sampling application link.

Other non cryptographic uses of random values could be used to prevent bias for things like "random screenings" of airline passengers, jury selection, and collection of census data. I doubt this will be implemented, but one can hope.

Service Security

We can make three types of assumptions from a subterfuge perspective.

The numbers are truly random, but are provided to the NSA in
advance (or are simply delayed for public view).
The historical record can be modified by the NSA or NIST, since
they have access to the private key.
The numbers are not truly random.

Not being random is something that would need an audit or some kind of analysis to prove. I doubt they are not random, but that does not mean that a non random value could be used for say, a single output.

The 2nd is unlikely to occur, since acceptance of the service would only be likely if you could verify the record from other parties, which one does trust to have been unmodified. Also since the output is based on the prior outputs, the entire chain would need to be tampered with.

The 1st is much more likely, the outputs could be delayed for a substantial amount of time, even days, and you would not know unless the entropy source can be audited by a trusted party. Since the signature is generated using a known future time code plus the current and prior values, it is trivial do to this without detection. Seeds could potentially be chosen at random and tested to give an output with a specific bias, but a massive amount would probably need to be tested to give appropriate output, at significant cost to the attacker (each requires an RSA sign and a hash, and the guarantee that the one specific value will be used by the target).

Given this, one would probably use these numbers only for uses where that would be highly unlikely to occur. Most applications would fall into that category. Anyone who needs these type of numbers for a use that is likely to be manipulated by an intelligence agency would just build their own entropy generator, which is not too difficult. If nobody is using the service for something the NSA would want to tamper with, the NSA wont tamper with it, it is simply too expensive and there would be no gain.

The only concerns I have from a cryptographic perspective are how the numbers are actually generated. The page does say that the output is full entropy and the output is 512-bits. It may be safe to assume that the "Seed Value" is actually the hashed output of the entropy source/DRBG, as the XML schema file says the "Output Value" is the SHA-512 hash of the signature, which I have verified to be the case. This means the output value is computationally infeasible to predict without all the input values AND the private key.

The specifics of the seed number are not listed, one can only assume that the samples are passed through SHA-512 to give this, but the size of the sample is not listed. Since the Beacon page specifically lists compliance with SP800-90, the entropy sample should be at least 888 bits, but there is nothing to confirm that, and no detail on the actual method of output generation, such as the DRBG used (very very important), and the reseeding interval.

Other Security Concerns

At this point I will assume the service is still in beta prototype, as their XML schema file references values that are not given, such as randomValue and previousHashValue, which are most likely supposed to be the seed value and previous output.

The other unknown is how the signature is generated, since there must be someway to verify it, but no public key or any detail at all regarding the type of signature is listed. It is a 2048 bit value, so RSA is quite likely, possibly even generated by the same private key for their SSL traffic. I would hope that is not the case, when the key expires later this year, it may be difficult to verify previous outputs, as the old public key would need to be found.

Also, the page is encrypted using CBC mode using TLS 1.0, which means the connection is potentially vulnerable to tampering by a 3rd party while in transit. This type of service should be as invulnerable to tampering as possible with current technology and standards, and is not. This is not a problem with the service itself, just in how the service is accessed. The page accesses an XML formatted entry using AJAX on the same server, secured with the same protocol and key.

Acceptance is also dependent on public trust in the security of SHA-512, the methods used to measure the unpredictability of quantum behavior, and the methods described in SP800-90A for turning those measurements into random bits. SP800-90A is the publication that describes Dual EC DRBG....

Updates to the service as of March 2018

As mentioned above, the private key for their SSL traffic expired in 2014, at that point they got a new cert, and have since posted the specific certificate used to sign beacon data. That cert (2048-bit RSA, SHA256 hash) was valid for 3 years, and expired May 7th 2017. It is downloadable for verification of prior data, and they list the new public key used to sign current beacon data, but it is not a certificate and thus not signed with a root cert.

The new public key is 2048-bit RSA with 65537 as the exponent, same as in the previous certificate.

Their SSL traffic is now secured with TLS 1.2, the specific ciphersuite used is TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA. That cert has a 1 year validity, and is also 2048-bit RSA.

Their schema has been updated, and no longer references randomValue or previousHashValue. The XML records from the beacon match the schema correctly.

The service is still listed as a prototype, and they note that a new version of the beacon is in development, however there have been no updates since the last page edit on May 13th 2014.

Updates to the service as of October 2019

In June 2018, the service officially left prototype status and entered beta, using the "new version" I referenced earlier, which is now referred to as version 2.0. The new XML Schema file is fairly well documented. It appears the new beacon went online July 23rd 2018.

I was able to determine that the certificate used to sign the beacon output changed on pulse 502025, which occurred on August 16th 2019. The status of the pulse correctly specify a gap in the beacon output occurred (it was 3 minutes), with a code of 6 for certificate change, although this code is not listed in the XML Schema file. The prior certificate actually expired on January 11th 2019 and was used for an additional 7 months 5 days.

The current and prior certificates are easily obtainable from the service interface. Both were issued by DigiCert Global CA G2. The new public key is 4096-bit RSA with 65537 as the exponent.

Their SSL traffic is still secured with TLS 1.2 on my system, the specific ciphersuite used is now TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384. That cert has a 1 year validity (expiring November), and is still 2048-bit RSA. It is also issued by DigiCert, but is a common web server certificate for 14 separate NIST subdomains, including NVD and CSRC.

In May of 2019, they published a draft reference for randomness beacons, of which the version 2.0 service is an implementation of, as Internal Report 8213. This is an extremely detailed report of the design and implementation of the beacon system, and includes a security analysis with multiple threat assessments.

There are a few important changes with version 2.0 that are worth mentioning, the first is that they now have published block diagrams of how the system works, make note that although RNG3 is listed as quantum, the beacon project website specifies "We may soon integrate in the NIST Beacon a PML-developed quantum RNG (identified in the figure as #3) based on photon detection", implying that RNG3 is not currently active:

The next important change is how the hash chains are built, and the addition of the skip list. I have not verified the complete operation of the skip list, but it would appear to use the 1st hour/day/month/year as the anchor point for a hash chain, so it is much faster to audit the current beacon to the start of the chain, which could be years long.

Now instead of going back half a million hashes to go back a year, you simply go back to the start of the hour, then back by hours to the start of the day, and so on until the chain is verified back to the first minute of the first hour of the first day of the year, with a maximum of 124 verifications to go back to the beginning of the current year.

So to verify pulse 502025 (Aug 16th 2019, 14:14 Z) against the start of the month pulse of 479573, you skip back 15 minutes to 502013, then in 14 skips of an hour (60 pulses) back to 501173, then in 15 skips of a day (1440 pulses) to 479573, for a total of 44 verifications, compared to 22453 without the skip list feature.

The final point of note is that this is not the only implementation of the version 2.0 beacon technology, there are services run by the University of Chile and government of Brazil. In addition to a hardware RNG, the Chilean beacon uses entropy sources gathered from seismic measurements in Chile, a stream from a local radio station, a selection of Twitter posts, and data from the Ethereum blockchain. Brazil actually runs multiple beacons, including their primary which uses a photonic quantum TRNG, as well as a combination beacon which also includes the outputs of the Chilean and NIST beacons as sources of entropy. The output of the Chilean beacon is also one of several inputs to Cloudflare's own beacon, which is not based on the NIST design or API.

At this point, the design seems sound, and if they fix the cert issues and get RNG3 active (maybe it already is), this and others like it do appear to have many uses, although cryptographic use may not be one of them, except as an additional source of entropy and not as a primary source.


128 bit hash with least chance of collision? I'm building a storage system for JSON documents where they are looked up on a 128 bit key. These JSON documents have a timestamp within them, but apart from that are user-entered data. These JSON documents can have within them private information, so I want to avoid any issues where two documents have the same hash and the wrong one is served.

Should I use MD5, which I know is vulnerable to collision attacks, or go for one of the SHA functions and use the first 128 bits?

The two proposals in the question have their advantages and disadvantages.

Using MD5
There are three major types of attacks to worry about.

Preimage attacks: given $h$ find $m$ such that $H(m)=h$
Second preimage attacks: given $m$ find $m'\neq m$ such that $H(m)=H(m')$
Collision resistance: find any $m$ and $m'$ such that $H(m)=H(m')$

MD5 is broken with respect to collision resistance. So, what could an attacker do if you use MD5. They could submit two documents that they created which has the same hash value. Since the attacker would have to create both documents, no private information will be leaked. To learn private information, they'd have to break #1.

MD5's preimage resistance is academically broken. It has not been broken, however, in a practical sense.

Truncated SHA
Since NIST has a truncated mode for SHA-512/256 and SHA-512/224. This should give some credibility to the idea. The link talks about some potential attacks, but all are purely academic at this point.

Now, they do suggest using a unique IV for each truncated length. This is to fix "Issue #1" on slide 7. This issue is very specialized and will not matter for your application as you will always be using the same size output. That said, if you have the ability to modify the IV, I would do it. Modifying the IV could cause problems with interoperability and might break things any time you update software, so you'll have to weigh the options.

The near-collisions is also purely academic as we cannot efficiently find near collisions for say SHA-256 (or 512). This is pointed out on slide 15.

The main disadvantage of truncated SHA is that there are no reduction proofs to the original hash function. Basically this means that the truncated version could be less resistant to preimage attacks, but no known preimage attacks exist on truncated versions.

Xor SHA512 (from comments)
This method seems better than using MD5, but worse than using truncated SHA. Let's look at an example (for this I'm going to split the digest at the byte level to keep it simple and use a short output).

Say I'm looking for a preimage attack and am given a digest of 01001010 00100111. The XOR would be 01101101. If I can find a near collision that looks like 00101010 01000111, the XOR is the same. Thus, this construction is also vulnerable to near-collisions, granted this is more of an academic attack.

Since this is also vulnerabile to near-collisions, and since NIST uses Truncated SHA, I'd go with that instead.


initial value for RSA and SHA-256 signature encoding As described in RFC 8017, RSASSA-PKCS1-V1_5 uses the following bytes during the encoding process :
0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60,  0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20
Does anybody know how to compute these values?

Digging the RFC 8017

9.2.  EMSA-PKCS1-v1_5
For the nine hash functions mentioned in Appendix B.1, the DER encoding T of the DigestInfo value is equal to the following:

and

A.2.4.  RSASSA-PKCS-v1_5
The object identifier for RSASSA-PKCS1-v1_5 SHALL be one of the
following.

Both combined below;
Hash algorithm   OID                           the DER encoding T of the DigestInfo
------------------------------------------------------------------------------------------
MD2              md2WithRSAEncryption          (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 02 05 00 04 10 || H.
MD5              md5WithRSAEncryption          (0x)30 20 30 0c 06 08 2a 86 48 86 f7 0d 02 05 05 00 04 10 || H.
SHA-1            sha1WithRSAEncryption         (0x)30 21 30 09 06 05 2b 0e 03 02 1a 05 00 04 14 || H.
SHA-224          sha224WithRSAEncryption       (0x)30 2d 30 0d 06 09 60 86 48 01 65 03 04 02 04 05 00 04 1c || H.
SHA-256          sha256WithRSAEncryption       (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 01 05 00 04 20 || H.
SHA-384          sha384WithRSAEncryption       (0x)30 41 30 0d 06 09 60 86 48 01 65 03 04 02 02 05 00 04 30 || H.
SHA-512          sha512WithRSAEncryption       (0x)30 51 30 0d 06 09 60 86 48 01 65 03 04 02 03 05 00 04 40 || H.
SHA-512/224      sha512-224WithRSAEncryption   (0x)30 2d 30 0d 06 09 60 86 48 01 65 03 04 02 05 05 00 04 1c || H.
SHA-512/256      sha512-256WithRSAEncryption   (0x)30 31 30 0d 06 09 60 86 48 01 65 03 04 02 06 05 00 04 20 || H.

and in

B.1.  Hash Functions
The object identifiers id-md2, id-md5, id-sha1, id-sha224, id-sha256,
id-sha384, id-sha512, id-sha512/224, and id-sha512/256 identify the
respective hash functions:
   id-md2      OBJECT IDENTIFIER ::= {
       iso (1) member-body (2) us (840) rsadsi (113549)
       digestAlgorithm (2) 2
   }

   id-md5      OBJECT IDENTIFIER ::= {
       iso (1) member-body (2) us (840) rsadsi (113549)
       digestAlgorithm (2) 5
   }
   ...

Therefore it is the DER encoding of the above object identifiers. See example on A Layman's Guide to a Subset of ASN.1, BER, and DER (5.9)


Fully homomorphic encryption with polynomials I have read some texts concerning fully homomorphic encryption but didn't find the following simple idea.

Let $p$ be a prime. We choose secret key $x_0$ in the interval $1\le x_0<p$. Let $\mathrm{Enc}(m)$ be a polynomial $P(x)=a_{p-2}x^{p-2}+\ldots+a_1x+a_0$ with random $a_{p-2},\ldots,a_1$ and $a_0$ such that $P(x_0)=m$; $\mathrm{Dec}(P):=P(x_0)$ (everything is modulo $p$). This construction gives FHE because $(P_1P_2)(x_0)=P_1(x_0)P_2(x_0) \bmod(x^{p-1}-1)$ and $(P_1+P_2)(x_0)=P_1(x_0)+P_2(x_0).$

Is this idea reasonable or I missed some pitfalls?

I missed some pitfalls?

The most obvious one is that the secret key $x_0$ is recoverable with a single known plaintext/ciphertext pair.  That is, if we know both $m$ and $Enc(m) = a_{p-2}x^{p-2} +\  ... \ + a_1 x + a_0$, then we know that $x_0$ is a root of the polynomial $$a_{p-2}x^{p-2} +\  ...\  +\  a_1 x + (a_0 - m)$$
Roots of polynomials modulo $p$ can be efficiently recovered; this will give us the value $x_0$ (and possibly a few other false hits).

The other practical issue is that your ciphertexts consists of $p-1$ values; unless $p$ is tiny (e.g. no more than $2^{40}$), then you have impractically large ciphertexts.


The compression of the eliptic curve point coordinates Some time ago I faced the problem of the unexpected format compression of the points on elliptic curve. I used ECDH procedure with a third party service on the base of the $\mathbb({F}_{2^m})$ curve in the polynomial $(m,k_3,k_2,k_1) = (431,5,3,1)$ representation.

As response I received a compressed point in the following format:

03 39000436 + "108 other digits"

My confusion was that I expected to see the compression format corresponding to X9.62 standard: Public Key Cryptography For The Financial Services Industry:
The Elliptic Curve Digital Signature Algorithm (ECDSA)

I expected to see 03 + "108 digits". Here 03 is a sign of the compression format and 108 is the size of the $X$ and $Y$ coordinates (54 bytes each) for $(431,5,3,1)$ curve.

Could you please help me to understand what does this 39000436 mean?

In this case the 03 is not a sign of the compression format. It's a DER encoding of an ASN.1 BIT STRING, with a length of 39 hex (57 bytes). 00 means that all the bits in the remaining 56 bytes are used; this is rather common. 00 itself is not part of the encoded value.

Within this BIT STRING there is a value starting with 04 36. Here 04 is not an uncompressed point, but it is an ASN.1 OCTET STRING. Again, 36 is the length, in this case 54 bytes (the previous 57 bytes with an additional overhead of 00  04 36).

A BIT STRING is often used to be able to use any key or data format within it. The OCTET STRING is probably used to wrap the coordinate(s) within it. Because the BIT STRING doesn't indicate that there is an ASN.1 encoding within it (it contains a primitive value rather than a constructed value), decoding is a two step process. In this case the OCTET STRING is spurious, but it may be different for other structures that consist of a SEQUENCE of elements.

The 54 bytes of the value of the OCTET STRING are the minimum number of bytes to store a single 431-bit coordinate: $\big\lceil 431 / 8 \big\rceil = 54$. This could be the X coordinate that is the result of an ECDH calculation. If it was a point representing a public key you'd expect a compressed or uncompressed point, which would take one byte in addition to the 54 bytes given.


Security of SRP-6a against impersonating server choosing small/wrong N I'm looking at an implementation of SRP (Secure Remote Password) that essentially follows the Stanford documentation (http://srp.stanford.edu/design.html). I'm worried about one aspect though: In the initial message exchange the server sends the parameters to be used (modulus $N$, generator $g$, salt $s$) to the client after potentially looking up these parameters per user.

A correct server would choose $N$ as a large safe prime and $g$ as a generator. Under these circumstances I can see why the further protocol will give no information to try more than one password per protocol execution to a) a passive attacker, b) a man-in-the-middle attacker, or c) an active attacker that impersonates a server but doesn't have a copy of the server's database of password verifier values (otherwise a brute-force attack is trivial).

However, given that the attacker is not likely to play by our rules, what would happen if an attacker that impersonates a server (but doesn't know the password verifier stored in the server database) choose bad values for $N$ and $g$?

These could be

small $N$
composite $N$
non-safe prime $N$
generator $g$ of a small subgroup in composite or non-prime $N$

Wouldn't the attacker in the server's position then be able to brute-force the discrete logarithm and learn the password-equivalent secret $x$ modulo their chosen small $N$ or in a small subgroup?

I don't see how the server can directly learn $x$; what a server would be able to is perform a single exchange with the client (recording the initial parts of the protocol), and then go through a dictionary, and test various passwords (that is, various possible $x$ values), and realize when he finds the right one.

The idea here would be to select a prime value $N$ where $N-1$ is smooth (that is, a product of small factors); this makes solving the discrete log problem modulo $N$ easy.

With that, when the client sends $g^a$ as its initial exchange, the server can immediately recover $a$.  It then sends back random values for $B$ and $s$.
The client then sends its verifier $H[H(N) \oplus H(g) | H(I) | s | A | B | K_{Client}]$.

After that, it's easy; if the server has a guess for the password, it can compute the corresponding $x$ value, and then the shared key that the client computes; $K_{Client}=H( (B − kg^x)^{a + ux} )$; where $B, k, g, a, u$ are known values, and $x$ depends only on the password.  Then, we can go back to the verifier and recompute it based on the possible $K_{Client}$ value (as $K_{Client}$ is the only value that the server does not know; if the computed value matches the value that the client sent, then we have correctly guessed the password (or we found a collision in the hash function).

This isn't likely the only game we could play with a malformed group; it is likely to be the most serious.

The moral of this story: either the client must verify that the group proposed by the server is secure (both $N$ and $(N-1)/2$ are prime; $g$ is a generator, that is, $g^{(N-1)/2} = -1$ and $g \ne -1$); or the client needs not to work with arbitrary $N$, $g$ values, but instead only with preconfigured ones that it knows are secure.


State of the art in zero knowledge proof compilers? What is the current state of the art zero knowledge  proof compiler ? I need one that can minimally handle double exponentiation  by a known value  E.g.

$$Pok\{(\alpha):h=g^{\alpha^b}\} $$
where b, g and h are public but $\alpha$ is secret.

Preferably it should be able to handle double discrete log proofs E.g.

$$Pok\{(\beta):h=g^{a^\beta}\} $$ where a, g and h are public and $\beta$ s secret.

ZKPDL does not handle at least the later case.

A protocol for double discrete log proofs is given in M. Stadler, "Publicly verifiable secret sharing", Eurocrypt '96, Section 3.3.

In Stadler's notation, given $g$, $y$, and $V = g^{y^\alpha}$, and $A = h^\alpha$ for some generator $h$, Stadler's protocol shows how to prove that $\log_h A = \log_y(\log_g V)$. Now, to solve your problem, let $V$, $g$, and $y$ be known. To prove knowledge of $\alpha$, have the verifier choose a generator $h$. The prover provides $A = h^\alpha$ and uses Stadler's protocol to prove that $\log_h A = \log_y(\log_g V)$.


Hash of multiset of values, which lets me compute the hash of the union Cryptographic hash functions normally take as input a bitstring.

I am looking for a hash function that takes as input a finite multiset of values.  In other words, given $S \subset \{0,1\}^*$, I want to compute $H(S)$, a hash of $S$.  Also, I would like this function to be chosen so that given the hashes $H(S),H(T)$ of two multisets $S,T$, I can efficiently compute the hash $H(S \cup T)$ of their union.  (If you like, you can think of this as a sort of associativity property.)

I would prefer a hash function that behaves essentially like a random oracle on this domain.

Are there any good constructions?  Are there any constructions that are based upon a standard hash function and whose security is reducible to the security of the underlying hash?

Here is another way to think about it.  I want a hash function that accepts a sequence of bit-strings as input.  If the input is $x_1,\dots,x_m \in \{0,1\}^*$, I'll let $H(x_1,\dots,x_m)$ denote the output.  I want this function to have two properties:

Commutative: If $y_1,\dots,y_m$ is a re-ordering of $x_1,\dots,x_m$, then $H(x_1,\dots,x_m) = H(y_1,\dots,y_m)$.
Associative: Given $H(x_1,\dots,x_m)$ and $H(y_1,\dots,y_n)$, there is an efficient way to compute $H(x_1,\dots,x_m,y_1,\dots,y_n)$ (without knowing the underlying entries $x_1,\dots,x_m,y_1,\dots,y_n$).

One solution is a group-based hash function.  Choose an abelian group $(G,+)$ and a conventional hash function $h:\{0,1\}^* \to G$.  Then, set

$$H(S) = \sum_{x \in S} h(x),$$

or in other words,

$$H(x_1,\dots,x_m) = h(x_1) + h(x_2) + \cdots + h(x_m),$$

where $+$ represents the group operation of $G$.  Notice that this is commutative.  It is also associative: given $H(S),H(T)$, it is easy to compute $H(S \cup T) = H(S) + H(T)$.

The security of this depends partially upon the choice of $G$.  Here are some sample instantiations:

If you choose $G=(\mathbb{Z}/p\mathbb{Z},+)$ where $p$ is a large prime, the resulting scheme has been proposed by Bellare et al. under the name AdHash.  I would expect this to provide approximately 80-bit security if you choose $p \approx 2^{1600}$.
If you choose $G=((\mathbb{Z}/p\mathbb{Z})^*,\times)$ where $p$ is a large prime, the resulting scheme has been proposed by Bellare et al. under the name MuHash.  I would expect this to provide approximately 80-bit security if you choose $p$ such that the discrete log problem modulo $p$ provides at least $2^{80}$ security.
If you choose $G=(GF(2^n),+)$ (i.e., the group operation is xor of $n$-bit strings), the resulting scheme is insecure: it can be broken using a simple linear algebra based attack.

See also https://crypto.stackexchange.com/a/5231/351


Research Question (Part 2): new symmetric key cryptosystem A few weeks ago I asked about a new symmetric cryptosystem discovered as consequence of some new mathematics work (link here). As per suggestion of commenters, I spoke with a cryptography professor, a computer security expert, and also continued to discuss with different math professors.  We have since established the following facts as given in the below list. We wanted to (for the last time) ask a broad audience that could provide useful feedback given this now established new information.

Encryption takes form $E(T, K, P) = (T, C)$, and $D(T,K, C) = P$ for publicly chosen $T$.  Some of the following points have redundancies between each other, but I allow this for clarity.  The main properties of the cryptosystem are as follows.

The security of the system rests on no unproven assumptions (such as the difficulty of factoring).
Perfect secrecy: for $x \in P, y \in C$, $p(x|y) = p(x)$  (unconditionally secure), as arbitrary number of ciphertext gives no information about key or message.
Key reuse: unlike the one-time pad, given arbitrary number of $(T, C_i)$ pairs and no plaintext, the attacker learns nothing about $P_i$ or $K$.  Given $(T, P_i, C_i)$, the attacker learns nothing about $P_j$, $i \not=j$, given $E(T', K, P_j) = (T', C_j)$ for $T' \not=T$, nor about the key $K$.
Secure under chosen plaintext attack: the attacker learns nothing usable about $K$ with an arbitrary number of chosen plaintext/ciphertext pairs.
Semantically secure
Probabilistic system, but Bob can always successfully decrypt with probability 1
If the attacker guesses a key $K$, they have no way of verifying if the guess is correct, only that it is false.
If Alice and Bob share $l$ messages using the same public object $T$, then if Eve obtains a plaintext/ciphertext pair she may decrypt all such messages, but she will be unable to decrypt messages sent using public object $T' \not=T$.
More general cryptanalysis: with large number $l$ of distinct $(T_i, C_i)$ pairs so that $(T_i, C_i) \not = (T_j, C_j), i \not=j$, then, if Eve has a lot of compute, she may brute force construct an approximating key $K_a$, that would, with probability proportional to the size of $l$, give useful information about any new $C$, thereby ruining any previous notion of perfect secrecy with the cipher.  However, if Alice and Bob use the same $T$ for each message, such an approximating key could not be built, but then the messages would be susceptible to plaintext attack.
Note on efficiency: worst case encryption and decryption times grow linearly with key size.  In most cases encryption/decryption time grows at rate of log of key length.

Again, given this new (verified) information, does this system offer any theoretically interesting properties that could warrant publication?  Thank you all for your time.

Again, given this new (verified) information, does this system offer any theoretically interesting properties that could warrant publication?

Again, no.  You could put together a paper and submit it to eprint (or maybe arxiv, I'm not familiar with their acceptance policies), but beyond that, I can't think of any journal or conference that'd be interested.

As for your "verified" information:

  Perfect secrecy: for $x \in P, y \in C$, $p(x|y) = p(x)$

It is a homework exercise to show that if you have this property, then you must have at least as many keys as possible plaintexts.  So, to encrypt a megabyte plaintext, you must have a megabyte key.  So, do you have megabyte keys?  Or, do you have a low ceiling on the size of the plaintext you can encrypt?

  If Alice and Bob share $l$ messages using the same public object $T$, then if Eve obtains a plaintext/ciphertext pair she may decrypt all such messages

So, the public object $T$ is effectively a nonce; that is, a given $T$ value can be used to encrypt only a single message.

  with large number $l$ of distinct $(T_i, C_i)$ pairs so that $(T_i, C_i) \not = (T_j, C_j), i \not=j$, then, if Eve has a lot of compute, she may brute force construct an approximating key $K_a$, that would, with probability proportional to the size of $l$, give useful information about any new $C$

So, if the attacker gets a number of ciphertexts, they can get information about plaintexts encrypted with the same key.  This falls rather short of the "perfect secrecy" you claimed in the previous bullet points.

The only comeback would appear to be "by a lot, you mean more computation than is feasible.  However, if you make that argument, you have to assume that there are no optimizations beyond the attack you have sketched out; that means that you are making an assumption (and so you are not really any better than, say, AES or ChaCha…)

  worst case encryption and decryption times grow linearly with key size. In most cases encryption/decryption time grows at rate of log of key length.

I'm not sure what to make of this.  By 'key length', we typically mean 'length of the key in bits'.  To use $n$ bits of the key as part of the encryption or decryption time, that takes at least $O(n)$ time (if nothing else, to read the key bits).  If encryption/decryption time grows (in most cases) logrhythmically with key length, that means in most cases you don't access the majority of the key bits (because you don't have the time).  This property would make key searching attacks far more efficient (as the attacker wouldn't have to guess most of the key).

Is that what you really meant?


SHA-1 collision for strings of two symbols Is it possible to have strings of two (Unicode) symbols with equal SHA-1 hash?

For example, smth like "ab", "ba".

No, that's actually pretty easy to compute, because you only have to compute all possible hashes of possible two strings, which would be $n^2$, where $n$ is the number of possible characters / symbols.

Edit:

As fgrieu correctly explained in the comment: Because of the birthday attack we would expect a natural collision between two SHA-1 hashes to occur at $\approx 2^{80}$ hashes.

And $2^{80}$ is a lot larger than $1,111,998^2$.

2nd Edit:

There are a lot of different sources for the exact amount of Unicode characters / symbols there could be (see comments below), but most of them are around $1'100'000$ and are either way far too small to reach $2^{80}$.