Is one time pad cipher reuse and random key secure? The sender and receiver share two different secret keys:  s1 and s2 both y bit values. 'x' is a randomly generated y bit value. The reader sends to the tag a challenge y =  x ⊕ s1, and the receiver  responds with z = x ⊕ s2 after recovering x = y ⊕ s1.

s1 and s2 never change, x is randomly generated each complete transaction.
Can you determine s1 and s2 through a single transaction? After multiple?

If your goal is to ensure only the legitimate sender with knowledge of $s_1$ and $s_2$ can answer the challenge, then this protocol fails to achieve your goal: eavesdropping a single challenge/response pair $(y, z)$ is enough to forge any number of subsequent responses pairs with the same $s_1$ and $s_2$.

Specifically, $z = y \oplus s_1 \oplus s_2$, so to forge the correct response $z' = x' \oplus s_2$ to a subsequent challenge $y' = x' \oplus s_1$ it suffices to recover $s_1 \oplus s_2 = z \oplus y$ and then to compute $$z' = y' \oplus s_1 \oplus s_2 = x' \oplus s_1 \oplus s_1 \oplus s_2 = x' \oplus s_2$$ as expected.

If each $x$ is independently uniformly distributed, then you can't recover $s_1$ or $s_2$ from it (effectively, you have encrypted $s_1$ with the one-time pad $x$ in this scenario!), but seldom is the pad the object you're interested in protecting in the end!

So what are you really trying to accomplish here?


Key derivation: Does it make sense to use KDF and PRF consecutively? I'm in a project, where the output of a Key Agreement algorithm (uses ECC) is used as input for a KDF, and the output of the KDF (X9.63 KDF) is consecutively used as input for a PRF (CMAC) to calculate AES session keys.

Summary: ECC-PAKE->KDF->PRF->AES_keys.

My question: Is there any major advantage of using both KDF and PRF? Wouldn't the KDF good enough in this scencario?

Assuming the KDF is actually secure,There is no clear advantage other than domain separation, and certainly some severe disadvantages (code complexity and size).

If you have the ability to change things, I would simply use one call to HKDF-SHA256 or HKDF-SHA512 once to get all the bytes you need.  SHA-256 is hardware accelerated on some platforms so you might prefer that.

Many crypto libraries have HKDF, if not it is trivial to implement correctly if you have an HMAC primitive available.

UPDATE: I now see that the latest ANSI X9.63 still specifies SHA-1 as its hashing primitive. SHA-1 is broken in terms of collision-resistance. While that doesn’t immediately affect a KDF (which relies on pre-image resistance), it does means you should clearly replace it with something stronger as soon as possible. SHA2-256, SHA2-512, SHA-3, BLAKE2 are all reasonable choices.


How to generate 1024-bit RSA key I have generated a prime number with a 1024-bit size.

Now, when I create an RSA key - how many bits does the key have?

By definition, an integer $a$ is $n$-bit iff $2^{n-1}\le a<2^n$. It follows that the product of two $n$-bit primes is a composite of $2n$ or $2n-1$ bits.

In order to generate an RSA key of $2n$ bits, it is customary to generate two $n$-bit primes each at least $2^{n-1/2}$; this ensures that their product is at least $2^{2n-1}$, thus exactly $2n$-bit.

$1204$ or $2408$ bits would be unusual RSA key sizes. $1024=2^{10}$ bits used to be common, $2048=2^{11}$, $3072=3\cdot2^{10}$, and $4096=2^{12}$ bits are common modern sizes.


Complexity of number field sieve theorem does not match with security of elliptic curves Number field sieve algorithm can is used to break discrete logarithm on field $F_{p^n}$. The algorithm has time complexity $\exp((c+o(1))\cdot(\log p^n)^{1/3}\cdot(\log \log p^n)^{2/3}$. Originally the constant $c$ is $(64/9)^{1/3} = 1.92$. Due to recent works, the more advanced Special extended tower number field sieve algorithm has $c = (32/9)^{1/3} = 1.54$.

Using this I tried to estimate the security of pairing-based elliptic curves. Consider BN256 curve. The pairing based elliptic curve has embedding degree 12. This means, the discrete log on BN256 can be mapped to discrete log on $F_{p^{12}}$, where $p$ is 256 bit prime. Now, on calculating the complexity of original NFS algorithm on $F_{p^{12}}$, we get roughly $$\exp(1.92 * (12*256)^{1/3} * (\log_2 (12*256))^{2/3}) = \exp(142.9) = 2^{206.16}$$ by wolframalpha (I ignored o(1) term for simplicity). So, BN256 curve originally provided 206 bit security. But in many places I saw that BN256 curve provided 128 bit security. Where I am doing wrong?

Edit: By @Poncho's answer, BN256 curve can be attacked better by pollard's rho algorithm. That justifies why BN256 is claimed to have 128 bit security earlier. After the recent Tower NFS algorithm, BN256 is claimed to have less than 110 bit security (Table in this blog). But when I calculate by wolframalpha,
$$\exp(1.54 * (12*256)^{1/3} * (\log_2 (12*256))^{2/3}) = \exp(114.6) = 2^{165}$$.
Therefore, even now, BN256 curve should have 128 bit security right?

But in many places I saw that BN256 curve provided 128 bit security. Where I am doing wrong?

There are two potential attacks against the DLog problem in BN256

The first is to attack the DLog problem in the finite field; that is, given the points $G$ and $H$, we compute $e(G, G)$ and $e(G, H)$, and then find the value $x$ with $e(G, G)^x = e(G, H)$.
The other is to attack the DLog problem in the elliptic curve itself; that is, given the points $G$ and $H$, you use Pollards Rho (or Big-Step-Little-Step) to directly solve $xG = H$ (ignoring the pairing operation entirely).

As BN256 is a 256 bit curve, we know that the cost of the second approach is no more than an expected $2^{128}$ point additions, hence the security of the curve can be no more than 128 bits.


Zero Knowledge Proofs in BPP I understand that there are non-interactive (static) ZK proofs for every language in BPP, but I am not sure I fully understand this.

Can someone give an example of a Zero Knowledge Proof in BPP?

A zero-knowledge proof for a language in BPP is trivial: a statement in BPP can be verified in probabilistic polynomial time (by definition). So, for any language $L$ in BPP, and any $x \in L$, here is a trivial proof that $x\in L$: the prover sends nothing, and the verifier checks whether $x\in L$ (this takes polynomial time) and output yes iff this holds. Correctness is trivial, soundness too (the prover cannot cheat as he does not send anything at all), and zero-knowledge as well (it requires simulating an empty transcript...).

Here is an example: consider the language of prime numbers. Given a number $n$, the prover wants to convince the verifier that $n$ (which they both know) is prime. To do so, he comfortably stays at home and watches a movie, while the verifier checks by herself that $n$ is prime, using any polytime primality test of her choice. When she's done, she can just tell the prover "ok, you convinced me".


LWE: error and float operations Background

I'm trying to make sense of the error in implementations of LWE and R-LWE.  In LWE and R-LWE error is added to vectors in lattices to make it computationally infeasible to recover any meaningful data.

It was said here that using float operations in PRNG's aren't reliable enough across different environments.

According to the accepted answer on this question though, it's possible to "trivially" generate cryptographically secure, nearly uniform distributions of floating point decimals.

Questions

Does the error used in LWE or R-LWE rely primarily on float operations?
Do float operations need to be in a finite field to be secure?
Before rounding occurs, are all numbers floating decimals?

Conjectures

My assumption is that Case 1 may be likely, but Case 2 is true.  This leads me to believe that only error terms are treated as floating point decimals as a way to maintain efficiency and security, but taking everything either modulo a number or modulo an ideal generates an integer.  So in effect, the error taken modulo a number produces a lattice point (integer), or error taken modulo an ideal produces a lattice (finite field).

Is this an accurate assessment?

Answering point 3, no.  Rounding a floating point number just leads to a floating point number.  It just has less significant digits.  So they're still represented as a significand and exponent.  This is a widely accepted format these days.  An integer is a totally different storage method that does not lead to accumulated errors.  They're 100% precise.  The uniform distribution problem is exacerbated by the gargantuan 24 orders of magnitude variance in precision of floating point numbers as:-

Further arithmetic operations on a rounded floating point number will still accrue rounding errors in difficult to predict ways.  And different languages have different types of numbers.  For example Java has different types of numbers compared to  Perl, and those are different to C /C++.  This contributes to the difficulty of  native random floating point number generators.

It's typical to cast a number from one kind to another if you want to change type.


Finding the LFSR and connection polynomial for binary sequence. I have written a C implementation of the Berlekamp-Massey algorithm to work on finite fields of size any prime. It works on most input, except for the following binary GF(2) sequence:

$0110010101101$ producing LFSR $\langle{}7, 1 + x^3 + x^4 + x^6\rangle{}$

i.e. coefficients $c_1 = 0, c_2 = 0, c_3 = 1, c_4 = 1, c_5 = 0, c_6 = 1, c_7 = 0$

However, when using the recurrence relation

\begin{equation}
s_j = (c_1s_{j-1} + c_2s_{j-2} + \cdots + c_Ls_{j-L}) \mbox{ for } j \geq L.
\end{equation}
to check the result, I get back:

0110010001111, which is obviously not right.

Using the Berlekamp-Massey Algorithm calculator they say the (I believe) characteristic polynomial should be $x^7 + x^4 + x^3 + x^1$. Which, according to my paper working, the reciprocal should indeed be $1 + x^3 + x^4 + x^6$.

What am I doing wrong?  Where is my understanding lacking?

This is probably just a difference in notation than any failure in
understanding or implementation. Some people define recurrence relations with subscripts in reverse order than others; the original description given by Berlekamp in his 1968 book Algebraic Coding
Theory began counting from $1$ instead of $0$ etc.  Observe that
$$x^7 + x^4 + x^3 + x^1 = x^7(1 + x^{-3} + x^{-4} + x^{-6})$$
in comparison to your $1 + x^3 + x^4 + x^6$ which you say is the
correct reciprocal of what the web site's answer should be.
So I would say that the web site seems to be following
Berlekamp's original description and giving you an answer that is "off-by-one".


Toy hash algorithm that can be broken I'm looking for a toy hash function, where the idea is to have high school students break (i.e. find a collision) a hash function by hand, in order to teach them how one way functions and hashing works.

Do you happen to know some function like that?

As for how hard I want it to be to breakable: Ideally a "sizeable" function so that depending on some variable it can be easier or harder, but overall I'm looking at something about between 10 and 30 minutes.

I like the didactic approach in this answer. But for something that behaves more like a hash function should, we might define $H$ for strings of digits $s$ as: $H(s)=(((1||s)\bmod 97)||s)\bmod 99991$ where $a||s$ is the number resulting from prepending the decimal representation of $a$ to the string $s$.

Worked out example for $H(012345678)$
$=(((1||012345678)\bmod 97)||012345678)\bmod 99991$
$=((1012345678\bmod 97)||012345678)\bmod 99991$
$=(37||012345678)\bmod 99991$
$=37012345678\bmod 99991$
$=77082$.

With some math insight and very little extra computational effort, one can exhibit a collision; a "brute force" search for collision is also feasible with simple use of a spreadsheet.


Why no swapping block in the last round of DES? Round 16 on the encryption side, and round 16 on the decryption side of DES have no swapping module.

Why is it like this? Can anyone provide any justification?
This is my homework question.

In "Applied Cryptography" — Chapter 12, , Bruce Schneier writes:

The final permutation is the inverse of the initial permutation and is described in Table 12.8. Note that the left and right halves are not exchanged after the last round of DES; instead the concatenated block $R$16$L$16 is used as the input to the final permutation. There’s nothing going on here; exchanging the halves and shifting around the permutation would yield exactly the same result.
This is so that the algorithm can be used to both encrypt and decrypt.


Can ECDSA signatures be safely made "deterministic"? Using the terminology of the ECDSA Wikipedia page, ECDSA (and DSA) signatures require a random k value for each signature which ensures that the signature is different each time even if the message and key are the same. For some applications, a "constant" signature may be desirable.

It seems to me that there would be no harm in implementing "constant" ECDSA by setting the "random" k value to be the x-coordinate of the message hash z (converted to a curve point in some arbitrary fashion) multiplied by the private key. Obviously the method translates back to DSA.

This scheme might be useful for implementations that do not have access to a source of random numbers.

Are there any problems with this?
Is there a faster way of generating a suitable k than a point multiplication?

There is a draft RFC which describes a way to implement deterministic (EC)DSA (with test vectors). In this draft, both $h(m)$ (the hash of the message) and $x$ are used as input to a deterministic PRNG which uses HMAC (that's HMAC-DRBG as specified by NIST); the PRNG output is used to yield $k$. I am not sure your simple multiplication with $x$ would be enough to guarantee security; ideally, a random oracle should be used, and HMAC-DRBG is the closest to a practical random oracle that I could find.

Note that $k$ must be generated uniformly in the $[1, q-1]$ range (where $q$ is the subgroup order). Any information on $k$, even partial (such as: values between $1$ and $2^{160}-q$ are twice as probable than values between $2^{160}-q$ and $q$), can be exploited by the attacker.

(There will be a new draft version with a few text changes in the draft -- but the same test vectors -- as soon as I find the time to do it.)

Edit: the RFC is now published as RFC 6979.


What is the new attack on OCB2 and how does it work? OCB2 is proposed by Rogaway, Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC
, and it is standardized in ISO/IEC 19772:2009. The author also provided a proof by security reductions, that is, a break of OCB2 implies the break of the underlying block cipher.

However, Akiko Inoue and Kazuhiko Minematsu describe practical forgery attacks against OCB2.

How does the attack work (on a high level)?
Why did the proof by security reduction fail?
What are the implications?

How does the attack work (on a high level)?

It's an unfortunate consequence of how the pad of the last encryption block is computed. The pad can essentially be used to both eliminate the block cipher operation for a chosen ciphertext's decryption (allowing the attacker to determine the plaintext) and the pad can be used as the tag in this attack. It's quite incredible.

The attack crafts a special initial plaintext, sends it to an encryption oracle, receives a ciphertext and tag, modifies both of those, and then sends them to a decryption oracle which accepts the modified tag for the modified ciphertext (hence, a successful forgery).

The modified ciphertext (which is submitted to the decryption oracle) will have it's block cipher operations cancelled out in decryption. See the paper for details on how this works. The gist of the idea is that the pad used for the last (and only block) has the same block cipher operation in it as the ciphertext block. Said another way, the pad and the ciphertext are both the results of data xored with the block cipher called on the same input. Since the pad is xor-ed with the ciphertext block, we essentially eliminate the only operation requiring knowledge of the secret key, so we now know what the plaintext will be.

The correct tag for the modified ciphertext turns out to be the pad from the original encryption oracle call. This pad is simply the last block of the initial plaintext, which was sent to the encryption oracle, xor-ed with the last block of ciphertext that the oracle outputs. So a forgery takes exactly one encryption oracle call.

I highly recommend reading the paper for details, I've tried to keep all the math out of this since you asked for high level, but the magic is really in how the plaintext is crafted and how the ciphertext is modified in a way that the corresponding tag can be deduced by the attacker.

  Why did the proof by security reduction fail?

The security reduction failed because of a subtlety in how XEX (xor encrypt xor) and XE (xor encrypt) were combined into XEX* for OCB2 mode. The issue is that, even if the encryption function (e.g. the block cipher) is information theoretically secure (think a uniform random permutation), XEX* is not.

There is an issue with what the adversary is, by definition, allowed to do in the security proof of OCB2. The adversary is assumed to be tag-respecting, i.e. it can only query the encryption and decryption oracle with certain parameters to XEX*, but the construction of OCB2 actually violates this tag-respecting property in a very subtle way. I again will refer you to the paper for details, the proof is a bit complex and there's no good way to thoroughly give it without re-rewriting it.

The solution to enforcing this tag-respecting property is rather simple, which is to use XEX to generate the padding used in the last block, rather than XE.

  What are the implications?

This break is very specific to OCB2, down to how it uses XEX*. OCB1 and OCB3 are not affected. Use of the ISO spec of OCB2 should be discontinued. For deployments using OCB2 that need to path a quick fix, the solution mentioned above of using XEX rather than XE for the padding of the last block should suffice. The authors call this modification OCB2f and assert that the security bounds claimed for OCB2 are in fact now correct.

I've tried to answer in readable fashion without getting into all of the technical details (which would amount to re-writing the paper), but the best way to really understand the attack and its impact is to read the paper and grok the math behind how the attack works, and how it violates the assumptions that were made in the original security proof.


Proof that MAC and hash composition is insecure Let $F$ be a secure PRF and $H$ a universal hash function.

How can I exhibit a pair $(F,H)$ whose composition $$S'((k_1, k_2), m) = F(k_2, H(k_1,m))$$

is an insecure MAC (or an insecure PRF, since a MAC can be defined as a PRF) ?

I guess that, in order to find a pair $(F,H)$, the trick would be creating some $H$ whose image space is short enough so to easily find a collision, but I'm not good at finding an example of such functions, the books I read always try to abstract these functions.

Without breaking $F$, you can't: $S'$ is a PRF with almost the same security as $F$.

Let $k_1$ and $k_2$ be uniform random keys.  Let $F$ be a PRF, with advantage $$\operatorname{Adv}^{\operatorname{PRF}}_F(A) = \lvert\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]\rvert$$ for any distinguisher $A$, where $f$ is a uniform random function with the domain and codomain of $F$.  Let $H$ be an $\varepsilon$-almost universal hash family, so that $\Pr[H_{k_1}(x) = H_{k_1}(y)] \leq \varepsilon$ for any $x \ne y$.  (Without qualification, $\varepsilon = 1/|T|$ where $T$ is the codomain of $H$.)

Define $$S'_{k_1,k_2}(m) = F_{k_2}(H_{k_1}(m)).$$

Fix any PRF-distinguisher $A'$ for $S'$ making $q$ queries, and let $U$ be a uniform random function with the domain and codomain of $S'$.  We will bound the advantage of $A'$ at distinguishing $S'$ in terms of the advantage of another algorithm $A$ at distinguishing $F$ and the collision probability $\varepsilon$ of $H$:
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')
    &= \lvert\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]\rvert \\
    &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A) + \binom{q}{2} \varepsilon,
\end{align*}
where $A$ is a PRF-distinguisher for $F$.  As long as $\operatorname{Adv}^{\operatorname{PRF}}_F(A)$ is small and $q$ is not too large, $\operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')$ is small too.

We will do this by the triangle inequality with the intermediate probability $\Pr[A'(f \circ H_{k_1}) = 1]$ that $A'$ returns 1 on a variant $f \circ H_{k_1}$ of $S'_{k_1,k_2} = F_{k_2} \circ H_{k_1}$, where a uniform random $f$ has been substituted for $F_{k_2}$.

Define the PRF-distinguisher $A$ for $F$ by $A(\mathcal O) = A'(\mathcal O \circ H_{k_1})$.  Then
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRF}}_F(A)
    &= \lvert\Pr[A(F_{k_2}) = 1] - \Pr[A(f) = 1]\rvert \\
    &= \lvert\Pr[A'(F_{k_2} \circ H_{k_1}) = 1]
           - \Pr[A'(f \circ H_{k_1}) = 1]\rvert.
\end{align*}
If $A'$ is a good distinguisher for $S'$, we will find that $A$ is a good distinguisher for $F$, unless $A'$ just got lucky finding collisions in $H$.
Now consider the $q$ queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ for the oracle $f \circ H_{k_1}$.

From queries to $H_{k_1}$ alone, of which we assume only the weak property of collision probabilities on two distinct inputs, an adversary could find a collision among three inputs with high probability—e.g., in a polynomial evaluation MAC $M_{r,s}(m) = s + \sum_{i=1}^{|m|} m_i r^{|m| - i + 1}$ the adversary could trivially recover the keys $r$ and $s$ from two distinct queries and find arbitrarily many collisions with probability 1 after that.

But since $f$ is a uniform random function, the only information $A'$ can learn from oracle access to $f \circ H_{k_1}$ is whether the queries collide in one of $H_{k_1}$ or $f$, or definitely do not collide in either.  The adversary can adaptively act on the information that queries might collide only if a collision actually occurs in $H_{k_1}$, which happens with probability at most $\varepsilon$ for any pair of inputs submitted.  Thus, to study $\Pr[A'(f \circ H_{k_1}) = 1]$, it suffices to set a bound on the probability that there is a collision at all.

Among the queries $x_1, x_2, \ldots, x_q$ submitted by $A'$ to $f \circ H_{k_1}$, the event $C$ of a collision in $H_{k_1}$ has probability
\begin{multline*}
  \Pr[C] = \Pr[\exists i < j\colon H_{k_1}(x_i) = H_{k_1}(x_j)] \\
    \leq \sum_{i<j} \Pr[H_{k_1}(x_i) = H_{k_1}(x_j)]
    \leq \sum_{i<j} \varepsilon = \binom{q}{2} \varepsilon,
\end{multline*}
In the event $\lnot C$ that the queries do not collide in $H_{k_1}$, the distribution of each $f(H_{k_1}(x_i))$ is independent uniform random, identical to the distribution of $U(x_i)$.  Hence necessarily $\Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C] = \Pr[A'(U) = 1]$, so that
\begin{align*}
  \Pr[A'(f \circ H_{k_1}) = 1]
    &= \Pr[A'(f \circ H_{k_1}) = 1 \mid C]\,\Pr[C] \\
    &\quad + \Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C]\,\Pr[\lnot C] \\
    &\leq \Pr[C] + \Pr[A'(f \circ H_{k_1}) = 1 \mid \lnot C] \\
    &\leq \binom{q}{2} \varepsilon + \Pr[A'(U) = 1],
\end{align*}
and thus $\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1] \leq \binom{q}{2} \varepsilon$.
Summing up,
\begin{align*}
  \operatorname{Adv}^{\operatorname{PRF}}_{S'}(A')
  &= \lvert\Pr[A'(S'_{k_1,k_2}) = 1] - \Pr[A'(U) = 1]\rvert \\
  &\leq \lvert\Pr[A'(F_{k_2} \circ H_{k_1}) = 1]
            - \Pr[A'(f \circ H_{k_1}) = 1]\rvert \\
  &\quad + \lvert\Pr[A'(f \circ H_{k_1}) = 1] - \Pr[A'(U) = 1]\rvert \\
  &\leq \operatorname{Adv}^{\operatorname{PRF}}_F(A)
         + \binom{q}{2} \varepsilon,
\end{align*}
QED.

This follows the structure of the proof of Lemma 3.3 in:

  Shay Gueron and Yehuda Lindell, ‘GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte’, in Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 109–119

Variants of the theorem appear in many earlier papers, including the MDx-MAC paper that preceded the creation of HMAC, and the HMAC/NMAC security papers.


Why do block ciphers need a non-linear component (like an S-box)? Why is there a requirement of "Non-Linear functions" as a component of many popular block ciphers (e.g. the S-box in DES or 3DES)?

How does it make the cipher more secure?

The only intuition I have is a non linear function can have many roots (solutions). E.g. for a non linear $y = F(x)$, if attacker knows $y$ to find out the $x$, there might be many choices which satisfy $y= F(x)$ hence it adds up complexity at attacker's end when he tries to make his way back (trace back) from cipher text to plain text.

Any references or detailed material are appreciated.

If a block cipher is linear with respect to some field, then, given a few known plaintext-ciphertext pairs, it is possible to recover the key using a simple Gaussian elimination. This clearly contradicts the security properties one expects from a secure block cipher.


Efficiency of McEliece cryptography (ciphertext expansion) Most of the sources say McEliece has never gained acceptance because of its large size of private and public keys.

However I have never heard about the size (or length) of its ciphertext. ("Ciphertext expansion".) For example, McEliece offers the linear code of length 1024 and of dimension 524. That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency?

That means a plaintext of length 524 will be encrypted to a ciphertext of length 1024 and then will be sent. Isn't is also an inefficiency?

Not really; or at least, that's not an inefficiency we care about.

A length of 1024 means, in this context, 1024 bits (or 128 bytes).  This compares favorably to RSA (for which a key with a 1024 bit ciphertext has questionable security).  More importantly, a ciphertext of 1024 bits is fairly cheap to transport; it fits extremely easy in an IP packet (if we're communicating over IP); over wireless (which we tend to be sensitive to message length due to power reasons), it's still not too bad.

The reason we don't use McEliece now is the "expense"; that is, those parts of the cipher that make it costly to implement.  And, the expensive part of McEliece is the public key (which is circa 200kbytes); we could fit it into a certificate, or pass it as an authenticated part of the key negotiation protocol, but it would be painful.  Most everything else about McEliece (the ciphertext size, the computational effort) are things we can easily live with (with the possible exception of the private key; we don't have to worry about transporting that around, but we still need to store it securely).


RSA padding and Least Significat Bit Oracle Attack So my question is do padding schemes used in RSA protect it against Least Significant Bit Oracle attack?

The attack I am talking about is described here:
RSA least significant bit oracle attack

As far as I know the padding schemes add some random bytes to the end of the block so that it always gives a different value when encrypted. But if it is done this way we can continue doing the LSB oracle attack and get the deciphered block, then easily discard the random bytes. Am i missing something about how padding schemes work?

Actually, the "Least Significant Bit Oracle attack" isn't actually an attack.

Instead, it is the observation that, if you were given a magical black box (an Oracle) that is able to take an RSA encrypted ciphertext, and give you the lsbit of the plaintext, you could use that Oracle to decrypt the entire ciphertext.

What we can conclude from that observation is that determining the lsbit of the plaintext is as difficult as doing a full decryption.  We use the phrase "hard bit" when discussing this (and similar) situations.

Since we don't actually have such a magical Oracle, we can't actually perform this in practice.

Since this is not specifically an attack (and in fact, is proof that the lsbit is not specifically weak), padding methods don't need to defend against it.


How to estimate the maximum computational cost bound for Key Derivation Functions (KDFs) before it becomes useless security-wise? From my understanding of Key Derivation Functions (KDFs), e.g. scrypt, Argon2, etc, we can tune their parameters such that it eventually becomes harder for an attacker to brute force a password-to-key through them.  At this point, the attacker may directly brute force the, say AES128, key.
It is nice to not over-tune the parameters of KDFs, so that the user is not needlessly suffering using a slow application.  I think it is ideal if the KDF is tuned only so that the user suffers least while still maximum possible security out of, say, AES128-CBC (or whatever other symmetric cipher).
An easy way is to explore all improvements in hardware and algorithm design, in order to get an estimation how long would it take certain well-funded organisations have to wait until they finally manage to decrypt my cipers.  But I think this approach is needless complex as I think we can probably say a lot about the computational bounds of KDFs by simply studying the problem from an information theoretic perspective.
Below is an attempt. My question is: can we make it tighter?

What I have done so far:
Let's say that $f$ is a 128 bit encryption/decryption function, and the KDF function is $k$.  also let's say that a single round of $k$ equals the encryption/decryption of a single block by $f$.  Let's say that our password has only $70$ bits of entropy.
So the total attempts to bruteforce all keys is $2^{128}$, while the total attempts to bruteforce the password is $2^{70}$.  Since $f$ and $k$ computationally cost equally $c$, then the actual cost of bruteforcing the keys is $c \times 2^{128}$, while the password is $c \times 2^{70}$.  In this case, the adversary will obviously go after bruteforcing the password.
To make the attacker not find the password easier to break, we can repeat the KDF $k$ for $r$ many times until the difficulty matches.  Basically:
$$\begin{split}
c2^{128} &= rc2^{70} \\
2^{128} &= r2^{70} \\
\frac{2^{128}}{2^{70}} &= r \\
2^{128-70} &= r \\
2^{58} &= r \\
\end{split}$$
If the KDF $k$ is itself is implemented by recursively calling $k$, then this $c$ is guaranteed, and simply repeating it long enough, recursively, will guarantee that the difficulty of bruteforcing the password via the KDF $k$ is as hard as bruteforcing keys with $128$ bits of entropy.
Meaning, if $r > 2^{58}$, then for the attacker would find it easier to bruteforce the key directly.  In this case, the attacker would totally ignore the KDF $k$ and move on to bruteforce $f$'s key.  In other words, $r>2^{58}$ is pointless.
Update:  the above is also implemented as part of ciphart.

Generally we look at strength by looking at the order $O$ that it adds to the password search when an attacker is trying to guess passwords. That's just the same as the number of iterations basically, assuming a salt and correct password hash. Often it is simpler to just use bits, which is basically the $\log_2$ of the order.
So if a password strength is an average of about 40 bits, then you'd take the $log_2$ of the number of iterations and simply add the values together to get the resulting strength. So given 1048576 iterations, we'd get around $40 + \log_2(1,048,576) = 40 + 20 = 60$ bits of strength. Given the average weakness of passwords, there is no higher limit that is not entirely impractical. Obviously performing $2^{88}$ operations to allow for even average passwords to have 128 bits security is out of the question. So generally you should aim for the highest value possible for a specific service.
For the same reason it is very important to take other measures than just using a password hash with large iteration count. Possible measures are a max number of retries, an added delay before testing each password, requiring a good password with (likely) high entropy or using a password manager of some kind. Browsers nowadays offer internal password managers including generation for a good reason.
Note that some of password hashes such as bcrypt use a two-exponential "work factor" instead of an iteration count to give a better idea of the strength added to the password entropy in bits.


What are Keyed functions? (Not Hash) I hope this question is not too obvious, but I came across this paper about PRF, and at some point it writes:

"Let $\mathcal{F}:=\{F_s\}_{s∈S}$ be a family of keyed functions, where each function $F_s$ maps ${\{0, 1\}}^{\ell_1}$ to ${\{0, 1\}}^{\ell_2}$."

What is this meaning of keyed function? What is $S$ in this example?

Thank you!

In the question, each function $F_s$ is transforming an $l_1$-bit bitstring into an $l_2$-bit bitstring.

I read $\mathcal{F}$ being "a family of keyed functions" as meaning that we can re-express all the $F_s$ (that is $\mathcal{F}$) as a single function $F$ with an extra (say, first) argument $K$ in $\{0,1\}^k$ designated the key, and one such key $K_s$ for each $s$ in $S$, such that $\forall x\in{\{0, 1\}^{\ell_1}}, F_s(x)=F(K_s,x)$.

Alternatively, we could have $K_s=s$, and the first argument of $F$ coming from $S$ (that would be the keyspace) rather than some $\{0,1\}^k$. The context should tell.

Addition: That use of "a family of keyed functions" is at least ambiguous and uncommon as far as I can tell. The answer is trying to make sense out of it, but is far from an endorsement.


Calculation of time needed to crack DES with my CPU I have a laptop that has the CPU and the RAMs shown below in the images.

My question is that, using this CPU and the RAMs, how much time would it take for me to crack an old school DES algorithm with 56 bit key.

I have read on the web that it was cracked in 56 hours using a 220,000$ machine in 1998. But I believe we are much more advanced in computing speed after 15 years and counting.

I would also highly appreciate if someone can explain the steps of how such a calculation takes place.!

I can't provide you with good numbers without actually benchmarking on your system.

All I can provide you with are estimates, based on the fact that Serpent is roughly as fast as DES. Of course the figures I can give you aren't actually brute-force figures but rather how much data can be encrypted per time, but this should give a solid estimate of the required time.

The general approach is to measure how many keys per second you can try and then divide $2^{56}$ by this number which will result in the number of seconds you'll need.

So let's estimate for Serpent with 56 bits. Serpent can get up to 0.16 GB/s on your machine as this is mainly computation bound. 0.16 GB is roughly $2^{24}$ blocks for DES, meaning you can roughly try $2^{24}$ keys per second. This means you need $2^{56}/2^{24}=2^{32}$ seconds for this which is equal to 136 years.

I'm sorry but I doubt this is feasible for you.
Note that even the brand-new Intel Core i7 6700K can only do 0.47 GB / s meaning an i7 6700K would also still require roughly 45 years. And to get even more crazy: the Intel Core i7 5960X is the best consumer CPU as of now can only do 0.63 GB / s resulting in 34 years. Now finally consider the currently strongest possible server mainboard running 8x Intel Xeon E7-8890v3 with 18 cores. There's no measured benchmark out there but I assume the performance to scale linearly with the number of cores (75 MB/s per core) and the frequency (62.5 MB/s with E7's freq). This would mean that this board could do 9GB / s of Serpent meaning $2^{30}$ blocks and thereby $2^{26}$ seconds being equivalent to 2.12 years (however this board would roughly cost $56k in 2015).


Is Strong MAC stronger than existential unforgeability? Especially in the context of Encrypt-then-Authenticate.

I assume that by a "strong MAC" you mean that it is infeasible for an adversary to also find a different MAC tag on a message which has been tagged. Any deterministic MAC (with canonical verification) is a strong MAC, but it is certainly not the case that every MAC is a strong MAC. Thus, indeed, there exist secure MAC schemes (that are existentially unforgeable) but are not strong MACs, meaning that this is a strictly stronger notion (by definition, a strong MAC is existentially unforgeable so the question is just whether it's the same or strictly stronger as a notion). Note that in order to achieve CCA security you need a strong MAC and thus in the context of encrypt-then-authenticate, this is indeed needed. It is possible to define a weaker type of authenticated channel for which it would not be necessary, but typically it is required.

For those not sure what a strong MAC is, see the following pasted excerpt from "Introduction to Modern Cryptography":


How can I estimate the amount of entropy (with JavaScript) that I'm seeding a CSPRNG with? I am trying to determine how much entropy is going into a specific CSPRNG in JavaScript, but I can't seem to find a pure-JS client-side implementation of an entropy estimator.

So, I need to find a way to estimate entropy locally with pure JavaScript.

If it helps, the entropy is in an array which should be easy to manipulate.

If someone chooses to run your program with a seed that you can't predict but an adversary can, you won't be able to tell.  There is no way around this: nothing about the software can tell you what an adversary does or doesn't know; you can only use cryptography to ensure that if an adversary doesn't know a key and the message, then they can't decrypt the message.

In general, to estimate the entropy of a system, you need to have a model for how the system behaves.  This is how all entropy estimation tools work: they posit some parametric model for how the input data might have been generated; then use the data to fit parameters for that model; and finally spit out the entropy of the model with the fitted parameters.


After ECDH with Curve25519, is it pointless to use anything stronger than AES-128? Is the following reasoning correct:

After ECDH with Curve25519, the resulting shared secret will be an EC public key with a bit strength of 128 bits.

This public key would then be hashed (let's say with SHA-2-256) to produce a key of length 256 bits for use in symmetric encryption. This symmetric key would have a bit strength of slightly less than 128 bits (because the hash operation reduces the bit strength very slightly).

Therefore using AES-256 with this 256 bit hash as a symmetric key would be a waste of time, and the 256 bit hash should be truncated to 128 bits and AES-128 used for the purposes of symmetric encryption. AES-128 would be 40% faster than AES-256, and there would be no advantage to using AES-256 over AES-128.

The reasoning is wrong, because the scaling of attacks on AES is qualitatively different from the scaling of attacks on X25519.

A successful multi-target attack on a system using AES-128—that is, an attack that recovers one of many keys—can cost much less than $2^{128}$ evaluations of AES-128.  Specifically, using Oechslin's rainbow tables, and on a machine parallelized $p \geq n^2$ ways, the expected cost of recovering the first of $n$ keys is $2^{128}/n$, the expected time is that of $2^{128}/np$ sequential evaluations of AES-128.  The expected cost of breaking all of the $n$ keys is still close to $2^{128}$, but in a real network of users, compromising one of them may be enough to compromise many of them.

In contrast, a successful attack on X25519 is expected to cost at least about $2^{128}$ bit operations using the best known strategy, even if it is a multi-target attack.  The expected cost of recovering all of $n$ keys is about $2^{128}\sqrt{n}$ bit operations, so there is an advantage to batch multi-target attacks, but the cost to recover the first one is still an insurmountable $2^{128}$ bit operations.

If you say that AES-128 has a ‘128-bit security level’, then you should consider X25519 to have a much higher security level.  But I don't think that's reasonable.  Rather, I think it is reasonable to say X25519 has a ‘128-bit security level’ and AES-128 has a much lower security level.

If you must use AES, then use AES-256 unless you have an overwhelming budgetary constraint preventing you from doing so.  If you don't need to do economics, don't let the adversary do economics either.

Consider using the simpler faster safer Salsa20 or ChaCha if what you really need is an IND-CPA cipher and you were going to use AES-CTR or AES-CBC or something instead.  Consider using authenticated encryption unless you have a reason not to—really, consider using NaCl crypto_secretbox, just like NaCl crypto_box uses internally with the outcome of an X25519 key agreement.


LED cryptography algorithm I would like to better understand the operation of the LED algorithm, especially the process of substitution and permutation of the blocks and especially the use of the keys in each round.

The keys in each round are expansions of a single key or keys are different?

Already consulted sources:

https://www.cryptolux.org/index.php/Lightweight_Block_Ciphers#Zorro

https://eprint.iacr.org/2012/600.pdf

But could not find if each round are expansions or are different keys.

The bottom of page 3 of your second link (the specification for LED) seems pretty clear:

"Note that for a 64-bit key $K$, all subkeys are equal to $K$, while for a 128-bit key $K$, the subkeys are alternatively equal to the left part $K^1$ and to the right part $K^2$ of $K$."

Basically, the input master key is split into a sorted list of nibbles, and whenever the algorithm needs subkey material it just uses nibbles directly from this sorted list -- moving each used nibble to the 'back of the line', so that all nibbles are used in succession.  Since the algorithm calls for 64 bits of subkey material at a time (16 nibbles), for a 64-bit master key every subkey will simply be the master key, and for 128-bit keys the algorithm will use the first 16 nibbles of the master key, and then the second 16 nibbles, and then the first 16 again, and so on.  The top of page 4 shows a diagram of how this works out for an 80-bit master key.

I would also point out that the subkeys are not used in each 'round' as stated in your question, but rather in between each step, where every step is composed of 4 rounds.  Each round consists of four operations, very similar to those used in AES -- first you xor a round constant into the state, then you replace each of the nibbles using a nonlinear substitution operation (the s-box from the cipher PRESENT), you transpose the nibbles, and then you 'mix' the nibbles by passing them through a highly diffusive linear permutation with a high branch factor (similar to MixColumns in AES, except optimized for nibbles).


Attribute-based cryptography I am trying to create a social network, in which I want to use attribute-based cryptography. One professor told me it is possible to do it only in J2EE, but he can barely code! Some friends of mine suggested using .NET.

I know through research that both are feasible, but since it is going to be a web-based application I was wondering if it would be possible to do it in PHP. Does anyone know? I can't find any material regarding this.

Is it difficult to implement algorithms in PHP? Can I implement AES or other symmetric algorithms in PHP? OR should I just stick to .NET?

If you need something that already exists, have a look at the advanced Crypto software collection and specifically cpabe — which implements ciphertext-policy attribute-based encryption scheme that uses C and PBC library for pairings.


RFC 4493 (AES-CMAC) algorithm with 256 bit key I apologize for the newbie question. If I were to use a 256-bit key and AES256 (assuming I had the function instead of AES128, the length of the for loops in the functions xor_128, leftshift_bit, generate_subkey, etc would remain as 16 correct? Since AES256 also returns a 128-bit result

example xor_128 function

void xor_128(unsigned char *a, unsigned char *b, unsigned char *out)
 {
      int i;
      for (i=0;i<16; i++)
      {
          out[i] = a[i] ^ b[i];
      }
  }

The AES-CMAC Algorithm in rfc4493

AES has 128, 192, and 256 bits key sizes and always 128-bit block size. They are usually written as AES128, AES192, and AES256. The block size is implicit since it is always 128.

The basic function xor_128 is used to support x-or operation of CBC-MAC for the message block, ciphertext blocks, and keys. The block size is always 128 regardless of the key size.

The rfc4493 is not mentioning the AES192 or AES256. This doesn't mean that one cannot use any other than AES128. The rfc4493 only provides a test code for AES128.

The NIST provides test vectors in NIST:  Block Cipher Modes of Operation - CMAC Mode for Authentication for AES128, AES192, and AES256.

The Generate_Subkey algorithm also needs the xor-128 to derive the keys, since the keys are xored with the blocks. This can be seen from the code

  Step 4.  if flag is true
           then M_last := M_n XOR K1;
           else M_last := padding(M_n) XOR K2;

The constants are the same and the standard can be found in  NIST 800-38B: Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication


Stateless and deterministic number generation I want a stateless deterministic pseudorandom generator.

Following number generation is deterministic, whenever I give $constantValue$, and index it will value $A$

$A  = Hash(constantValue + index)$

$index$ ranges from $0$ to infinity.

It is a deterministic value generation, but I have to keep state (index) to avoid generation of one value more than once.

My question is how can I make it stateless ( I do not have to keep a right index to avoid generation of one value more than once.)

I want to avoid generating one number (A) more than once I have to keep right index (state).

At the same time, I want value generation to be deterministic.

State here can be considered as---Merkle Signature scheme is stateful signature scheme, but SPHINCS is a stateless signature scheme.

Note that hash and a constant value is mandatory to be part of a pseudorandom generation.

I want a stateless deterministic pseudorandom generator.

I don't see how that can work.

"Stateless" - the generator is always in the same state

"Deterministic" - given the same state (and inputs, but there's no inputs here), the generator always generates the same output.

Hence, you end up with something that always generates the same output; hardly pseudorandom.

The comparison with SPHINCS doesn't appear to be quite valid; the original SPHINCS is not deterministic (it selects the path through the hypertree randomly); you could make it deterministic (by depending on the message being signed to seed your randomness), but that's making it depend on an input that your pseudorandom number generator doesn't have.


What does public-coin mean in interactive proof and zero-knowledge? For related materials I read, it seems that for the public-coin setting, the verifier will always send random messages to the prover. In this setting, can we regard the verifier as an honest verifier, since he always replies with a random message (rather than a message depends on previous messages)?

In [GK'91], it is proved that suppose that $L$ has a constant-round, negligible error, public-coin black-box ZKproof. Then $L \in BPP$. This theorem confuses me a lot.

For example, for Schnorr's protocol, we know that it is special honest-verifier zero-knowledge. But according to [GK'91], it seems that the protocol is not public-coin zero-knowledge (except DLOG is in $BPP$). Therefore, it seems that we cannot treat public-coin settings as honest-verifier settings. But what is the difference between public-coin and honest-verifier?

I am sorry that maybe I misunderstood some related definitions. Could anyone help me with this question?

In this setting, can we regard the verifier as an honest verifier, since he always replies with a random message (rather than a message depends on previous messages)?

No. In a public coin protocol the honest verifier will always send random coins as their messages.
A malicious verifier is under no obligation to do so.
They can choose whichever message makes the simulator's life the hardest.

Imagine some public coin zero-knowledge proof protocol where the length of verifier messages is at least linear in the security parameter. We can modify this protocol so that the prover does something stupid (say send the witness) in response to a very small number (say just one) of possible verifier messages.

In the honest verifier case this is not an issue because the case only occurs with negligible probability. So the original simulator still works for this modified protocol. I.e., the protocol remains HVZK.
But a malicious verifier can just always choose that one bad message, making simulation impossible without being able to efficiently find witnesses.

So there's no contradiction. [GK'91] only applies to ZK proofs, whereas Schnorr is only an HVZK proof.

Additionally one might note, the language you call $\mathsf{DLOG}$ is not in general a hard language. For any cyclic group $(\mathbb{G},\cdot)$¹ of order $q$ generated by $g \in \mathbb{G}$, the language for which Schnorr is an HVZK proof can be defined as follows:

$$\mathsf{DLOG_{\mathbb{G}}}=\{A\in\mathbb{G}\mid \exists x \in \mathbb{Z}_q: g^x=A\}$$

However, since the group is generated by $g$, this is just a very convoluted way of saying $$\mathsf{DLOG_{\mathbb{G}}}=\mathbb{G}.$$

Thus, if group membership can be decided efficiently for $\mathbb{G}$, then this language is not actually a hard language and it would actually hold that $\mathsf{DLOG_{\mathbb{G}}} \in \mathsf{BPP}$.
In fact in many cases, it's actually true that $\mathsf{DLOG_{\mathbb{G}}} \in \mathsf{P}$. For example in the case of an elliptic curve over a finite field it is trivial to deterministically decide whether a given point $P$ is on the curve or not by just evaluating the curve equation. Similarly in the safe-prime setting it is easy to check group membership.

The interesting part of Schnorr is not usually that it proves the existence of a discrete log, it's that it's also a proof of knowledge.

¹ Written in multiplicative notation as any sane person would.


How can I find the generator of a composite group and $Z_p*$? I was doing some research on elliptic curves. I know how to find the generator of $Z_p$ (this is a prime group). But I came across the term $Z_p*$ (group containing elements that relatively prime to $p$, which is composite obviously).

So I want to know how to find the generator of a composite group. How can I find the "generator" of a "composite group" (group order is composite)? And how can I find the "generator of $Z_p*$" (field with composite elements ranging from $\{1,2,\dots,p-1\}$)?

$\newcommand{\Z}{\mathbb{Z}}$If I have understood your question correctly, your goal is to find a primitive root modulo $p$, also called a generator of $(\Z/p\Z)^\times$, knowing that $p$ is prime.

Do you know the prime factorization of $\phi(p) = p - 1$?  If you don't, this is hard.  If you do, there's at least one common fast case, and there's always a general slow case.

Fast case.  Is $p$ a safe prime—that is, is there another prime $q$ such that $p = 2 q + 1$?  If so, then there are only four possible orders, $\{1,2,q,2q\}$, corresponding, respectively, to the subgroups $\{1\}$, $\{1, -1\}$, the quadratic residues, and the whole group.  Thus to find a generator of $(\Z/p\Z)^\times$ it suffices to find a quadratic nonresidue other than $-1$.

You can use the law of quadratic reciprocity to quickly pick a generator.  For example, if $p \equiv 3 \pmod 8$ or $p = 5$, then $2$ is a quadratic nonresidue and hence a generator; otherwise $p \equiv 7 \pmod 8$, since $p \equiv 3 \pmod 4$ by virtue of being a safe prime above 5, so $-2$ is a quadratic nonresidue and hence a generator.

(Why is this case common?  Often the goal is to find a generator for a Diffie–Hellman group, which over finite fields is always done with a safe prime modulus—although in that case usually one seeks a generator of the order-$q$ subgroup instead, i.e. a quadratic residue other than $-1$.  See, e.g., RFC 2412, Appendix E ‘The Well-Known Groups’.)
Otherwise, general case.  Let $\phi(p) = p - 1 = q_0^{e_0} q_1^{e_1} \cdots q_{k-1}^{e_{k-1}}$ for primes $q_i$.  March through the quadratic nonresidues $x \in (\Z/p\Z)^\times \setminus \{-1\}$, and for each distinct factor $q_i$ of $p - 1$, check whether $$x^{\phi(p)/q_i} \equiv 1 \pmod{p}.$$  If for some $x$ the powers $x^{\phi(p)/q_i}$ are all not congruent to 1 modulo $p$, then you have found an element of maximal order $\phi(p)$ which is therefore a generator.

(It doesn't hurt to test all elements, but you may be able to skip quadratic residues faster than computing the modular exponentiation.)


Encrypt with elliptic curves The last days I was looking for a way to encrypt using ECC, without having to make the program myself. I was sure that someone should have done it for everyone by now.

The best approach I had was with bouncy castle. The bad thing about it, is that I never found a "encrypt" or "decrypt" method. The best thing I could found was a sign method and a verify method. The thing is that I read about hybrid encryption, so I was trying to encrypt something with this method, so the signature isn't enough.

Also I've seen code that uses the Cipher class. But after implementing what it said and the execution failed, I saw at the Cipher class documentation that ECC is not implemented there.

Thanks for the help

While it is possible to encrypt using elliptic curves, typically some form of hybrid encryption is used (for performance reasons or because the algorithm supports only a few bytes of data). Typically an Integrated Encryption Schemes is used.

In these systems, another symmetric (AEAD) algorithm (AES in some modern and strong mode, Chacha+Poly1305, or a symmetric cipher and a MAC) is used to do the encryption, and the asymmetric algorithm is used to do a key agreement (typical in case of ECC) or key exchange (typical in case of RSA).

The key agreement process typically employed is based on Diffie-Hellman key exchange.

If you want an off-the-shelve program to encrypt data using ECC as key agreement, have a look at GPG. Versions beyond 2.1 have support for a handful of curves.

If you want to write a program that uses ECC, you will have to find a library that does ECC DH, or better yet, have a library that does the combination of key exchange and symmetric encryption for you (the so called seal and open operations), like NaCl or libsodium.


Are zkSNARKS practical? I'm considering using zkSNARKS for a project i'm building. I have some questions about the practicality of such algorithms:

Does a standard secure implementation exists?
What is the complexity for the generator, prover, and verifier procedures? What does it depend on?
Is it efficient in practice on normal computers (contrary to say homomorphic encryption, which has polynomial complexity but very inefficient in practice)? What are the results of profiling done on actual implementations?

Proof generation complexity is large but better than previous ideas.
For the verifier the complexity depends linearly on the size of the function the input and the output $O(|f|+|x|+|y|)$ where $y=f(x)$ the computation to be verified for a particular value security of the parameter.
The proof size is constant.

For more details you can check the papers and implementations in http://www.scipr-lab.org. I think it is the best resource on the subject.


What is the complexity of finding SHA-1 collisions? Given the recent news about SHA-1 collisions, what is the complexity of finding a SHA-1 collision?

Marc Steven's HashClash is still detailing about 260. Does the previous complexity still hold?

Yes, according to the technical paper linked from that site:

  the state-of-the-art collision attack on full SHA-1 was presented by Stevens [Ste13b] with an estimated cost of $2^{61}$ calls to the SHA-1 compression function.

They further state:

  Based on experimental data obtained in this new work and the 2013 state-of-the-art collision attack, we can project that a real SHA-1 collision will take between 49 and 78 days on a 512 GPU cluster. Renting the equivalent GPU time on EC2 will cost between 75K US\$ and 120K US\$ and will plausibly take at most a few months.

I would be surprised if no one has a search running in the next couple of months (if not already).


Probabilistic RSA, IND CPA Suppose we have classic RSA scheme. Let $n=pq$, $e$ public, $d$ secret.

Then message(M), not empty(not 0), is encrypted by choosing random $r$ and computing $A=(r^e)^e$ and $B=(Mr)^e$

$(A,B)$ is then cipher text.

Why is this not IND-CPA secure? Have trouble grasping IND-CPA concept.. well concept is clear, but how to prove it?

Given above scheme, my thoughts are, since we are able to feed $M=1$ to oracle, we receive $r^{e^2}$ and $(r^2)^e$, but that thought leeds me absolutely nowhere.

I think i got it.

Query:

Let $m={1,2}$, and query $oracle(m)=(A,B)$

Checking:

Lets compute $s=B^e=(m^er^e)^e=m^{e^2}A$

Lets compute $sA^{-1}=\frac{m^{e^2}r^{e^2}}{r^{e^2}}=m^{e^2}$

if $s=1$ then $m=1$, $m\neq 1$ otherwise

Hopefully logic holds.


Length-preserving all-or-nothing transform Is there any known way to construct a length-preserving all-or-nothing transform?  In other words, a secure all-or-nothing transform where the length of the output is the same as the length of the input.

My thanks to @Ricky Demer for suggesting this question.

Yes.  Any public random permutation should suffice.  (A public random permutation is like a random oracle, except it is a random permutation rather than a random function.)  A public random permutation is automatically length-preserving, and it meets the requirements for an all-or-nothing transform.

And, a public random permutation can be constructed in a number of ways.  The best construction depends upon whether we care more about theoretical concern or engineering concerns.

Theoretical perspective

From a theoretical perspective, the question of how to build a public random permutation has been answered by the following paper, at least for sufficiently long messages:

The Random Oracle Model and the Ideal Cipher Model are Equivalent.   Jean-Sebastien Coron and Jacques Patarin and Yannick Seurin.  CRYPTO 2008.  IACR ePrint 2008/246.

That paper shows that one can construct a public random permutation by using 6 rounds of a Feistel network, using a random oracle for the F function in each round.  They prove that this is secure in the random oracle model.  Replacing the random oracle with a cryptographic hash function then gives a reasonable construction.

Their construction will work as long as the message length is not too short.  If we want a public random permutation on $n$-bit messages, then their construction yields $k$-bit security as long as $n \ge 48 + 34k$.  For instance, if you want a 80-bit security level, their construction is proven secure for $n$-bit messages, as long as $n \ge 2768$ bits (i.e., $\ge 346$ bytes).  Thus, their construction is not useful in practice for short messages, but it is useful for long messages.  Their proof might be conservative, and it is possible that the actual security level is better than what their proof promises (so the scheme can actually be used securely on shorter messages than what I list here), but that's just speculation.

In summary, their construction yields a public random permutation on $n$-bit blocks, which in turn provides a length-preserving all-or-nothing transform on $n$-bit messages.

Engineering perspective

From a practical/engineering perspective, if we don't care about provable security, we can probably take any block cipher $E$ of the desired block width, choose a random key $K_0$, make $K_0$ public, and use $E_{K_0}(\cdot)$ as the all-or-nothing transform.  This is likely secure for typical block cipher constructions, though there is no proof.

From a theoretical perspective this can be shown secure assuming the block cipher can be modelled as an ideal cipher (e.g., it is free of related-key attacks, etc.), though that is a strong assumption that not all block ciphers may satisfy.

If the length $n$ of the message is very short, then we may need to use a special short-block cipher (e.g., with techniques for format-preserving encryption) as our block cipher.


Permutation and modes of operation I'm reading the book "Serious Cryptography A Practical Introduction to Modern Encryption" from Jean-Philippe Aumasson, and in the first chapter, it is written this :

  We can try to abstract out the workings of a cipher, first by identifying its two main components: a permutation and a mode of operation. A permutation is a function that transforms an item (in cryptography, a letter or a group of bits) such that each item has a unique inverse (for example, the Caesar cipher’s three-letter shift). A mode of operation is an algorithm that uses a permutation to process messages of arbitrary size.

But when I search about "mode of operation", I only found "block ciphers" using it.

Do all ciphers (for instance stream ciphers) have modes of operation?

And do all ciphers use permutation?

Thanks !

if a cipher operates on fixed length blocks it has to be a permutation by definition since a one to one function is automatically a permutation on the finite domain $\{0,1\}^n.$

This gives the Electronic Codebook Mode, which uses a key to choose which pseudorandom permutation to use, but it leaks information, so modes of operation were invented for block ciphers, to stop equal messages resulting in equal ciphertexts.

Stream ciphers are not permutations in general. Stream ciphers don't have modes of operation in general.

Permutations play a significant role in asymmetric ciphers as well, and the discrete log map over the multiplicative group $Z_{p}^{\ast}$, for example,  is a permutation.


Limit AES-256 to Alphanumeric characters Is there a way to limit the output of AES-256 to only alphanumeric characters and maintain 256-bit key?
I'm looking encrypting some data and use the encrypted data in a system, and the reason behind using Alphanumeric characters is that the system might have issues processing special characters.

The standard way to do this is known as "ASCII armoring".

The idea is that, on encryption, you have the crypto (AES in your case) generate the ciphertext in binary, and then you convert that binary into the character set that is appropriate to you; you can convert it into hexadecimal, you can encode it into Base64, or you can use a more aggressive encoding with a larger character set.

Then, on decryption, you would take the ciphertext you receive, and convert it back into binary, and then hand that back to your decrypt for the rest of the decryption.

This procedure does make the ciphertext longer; doubling the size of you use hexadecimal; 33% longer if you use Base64; somewhat less if you use a more aggressive encoding.  However, it can be shown that this cannot weaken the cryptography.


How does this formula work $(aG + bG) = (a + b) G$ in ECDSA? Please explain how does this formula $(aG + bG) = (a + b) G$ work in ECDSA?

According to the source:

$a$ and $b$ are different private keys

Suppose

$a = 3$

$b = 4$

then the public key is $Q = aG$ and $W = bG$ (secp256k1)

Q = F9308A019258C31049344F85F89D5229B531C845836F99B08601F113BCE036F9

W = E493DBF1C10D80F3581E4904930B1404CC6C13900EE0758474FA94ABE8C4CD13

Now we take the formula $(a + b)G$

$(3 + 4)G$

$7g$

$c = 7$

public key $P = cG$

P = 5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

Now take the formula $(aG + bG)$

$(Q + W)$

And the amount of public keys $(Q + W)$ will be

DDC465F353664403A152988A8BA8662FC6EEFEEEE3076EF93B2A2732D56EC2CB

Why it turns out:

DDC465F353664403A152988A8BA8662FC6EEFEEEE3076EF93B2A2732D56EC2CB

Why is the answer of this sum not this value:

5CBDF0646E5DB4EAA398F365F2EA7A0E3D419B7E0330E39CE92BDDEDCAC4F9BC

..how does this formula $(aG+bG) = (a+b)G$ work in ECDSA?

Perfectly well. It follows from the definition of $kG$ as $\overbrace{G+\cdots+G}^{k\text{ times}}$, associativity and commutativity of point addition. Notice that operator $+$ in $(aG+bG)$ and $G+\cdots+G$ is elliptic curve point addition, while operator $+$ in $(a+b)$ is addition in $\Bbb Z$ (signed integers) or $\Bbb Z_n$ (integers modulo $n$, where $n$ is the order of $G$).

Be confident that $3G+4G=7G$ holds, and if $Q=3G$, $W=4G$, $P=7G$ then $Q+W=P$.
The issue is on what arguments the point addition of the final $+$ is computed.

In the question, what's shown after Q = is the X coordinate $Q_x$ of point $Q$. The Y coordinate is missing. Therefore what follows Q = does not settle between two points: $Q$ of coordinates $(Q_x,Q_y)$ and $-Q$ of coordinates $(Q_x,Q'_y)$ with $(Q_y)^2=(Q_x)^3+7\bmod p$ (per the equation of secp256k1) and $Q'_y=p-Q_y$. Same issue for $W$ and $P$.

  Why is the answer of this sum not this value (..)

This value ended up being the X coordinate for $Q-W$ (or equivalently $-Q+W$) instead of $Q+W$ as thought, due to the above. This also is the X coordinate for the base point $G$, because $Q-W=3G-4G=(3-4)G=(-1)G=-G$.


How many bits of hash are realistically needed for key verification? Say I'm connecting to a web server secured with TLS but with a self-signed certificate. Accordingly, I call the owners of the server and ask them what SHA1 fingerprint they have.

They start reading out the hex digits to me and I follow along, but before reaching the end, I just say "That's fine thanks, no need to read the rest." as I click the OK button.

How far along is the point where its reasonable to stop checking and still remain practically secure?

I recommend stopping after 20 hex digits, i.e., 80 bits.  That should be enough for security.  Suppose you connect to no more than 128 different servers with self-signed certificates, for which you will use this verification procedure.  Then it would take an adversary $2^{80}/128 \approx 2^{73}$ steps of computation to fool you, which is beyond what is feasible given the current state of technology.

I would not recommend 40 hex digits, i.e., 160 bits.  That offers needlessly poor usability.  If there's one thing we've learned about usable security, it is this: If it's not usable, it won't be secure either.  That's because people will find excuses to avoid the security advice, or to completely evade your security mechanism, or skip the verification step.  Or, they'll be tempted to communicate in the clear and skip the crypto and they'll make up rationalizations for it ("oh, this conversation isn't very secret", "oh, just this once", "what are the odds someone is listening in?", "I'll use coded references and it'll probably be OK"), and historically speaking, that tends to turn out badly.

As @CodesInChaos correctly states, collision attacks are not an issue here, so you don't need to double the number of bits you check.  Therefore, there is no need to check 160 bits.  Instead, as @CodesInChaos explains, this is a multi-target pre-image problem.  In general, if you want to force the attacker to perform $2^b$ steps of operation, and if you connect to $n$ different servers that use self-signed certificates that you verify in this way, then you should verify $b + \lg n$ bits of the hash.  I would suggest using a value of $b$ somewhere in the range 64..80; $b=80$ should be more than sufficient (a conservative choice), and $b=64$ is probably adequate.

I checked my SSH ~/.ssh/known_hosts file, which records all of the SSH hosts I've connected to in the past decade or so.  I found about 117 different hostnames, corresponding to $n=79$ different public keys (sometimes one host has two slightly different hostnames).  So taking $n=128$ seems like a pretty reasonable, conservative choice.

Note that you're not going to get perfect security through this mechanism.  All you need to do is make the MITM attack expensive.  In real life, rather than spending millions of dollars to find a matching public key through some expensive computation, it is more likely that the bad guy will attack some other weaker point in your system (e.g., exploit a zero-day in your software or in the server's software; bribe or impersonate the owner of the server; etc.).  Therefore, realistically, 18 hex digits (72 bits; i.e., 65 bits of security, assuming you connect to no more than 128 such servers) is probably enough to ensure that the crypto is not the weakest link in the system, if you want to cut it fine.  But 20 hex digits gives you a little bit of a margin for error.

If you want to optimize this to the max, you could use a slow hash function (e.g., bcrypt, PBKDF2), which might slightly reduce the number of digits you need to verify.  For instance, if you use 4096 iterations of hashing, you can probably reduce the number of hash digits to check by 3 hex digits (since $4096=2^{12}$, and 12 bits = 3 hex digits).  Also, if your hashing procedure hashed both the public key and the domain name (rather than just the public key), you could eliminate the opportunity for multi-target attacks, reducing the number of bits you need to verify from $b+\lg n$ to $b$ bits (e.g., reducing the number of bits to verify by about 7 bits, or about 2 hex digits).  You could also look at Paŭlo Ebermann♦'s suggestions for how to encode the hash in a way that makes it easier to compare hashes.  For instance, a sequence of words may be easier to verify than a sequence of hex digits, particularly if the dictionary is chosen appropriately.


16 bit (2 byte) Digital Signature I'm developing an experimental Amateur Radio digital protocol for over-the-air data exchange.  A part of any protocol over fallible transport layers is of course some kind of error control (ECC, FEC, CRC, etc).  My original intention was to use a simple 16 bit CRC to checksum each individual packet.

An additional concern is the potential spoofing of packets.  With a simple CRC this is pretty trivial, as the protocol and implementation will be open-source, it would be easy to construct packets that appear to be from any station.

The protocol may also be used over error-free transport layers as well, in which case the CRC, used purely for error checking, would become redundant.

What I'd like to explore is replacing a simple 16-bit CRC with what amounts to a digital signature.  Thus it would serve the purpose of providing at least 16-bit quality CRC, along with a unique CRC that cannot be trivially generated to spoof packets from a station.

I realize that, cryptographically speaking, a signature as small as 16 bits can be easily brute forced. However, similarly, a 16-bit CRC also has a fairly high probability of collisions.  Unfortunately that is the limitation when dealing with data transfer at rates as potentially low as 300 baud, and typically at 1200 - 9600 baud.  There is no luxury to transmit large signatures and checksums.

For critical information, such as an OTA software update, that data would be properly signed using standard methods with appropriate length bit lengths.  Of course the higher level data can also be signed as well.  My question is pertaining to the lower-levels of data exchange at the individual packet level, and adding at least some level of anti-spoofing that would also serve the same purpose as basic CRC.

The public and private keys can be pretty much any size, as the public keys would only need to be exchanged once for each pair of stations that wish to communicate.  It is the individual packet signing I would like recommendations on.

Note that the entire payload cannot be encrypted, as that would be in violation of FCC regulations for Amateur Radio.

A method such as encrypting just the CRC using an asymmetrical encryption would not suffice, because not all packets are intended for consumption by a single station. Beacons and other broadcast packets are intended to be received by all listening stations. So encrypting the CRC so it can only be decoded by a single receiving station would only solve the issue for direct station-to-station communication and not more generally.

TLDR: Can't do.

16-bit is simply not enough for digital signature, which requires many times more bits¹, and can't be checked if truncated (becoming useless).

One may want to consider a Message Authentication Code, such as HMAC with SHA-256. At least, that's cryptographically better than an encrypted CRC². But there must be a shared secret between sender and receiver(s), thus that's not usable in the question's stated context.

If one absolutely needs public-key verification, the only option that I see is signing a group of earlier packets in a special signature packet (or group of signature packets), as the question proposes for "critical information". Problem is that losing a single packet prevents verification of the signature.

¹ To attain even mild security (80-bit), the most compact signature schemes around require about 224 bits (or 160 for a BLS scheme once used but now thought quite vulnerable), for something that is added to data renaming in clear; or down to 64 bits if you accept that about 1200 bits of the payload remains scrambled until cryptographic verification (even though only the public key is involved for the unscrambling, it's very debatable that the later meets the requirement of non-encryption in amateur radio).

² It is trivial to alter a message without changing the CRC, thus the encrypted CRC.


Is container format relevant to security of encrypted message inside? Still trying to design a fully binary cryptography container format for my mobile app, I am here asking if container is ever relevant.

Thanks to Apple, I cannot use GPG directly because I can neither call GPG through GPGME (fork(2) is not allowed) nor embed it (license conflicts)

The container format is simple ar(1) format that store its contents in plaintext, probably then compressed with some algorithm like Gzip. I am wondering if the container format affects the security of the already encrypted data, the MAC and IV that is held as separate entities within.

The plan is to use AES-CTR (or AES-CFB, or AES-OFB, or my homebrew cipher SHA512-HMAC-OFB which turned out to be just as fast as AES thanks to its larger block size) to encrypt the data and put it in the archive file (data.obj in the archive), its initialization vector in plain (iv.bin), asymmetrically encrypted symmetric key (key.bin, if relevant), the SHA512-HMAC of the archive in "check archive" form that is described below (mac.bin) and some metadata (algorithms used, compression of plaintext used, probably a user supplied tag in plain text) in plain (info.json)

EDIT

ar(1) format stores file name (up to 16 characters), owner UID/GID, modification time, file mode (permissions) in its file header.

MAC (or signature) is calculated on a "check archive": every entity except the MAC (or signature) itself are in the check archive, which is also in ar(1) format, sorted in binary order based on their file names, retaining all their properties (name, owner, modification date and file mode).

Converting the comments to an answer…

Ricky Demer:

  "algorithms used" should be stored with the key(s).  "compression of plaintext used, probably a user supplied tag" should go into the MAC.

Maxthon Chan:

  That is, algorithm should not appear in the container at all, and everything that is not MAC itself should be included in MAC?

Ricky Demer:

  Yes. Also note that compression may be problematic.

Maxthon Chan:

  I forgot the asymmetrically encrypted symmetric key may appear in the file as well as key.bin. How to deal with that?

Ricky Demer:

  If you're using public keys too, then you should probably use digital signatures, possibly instead of a MAC.


Is there an easy way to calculate "d" in the RSA algorithm? Quite frankly, it is a pain to use the Extended Euclidean Algorithm to calculate d (the private exponent) in RSA. The equation used to find d is:

$$ e  d \equiv1~(\mathrm{mod}~ \varphi(n)).$$

Does anyone have a way to solve for d using basic algebra or something simpler? If not, can someone explain how to use the Extended Euclidean Algorithm to find d?

The easiest way which is widely known to calculate a modular inverse is finding the smallest $k\in\mathbb N$ such that the following expression is an integral integer:

$$\frac{1+k\cdot \varphi}{e}$$

If this is an integral integer, it is the inverse of $e$ modulo $\varphi$ and thus $d$ and you'll find it with at most $e$ tries.

The issue obviously know is that the run-time of this will grow linearly with the size of $e$, as opposed to the extended euclidean algorithm (EEA) which will run in time proportional to (a power of) the logarithm of $e$, which will especially be much faster than the above method when $e$ is chosen as large as the modulus. If you want to see examples and how-tos on the algorithm, Wikipedia is your friend as usual.


Is the salt value a secret or can it be stored in cleartext just like the IV? From Wikipedia I read that the IV is used to randomise the mapping of cleartext to cipher text and that the IV is usually stored (in cleartext) together with the encrypted record. (http://en.wikipedia.org/wiki/Initialization_vector)

However if I look at a specific implementation in C# when deriving the key using Rfc2898DeriveBytes, a salt value is required and I understand the need of the salt.
But obviously I will need the salt later on the regenerate the key from my secret passphrase.
Does that imply that the salt itself is not a secret and can be stored together with the encrypted record in cleartext, just like the IV?

string passphrase = "Hello World, I'm the secret!";
string salt = "13245678";

var deriveBytes = new Rfc2898DeriveBytes(passphrase, Encoding.UTF8.GetBytes(salt), 50000);

using (var rijndael = new RijndaelManaged())
{
    rijndael.KeySize = 256;
    rijndael.Key = deriveBytes.GetBytes ( rijndael.KeySize / 8 );
    rijndael.IV = deriveBytes.GetBytes ( rijndael.BlockSize / 8 );

...
}

The salt can be kept public.

All that matters is that the salt is available for you to use when it comes to re-deriving your password from some input guess.

In many ways, a salt performs the same function that an IV does for ciphers.

You can read more about salt and password hashing here.


What are the subsequent inputs to the DES key schedule after round 1? I've just been studying the DES crypto algorithm as presented by Christof Paar in his book entitled, Understanding Cryptography as well as his lecture. There is a diagram on page 68 of the text where the key schedule is shown and I understand the following information about it already:

A 64 bit "key" is originally input
That 64 bit key has 8 bits removed from it during the Permuted Choice 1 permutation, making it now a 56 bit key.
The 56 bits output from PC-1 are now split into two subsections, $C_0$ and $D_0$ , each of which are 28 bits.
$C_0$ and $D_0$ each have their respective 28 bits rotated left once if the round is 1,2,9, or 16, otherwise their respective bits are rotated left by 2 bits.
** After the above occurs, the permuted 56 bits gets processed by the Permuted Choice 2 permutation and the output is a 48 bit round key. **

I highlighted item #5 here because this is where my confusion lies and the precursor to my question: Once we have a round key, $k_1$ for example, it is obviously then placed into the $f$ function as input along with the $R_i$. However, after this round completes, the round key $K_i$ is 48 bits but the key schedule transforms appear to take a 56 bit input. Can someone please explain how we get from a round key such as $k_2$ (the subkey for round 2 of the algorithm) to round key $k_3$? Is the original key re-used again for each round transformation or is the previous rounds key used?

As you already correctly observed, to get $k_1$, you rotate $C_0$ and $D_0$ left to obtain $C_1$ and $D_1$ and apply PC-2 to $C_1$ and $D_1$.

To get $k_2$, you simply rotate $C_1$ and $D_1$ left to obtain $C_2$ and $D_2$ and apply PC-2. To get $k_3$, you rotate $C_2$ and $D_2$ left to obtain $C_3$ and $D_3$ and apply PC-2. This continues until $k_{16}$. Also see Figure 3 in the Wikipedia article on DES for a graphical illustration. The round keys $k_1, \dots, k_{16}$ are then used in the round function of the respective round.


TLS 1.2 Server Key Exchange problem Below the Wireshark snapshot of the handshake compliant to the TLS 1.2.
The position 1 displays the enum ServerECDHParams where I can use any curve having the own ID RFC8422. I'm free for example to use Edwards, Brainpool or NIST curves having an ID assigned by IANA.
Please correct me when I'm wrong but at the position 2 I have to provide the value from the enum SignatureScheme which defines not only the signature algorithm (ECDSA in this case) but also the hash and the curve.
What value should I then use if the ECDSA certificate contains a signed public key based on for example brainpoolP256?
The migration to TLS1.3 is not an option because the task was to extend the proprietary legacy server side TLS1.2 stack implementation to use the ECC.
Not using of brainpool is also not an option as this is a customer requirement.
Full specification of the domain parameters in the Server Key Exchage is hardly supported by any embedded TLS 1.2 client.
Thank you in advance

You're wrong. This is a difference between TLS 1.2 and 1.3.
In 1.2 SignatureAndHashAlgorithm identifies only the algorithm (not curve) and hash. In 1.3 SignatureScheme does identify the curve for ECDSA, and the certificate OID for RSA-PSS. See the next to last para on page 44:

[1.3] ECDSA signature schemes align with TLS 1.2's ECDSA hash/signature
pairs.  However, the old semantics did not constrain the signing
curve.  If TLS 1.2 is negotiated, implementations MUST be prepared
to accept a signature that uses any curve that they advertised in
the "supported_groups" extension.

(although in 1.2 and lower before RFC7919, that extension was elliptic_curves not supported_groups!)
Wireshark is showing both decodes: the single, combined SignatureScheme name for 1.3, and the separate hash+signature names for 1.2, and only the latter apply in your case. This is arguably a bug: some other places this field occurs it could be ambiguous whether to use the 1.2 or 1.3 interpretation, but ServerKX can (occur and) contain this field only in 1.2 so it should have the 1.2 interpretation.
And the brainpool curves are designed so that standard (X9.62) ECDSA works with them. Edwards curves as such cannot, but (IINM) they can be converted to Weierstrass curves which can.


Timing Side Channel on error-correcting code This question may be a basic question but it is not clear to me at the moment.

I have an Error Correcting Code (ECC) in a key-encapsulation scheme designed for post-quantum cryptography which operates on secret data.

The ECC I am using is constant time as long as the number of errors which need to be corrected is constant, and as long as those errors occur at the same positions in the message. The runtime does not depend on the secret data itself, only on the #errors and their positions in the secret data.

Does this leak any useful information? The # of errors which occur is not always constant in a real scenario...

This may indeed leak information. If we can induce data dependent errors. If an attacker can induce a bit flip it won't help him, but it is actually more likely he could induce bits to be set by generating relevant interference.

If a bit was 1 to begin with the extra interference won't make it any more 1, but if it was 0 to begin with? setting it to 1 would be an error which needs correcting and you may be able to time this.
Just in general trying to create more set bits seems like a practical attack and with the timing of the ECC would allow at least (over repeated attempts) to assess the number of set bits.

A more complicated attack on which bit is set would require a great degree of control on the errors. Need much more information on the complete setup in order to confidently rule this out, but it seems more far fetched.


How can two parties offline generate a sequence of corresponding key pairs that are still sufficiently random I'm looking to design a protocol between two parties A and B to generate sequence of RSA private keys $p_{a_0}, p_{a_1}, ... p_{a_k}$  and a sequence of corresponding RSA public keys $P_{b_0}, P_{b_1} ... P_{b_k}$.
with the property that $P_{b_k}$ is the corresponding public key of private key $p_{a_k}$. But there is a twist:
$A,B$ will share an initial secret. After this point $A$ will generate its private keys ,and $B$ will generate JUST the public keys and $B$ should have NO way of knowing what $A's$ private keys are. So $B$ should be able to offline generate public keys without knowing what they're private keys are but the protocol should ensure that $A$ ends up with correspoing private keys to $B$'s public key sequence.
The use case is in an "eventually-compromised" system that is $A,B$ initially can share information freely but at some point their computers/networks become infected at which point they shut down and operate in a purely offline manner for a while. During this time I want them to be able to create documents/digitally sign/verify digital signatures of each other despite the inability to communicate and possibility of discovering that some of their keys have been compromised.

If RSA is not a requirement, here's a potential solution that uses ECC.
A generates a key-pair, $p_0, P_0$. A and B share a secret $s$ and the public key $P_0$. To move to the next key-pair, A multiplies the private key by $s$ and B multiplies the public key by $s$, so that the key-pair is $p_n = s^np_0, P_n = s^nP_0$ at step $n$.


What are the pros and cons of SIP media encryption types SRTP, ZRTP, and DTLS? I'm just getting used to SIP for my first time using Linphone. Which encryption is better and why? My Settings > Network > Media Encryption has the options of SRTP, ZRTP, and DTLS.

I hope to keep this as simple as I can. I'll begin with some terms:

To establish any kind of SIP call, you first need to talk to the SIP server and well, initialize a session.
The call itself happens over a media stream, which may or may not be encrypted and may or may not be proxied by the SIP server depending on what was negotiated and the presence or absence of NAT.

The terms in your dashboard are actually confusing, as you'll see. To secure that media stream you need to exchange a key of some kind and work out if you trust each other and SRTP does not specify how to do this.

One way and the way I have seen used most often is SDES. I suspect what your interface is describing as "SRTP" is in fact "SIP and negotiating keys with SDES and encrypting with SRTP".

Needless to say, to exchange a key using this (simple) mechanism you absolutely have to be talking SIPS (or SIP over TLS). If you are not, or any part of the SIP chain is not, you are in trouble. You are likewise exposed to all drawbacks of TLS in establishing trust (you are reliant on PKI, which you may or may not regard as a good thing).

DTLS is actually DTLS-SRTP. This is another way to negotiate keys but rather than use an extension to SIP to do it, SIP simply indicates the media stream uses DTLS-SRTP and key negotiation happens in the media stream. Key negotiation happens as in TLS and thus relies on PKI.

ZRTP is the same idea and also happens in the media stream, except that rather than rely on TLS for the establishment of keys, Diffie-Hellman key agreement takes place and key verification is done by verifying "fingerprints" in the form of short strings. You can think of this as the voice equivalent of OTR.

Now let us introduce a major gotcha in SRTP - there is a NULL cipher which can be negotiated for "no crypto please" much like the NULL cipher in TLS.

Which to use then. On initial setup, all require you to trust your SIP server to negotiate the call successfully. Thereafter ZRTP will detect any MITM, whereas DTLS versus SDES will not. Of the the other two I would say that DTLS is more secure, since theoretically with key pinning and trust-on-first-use, you could achieve a similar guarantee to ZRTP (and the question of "which is better" becomes "do you trust certificate authorities". You could also potentially use a private PKI with DTLS). In addition, with DTLS, an attacker must compromise both the SIP server to redirect the SRTP stream and provide certificates the peers trust; this may or may not be easy. SDES as described exchanges keys via SIP, which must be entirely trusted.

I would generally say that ZRTP > DTLS > SDES given expected implementations, but the devil is in the detail. For example, can you key pin? Does your software tell you if the NULL cipher is in use? Can you configure your software not to negotiate it?

However, things get more complicated when realities arise. With many VOIP providers you are reliant on their SIP proxies to establish your communication and they may not negotiate the protocol you want. Moreover, media streams can be proxied especially if you are behind NAT and some VOIP software may not understand ZRTP. To this end FreeSwitch has a dedicated option for ZRTP passthru.

So to summarize, it really depends on what is available and what you can negotiate. However, all three result in your media stream being protected by SRTP, which uses AES in counter mode, with truncated HMACSHA1 in Encrypt-then-Mac mode over the packet header including index. The gotcha is that integrity protection might not be used. With the least truncated HMAC for integrity protection I think this would count as "not terrible" but also perhaps not the best.

In short, I would say that:

ZRTP may be the best choice for small environments or maybe even large ones if the verification step is taken seriously.
DTLS-SRTP may be a good choice if you configure all devices to trust only a well controlled CA you own. This however means calling out is difficult. If you generally trust CAs, this is a good choice.
SRTP+SDES requires you definitely trust the SIP server, but if you do then this is OK.

In all cases you need to be sure you are talking to the correct SIP server and doing so securely, especially and critically for the first communication.


Why must the sender and receiver be synchronised in synchronous stream ciphers? I would like to know why the sender and receiver must be synchronized in synchronous stream ciphers as said in synchronous stream cipher. Why is there no synchronization between the sender and receiver in asynchronous stream ciphers?

I'm thinking that a plain text is first encrypted and then decrypted. I can't get how encryption and decryption are done at the same time. Is this synchronization done in block ciphers too?

With a synchronous stream cipher (Sync SC), the stream is generated from the internal state, which is built from the key, and depending on the algorithm, a nonce. As the algorithm goes through its steps, the state is changed, and new stream bits are generated. If you want go get to the 11560th bit of stream, you have to start at bit 1 and go through all steps until you get the state at the right point for the bits you want, you cannot just get there in a single step.

Most Sync SCs have a large internal state built from the key, which is processed in some way defined by the algorithm, of which a small bit is exported as the stream. The processing and export is repeated to generate more stream bits.

The asynchronous stream cipher (Async SC) allows you to get there in a single step, or sometimes a little more than 1 depending on the algorithm. CTR mode on a block cipher is an example of an asynchronous, or seekable stream cipher. You use the key, the nonce, and the block number you want, and it generates the stream for that block. Salsa and ChaCha are built using a type of counter mode. CTR mode on a block cipher only requires a single encryption operation to generate any single block, regardless of its position in the stream, and only needs to change the block counter to get there.

In terms of getting the sender and receiver synchronized, with the Async SC you only need to know which block or bit you are on, and you are synchronized. The Sync SC requires the sender and receiver to both generate stream bits until they get to the same point, then they must make sure they do not get out of sync. Depending on the protocol and type of data, they may need to start at the beginning.  If using a Sync SC in a real time communications protocol, that can be a showstopper.

Some Async SCs may need some of the prior stream bits as input, which requires successful decryption of some of the prior data. An example of an Async SC that needs prior stream bits is a hash function that hashes the last output. This is not used in practice because it is not secure, but it is useful as an example.

Block ciphers also need some sort of synchronization, but that is mode dependent. Some modes turn the block cipher into a stream cipher, as referenced above in CTR mode. Some require only the prior block to sync, such as CBC mode. Any block cipher mode will need to keep the block alignment in sync.


What algorithm for AES key wrapping to choose in an embedded environment In an embedded environment, what AES key wrap algorithm is best, in terms of performance and security coverage?

We are using RSA PKI asymmetric encryption.

AES with ECB and CBC mode

AES-ECB could well directly leak information, especially if it is used over multiple keys. The start of the private values within an encoded key are likely not precisely on a block boundary, so looking for repetition of blocks may for instance indicate that a key contains a smaller private exponent value than other keys. This will not likely leak enough information for a break, but telling auditors that parts of the key may be leaked is not recommended.

AES-CBC can be used, but it doesn't offer any integrity protection. Furthermore, it is vulnerable to padding oracle attacks and will directly leak data if the IV is predictable (distinguishable from random by an attacker). You may directly leak information about the RSA components if the IV is set to a static value for the same reason as for AES-ECB. Both will require some kind of padding, and a description on how to unpad (PKCS#11 often simply uses the encoding of the RSA key itself for that). This makes it perfectly valid to use zero padding.

Unfortunately many HSM's use ECB or CBC with a zero based IV to wrap keys. I'm not sure that those cryptographers were thinking at the time. Not recommended.

The AES-KW mode

AES-KW seems to be mainly concerned with symmetric keys and will probably not be very efficient for RSA keys. It requires input that is a multiple of the block size so just like ECB and CBC it will require padding. Otherwise it will be more secure than ECB and CBC. Still, AES-KW is probably not a good idea.

The AES-(GCM-)SIV mode

Static IV or SIV mode was specifically created with unique input messages in mind. As each RSA private key is (or should be) different from the next, SIV mode is especially useful for key wrapping; it is one of the stated goals for SIV.

Most cryptographers here will probably choose AES in SIV mode for encryption. This mode does expand the wrapped key compared to an unwrapped key, but it doesn't require an IV, and it protects the integrity of the key to boot. It also doesn't require padding, so that the expansion is just the authentication tag size (which doubles as the static-IV).

AES-GCM-SIV is a useful, fast alternative to SIV mode. It is probably a good idea to keep the authentication tag / IV size to 128 bits, especially when using GCM mode. Probably you don't need the GCM speedup for RSA key encryption, so normal SIV mode might be a better choice, if available.

One thing that slightly irks me is that the SIV is usually placed in front of the wrapped key. This makes in-place encryption impossible. However, the mode is just as secure if you place the SIV at the end (but that breaks compatibility with the description).

Unfortunately, I think that the order of availability is the exact reverse to the security provided by the various modes.


Is it possible to figure out whether a plain TCP packet is (aes) encrypted or not? I captured some plain TCP packets (not HTTP) which are not using HTTPS.

I am wondering whether these packets are using AES 256 (or 128) or not.

Is there a way to do that?

Thanks

Without knowing anything about the application layer protocol on top of TCP, it's very hard to answer this question.

A good symmetric cipher (like AES) will produce uniformly random bytes. So if the data in the packet looks uniform, there's a very good chance it's been encrypted. You won't be able to distinguish between different algorithms, though, and you probably won't be able to distinguish between different modes of operation.

Your best bet is to figure out the application protocol being used, and look at the corresponding messages establishing the connection.