Mixing x into permutation through XOR vs. modular addition

Either operation works as long as one operand (or both) is unpredictable and the two operands are (practically) statistically independent. Normally XOR is used because it requires fewer transistors and less time than modular addition in hardware based implementations.

In software both operations run in one cycle for data that fits a register size. This gives addition an advantage over plain XOR operations. Differences in inputs to the steps of the permutation propagate faster with additions because carry bits influence the probability that an output bit may change.

ChaCha is primarily meant to be used in software implementations on machines with native support for 32-bit modular addition. Replacing the final additions with XORs is very unlikely to effect security, so the choice may be arbitrary.


Yes, you a right; also after running the GF(128)/GCM multiplication test I confirm that the product of the test values is

0x0388DACE60B6A392F328C2B971B2FE78 $\times$ 0x66E94BD4EF8A2C3B884CFA59CA342B2E = 0x5E2EC746917062882C85B0685353DEB7


How to factor an RSA256 public key with YAFU?

There are various ways of doing this. Let's assume you're using Python.

Start by installing PyCrypto. This includes a lot of useful tools.
You need to convert the raw base64 string into a readable RSA key file. This is easily done:

-----BEGIN PUBLIC KEY-----
MDwwDQYJKoZIhvcNAQEBBQADKwAwKAIhAIl47p5SrV3uMTsUAbwE0E+j+QynAY/C
Vq/Gf8IAOQy7AgMBAAE=
-----END PUBLIC KEY-----

Save this to a file called, for example, rsa256.pub.
Import this key into Python and extract the values of $n$ and $e$:

from Crypto.PublicKey import RSA
key = RSA.importKey(open('rsa256.pub').read())
print key.n, key.e

Now factorize $n$. YAFU sounds perfect for the job. (I use msieve, which also works well.) On a decent computer, it should only take a few minutes to break a 256-bit modulus. This will give you two factors. Call the larger one $p$ and the smaller one $q$.
Back in Python, you need to run a bit of code to calculate the decryption exponent $d$. You should then have sufficient information to generate a private key:

def egcd(a, b):
    """Extended Euclidean algorithm"""
    """https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm"""
    x,y,u,v = 0,1,1,0
    while a != 0:
        q, r = b // a, b % a
        m, n = x - u * q, y - v * q
        b,a,x,y,u,v = a,r,u,v,m,n
    return b, x, y

def modinv(e, m):
    """Modular multiplicative inverse"""
    """https://en.wikipedia.org/wiki/Modular_multiplicative_inverse"""
    g, x, y = egcd(e, m)
    if g != 1:
        return None
    else:
        return x % m

def pqe2rsa(p, q, e):
    """Generate an RSA private key from p, q and e"""
    from Crypto.PublicKey import RSA
    n = p * q
    phi = (p - 1) * (q - 1)
    d = modinv(e, phi)
    key_params = (long(n), long(e), long(d), long(p), long(q))
    priv_key = RSA.construct(key_params)
    print priv_key.exportKey()

Call pqe2rsa() with the values of $p$ and $q$ from step 4 and the value of $e$ from step 3, and you should get a private key.


What does $\text{PK}=\text{pk}\oplus\text{H}(\text{opk})$ represent in this paper?

Reading section III A of the paper (caveat, I've not read the whole paper), it looks like the construction has been generalised so that $H$ maps to the abelian group where the public key operations take place. As such the $\oplus$ operation generalises to the abelian group operation. This notation is unwelcome, but I think in previous work the abelian group in question did combine with XOR.
In the RSA case it would appear that the operation is multiplication modulo $N$ and the hash function maps to $\mathbb Z/N\mathbb Z$.


How to prove that a one way function is uninvertible?

Your $f$ is not uninvertible in your definition. If $f(a,b) = 0$ just output $x' = (0,0)$ and if $f(a,b) = 1$ output $x'=(1,1)$. This is a very efficient algorithm that outputs an $x'$ such that $f(a,b) = f(x')$.

The point is that there is a notion in maths of an invertible function, in general: this means that for any image of $f$ there is a unique point that maps to it. A one-way function is such a function, with the extra addition, that you cannot efficiently compute this unique preimage. Your $f(a,b) = a \land b$ is also not one-way, because there are 3 pairs that map to $0$.

$f$ being not uninvertible does not imply it's invertible in this sense.

Concretely: cryptographers hope/assume that a cryptographic hash function is uninvertible (this is why we store hashes of passwords).
Also, that RSA is one-way: an encryption has a unique decryption, but it's not efficiently computable without the private key (a so-called trapdoor).

That a one-way function is uninvertible is clear from the definitions (write down your definition of one-way function: it should be immediate; if not, edit your question adding that definition).


I think it will most likely scale out of bounds with 100 multiplications.
Even with quite large polynomial modulus degree with small scale goes out of bounds with tens of multiplications.


What is meant by the probability distribution of a verifier?

A probability distribution is how the verifier's knowledge of the unknown value is summarised. This idea is usually easier to grasp for Bayesian statisticians than classical ones.
Suppose that the unknown value $x$ is just a $n$-bit string, a verifier might start out with no information about $x$ and thinks all $2^n$ possible values are equally likely: a uniform probability distribution on $2^n$ values. After an interaction with the prover, the verifier might say "I now know that $x$ is not one of these $k$ values" and their knowledge could be summarised as a uniform distribution on $2^n-k$ values. Or they might say "I now know that $x$ has even Hamming weight", giving a uniform distribution on $2^{n-1}$. They might say that "I am now 90% sure that $x$ has even Hamming weight" and give a two-valued histogram distribution with probability $1.8/2^{n}$ on even Hamming weight values and $0.2/2^n$ on odd Hamming weight values. They might even say "I think that interpreted as an integer $x$ is (truncated) Poisson distributed with mean $\mu$". All of these are different types of knowledge that the verifier might infer about $x$ based on their interactions with the prover.
The important thing about a zero-knowledge proof is that whatever the verifier infers from their interactions with the prover, they could generate the same information and inferences on their own.


Schnorr signatures: multisignature support

Here is a simple-minded Ed25519-based multisignature or collective signature scheme, in which Alice and Bob each having their own private key, kept secret from one another, must work together to create a joint signature that a verifier knowing both of their public keys, or only a joint public key, can verify.  This is a simplification of a recent IETF internet-draft, draft-ford-cfrg-cosi, presently under consideration by the CFRG.

$\newcommand{\F}{\mathbb{F}}\newcommand{\Z}{\mathbb{Z}}\newcommand{\concat}{\mathop{\Vert}}\newcommand{\U}[1]{\underline{#1}}$Let $p = 2^{255} - 19$, a prime; let $E$ be the elliptic curve $$-x^2 + y^2 = 1 - \frac{121665}{121666} x^2 y^2$$ over $\F_p$ (edwards25519, the twisted Edwards curve birationally equivalent to Curve25519 used in the Ed25519 signature scheme); let $P$ be the unique $\F_p$-rational point on $E$ whose $x$ coordinate is 4/5 and whose $y$ coordinate is ‘positive’, and let $\ell$ be its order; let $H$ be a uniform random choice of function from byte strings to $\Z/\ell\Z$; let $\U Q$ be some byte string encoding of a point $Q \in E(\F_p)$.

To begin, Alice picks a secret scalar $a \in \Z/\ell\Z$ and a secret 32-byte hash key $h_a$, and shares the encoding of the point $A = [a]P$.  Bob does likewise with $b$, $h_b$, and $B$.  Their joint public key the encoding of is $A + B$.

An Alice/Bob signature on a message $m$ is the encoding of a point $R \in E(\F_p)$ and a scalar $s \in \Z/\ell\Z$ such that $$[s]P = R + [H(\U R\concat \U{A+B}\concat m)](A + B).$$

How do Alice and Bob create such a beast?  First, Alice computes $r_a = H(h_a\concat u_a \concat m)$ where $u_a$ is an independent uniform random 32-byte string, and keeps $r_a$ secret but shares $R_a = [r_a]P$; Bob does similarly with $r_b$ and $R_b$.  Then they each compute $R = R_a + R_b$.  Next, Alice computes $$s_a = r_a + H(\U R\concat \U{A+B}\concat m)\,a,$$ and Bob computes $s_b$ similarly.  Finally, to commit the signature creation, they jointly compute $s = s_a + s_b$ and reveal $R$ and $s$.

This is an Alice/Bob signature, because

\begin{align*}
  [s]P &= [s_a + s_b]P \\
       &= [r_a + r_b + H(\U R\concat \U{A+B}\concat m)\,(a + b)]P \\
       &= [r_a]P + [r_b]P + [H(\U R\concat \U{A+B}\concat m)][a + b]P \\
       &= R_a + R_b + [H(\U R\concat \U{A+B}\concat m)]([a]P + [b]P) \\
       &= R + [H(\U R\concat \U{A+B}\concat m)](A + B).
\end{align*}

Unlike a naive concatenation of two Ed25519 signatures which takes a net 128 bytes of storage, an Alice/Bob signature takes only 64 bytes of storage, and that remains so no matter how many additional signers you add.  Conveniently, the resulting Alice/Bob signature is also an Ed25519 signature under the public key $\U{A+B}$, so you can use existing Ed25519 verifiers to verify it.

(Security analysis is left as an exercise for the reader.  Hints: Suppose evil Bob knows Alice's public key $A$ before the two of them collectively
publish the joint key $P$.  What nefarious deed can Bob commit in that case?  If Alice's random number generator is wedged when she makes a signature so it returns the same $u_a$ each time, how can Bob exploit that to do something nefarious with Alice?)

This scheme has various properties:

Each party's part of the signature was generated by a different private key not known to the other parties.
All parties must agree to make the signature before it will be accepted by a verifier.  We could easily extend the definition of a signature to include a list of the signers, and have a verifier require some threshold of signers before accepting it, at the cost of a little extra space to store a signature (as in draft-ford-cfrg-cosi).
If we adapted it thus to a threshold scheme, the subset of possible signers who did sign it would not be anonymous to a verifier.

There are variations on the theme of multisignatures: are the signers anonymous to one another, are there thresholds, if there are thresholds is the subset of possible signers who did sign revealed to a verifier?  You'll have to look closely at exactly what Bitcoin's scheme is to see which properties it provides.  For further background, you might read Micali, Ohta, and Reyzin's paper introducing Schnorr multisignatures, or Bellare and Neven's elaboration on it.


Advanced Access Content System (AACS) and Subset Difference techniques for Broadcast Encryption

There is no "public" key in AACS (at least, no in the part which uses SDR).

Each movie is symmetrically encrypted with a movie-specific key, and stored as is on the disc. All copies of a given movie use the same key; indeed, all copies of a disc are bit-to-bit identical (it would not be economically sound to do otherwise). Two distinct movies, however, use distinct keys.

From that point, the problem of giving access to the movies to all "allowed" players (and only to them) is reduced to the problem of giving them access to the movie encryption key. A movie encryption key is small (a few dozen bits), an encrypted movie is huge (several gigabytes); presumably, keys will be easier to handle. On the disc, physically, there is only one instance of the movie itself.

Each player has its own key. So one model is the following: the disk contains the movie, encrypted with the movie key $M$, and a complete set of $E_P(M)$ (movie key $M$ encrypted with player key $P$). Each player would decrypt "his" $E_P(M)$ to retrieve $M$ and decrypt the movie. If, at some point, a given player key $P$ is detected to have been leaked (e.g. there is some downloadable software which uses that key to decrypt movies), then the movie editors just have to stop including $E_P(M)$ for that key $P$ in the discs they press (we would say that the offending key is revoked).

Now, the problem with that model is that there are billions of player keys (for all the current and future players, because we want disks sold now to be playable on systems which will be built next year) so the total size of all these $E_P(M)$ would exceed the disk capacity (it would need several dozen of gigabytes, more than the movie itself). So the tree-like structures come into play. The player keys all come from a giant tree structure. The needed size on each disc is in $O(\log n) + O(r)$ where $n$ is the number of player keys in circulation (including future keys) and $r$ is the number of revoked keys. This is small enough for existing discs (in particular Blu-ray discs, which use AACS) as long as there are not too many revoked keys (the hope is that revocation will remain a rare occurrence).


Is there any protocol, that given $E(m)$ can compute homomorphic $E(m \bmod p)?$

If there were a way to perform that operation (for any $p>1$ relatively prime to $N$) without the Pallier private key being involved, then you have just shown that Pallier is Fully Homomorphic; that is, you can homomorphicly implement any computation; at the very least, by doing homomophic circuit evalutation.

One approach to show this is to implement a NAND function, which we can do as follows:

$$\textit{NAND}(x, y) = 1 + p^{-1} \cdot ( \lambda(x + y) \bmod p - \lambda(x+y))$$

where:

All the operations are done homomorphically, for example, $x + y$ means the homomorphic addition of $x$ and $y$
$\lambda$ is an integer $p > \lambda \ge p/2$
$p^{-1}$ is the multiplicative inverse of $p$ modulo $N$

All the computations included in the NAND definition are additions, subtractions, multiplications by the constants $\lambda$ and $p^{-1}$ (all of which can be performed homomorphicly within Pallier), and the $\bmod p$ operation, which we are assuming also can be performed homomorphicly.

And, if we evaluate NAND (assuming that $x, y$ are constrained to be either 0 or 1, we find that if either $x, y$ are encrypted 0 (or both are), NAND evaluated to encrypted 1; if both are 1, it evaluates to an encrypted 0.

And, NAND is known to be complete; we can construct any circuit be a sufficiently large pile of them.  That is, we can design a circuit to evaluate our function (e.g. SHA-3), and then give as inputs as a series of encrypted 0's and 1's, and get the output as a series of encrypted 0's and 1's.


If you need a MAC, use a MAC. For example, HMAC which uses a hash function. Don't try to use a random hash function in your own scheme, because some such schemes are not secure.

  Reason to use/not use this data as input to the hash? (In the context of authenticity of data…)

If you do have a secure MAC, any constant data will not affect the authenticity. Two different inputs will have completely different and unforgeable MACs even if they are known to differ in only e.g. one bit.

  Impact on the "strength" of the hash function – can this constant help attacker to find out the source data of the hash function? (Help him do some smart brute force or something.)

Known constant data will not make it any weaker than if the data was not there. In the case of a hash function (not MAC) it could slightly improve a brute force search of two hashes if you knew they shared a long enough prefix... but as long as the data is unpredictable enough that shouldn't matter, and in the case of keyed MACs there is no such advantage.


If I understand the question right, what you are looking for is a fair secret sharing protocol. Most secret sharing protocols are unfair. For example, in 3-out-of-4 secret sharing with 2 dishonest parties, once one honest party broadcasts their share, the two dishonest parties can privately collude to reconstruct the secret. Then if they refuse to participate, the 2 honest parties cannot reconstruct the secret.

Fairness is described as "if there is a player getting the secret in the recovery phase, then each player participating to the reconstruction process does too" [1]. That reference proposes such a protocol and you can find a number of others by looking at the references in that paper.


Generating Diffie-Hellman parameters efficiently

The standard solution is to generate $g$ and $p$ once during application development, then hardcode $g$ and $p$ in your code.  There are standard choices for $p$ and $g$, e.g., documented by NIST in their FIPS series.  I suggest using one of those.  There is no need to re-generate $g$ or $p$ each time.  You can use the same $g$ and $p$ for everyone.  See also Is it safer to generate your own Diffie-Hellman primes or to use those defined in RFC 3526? for more details in this vein.

And make sure you use larger parameters.  For security, I recommend that the prime $p$ should be at least 2048 bits long, and $g$ should generate a subgroup of size at least $2^{128}$ (or generate the whole group).

ECDHE will provide even better performance than Diffie-Hellman, but you can try the above first.  Hardcoding the parameters should already make a huge difference.


The format they are proposing for the key seems to be some sort of bit-packed array. First, with 6 bits, there are 64 possible values (0-63). Now, imagine you have replacement rules (your key) like these:

0 -> 17
1 -> 43
2 -> 12
...
63 -> 8

Which means: when encrypting, replace all occurrences of the value 0 with 17, all 1s with 43, etc. These values may correspond to letters, but that is not necessary at this point. As the numbers on the left side of the mapping table are sequential, an alternative form of writing this key would be $17,43,12,...,8$. This could easily be transformed into the more verbose initial version. Each number in the list takes 6 bits to represent (since it must also be $<64$), and there are 64 of them, so total bits to store the key is $64*6=384$.
In a way, this key size is deceiving. Key of size $l$ bits normally implies that there are $2^l$ possibilities for the key. Here, you were right to use factorials. There are only $64!\approx 2^{296}$ possible keys. To understand why this is true, think about what happens if the key is sent, but the last 6-bit number is left off. We can figure out which one it is just by seeing which value hasn't been used yet. Even if the last two 6-bit numbers are left off, there are only two possibilities for the key ($a,b$ or $b,a$). So clearly, sending 384 bits means that we are sending more than we strictly need.
The 6-bit character code is just one possible way to convert these 6-bit numbers the algorithm uses into characters that are useful for humans.


Using Hadamard Form of a Matrix in the Block Cipher

This is evident. Let $B$ be a $2^n \times 2^n$ matrix. We have:

  $$a_{i\oplus (j+2^{n-1})}=a_{(2^{n-1}+i)\oplus j},a_{i\oplus j}=a_{(2^{n-1}+i)\oplus (2^{n-1}+j)}.$$

So, $B$ has the following form and therefore is a Hadamard matrix as follows
$$B=
\left(
\begin{array}{cc}
U & V \\
V & U
\end{array}
\right)_{2^n\times 2^n}\, $$


It is well defined.
The hash function has no impact on whether HMAC is defined for a null string text argument. As long as HMAC is defined for a particular hash function, the resulting HMAC of a null string text argument should also be well defined.
The definition of HMAC according to FIPS 190-1 is:
$HMAC(K, text) = H((K_0 \oplus opad)|| H((K_0 \oplus ipad) || text))$
If $text$ is the empty string the right hand side simply collapses to
$H((K_0 \oplus opad)|| H(K_0 \oplus ipad))$
which is well defined.
The hash function used has no impact on the existence of the null HMAC.


Have I understood pedersen commitment correctly?

Yes, $p$, $g$ and $h$ are system parameters. $g$ and $h$ only need to generate large prime subgroups of $\mathbb{F}_p^{*}$, and the equation $p=2g+1$ is not required. (In fact, if I understand what you mean correctly, it does not always suffice as $-1/2$ has the same order as $2$)

It is important that $g$ and $h$ not be related by a known equation of the form $g=h^k$, because in that case the commitment is easily forgeable. One solution is to fix $g$ and $h$ to be small integers, and verify they have large prime order modulo some prime $p$.


Definition of one-way functions: randomly-chosen point vs every point

The reason you are looking at a random choice of $x$ is that, otherwise, there is no probability space any longer. Put differently, if we require that for every x there should not be an algorithm that given an image $f(x)$ can output a preimage, we have a problem, because there is such an algorithm. For every $x$ consider the algorithm $M_x$ that on any input simply outputs $x$. Thus, we have just defined for every $x$ an algorithm that (on input $f(x)$) inverts the function.


Ring Signatures: Why is the combination function easy to solve?

I think I might have a potential solution, anyone care to confirm this? Let's take an example with 5 public keys (including ours). Let's assume our $s = 3$.

Let's borrow from that previous Stack Overflow post. Let's define a left var as

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

and we know that

$$ z = r = E(E(l \oplus y_4) \oplus y_5))$$

Now let's start decrypting $z$:

$$D(z) = E(l \oplus y_4) \oplus y_5$$
$$D(z) \oplus y_5 = E(l \oplus y_4)$$
$$D(D(z) \oplus y_5) = l \oplus y_4$$
$$D(D(z) \oplus y_5) \oplus y_4 = l$$

We've solved for $l$! Solving for $y_s = y_3$ is easy now:

$$l = E(E(E(v \oplus y_1) \oplus y_2) \oplus y_3 )$$

$$D(l) = E(E(v \oplus y_1) \oplus y_2) \oplus y_3$$

$$D(l) \oplus E(E(v \oplus y_1) \oplus y_2) = y_3$$

And then we just do $g^{-1}(y_3)=x_3$, giving us our full signature.


TCG design specification of TPM and nonce creation

In cryptography, $n$ is frequently used to point to some specific number.

The statement

  The creation of all nonce values MUST use the next $n$ bits from the TPM RNG.

simply clarifies that all nonce values have to be generated using the TPM RNG, by using/extracting the next $n$ number of bits from that RNG. Maybe it helps to think of “$n$ bits” as “x number of bits”, where “x” is the amount specified in the paper.

So, if a paper explains that (for example) a “nonce size is 64 bits” and later states you have to extract the next $n$ bits from some function or RNG to initialize that nonce, $n$ would be 64. Taking this example, the line you’ve stumbled upon would mean: “The creation of all nonce values MUST use the next 64 bits from the TPM RNG.”

But please note that that‘s merely an example. If a paper would point to 32 bits, or 128 bits, or whatever other number of bits, $n$ would have to be interpreted as another number/count/amount accordingly. Also note that we are talking about bits in this specific case and paper. Other papers might as well use $n$ to mention “$n$ bytes” or other units (eg: “$n$ rounds of encryption”).


Verification of encryption for ElGamal cryptosystem

Actually, an ElGamal ciphertext $(a,b)$ is "valid" iff $(a,b) \in G^2$,  because for any message $m\in G$ and any $\mathsf{pk}\in G$, the encryption of $m$ will be in $G^2$, because for any $r$, $(g^r,\mathsf{pk}^r\cdot m)\in G^2$, and any $(a,b)$ chosen in $G^2$ can be correctly decrypted by any secret key by computing $m=\frac{b}{a^\mathsf{sk}}$. The proof of knowledge of the random coin $r$ is sufficient to show that you know how the ciphertext was produced.

I do not know if that answers your problem.


Why are elliptic curves over a field of characteristic 2 or 3 insecure?

There is no known subexponential-cost algorithm for computing discrete logs in elliptic curves over fields of small characteristic—barring standard generic algorithms on groups of smooth order, transfers to $\operatorname{GF}(2^n)$, etc.—but there seems to be exploitable structure that just hasn't been worked out yet.  The most recent survey seems to be from 2015:

  Stephen D. Galbraith and Pierrick Gaudry, ‘Recent progress on the elliptic curve discrete logarithm problem’, IACR Cryptology ePrint Archive: Report 2015/1022, 2015-10-22.

See in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18.


What are some approaches to attack an triple key polyalphabetic cipher when the IV key and PT key are known?

I can't comment yet and have no solution, but I still wanted to post my own analysis and hope it'll get you a bit further. BTW, the site you linked to with the info about Quagmire IV is mine and yes, sorry about the ads! I haven't updated it in many, many years, so I was surprised to see it pop up :)

The first thing to do is try to find plausible candidates for letters in the keyword. I'm absolutely assuming the CT key was produced in the same way the PT keyword was, i.e. a keyed alphabet and not a completely random one. The latter case will require hill-climbing algorithms and is not in scope at this time.

From the crib I could deduce:

P and R are 3 letters apart (2 between them). Since in the regular alphabet there's only one between them, I think both are used in the keyword. PxxR. If you put the R in front, the P ends up at the back of the alphabet and this is unlikely, since that would require almost every letter after the P in a regular alphabet to have been used in the keyword.
I and X are 13 letters apart. I think the I is not part of the keyword, because if you put the I at the front somewhere the X is totally out of place somewhere in the middle and it could only be the 11th, 12th or 13th letter in the keyword and I assume the keyword is shorter.
However, the X may be part of the keyword, since the I ends up near its original location when the X is put at the front, but this requires that at least 5 letters that normally come after the I appear in the keyword, plus one extra letter for every position that X moves to the back. This makes it more likely that the X is the first or second letter in the keyword, than any other.
The M and S are 10 letters apart, where normally they are only 6 letters apart. This implies that either one of them was used in the keyword. Both are possible, since the other letter would end up reasonably close to their original positions in the alphabet. If the M was used, it is most likely one of the last letters in the keyword; if the S was used it is likely one of the first three or four.
The A and F are 24 letters apart, as opposed to the original 5 letters. From this it is highly unlikely that the A alone was used, since that would leave the F way at back of the alphabet. Either both were used in the order of FxA, with one letter between them, or the F alone was used as the second to last letter of the keyword and the A is the beginning of the padding.

Putting this all together, I believe the keyword definitely contains P??R, S or M, and F?A, not necessarily in that order. It may contain an X at the beginning as well.


Shamir Secret Sharing and Diffie-Hellman procedure

This protocol is insecure because the original Diffie-Hellman method can be exploited by man-in-the-middle attacks.

For this reason, you should never use Diffie-Hellman alone.


Why are logic gates assigned integers when checking QAP in zkSNARK algo?

Assigning "coordinates" (integers) to arithmetic gates is a way of combining multiple verification equations into a single one by Lagrange interpolation, and then testing that single equation at a random point. Choosing that point at random effectively results in random weights for original equations in the combination. This point could be compared to challenge of Schnorr protocol. For the statement cited, resulting polynomial is representing all the gates in the circuit.


For many signature schemes, having two signatures using the same randomness for two different hash values allows recovery of the private key. This is used in many security proofs by showing that an adversary that forges a valid signature can be coerced through replaying into producing two signatures of this form. As a consequence, an forger can be twisted into a key recovery attack.

The technical question is how can you make sure that the forger is going to comply to our expectations and really forge two signatures for the same randomness. Indeed, in general, nothing forces the adversary to use its randomness in a simple way. In particular, giving him the same coins and forcing changes the messages is not going to achieve the desired goal, because the adversary is allowed to mix the messages themselves into the randomness used for signing.

The key idea is to restart the adversary with the same randomness let it run without change until it generates the message $M_0$ that was signed in the first run together with its rzndomness and then force a change on the rest of the run. At this point, in a practical setting, you could imagine using a fault attack on the hash function. However, in a theoretical model, the change is achieved by changing the responses of the random oracle that models the hash function on the first query that involves $M_0$ and all subsequent queries.

When you do that, you already know the behavior of the adversary until $M_0$ is generated and hope that it will forge again on $M_0$ with the same randomness but a different hash value. This is where the forking lemma comes into play (for a general version, see Multi-signatures in the plain public-key model and a general forking lemma by Bellare and Neven http://cseweb.ucsd.edu/~mihir/papers/multisignatures-ccs.pdf). In this general version, it is a technical lemma that analyzes the behavior of an adversary that receives some random values (each taken uniformely from at set of $h$ elements) and outputs a pair of values $(J,\sigma)$ with $0\leq J\leq q$ when several runs with inputs sharing a common prefix are performed. Note that when $J=0$, the adversary is considered to fail. The result of the forking lemma is that the probability of getting two related runs with the same value of $J$ and a common prefix of length $J-1$ is not too small. More precisely, if $acc$ denotes the probability of success of an adversary on a random input and $frk$ the probability of getting two related runs as above then:
$$
frk\geq acc\cdot \left(\frac{acc}{q}-\frac{1}{h}\right).
$$

The proof given by Bellare and Neven is not too hard to follow and I would recommend reading it.


If the KGC gets compromised it will break security, so why should a KGC generate private keys.

Certificateless crypto tries to overcome the problem which exists in identity based crypto, i.e., that the KCG generates all the private keys of the users (that is necessary in IBE, see below) and thus knows all the private keys of users (which in turn enables the KCG to decrypt all the ciphertexts intended to it's users). Certificateless crypto is similar to IBE (thus requires a KCG), but does not reveal the entire private key to the KCG.

However, if the KCG in certificateless crypto gets compromised, then you have a problem which also exists with certification authorities (CAs) in public key crypto. In particular, someone who gets the private key of the KCG in certificateless crypto or of the CA in context of public key crypto can incorporate all users he would like to. Essentially, due to fact that he can issue "fake" keys on behalf of users and pretending that they are authentic keys. However, in IBE a compromise is much more devastating than in certificateless crypto or public key crypto, since in the latter two cases the adversary may only issue new "fake" keys but is not able to regenerate all the previous keys as it is the case with IBE (which allows him to decrypt all the previous ciphertexts intended to registered users).

  Will it be possible that user will generate pair of public and private keys and for authenticity of public key only, we will use some trusted center?

That is the case in public key crypto (but as said above, that will not help against a compromised CA which certifies the keys) and in part the case with certificateless crypto.

If we do not assume a compromise of the CA/KCG but that the KCG works as it is supposed to work, then one can subsume the three different concepts as follows. I'll try to give you the big picture and hope it helps you to understand the idea of certificateless public key cryptography.

We have three basic approaches in the field of public key cryptography:

In traditional public key cryptography, a user $A$ generates a private/public key pair $(sk_A,pk_A)$ locally and since this key pair has absolutely no indication to which indentity (user $A$) it belongs, it is necessary to certify the public key, i.e., bind the public key $pk_A$ to the user $A$'s identity. This is commonly done by letting some trusted authority, a certification authority (CA), sign $pk_A$ with additional identifying information of user $A$ after user $A$ proves by some means that he really is user $A$ (the result is what is called a certificate). To encrypt some message for users you have to obtain an authentic public key of the CA and for every user.
Identity-based cryptography aims at letting the users public key be its identity (e.g., the email address) and so to remove the requirement for certificates. In ID based cryptography a user $A$ uses his identity (e.g., his email address) as public key. Now, however, since this identity could be used by anybody to compute the respective private key, it is clear, that there needs to be some other entity involved in generating the respective private key (To see the requirement for such an entity, think of the fact that I could use your email to compute a private key for your identity otherwise). We require a trusted authority (the KCG) owning some secret master key to compute the private key $sk_A$ that corresponds to the public identity string $ID_A$ and this trusted authority has to check whether $ID_A$ (e.g., the email address) indeed corresponds to $A$ and then issues the private key $sk_A$ corresponding to the identity $ID_A$. The advantage is, that you only need the parameters (corresponding to the master secret) of the KCG in an authentic fashion but no longer any authentic key of the users. Now, however, the KCG knows your private key and may use this private key to decrypt your messages, so it needs to be fully trusted. That's an inherent problem of identity based cryptography, although one may implement multiple KCGs (each having a share of the master secret) who compute the private keys for identities in a distributed fashion, so that neither gets to know the entire private key of a user. But it is questionable if this is really practical.
Certificateless public key cryptography is inbetween these two approaches. It aims to get rid of the problem that the KCG gets to know the entire  private keys of all users. Having said that, in this approach the KCG only computes a partial private key of user $A$ based on the identity $ID_A$ (clearly, also here user $A$ has to prove by some means that $ID_A$ is associated to him) and the user then combines this partial private key with some secret information (only known to him). Consequently, the KCG no longer gets to know the entire private keys of the users. Then a user, however, needs to take the parameters of the KCG and needs to combine the user chosen secret with this parameter to obtain an additional user public key. So, to encrypt a message for a user the identity string plus this public key is required. The advantage here, however, is that this public key does no longer need to be certified, since it contains the identity $ID_A$ of user $A$ and if the KCG is trusted (and the parameters of the KCG are authentic) one can assume that the user associated to $ID_A$ really corresponds to $A$ and holds the corresponding private key.


Google is using RC4, but isn't RC4 considered unsafe?

Academically speaking, RC4 is terrible; it has easy distinguishers ("easy" means "can really be demonstrated in lab conditions"). It is also hard to use properly. However, SSL/TLS uses RC4 correctly, and in practice the shortcomings of RC4 have no real importance.

The power-that-be at Google decided to switch to RC4 by default because of the recent "BEAST" attack, which demonstrates (again, in lab conditions) a compromise of a Paypal cookie. There is no such dramatic demonstration for an attack on RC4 as used in SSL, so it was estimated that using AES-CBC with SSL/TLS 1.0 was "more risky" than using RC4.

The academically "right thing" to do would be to use AES-CBC with TLS 1.1 (or any ulterior version), which has no problem with BEAST and none of the RC4-related weaknesses either. However, Google makes money in the real world, and, as such, they cannot enforce a configuration which would prevent a third of their user base from connecting.


(12:15) gp > p=15860584089531798358308118294328202587;
(12:15) gp > y=6361196924231058595008858273263807320;
(12:15) gp > x=znlog(Mod(y,p),Mod(5,p))
11473769387225613271575199155876761324
(12:17) gp > ##
  ***   last result computed in 1min, 26,253 ms.
(12:17) gp > Mod(5,p)^x == Mod(y,p)
1
(12:17) gp >
firas@wakaba ~ % cat /proc/cpuinfo |grep 'model name'
model name      : Intel(R) Core(TM) i5-3330 CPU @ 3.00GHz

From the documentation:

  This function uses

  a combination of generic discrete log algorithms (see below).
  in $(\mathbb Z/N\mathbb Z)^*$ when $N$ is prime: a linear sieve index calculus method, suitable for $N < 10^{50}$, say, is used for large prime divisors of the order.

  The generic discrete log algorithms are:

  Pohlig-Hellman algorithm, to reduce to groups of prime order $q$, where $q \mid p-1$ and $p$ is an odd prime divisor of $N$,
  Shanks baby-step/giant-step ($q < 2^{32}$ is small),
  Pollard rho method ($q > 2^{32}$).


Ad hoc…

What you’re describing is not much different from the encryption in storage systems… only that your “storage system” is a file (foo.txt) instead of a hard drive. Now, in a perfect world you would encrypt every block of data (that you store in foo.txt) with its own key, but that would be pretty impractical in your situation. From my point of view, the most obvious solution would be to use a “tweakable cipher” or a “tweakable narrow-block encryption mode”. They were designed to avoid (read: work around the problem) the “need separate key per stored data block”.

Therefore, and relying on your description, I’ld most probably opt-in for a “tweakable narrow-block encryption mode” like LRW (paper), XEX (paper), or XTS. An example representing one of the more frequently used implementations would be AES-XTS. Depending on your coding skills, it shouldn’t be all too hard to incorporate such a solution into the CRUD functionalities of your application.

But, it depends on the details…

For the sake of completeness, let me mention that there are other options out there, which might also lead to a valuable solution. I merely mentioned what I personally would tend to use, based on the information you provided. But choosing a fitting solution will strongly depend on things like the kind of data you want to store, how it’s formatted, what security level you expect, what specific scenario is to be assumed, etc. (Always check for potential attack vectors!) You will have to assess and verify all the little details to be able to choose a most optimal solution that perfectly fits your individual situation and needs.

One of many examples: If the filesize and available hardware capabilities permit it, you might be better off handling encryption/decryption on the whole file (using AES-CBC or something like that) instead of crypting the individual data-blocks you plan to create, read, update and delete. On the other hand, if we’re talking about a file that is bound to hold hundreds of thousands of individual data blocks/entries, and which therefore is bound to grow up to and beyond several gigabytes in filesize, loading that beast into system memory to wrangle with contained data will tend to be a bit… (let’s just call it) “non-optimal”.


How can I show RSA-OAEP is not IND-CCA secure if G always outputs 0 (i.e. there is no hash function)?

$b$ is random

Yes, but it is random in the set $\{0,1\}$. $b$ reflects the coin toss made by the decryption oracle / challenger in the IND-CCA game to decide if s/he encrypts $m_0$ or $m_1$ at the second bullet.

  Does $m_b \in \{b\mathbin\|m_1,\ b\mathbin\|m_2\}$ ?

No in general, and that holds even if we fix the indices to be in $\{0,1\}$ rather than $\{1,2\}$. The intended meaning of $m_b$ is:
$$m_b=\begin{cases}m_0&\text{if }b=0\\m_1&\text{if }b=1\\\end{cases}$$
otherwise said, $b=0\implies m_b=m_0$, and $b=1\implies m_b=m_1$. Thus $m_b \in \{m_0, m_1\}$ with no concatenation involved. Note: the IND-CCA game allows to choose the two messages $m_0$ and $m_1$ equal, but that's a silly move.


How many bits can be safely extracted from the BBS generator at each step?

The direct answer to your question is in Koblitz and Menezes (Indocrypt 2006).
They pointed out that, for practical parameters, one can produce only $1$ bit per iteration if one wants provable security. See Section 6 of the paper for the detail.

Additional note:
if you can change the assumption from the hardness of integer factoring, then you can produce more and more.
I found an example in Steinfeld, Pieprzyk, and Wang “On the Provable Security of an Efficient RSA-Based Pseudorandom Generator” (ASIACRYPT 2006).


How can encryption software accept password lengths which are not one of the AES key lengths?

I imagine that Truecrypt uses a KDF, to derive a 128/192/256-bit key from your password.  This is standard practice.  It's unadvisable to use a password directly, as they're generally low-entropy (predictable), and too short (as you've noted).


Chain several RSA encryptions without increasing the message size

In this scenario, you don't need to do any padding (except for the first encryption).

If what you're encrypting with RSA is a random number between 0 and the modulus size, then you don't need any padding.  Padding is there to prevent the attacker from using the multiplicative properties of RSA to derive one plaintext from a bunch of others; this attack involves finding smooth plaintexts.  When a plaintext is a random number from the full range, this is unlikely to ever happen, and so we don't need to worry about it.

Note that, unless the original message (D0) is also a random number between 0 and N-1, you'll want to pad that.

In addition, in the decrypt direction, doing multiple decryptions can be done far more efficiently than applying each decryption in succession; you could actually apply (say) 1,000,000 successive decryptions almost as efficiently as you can do one.

On the other hand, it is not at all clear what you hope to gain from this procedure.  What is the problem you are solving?


If by "using them on a second device such as a PC running Windows" you mean that you open Whatsapp web there, then no you cannot decrypt your messages there.

Whatsapp web is a client that connects to your phone (usually using whatsapp servers as proxy).

The client has shared keys with the phone (you scanned them as QR code) and the phone uses this to encrypt the already (on the phone) decrypted messages.

+----------------------------------+                     +----------------------------------------+
|                                  |                     |                                        |
|                                  +--------------------->                                        |
|    Whatsapp Web Client           |     encrypted       |         Whatsapp Servers               |
|                                  <---------------------+                                        |
|     shared key with phone        |                     |                                        |
+----------------------------------+                     +---+---------------------^--------------+
                                                             |                     |
                                                             |                     |
                                                             |                     |
                                                             |                     |
+-----------------------------------+                        |                     |
|         encryption secret keys    |                        |                     |
|                                   <------------------------+                     |
|                                   |                                              |
|      Your phone                   |         encrypted                            |
|                                   |                                              |
|      shared key with web client   +----------------------------------------------+
+-----------------------------------+

Basically the Web client is just a GUI for your phone client, connected (securely) over the web.

You can try the following: Turn off your phone while using whatsapp web. You will see, that you cannot send and receive messages anymore.


Calculating $\mathbb F_{p^2}$-rational points of an elliptic curve defined over $\mathbb F_p$

The general case is that of field extension. Given a field $\mathbb{F}_q$ of $q$ elements (in your case, the field is $\mathbb{Z}_p$, the integers modulo a prime $p$), you want to define and do computations in a field $\mathbb{F}_{q^k}$ of $q^k$ elements for some integer $k > 1$. To do so, one first considers $\mathbb{F}_q[X]$ which is the ring of polynomials with coefficients in $\mathbb{F}_q$: a polynomial is the formal sum:
$$ A = \sum_{i=0}^{\infty} a_i X^i $$
for some values $a_i$ (the "coefficients") in the field $\mathbb{F_q}$, such that only a finite number of $a_i$ are distinct from $0$. The degree of the polynomial is the integer $n$ such that $a_n \neq 0$ but $a_i = 0$ for all $i > n$.

Polynomials can be added together, and multiplied together, in the natural way. If we define:
\begin{eqnarray}
A &=& \sum_{i=0}^{\infty} a_i X^i \\
B &=& \sum_{i=0}^{\infty} b_i X^i \\
\end{eqnarray}
then the sum of $A$ and $B$ is:
$$ A + B = \sum_{i=0}^{\infty} (a_i+b_i) X^i $$
and the product is:
$$ AB = \sum_{i=0}^{\infty} \left(\sum_{j=0}^{i} a_j b_{i-j}\right) X^i $$

There is a well-defined Euclidian division of polynomials: given polynomials $A$ and $B$, with $B$ being non-zero (the "zero polynomial" is the polynomial whose coefficients are all equal to zero), then there exist unique polynomial $Q$ and $R$ such that $A = BQ + R$, and the degree of $R$ is strictly less than the degree of $B$. (For this definition to work, we formally define the zero polynomial to have degree $-1$.)

If we can compute additions and multiplications, and we have an Euclidian division, then we can define a modulo operation: "$A$ modulo $B$" is the value $R$ in the equation $A = BQ + R$.

Now let's choose an polynomial $M$ of degree $k$ in $\mathbb{F}_q[X]$. To make things simpler, we choose a unitary polynomial, i.e. such that its highest non-zero coefficient $m_k = 1$. We then define $\mathbb{F}_{q^k}$ to be the quotient of $\mathbb{F}_q[X]$ by $M$: this is the set of polynomials of degree strictly less than $k$, and all operations (additions and multiplications) are taken modulo $M$. In other words, when adding and multiplying polynomials, we do as described above, with the additional rule that $M$ is zero, i.e.
$$ X^k = \sum_{i=0}^{k-1} -m_i X^i $$

This defines a ring. The beauty of the construction is that IF the polynomial $M$ is irreducible in $\mathbb{F}_q[X]$ (meaning that there exists no polynomials $U$ and $V$ of degree strictly greater than $1$ and strictly lower than $k$ such that $M = UV$), then that ring is a field. Another additional (and unobvious) property is that the choice of $M$ does not actually matters much, in that all fields $\mathbb{F}_{q^k}$ are isomorphic to each other, i.e. they describe the same inner structure. This is why we may talk of "the" field $\mathbb{F}_{q^k}$.

The field $\mathbb{F}_{q^k}$ is called the field extension of $\mathbb{F}_q$ of degree $k$. We formally map elements of $\mathbb{F}_q$ to the polynomials of degree $0$ in $\mathbb{F}_{q^k}$, which allows us to say that $\mathbb{F}_q$ is a subset of $\mathbb{F}_{q^k}$.

In your specific case, let's see what the above becomes. Your base field $\mathbb{F}_q$ is $\mathbb{Z}_p$, the integers modulo a prime integer $p$. You want a field extension of degree $2$, so you need an irreducible polynomial $M$ of degree $2$. To make computations easier, you would prefer $M$ to be as "simple" as possible, i.e.:
$$ M = X^2 + \alpha $$
with $\alpha$ chosen such that multiplications by $\alpha$ are easy. You also need $M$ to be irreducible (since you want a field), which here means that $-\alpha$ must NOT admit any square root in $\mathbb{Z}_p$. A very common choice here is to choose $p$ such that $p = 3 \pmod 4$, because then we can set $\alpha = 1$. If you do that, then $M = X^2 + 1$. In application of the rules above, this defines $\mathbb{F}_{p^2}$ to consist in polynomials $A = a_1X + a_0$ for all values $a_0$ and $a_1$ in $\mathbb{Z}_p$, and the additions and multiplications are done "naturally" with the extra rule that $X^2 = -1$.

If instead of writing $X$ you call it $i$, then you get the same construction as complex numbers $\mathbb{C}$ from real numbers $\mathbb{R}$, and the easy computation rules that @Cryptostatis lists in his answer. There is, notably, a possible extra optimization when implementing:
\begin{eqnarray}
(a_0+ia_1)(b_0+ib_1) &=& (a_0b_0 - a_1b_1) + i(a_0b_1 + a_1b0) \\
&=& (a_0b_0 - a_1b_1) + i((a_0+a_1)(b_0+b_1) - a_0b_0 - a_1b_1)
\end{eqnarray}
That is, the product of two values in $\mathbb{Z}_{p^2}$, with the modulus $M = X^2+1$, can be computed with only three multiplications in $\mathbb{Z}_p$.

For further information on finite fields, and details on the construction of field extensions, the very classic read is A Course in Number Theory and Cryptography by Neal Koblitz.

(From your question, I suppose that you want to dabble in Weil and Tate pairings; thus, you need to be able to navigate through somewhat hairy mathematics, and Koblitz' book is almost a must-read for that. When you master field extensions, proceed with Ben Lynn's PhD thesis, which I found to be a nice read on that subject.)


Is it absurd to estimate entropy from a sample?

Theoretically, you can break down the question of estimating the entropy of a given collection of (assumed to be independent and identically distributed) samples into two steps:

Estimating the distribution of the underlying random variable

Computing that random variable's entropy

Generally you can do the first by "counting". If you see the collection of 4 samples $0, 0, 0, 1$, you can set $\Pr[X = 0] = 3/4$, and $\Pr[X = 1] = 1/4$ (this is generally known as the "empirical distribution"). You can then easily compute the entropy.
Note that the rest of the question has a large caveat, in that you need a source of independent and identically distributed samples to apply it.
If you see $1011$, is this a single sample, or four independent, identically distributed samples?
To answer this you need to think carefully about how the samples are generated, but regardless I'll continue with discussing things assuming you can generate i.i.d. samples.
How accurate the entropy computation is therefore reduces to how close the empirical distribution is to the "true" underlying distribution.
For "large enough" sample sizes, it will converge to the true distribution, but quantifying the rate of convergence becomes important.
There are various ways to do this, a few are summarized in the empirical distribution function wikipedia page.
One particularly useful way to quantify this is via the DKW inequality.
Let $\mathcal{X}$ be the underlying (unknown) distribution, and let $X_1,\dots, X_n$ be $n$ i.i.d. samples from $\mathcal{X}$.
Let $F(x)$ be the cumulative distribution function of $\mathcal{X}$.
We define the empirical cumulative distribution function of the samples $X_1,\dots, X_n$ via:
$$F_n(x) = \frac{1}{n}\sum_{i = 1}^n \mathbf{1}_{X_i \leq x}$$
Here $\mathbf{1}_{X_i \leq x}$ is an "indicator function", which is 1 if $X_i \leq x$, and 0 otherwise.
So $F_n(x)$ counts how many of the $X_i$ are less than $x$ (and then normalizes it to be in $[0,1]$ by dividing by $n$).
The DKW inequality then states that for any $\epsilon > \sqrt{\frac{\ln(2)}{2n}}$:
$$\Pr[|\sup_{x\in \mathbb{R}} (F(x) - F_n(x))| > \epsilon] \leq 2\exp(-2n\epsilon^2)$$
This gives a "Chernoff-like" bound on how far the cumulative distribution function can be from the empirical cumulative distribution function.
After estimating the empirical cumulative distribution function, you can convert this into estimates for the various probabilities.
This is because $p_i = \Pr[X = i] = \Pr[X \leq i] - \Pr[X \leq i-1] = F(i) - F(i-1)\approx F_n(i) - F_n(i-1) \pm 2\epsilon = \tilde{p}_i \pm 2\epsilon$.
More formally, by applying the DKW inequality we will get that $|p_i - \tilde{p}_i| \leq 2\epsilon$ with probability all but $2\exp(2n\epsilon^2)$.
We can then compute the entropy of this:
\begin{align*}
\mathbb{H}[\tilde{X}] &= \sum_{i\in\mathsf{supp}(\tilde{X})} \tilde{p}_i(-\log_2(\tilde{p_i}))\\
&= \sum_{i\in\mathsf{supp}(\tilde{X})} (p_i\pm 2\epsilon)(-\log_2(p_i\pm 2\epsilon))
\end{align*}
From here you could try to bound how close this is to the true entropy.
Unfortunately the only ways I currently see to do it are rather handwavy --- $-\log_2(x)$ is convex so $-\log_2(2(x+y)/2) \leq -1 -\log_2(x)/2 - \log_2(y)/2$, but $\pm\epsilon$ may be negative, so you start running into issues along those lines.
Anyway, you can proceed as you mention, but to get an accurate estimation of the entropy:

You need to be able to "break" your random source into independent and identically distributed samples
You need a large sample size (so the probability an estimate falls outside of the DKW inequality, $2\exp(-2n\epsilon^2)$, is "small").


Can Reed Solomon parity blocks be used as an all-or-nothing transform?

Reed-Solomon codes are Maximum-Distance-Separable codes and thus have the property that in a $[n,k]$ RS code ---- meaning than there are a total of $n$ blocks of which $k$ are data blocks and $n-k$ are parity block ($n=2N$ and $k=N$ in the OP's notation) ---- any $k$ blocks are sufficient to reconstruct the entire codeword, that is, all the blocks can be found if we know $k$ of them. Note that it does not matter whether the $k$ blocks available are a mixture of data and parity blocks or parity blocks only, just as long as $k$ blocks are available.

So, in the scheme envisioned by the OP, if one has a $[2N,N]$ Reed-Solomon code ($N$ data blocks, $N$ parity blocks, for a total of $2N$ blocks) and keeps only the $N$ parity blocks, the $N$ data blocks can be reconstructed. If fewer than $N$ of the parity blocks, then the data blocks cannot be reconstructed in the sense that the decoder can come up with a list of $M$ possible candidates for the $N$ data blocks but cannot say which of the candidates is the correct one.  Here, each of the $M$ candidates on the list is a vector $[D_1, D_2, \ldots, D_N]$
of $N$ data block (each $D_i$ is a data block) and the decoder cannot determine which is the correct vector of $N$ data blocks. What is $M$?  Well, $M$ is the number of possible distinct values that each data block might have and thus is either the number of elements in the finite field over which the Reed-Solomon code is defined, or some power $L$ thereof if each data block is a vector of length $L$ over the finite field (and we are using an interleaved Reed-Solomon code). Either way, $M$ is pretty large.


If classical ciphers are used with compressed plaintext, how much does it make frequency analysis attack harder?

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

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

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

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


Can I use SHAKE-256 on 32-Bit Microcontroller?

SHA512 cannot be really run on a 32bit ARM microcontroller since it uses the 64bit constants,

Sure it can; a 32 bit ARM microcontroller can do the 64 bit additions (by performing the addition in 2 32 bit steps and including the carry from one to the other); it can also perform the 64 bit shifts/rotates required by breaking up the operation into multiple steps.
Now, it won't be quite as efficient as it would be if the processor handled 64 bit operations natively, but that's quite different from saying it can't do it at all.

since SHAKE256 uses only 32-bit values, can it be run on a microcontroller with 32bit registers?

Again, the microcontroller is quite capable of performing all the operations required.
What I don't know (and is not immediately obvious) is which would perform faster on an ARM; SHA-512 or SHAKE256 (and that might depend on the size of the input...)


What is the Lord of the Ring(s): Side Channel Attack and What are the results

How does this attack works on the high level?

Resource sharing on multicore CPUs has benefits like low cost and efficiency. This, however, is the attack point that we saw over the years. With the cache attack, the victim's data extracted with cache manipulations.
The countermeasure against the various cache attacks is disabling simultaneous multi-threading (SMT) and the obvious is the cleansing of the cache during the context switching. The cross-core cache attack is prevented by partitioning the Last Level Cache (LLC) (e.g. Intel CAT) and disabling shared memory for different security domains.
The presented attack works even the countermeasures are applied. This attack leverages contention on the ring interconnect, which is the component that enables the communication between the different CPU units.
The hardest part of this attack is getting information about the ring since it was not well documented.
L1 and L2 caches are called private caches since they are private to the core so that cross explanation is not possible. Since the Nehalem-EX the L3 cache (LLC) is divided into slices into equal size and only one slice per core.
In Intel architecture the L1, L2, and LLC are inclusive, meaning that if there is data on L1 and L2 then it is also in L3.

The ring-bus in the above picture tells most of its structure. It used in intra-process communications when a cache miss occurs in L1,L2 then the data must travel on the ring-bus to arrive LLC.
Now skipping the low-level details, the attacker's process can create a contention by transmitting 1 and idle with 0. By measuring the latency they can extract keys from insecure naive square-and-multiply RSA implementation. Like in the power attack, the second peak indicates the bit 1. This is similarly done for EdDSA.

The second face of this new channel is the keystrokes. The attack leaks the timing of the keystrokes and this can be used to reconstruct the typed words or worse the passwords. Like in this article;

Peeping Tom in the Neighborhood: Keystroke Eavesdropping on Multi-User Systems, 2009, Zhang and Wang

What are the mitigations against his attack?

For cryptographic code use secure implementations particularly constant-time programming principles. A side-channel secure implementation will not be vulnerable to the current state of being in the Cache-Ring attack. However, achieving that may not be an easy job since Intel CPUs perform hardware store elimination between the private caches and ring interconnect ( see Hardware Store Elimination)
For keystrokes, hardware can be designed based on spatial partitioning and statically-scheduled arbitration policies. Also, a software-based solution can be designed for sending the password in regular intervals.

What are the consequences of this attack?

It opened a new side-channel on the multicore CPUs. I've expected that clever minds will improve this attack in many ways. Note that, still, if your code is not vulnerable to cache attacks and they are timing-attack free, I don't see an exploit there, yet.

Are secure implementations affected by this attack?

Currently, no. Keystrokes, however, can be a big issue.


Calculating hash of original message by encoded message

As SEJPM notes in the comments, this is trivially achieved by making $E$ the identity function, such that $E(M) = M$ for all $M$.

If $E$ is not the identity function (and, in particular, if it's practical to find a message $M$ such the $E(M) ≠ M$), then $H(E(M)) = H(M)$ would be a collision attack on $H$.

Normal cryptographic hash functions are supposed to be collision resistant, so for such hash functions $H$ there cannot be any such function $E$ (at least, none that is practically computable and distinguishable from identity), or else the hash is broken.

But I suspect what you're really looking for is something else, such as $H'(E(M)) = H(M)$, where $H'$ and $H$ are two different hash functions.  This is easy to achieve by defining $H$ as $H(x) := H'(E(x))$ or, if $E$ is invertible, by defining $H'$ as $H'(x) := H(E^{-1}(x))$.  However, defining $H$ (or $H'$) like this does mean that if computing $E = E_K$ requires some secret key $K$, then the same key will also be needed to compute at least one of $H$ or $H'$.

What if we wanted to have $H'(E_K(M)) = H(M)$, where neither of $H$ and $H'$ depend on the key $K$?  In that case (assuming the $H$ isn't constant, and in particular that an attacker can choose two messages $M_0$ and $M_1$ such that $H(M_0) ≠ H(M_1)$) $E$ cannot be an IND-CPA secure encryption scheme, and thus cannot be semantically secure.  Semantic security is commonly considered the minimum baseline requirement for a secure modern encryption scheme (although there are some weaker but still useful security properties, such as Rogaway and Shrimpton's DAE security), so by that definition, even $H'(E_K(M)) = H(M)$ isn't achievable if $E$ is supposed to be secure (and $H$ is distinguishable from a constant function).


What advantage does facebook's new encrypted access_token have?

Disclaimer: I am writing this based only on what you write and my own guesswork.

Last I saw something about "encrypted tokens", it was about server load. When an app uses such a token, the token must be verified against what can be described as a big database of all existing valid tokens. Possibly, some people could have begun to try "random tokens" just in case it works (cost of trying a random token is about 0 for an amateur who will just try out a dozen or so, but the perceived potential gain is high). Risks of hitting a valid token are negligible (if the token includes enough secret random bits) but each such token must still be validated against the Big Database, and given the size of Facebook's user base, one can surmise that this implies a tremendous extra load on that database.

A way to reduce such load is to use a MAC: a keyed integrity check. Facebook's servers would first verify the MAC (with the secret key used to generated the MAC in the first place) and only tokens with a proper MAC would be forwarded to the database for the more expensive verification.

There are several methods to make a keyed integrity check; one of them is to add some "redundancy" in the token structure (e.g. a field consisting in a sequence of zeros) and then encrypting the whole with a pseudo-random permutation (a block cipher, using the whole token as a single "block"). To verify, the token is decrypted and the presence of the redundancy is verified. There is ample room for doing it wrong (e.g. if the token is longer than a cipher block, and an inadequate chaining mode is used) but it is still a possibility.

Therefore, without any other information, I find it possible that the "encrypted token" could be a keyed integrity check in disguise, meant to reduce server load.


Since $E$ is a secure PRP, instead of giving $C=E(X, S)$ to the adversary, you can give a uniform random $C\gets\mathcal{C}$.  To 'invert' this, adversary has to find a key $X'$ such that $E(X', S)=C$.

So, the construction being one-way function is equivalent to the property that, given a uniform random $C$, it should be hard to find $X$ such that $E(X, S)=C$.  I don't think that this necessarily follows from $E$ being secure, strong PRP.  For example, when the block cipher has polynomial-sized small domain (rather unusual case, I know), then this would not hold.  On the other hand, most reasonable block cipher constructions would have this property, I guess.  So, I think it could be considered as a secure OWF for practical purposes, in reasonable settings.


What password hash function for the next 50 years?

None. Cryptographic hashes are not directly suitable to store password hashes.

You should use a password hash (also known as a Password Based Key Derivation Function or PBKDF if it is used to derive a key) such as one of the secure variants of Argon2 to store passwords, not a generic cryptographically secure hash function.

However, if you're working with passwords then not updating your security for 50 years is madness; there is a lot of debate on the security of passwords as it is. Passwords generally only deliver a certain amount of security, often in the range 30-50 bits. That already doesn't provide enough entropy, let alone in 50 years time.

Password hashes add a work factor, but in 50 years this work factor may well have become insignificant due to progress in chip manufacturing. So the additional work factor (e.g. introduced by an iteration count) has become a much smaller hurdle to take. Note that finding passwords is an easily parallelized task, so it is not very dependent on single core CPU speeds.

You could also go for 128 or even 256 bits of security and let people write down a randomly generated password / key instead (for instance as 32 / 64 hexadecimal digits). That way you could use a simple hash just to hide the password / key at rest. For this you could use one of the hash algorithms above; I'd go for SHA-3. However, due to the larger password, your password management becomes more complicated as humans will probably not be able to remember it.

This can be solved by having people use a password manager that is secured with an easy to remember / less complex password or phrase. Such a password manager should then be directly available to hackers. Another advantage of using a password manager is that the passwords can be updated if a password has possibly become vulnerable in any way.

Similarly you could encrypt with e.g. a large EC public key and protect the private key of the key pair. However, most common asymmetric algorithms are vulnerable against quantum computers. Those could well become large and interconnected enough in the next 50 years. Post Quantum Cryptography is by and large still the domain of specialists (even more than common modern crypto).


How are the points in an elliptic curve over the finite field calculated?

Given
$$
y^2 = x^3 + x \pmod{13}\quad (1)
$$
note that in addition to the point at infinity, the other points are the solutions $(x,y) \in \mathbb{F}_{13}\times  \mathbb{F}_{13}$ of (1). With algebraic construction we add the point of infinity ($\{\mathcal O\}$) to the set of the solutions $$E := \{ (x, y) \in (\mathbb{F}_{13})^2 \mid y^2 = x^3 + x \} \cup \{\mathcal O\}.$$
Since you need to solve (1) for $y^2$ this implies that whenever $(x,y)$ is a solution so is $(x,-y).$ For a small field like this list the squares
$$\begin{array}{c|ccccccc}\hline
y & 0 & \pm 1 & \pm 2 & \pm 3 & \pm 4 & \pm 5
&\pm 6\\ \hline
y^2 & 0 & 1 & 4 & 9 & 3 & 12 & 10\\ \hline
\end{array}$$
and note that everything must be reduced mod 13. So $-4$ is actually $9.$
Now, whenever $x^3+x$ is equal to $y^2$ we pick up $(x,y),(x,-y)$ as points on the curve. So now prepare the table
$$\begin{array}{c|ccccccccccccccc}\hline
x & 0 & 1 & 2 & 3 & 4 & 5 & 6 &7 &8 &9 &10 &11 &12\\ \hline
x^3 & 0 & 1 & 8 & 1 & 12 & 8& 8& 5& 5& 1& 12& 5&
12\\ \hline
x^3+x & 0^* & 2 & 10^* & 4^* & 3^* & 0^* & 1^* & 12 & 0^*& 10^*&  9& 3^* & 11\\ \hline
\end{array}$$
and use the values of $x$ corresponding to the marked points to get the points
$$E=\{ (0,0),(2,\pm 6),(3,\pm 2),(4,\pm 4),(5,0),
(6,\pm 1),(8,0),(9,\pm 6),(11,\pm 4)\}
$$
on the elliptic curve, in addition to the point at infinity, which is the additive identity.


How to encrypt huge amount of data using AES-CTR

So, how can I encrypt a huge block of data (about 1GB) using AES-CTR?

So CTR-mode works as follows $C=P\oplus E_K(N)$ where $P,C$ are the plain- and ciphertext respectively and $E_K(N)$ is the encryption of $N$ under the key $K$ for every plaintext and ciphertext block.

Now if you were to re-use a $(N,K)$ pair this would indeed break security. This is why normally in CTR-mode to encrypt block $i$ we apply some function $f(N,i)$ to our nonce, for example $f(N,i)=N+i$ or $f(N,i)=N\|i$ ($\|$ denoting concatenation here) so we get different values for each block.

Of course you can't always maintain a global state value $i$ which is why for each new message $N$ or point where you don't to carry around $i$ you either derive a new $N$ from some contextual information (e.g. a packet counter) such that the $f(N,i)$ are unlikely to overlap or you choose a random $N$ and transmit it along.


There is Alice and there is Bob. But what is the name of the malicious user?

That's a funny question, I think it depends on the kind of attack you're performing.
For example, when you're trying to eavesdrop a communication, it's usually "Eve" who's doing it.
For more generic attacks, "Mallory" (Coming from "malice") is the most common choice.
As Stephen Ullrich pointed out in his comment, here's a list of all the commonly used characters: https://en.wikipedia.org/wiki/Alice_and_Bob


It demonstrates that for any fixed value $(x_1,x_6)=(a_1,a_6)$ of the first and last input bits, $$S(a_1,x_2,x_3,x_4,x_5,a_6)$$ forms a permutation as $(x_2,x_3,x_4,x_5)$ ranges over
 $\{0,1\}^4$ thus giving structural information about the DES
S boxes.


How can one turn a malleable encryption to not malleable

It seems like you are asking about converting an IND-CPA encryption scheme into an IND-CCA one.

In the symmetric-key setting, the standard approach that works is Encrypt-then-MAC.
In the public-key setting, this is a longstanding open question. There is no known black-box construction of IND-CCA from IND-CPA, nor is there a known impossibility of such a construction. However, there is such a transformation in the random oracle model: the Fujisaki-Okamoto transformation.


SNARK-friendly one-way compression functions

If you just need one-wayness (and not e.g. collision-resistance), want a compression function, and have 64 bytes of inputs, then there is a chance that you are exactly in the regime where Goldreich's one-way function, with proper choices of parameters, is unbeatable.

Concretely:

Pick once for all (and store) 256 uniformly random size-5 subsets of $[1,512]$. Denote them $(S_i)_{i \leq 256}$.
Define the following compression function $f$: on input $x \in \{0,1\}^{512}$, compute each of the 256 bits $y_i$ of the output as $P(x[S_i])$, where $x[S_i]$ denotes the subset of five bits of $x$ indexed by $S_i$, and $P$ denotes the predicate:

$P : (x_1,x_2,x_3,x_4,x_5) \rightarrow x_1 \oplus x_2 \oplus x_3 \oplus x_4\cdot x_5$.

Goldreich's function was thoroughly studied in the last 20 years (see the introduction of my paper for an overview). It's security is still far from perfectly understood, but essentially, the security decreases strongly when you look for a very long output. When you actually want a compression function and have a 512-bit input, I believe it should guarantee a clearly sufficient level of security.

As a bonus, observe that this is a completely parallelizable function: all output bits can be computed in parallel.

(of course, there are several other alternatives with low number of multiplications, or small circuit depth, but I think the above looks like a very good choice).


Why must curve25519 shared secret be hashed?

Shared secret resulting from the Diffie-Hellman step is a mathematical object; namely, the X coordinate of a curve point. It is a value in a non-binary range; moreover, it is indistinguishable from randomness only up to the security against discrete logarithm, i.e. about 128 bits. Thus, it is at least debatable that parts of the key might be guessable from the public DH values.

In other words, there are at least 128 bits of entropy ("entropy" here used as a loose meaning for "resistance to guessing attacks") in the 256-bit output of the DH, but you don't know really where. If you extract, for instance, the first 128 bits with basic truncation, then you don't know if you got your 128 entropy bits, or less, possibly much less.

No exploitable bias is really known at that point, but we know enough to be wary. Hashing the DH output is a simple and safe way to gather all the entropy and spread it around as needed, hence the recommendation.


What you're suggesting is likely good enough, and very likely far more secure than just about any other lock on your house.

If the only hash function you can find is MD5, go with it, but make sure to HMAC with the passphrase as the key. Again, it's not going to be the weak point of your security. I'm sure I could pick the lock on your front door faster than I could break an MD5 HMAC. Obviously, HMAC-SHA1 would be better, or SHA-256, even. See if you can find a SHA-1 for Arduino.

I don't understand the exact protocol you're proposing. Why the timestamp and a counter? Either alone would work fine, assuming you take more than one second to do the protocol. It doesn't hurt to do both, but let's break it down:

Client sends a request to open.
Server sends a unique string to the client.
Client computes HMAC(passphrase, unique-string) and sends the HMAC back to the server.
Server also computes the HMAC and compares them. If they match, the door opens.

That seems good enough to me, the only thing we're debating is the content of the unique string. A timestamp alone would work if you prevent replays. You could do that by having the Arduino spin until the clock ticks. But there's also nothing wrong with an equivalent of:

static int counter = 0;

...

sprintf(challenge, "%d-%d", time(0), counter++);
send(challenge);

and that would be unique enough.

The risk in this basic protocol would be someone pre-computing an appropriate HMAC. Strictly speaking, the timestamp and the counter helps thwart this, but in practical terms it isn't really going to help. If someone intercepts any given successful challenge and response, they can run a dictionary search on passphrases to find the right HMAC.

But still, it's almost certainly more secure than the locks on the other doors.

Jon


8-bit CFB in DES and AES - error propagation

17 bytes are affected in AES mode, not 17 bits. This is because the block size of AES is 16 bytes instead of 8 bytes for DES.

When you change the ciphertext it directly affects the bits that are at the same location of the plaintext, plus the time it takes to get out of the shift register, which is the size of the block size of the cryptographic primitive, i.e. 8 bytes for DES and 16 bytes for AES.

The question is however how many blocks are affected, not how many bytes. Note that the block size of CFB will be set to 1 bit, not the block size of the underlying block cipher. CFB is a stream mode after all.

So you could say that 9 * 8 = 72 blocks are affected for DES or indeed 17 * 8 = 136 for AES. This is probably not what is meant by the teacher, you're better off guessing 2 blocks for both or 9 for DES and 17 for AES. Also see the explanation by SEJPM here.

The nice thing about CFB8 mode is that if you drop or insert a byte that it will re-synchronize. What it won't do is to only flip those plaintext bits that are changed in the ciphertext, such as CTR mode does.

Nowadays we're not that interested anymore. We tend to catch transmission errors in a lower layer and then only decrypt if the entire ciphertext is available, preferably using authenticated encryption to catch any changes to the ciphertext (deliberate or otherwise).

Note also that CFB8 mode is terribly expensive; it requires a block encrypt for each byte that is transmitted, both for encrypting as decrypting.


What is the GnuPG process for going from a passphrase to a symmetric key?

GPG implements the OpenPGP standard RFC 4880, so it implements the String-to-Key Specifiers.

  3.7.  String-to-Key (S2K) Specifiers

  String-to-key (S2K) specifiers are used to convert passphrase
  strings    into symmetric-key encryption/decryption keys.  They are
  used in two    places, currently: to encrypt the secret part of
  private keys in the    private keyring, and to convert passphrases to
  encryption keys for    symmetrically encrypted messages.

  3.7.1.  String-to-Key (S2K) Specifier Types

  There are three types of S2K specifiers currently supported, and
  some reserved values:

   ID          S2K Type
   --          --------
   0           Simple S2K
   1           Salted S2K
   2           Reserved value
   3           Iterated and Salted S2K
   100 to 110  Private/Experimental S2K

I wrote my own implementation of OpenPGP a while back, if you dont want to search through the GPG source code. If I remember correctly, while decrypting test data I generated with GPG, I found that by default, GPG uses Iterated and Salted S2K (S2K3).

std::string S2K3::run(std::string pass, unsigned int sym_len){
    // get string to hash
    std::string to_hash = "";
    while (to_hash.size() < coded_count(count)){// coded count is count of bytes, not interations
        to_hash += salt + pass;
    }
    to_hash = to_hash.substr(0, coded_count(count));
    // hash string
    std::string out = "";
    unsigned int context = 0;
    while (out.size() < sym_len){
        out += use_hash(hash, std::string(context++, 0) + to_hash);
    }
    return out.substr(0, sym_len);
}

As for your second and third questions, I don't know. I would hope that no information of the password is stored in the file. I have tried to read the GPG source code, but failed doing so. It is very large and complex.


But the matrix is permuted, which is the operation enabling the trapdoor to operate.

Thus, the permuted matrix 'hides' the actual matrix $G$. So your extra hiding is unnecessary. The attacker knows the set of permuted generator matrices, but not the actual matrix.

The dimensions are huge, as a comparison, say you know that an RSA asymmetric key of 4096 bits has 2098 1's but nothing else.
That is a set of size $$\binom{4096}{2098}\approx 2^{0.999570 \times 4096}=2^{4094.23}$$ which is somewhat smaller than $2^{4096}$ but not by a significant multiplicative factor (less tha 2 bits weaker).

Knowing the code (say Goppa) and its parameters is important since these determine the strength implied by the length, dimension, and minimum distance of the code.

You could randomly choose a code, but then the advantage the legitimate decoder has, in terms of efficient decoding when in posession of $P,G$ and $S$ disappears.


Using round constants to thwart slide attacks

Yes the different round keys help, but without the different round constants in key-schedule, all the rounds of key-schedule algorithm will be same. Thus these identical rounds may generate sliding round keys. For example

AES-128 uses 11 round keys, without the round constants, all the rounds of the AES key-schedule will be same. Thus there is chance that there exist two master keys $Ka$ and $Kb$, such that there corresponding round keys differ at only one place.

Suppose 11 Round keys for $Ka$ are: $ka,k1,k2,k3,k4.......k9,k10$
and 11 Round keys for $Kb$ are: $kb,k1,k2,k3,k4.......k9,k10$

if you set $Kb=k1$, then 11 Rounds for kb will be: $k1,k2,k3,k4,k5....k10,k11$

Now you see Both keys have same round keys with an offset of one except that last round key of kb and 1st round key of ka. These identical keys with offset of 1 place help in making slid pair, which is required for Slide Attack.

If each round will have different fixed round constant, generation of such identical round keys will not be possible, thus preventing Slide Attack.


Can I open a file in plaintext (already decrypt) but the cipher doesn't change?

Yes, it's possible.

Let's assume that you have a text. It is possible for decrypt the text content from the ciphertext when opening the file. The content can be present in the memory without being written to disk. When you're done, it can be saved, which will encrypt the plaintext and write it to a file.

What you need to do:

Figure out the file format (this is probably symmetric, so don't forget random IVs and MACs/authentication tags).
Write either a standalone program, or a plugin for an existing program (e.g. LibreOffice). In particular

User interface,
file opening, parsing and decryption,
data serialization and encryption.


Understanding Encryption length calculation and rounds

Computers operate on bits and bytes internally. They do not operate on (hexadecimal) characters. Characters are for human consumption.

Hexadecimals use only 4 bits out of a possible 8 in each byte, assuming 8 bit ASCII or compatible encoding. To perform any calculation such as bit shifting, addition or modular multiplication, you'd first have to convert the characters to bits. So that's not something you would perform internally to your hash function. Only if you want to make your output compatible for human readable text do you need to convert to hexadecimals (or base 64 or any other encoding of binary in text).

A color consists of 3 bytes in the common RGB scheme. That they are represented as three concatenated hexadecimal bytes is again only for human consumption. If you look at the contents of a bitmap file (.bmp) then certainly the dots / pixels are not present as hexadecimal characters. They are bits and bytes.

A block cipher and secure hash (not password hash) uses a certain number of rounds to be secure. How many rounds depends on the complexity of the inner function; some algorithms have a lot of simple rounds and some have fewer complex rounds. You probably want to have at least some 30% of headroom against the best known attacks to your function (i.e. if 7 out of 10 rounds are broken then you'd consider your function secure, if 9 out of 10 are broken then you're living too close to the knife's edge).

Yes, the number of iterations is similar to the number of rounds in functionality. However, commonly each iteration in a password hash would already create a secure result if the input password has enough entropy. That is, you would at least not be able to reverse the function and gain information about the input. Instead, the number of iterations should be as large as possible so that an adversary has to perform a lot of work (the work factor) to brute force a large amount of password hashes.


F(x) = 1 matches your requirement and obviously isn't one way. It is trivial to find a pre image for this function as any value is a pre image of 1.
One way function doesn't mean it's hard to find the original value. It means it's hard to find any pre image which leads to the requested output value.
Finding the original value of a compression function is obviously impossible to do with high confidence if the original data is chosen uniformly. This for information reasons regardless of computing power.


The protocol of provisioning shared key to multiple devices?

This looks likely a classic server-multiple client scenarios, I had the similar situation:
Depend on real application, some of my thought:

For most case, IoT devices does not communicate to server at the same time? so server should be able to setup secure key for each of IoT devices through ECDH.
To have a common key for all devices looks too dangerous, that means as soon as one IoT device is compromised, hacker will be able to hijack all IoT devices..
It is only safe for each IoT device to use a common AES key--when you have physical access to them--for exp, in factory, in Lab, before shipment .. after it is been deployed to field, you must consider the different key for each device. Someone also burn a HW AES key into IoT device ROM, but still that have to be different for each of the IoT device, so one compromise does not jeopardize all devices.
Given ECDH could be too heavy for a IoT devices (usually take few back-forth communication), my suggestion would be to consider once time ECDH when IoT device is been activated, and using Ephemeral ECDH (ECDHE) which does not request regenerated ECC keys.


As with all things, the answer is "it depends".

If you're using a block mode with no padding (such as CTR or CTS) then you're probably fine.  The ciphertext length is the plaintext length, your hashing time is a function of the known length, and you return "error" on tamper.

If you use a block mode WITH padding (CBC, ECB, etc) then you're not so fine.  By using StE (or MtE) the recipient has to deal with the padding BEFORE knowing if it was a tampered message.  So let's say that I'm a bad actor and I tamper with your message en route.  I tamper wherever I need to tamper to mount a padding attack and observe results:

If you reply "padding failure" then you are a true padding oracle, and I chortle and attack you very quickly.
If you reply "error" sometimes in 'significantly' less time than others then you are checking the padding before starting the hash, and you have a noisy timing-based padding oracle.  I smirk and attack you.
If you reply "error" at almost always the same rate, but some more slowly than others, then I have hit the boundary condition between your plaintext interpreted padding length and the digest's padding length.  You have a whispering oracle, and I grumble and attack you anyways.  For good measure I fire up a botnet and DDoS you when I'm done, because you pointlessly annoyed me.

There's no situation where you win in online scenarios.

Note that this answer didn't care if you did asymmetric signature, MAC, or just a simple digest.  You processed untrusted data and leaked info via a side (or direct) channel.

In offline scenarios there's not much room for oracle attacks, so you will reliably detect an error induced in the storage layer.  Huzzah?

The right answer for padded block cipher modes is always EtM.  That way every tamper is rejected at the same time interval, and now the attacker is left with brute forcing for success (which is fairly improbable if your MAC is in the 128+ bit space).

To relate to the Apple problem:  An asymmetric signature is a valid message authentication code (some people reserve "MAC" for excluding asymmetric signatures).  The problem, as also related in Do I need to use a MAC with asymmetric encryption?, is when you don't have an association of WHO is allowed to sign the particular message.  Using a HMAC/etc only changes the equation by forcing the recipient to know a priori what key will be used. Binding the public key of the expected signer a priori solves the problem similarly.


authentication and access control in IoT

Not much, my impression is that the problems are more or less the same. People change the term to IoT because it sounds sexier than wireless sensors (and they can sell the same thing again as new). Another similar term is pervasive (ubiquitous) computing. Yet another related term is edge computing or fog computing.

The main underlying research challenges for security in all those are often the following:

resource-limited devices
lack of trust
decentralized
weak physical security
hard to update
often has energy constraints

just to name a few.


OK, lets go through this step by step:

Given:

$H_1 = E(m_1)$

$H_2 = E(E(m_1) \oplus m_2)$

and

$H_1' = E(m_2 \oplus E(m_1))$ because $m_1' = m_2 \oplus E(m_1)$

$H_2' = E(H_1' \oplus H_2 \oplus m_2 \oplus H_1)$ because $m_2' = H_1' \oplus H_2 \oplus m_2 \oplus H_1$

then substitute $H_1'$ in $H_2'$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus H_2 \oplus m_2 \oplus H_1)$

then substitute $H_2$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus E(E(m_1) \oplus m_2) \oplus m_2 \oplus H_1)$

and $H_1$:

$H_2' = E(E(m_2 \oplus E(m_1)) \oplus E(E(m_1) \oplus m_2) \oplus m_2 \oplus E(m_1))$

re-arrange the parameters of XOR:

$H_2' = E(E(E(m_1) \oplus m_2) \oplus E(E(m_1) \oplus m_2) \oplus E(m_1) \oplus m_2)$

now we can see that two parts can be stricken out:

$H_2' = E( \require{cancel}\cancel{E(E(m_1) \oplus m_2) \oplus E(E(m_1) \oplus m_2)} \oplus E(m_1) \oplus m_2)$

so we are left with:

$H_2' = E(E(m_1) \oplus m_2)$

meaning that $H_2' = H_2$.

Given that $m_1'$ and $m_2'$ are unlikely to be equal to $m_1$ and $m_2$ we can clearly see that many pairs of related, but different messages hash to the same result, creating collisions.

Here $E$ is of course the AES function.


Many single-time use keys encryption scheme (not Shamir's Shared Secret)

Since you already trust the server to securely delete the plaintext message after decrypting it for a client, you can trust it to delete the encrypted versions too.

So for instance the case of 3 keys K1 .. K3 and plaintext P, store K1(P), K1(K2(P)),K1(K2(K3(P))) since they all start with K1, that is the only key that can be used at first. after K1 is presented, apply it to everything in the series, so you end up with.
P, K2(P), K2(K3(P)). serve up P deleting it and store the rest as your new series for when K2 arrives. repeat the proceduce until the whole sequence and hence all the keys are used up.


What is the most efficient attack on NTRU?

I am a cryptographic researcher at Security Innovation, which acquired NTRU Cryptosystems.

  Now, I wonder what is the most efficient attack one could do? Does it have to be comprehensive like the meet-in-the-middle one?

The most efficient attack (the terminology "best known attack" is often used here) is the hybrid attack of lattice reduction and meet-in-the-middle attack from Nick Howgrave-Graham at Crypto 07, available at:
http://link.springer.com/chapter/10.1007%2F978-3-540-74143-5_9

In this type of attacks, one performs partial lattice reduction on the NTRU lattices, and then uses a meet-in-the-middle search on the remaining part of the lattice. It combines the strength of both techniques.

For a given NTRU lattice, one need to fine-tune the parameters of the hybrid attack, so that the effort to do lattice reduction is the same as the effort to search. The latest analysis of this attack against NTRU cryptosystems can be found from: http://eprint.iacr.org/2015/708

  Is it possible to use the LLL to speed up the process?

Exactly. One can view the lattice reduction part as a pre-processing of a searching attack, which allows one to reduce the searching space.

PS: LLL algorithm is not strong enough for large dimensional NTRU lattice, even in the partially reduced scenario. One needs to use the BKZ/BKZ2.0 algorithms.


Can I reuse a nonce to retransmit the same packet using ChaCha20-Poly1305?

I understand the "sudden death" implications of reusing a nonce with ChaCha20-poly1305, but I believe this rule doesn't apply if you are transmitting exactly the same packet.

There are two aspects to consider here: (a) confidentiality (can an adversary find out anything about the content of the plaintexts) and (b) authenticity (can an adversary forge packets).  On the confidentiality front you're unquestionably right.  A passive eavesdropper doesn't learn anything new about the plaintext from seeing the same ciphertext twice.

On the authenticity front I think it's trickier, and no verdict should be reached without careful analysis.  It's safe to say that authenticating the same message twice with the same nonce doesn't allow the adversary to easily forge any other message, so you're certainly not violating the authenticated cipher's rules.  But you do need to think about how this fits in the bigger picture—the protocol level above the cipher level.  I would ask myself, for example, whether there are scenarios where an active adversary could defeat some security property by replaying a packet they've eavesdropped on a second time, or suppressing the reception of packets and then feeding them to the recipient out of order.

Protocol design is tricky.  Authenticating individual messages doesn't automatically guarantee authenticity of a sequence of interactive session of messages.


XOR cipher for encrypting compiled C code

The encryption scheme seems to be:

re-use an existing 128-bit secret, originally used to unlock a read-prevention mechanism, as the 128-bit key;
split the plaintext (data to protect from prying eyes) into 128-bit blocks;
XOR each block with that 128-bit key.

That approach is flawed. Two cardinal mistakes are made:

Use XOR with a keystream that repeats.
Reuse a secret (and what's worse, without any level of derivation).

Due to 1., if there is anything guessable in the plaintext (such as, a block with like 40 consecutive 00h bytes, or an ASCII string of about that size that appears in the user interface, or a code sequence from a common library), the 128-bit secret is easily recovered, and the confidentiality of the whole plaintext is lost; that's kid's play, really. Same (for more effort and data, like a some kilobytes) if some characteristics of the plaintext are known (like instruction set and compiler), enabling attacks like frequency analysis.

Due to 2., the above attack also reveals the 128-bit key used to unlock a read-prevention mechanism, ruining it. The confidentiality of both earlier and later code is lost.

Why not use true cryptography? See this answer, especially the final paragraph and what it links to.

  What if I were to introduce some heuristic where, depending on the data content, the password was first rotated before XORing with a given block of plain text?

If the rotation is the same for each block, that will not help at all to protect the confidentiality of the ciphertext; the above attacks guessing the key work unmodified. That helps, even so slightly, to protect the secret used to unlock a read-prevention mechanism (because it is now mildly different from the one used in a futile attempt to protect the code's condifdentiality).

If the rotation varies with each block (say, as the low 7 bits of block number), it might help slightly w.r.t. the confidentiality in some cases, but in many others it harms significantly: for example, knowing that rule for rotation, and on the sole assumption there exist a contiguous zone of few kbyte where 90% of the bytes have their bit 7 of zero (with about random distribution of those that do not), it is now trivial to recover the whole key by frequency analysis; then the whole plaintext. What's needed here (if for some reason it was indispensable to use the same secret for two uses) is a derivation mechanism, not security-by-obscurity.

Also, are we talking password, or key? That's not the same thing. A key is assumed chosen at random, a password is not.


One common possibility is that your non-toy ElGamal cipher express integers as fixed-width octet strings, of width large enough for any element in the base field; that could be with I2OSP of PKCS#1v2.2 or equivalent, but there are a number of other (less common) ways.

Another possibility is that you did not try hard enough to find shorter ciphertext for your non-toy ElGamal cipher. When ASN.1 representation of integers is used, the digit size is an octet, and for some parameters an integer might be under the maximum size with low probability, like down to about 1/256 ≈ 0.4%. Even with two integers, quite a few hundred attempts might be necessary to observe a ciphertext below the usual size. There are other conventions where observing shorter ciphertexts would require billions attempts.