Other than password hashes, are there other uses for non-reversible crypto Hashing is useful for checking that an input matches expectations without giving away the stored expected version - so confirming passwords etc.

But are there other use cases? In general, cryptographic storage so data is retrievable seems to be the norm.

Data integrity is another usage. For example, when you want to send/download data, you want to make sure that the data is not modified or transmitted/downloaded correctly. To achieve this the data hashed and the hash value sent/downloaded on another channel. One may see examples of this file verification on Linux ISO download pages. Of course, hashing is not enough to protect you against some attacks. Therefore you need digital signatures.

Another one, when digitally signing the document, we first hash the document then sign the hash value. This is more efficient than signing the whole document.

Keyed-Hash Message Authentication Code (HMAC) is a message authentication code (MAC) that involves a Cryptographic hash function and a Cryptographic key.

Key Derivation Functions are also using hash functions to derive a key from your password plus various random sources.

Key Stretching: making a possibly weak password more robust against brute-force attacks. PNKDF2, bcrypt, Argon2 use key stretching.

Ratcheting: forward key chaining with no backward availability.

A special case of hash usage is the Merkle-Tree to verify the integrity of data with low bandwidth.

In Blockchains: hashes are a fundamental part of the blockchains.

Proof-of-work systems:

A Proof-of-Work (PoW) system (or protocol, or function) is an economic measure to deter denial of service attacks and other service abuses such as spam on a network by requiring some work from the service requester, usually meaning processing time by a computer.

Bitcoin mining and Hashcash use Proof-of-work systems.

Constructing Stream Ciphers as in ChaCha2 in TLS 1.3. This construction uses CTR mode of operation.

Public Key Cryptography: Trapdoor one-way functions are easy to compute hard to invert without special information. Most of the public key cryptosystems are based on Trapdoor one-way functions.

Commitment schemes allow committing a value while keeping others hidden and give the ability to reveal at a later time.

Lamport signature or Lamport one-time signature scheme can use one-way functions in which usually cryptographic hash functions are preferred.

Secure Random Number Generators such as Hash_DRBG use hash functions to improve and stretch the output from a true random number generator


Find $F(2x)$ from $F(x) = a^x \bmod p$ Given $F(x) = a^x \bmod p$, where $a$ is a primitive root of $p$,
Is it possible to work out what $F(2x)$ or $F(3x)$, etc if you know
what $F(x)$ is but not $x$.

If you use $F(x)$ then $F(2x)$, etc as session keys for a cryptosystem would be knowing a previous key compromise future keys.

Rephrasing fkraiem's comment as an answer:

  Hint:   $$a^{2x}=(a^x)^2$$

which also holds $\bmod p$.


How can I prove that it is impossible to find a cheater in shamir secret sharing? Three participants Quadratic polynomial, one cheater. The Cheater discloses a false (x,y) pair I need to prove that any one of the truth-telling participants can't tell which of the others is the liar. I do realize that any pair of participants have a linear subspace of possible solutions since they don't know the secret they can't tell if it is a member of their subspace, but I don't think it is a proof just an intuition as to why this claim is true.

You could use the fact that having two of three pairs does not reveal any information about the secret (polynomial). Also see the Wikipedia article on Shamir's secret sharing: it provides you with a nice graphical answer to your question.


Understanding Montgomery's parameterization of elliptic curves I'm having a bit of trouble understanding the translation of affine  coordinates to projective coordinates in Montgomery curve ECM. Would be very thankful if someone could explain it by expanding the derivation.

  From: Speeding the Pollard and Elliptic Curve Methods
  of Factorization page: 261.
  $$\begin{equation}\tag{10.3.1.1}By^2 = x^3  + Ax^2 + x\end{equation}$$

  Let $P_1 = (x_1, y_1)$ and $P_2 = (x_2, y_2)$ be two points in the
  curve, with $x_1 \neq x_2$ and $x_1x_2 \neq 0$.  Then $P_1 + P_2 = (x_3, y_3)$ satisfies

  $$x_3 = B[(y_1 -  y_2)/(x_1 - x_2)]^2 - A - x_1 - x_2,$$
   $$\begin{align}x_3(x_1 - x_2)^2 & = B(y_1 -  y_2)^2 - (A + x_1 +
 x_2)(x_1 - x_2)^2 \\ & = -2By_1y_2 + x_1x_2(x_1 + x_2 + 2A) + x_1 +
 x_2 \\ & = B(x_2y_1 - x_1y_2)^2/x_1x_2. \end{align}$$

  Similarly, $P_1 - P_2 = (x_4, y_4)$ satisfies $$x_4(x_1 - x_2)^2 =
 B(x_2y_1 + x_1y_2)^2/x_1x_2.$$ Multiply these equations and use
   (10.3.1.1) to obtain $$x_3x_4(x_1 - x_2)^2 = (x_1x_2 - 1)^2$$ after
  division by $(x_1 - x_2)^2$. This equation remains valid if $x_1x_2 = 0$. If $P_1 = P2$, a similar derivation yields

  $$4x_1x_3(x_1^2 + Ax_1 + 1) = (x_1^2 - 1)^2$$  These equations
  reference only the $x_i$, not the $y_i$. Fortunately ECM does not
  require us to compute the $y_i$.

(I  don't understand everything below this point. Could someone help me expand these derivations? Seems like it is oversimplified)

  Let $P$ be an arbitrary point on the curve and let the x-coordinate of
  $nP$ be the rational number $X_n/Z_n$. From the ratio
  $(X_{m-n}:Z_{m-n}),(X_m:Z_m) and (X_n:Z_n)$, one  can compute the
  ratio $(X_{m-n}:Z_{m-n})$ via the addition formula.

  $$X_{m+n} \leftarrow Z_{m-n}(X_mX_n - Z_mZ_n)^2\\ Z_{m+n} \leftarrow X_{m-n}(X_mZ_n - Z_mX_n)^2$$

  if $mP \neq nP$, and  via the duplication  formula $$\begin{align}
X_{2n} & \leftarrow (X_n^2 - Z_n^2)^2, \\
Z_{2n} & \leftarrow 4X_nZ_n(X_n^2 + AX_nZ_n + Z_n^2)
\end{align}$$

  The costs drop if we store the ratios $(X_m:Z_m:X_m+Z_m:X_m-Z_m)$ and rewrite the formulae as (the right sides of the addition formula have
  been multiplied by 4)

  $$\begin{align}
X_{m+n} & \leftarrow Z_{m-n}[(X_m - Z_m)(X_n + Z_n) + (X_m + Z_m)(X_n - Z_n)]^2 \\
Z_{m+n} & \leftarrow X_{m-n}[(X_m - Z_m)(X_n + Z_n) - (X_m + Z_m)(X_n - Z_n)]^2 \\
\end{align}$$
  and

  $$\begin{align}
4X_nZ_n & = (X_n + Z_n)^2 - (X_n - Z_n) \\
X_{2n} &  \leftarrow (X_n + Z_n)^2(X_n - Z_n)^2 \\
Z_{2n} & \leftarrow (4X_nZ_n)((X_n - Z_n)^2 + ((A + 2)/4)(4X_nZ_n))
\end{align}$$

Write $(x_i, y_i) = (X_i : Y_i : Z_i)$, so that $x_i = X_i/Z_i$ and $y_i = X_i/Z_i$, where $Z_i \ne 0$ is arbitrary.  (If you are not familiar with projective coordinates or you like visuals, see an illustration of projective coordinates on a real elliptic curve.)

Let's take the doubling formula for example, where $(x_3, y_3) = (x_1, y_1) + (x_1, y_1) = [2](x_1, y_1)$:

\begin{equation*}
  4 x_1 x_3 ({x_1}^2 + A x_1 + 1) = ({x_1}^2 - 1)^2 \tag{p. 261, second display}
\end{equation*}

so that

\begin{equation*}
  x_3 = \frac{({x_1}^2 - 1)^2}{4 x_1 ({x_1}^2 + A x_1 + 1)},
\end{equation*}

which in projective coordinates is

\begin{align*}
  \frac{X_3}{Z_3}
   &= \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2}
           {4 \frac{X_1}{Z_1}
              \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\
   &= \frac{{Z_1}^4}{{Z_1}^4}
      \cdot
      \frac{\Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2}
           {4 \frac{X_1}{Z_1}
              \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\
   &= \frac{\bigl({Z_1}^2\bigr)^2 \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 - 1\Bigr)^2}
           {4 X_1 Z_1 {Z_1}^2
            \Bigl(\bigl(\frac{X_1}{Z_1}\bigr)^2 + A \frac{X_1}{Z_1} + 1\Bigr)} \\
   &= \frac{\bigl({X_1}^2 - {Z_1}^2\bigr)^2}
           {4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr)}.
\end{align*}

From this, we can read off the numerator and denominator:

\begin{equation*}
  X_3 = \bigl({X_1}^2 - {Z_1}^2\bigr)^2
  \qquad\text{and}\qquad
  Z_3 = 4 X_1 Z_1 \bigl({X_1}^2 + A X_1 Z_1 + {Z_1}^2\bigr).
\end{equation*}

Obviously, we can multiply both of them by the same arbitrary nonzero factor too, but there's no need here.

For the addition formula that is not doubling, you're trying to write $[m + n]P = [m]P + [n]P$ in terms of $X$ and $Z$ coordinates for $[m]P$, $[n]P$, and $[m - n]P = [m]P - [n]P$.  That is, you have $x_1 = x([m]P)$, $x_2 = x([n]P)$, and $x_4 = x([m - n]P)$, and you're trying to find $x_3 = x([m + n]P)$.  Use the top equation on p. 261, $$x_3 x_4 (x_1 - x_2)^2 = (x_1 x_2 - 1)^2,$$ and again write it out in terms of $x_i = X_i/Z_i$.

The last part is a matter of tidying to reduce the number of distinct intermediate quantities, e.g. using the observation that

\begin{multline*}
  {X_1}^2 + A X_1 Z_1 + {Z_1}^2
   = {X_1}^2 - 2 X_1 Z_1 + {Z_1}^2 + 2 X_1 Z_1 + (A/4) 4 X_1 Z_1 \\
   = (X_1 - Z_1)^2 + \frac{A + 2}{4} 4 X_1 Z_1
\end{multline*}

to write the whole doubling formula in terms of $X_1 \pm Z_1$ for a total cost of 4A + 2S + 3M.


Diffie-Hellman and man-in-the-middle attacks See here for the man-in-the-middle attack on Diffie-Hellman that I'm concerned about: What is Diffie-Hellman?

How do we combat this? I have two questions:

Is one solution for both Alice and Bob just using a certificate authority, then they can each look up the other's certificate and know the secret key without really communicating (through Eve)?
The other solution I heard about is using RSA for signatures. My question in this case is that, if Alice and Bob are using RSA, why doesn't Alice just send Bob a secret symmetric key using Bob's public RSA key (signed with her private RSA key)? Isn't this basically what PGP does? I don't see the point in using DH if we're using RSA anyway.

Well, as it says in your link the problem is authentication. So somehow Alice and Bob must set up an authenticated channel. One way of implementing such a channel is by Alice and Bob holding each others public verification key for a signature scheme.

A CA would probably not hold a secret key for Alice and Bob. However, using a CA to get an authentic copy of the other parties public key for a signature scheme that would allow to set up an authenticated channel between Alice and Bob, so they could do DH key exchange. Apart from not trusting the CA with secret information, this has the benefit that Alice and Bob can now generate many secret keys with out involving the CA.
It is true that if Alice has a public encryption key for Bob and Bob has a public signature verification key for Alice, they could use the protocol you describe. However in general public key encryption and signature schemes are not the same(although for the particular instance of RSA there may be some overlap). If Alice and Bob only have keys set up for a signature scheme, they could use DH exchange to get a secret key.


Is it safe to use the same IV for multiple encryptions in AES CBC mode when you are always encrypting random bytes? I am generating random bytes (16 or 32 bytes at a time), and I want to encrypt them using a 128 bit AES key in CBC mode. Am I really weakening this horribly if I am reusing the same IV and key each time I encrypt a set of random bytes, given that there is no structure at all in the data I am encrypting?

We can add a nonce to our scheme and change the IV each time, I am just trying to understand why (if) it is really required when encrypting data with no structure?

No, you're not weakening your data in that case. You could even use ECB in to encrypt random data. Symmetric key wrapping often just uses ECB. But beware that it depends on how many bytes you encrypt.

You may want to make sure all bytes are random (if you know the plaintext size in advance). Think about encrypting a single random byte and filling the rest with zero's or PKCS#7 compatible padding. Identical values would be easily detected.

You may want to very clearly document what you're doing though, because if you add context / structure to your random bytes it would be pretty easy to mess things up.

You could use SIV if you want to have secure, authenticated key wrapping for your random bytes. You would not need to generate a random IV and SIV would handle additional structure well. You would need to have an implementation of SIV and room for the synthetic IV (which is also the authentication tag) though.


How is "post-quantum security" proven/shown? Due to growing concerns over the threat of quantum computing to asymmetric cryptography (RSA, ECC, etc), a number of "quantum resistant" replacements have been proposed (SPHINCS, McBits, and many more).  How are these cryptosystems proven (or argued) to be secure in the presence of quantum computers?

Are the schemes only proven secure against some finite set of quantum algorithms (Shor's algorithm, Grover's algorithm, etc), or are they proven secure against all quantum algorithms possible in some theoretical model of quantum computing?

This is in principle similar as how "normal" cryptosystems are proven. With some algorithms we can reduce them to some "hard problem", but we do not know that those problems are actually hard to solve. Only that we cannot solve them efficiently. For example, the Diffie-Hellman problem is not even known to be NP-hard, never mind the whole issue of P vs. NP.

Similarly, we know some problems that Shor's algorithm accelerates. Post-quantum algorithms avoid these and make use of problems to which Shor's algorithm does not offer an easy solution. However, that does not mean there is no other algorithm that solves them, or even that there is no way to use Shor's for them. (E.g. it is possible that the hidden subgroup problem in non-abelian groups can somehow be reduced to the HSP in abelian groups.)

In the end it is similar as with symmetric algorithms. They are not so much proved secure, but become proven after facing years of cryptanalysis.


How can we distribute Shamir's secret sharing scheme shares without a dealer? Let's say $k$ users have shares to a $(k,n)$ secret sharing scheme, and they want to issue new shares. How can they do this without collecting the shares together?

In particular, no set of $k-1$ users (including the new users) should be able to learn the shared secret during or after the share generating process. There is also no trusted third party.

One way to do this is by doing a secure multiparty computation. Is there a way to accomplish the task without a general multiparty computation scheme?

Here is the setup I am assuming, in the beginning you have a dealer who distributes $k$ shares from a $k$ out of $n$ secret sharing (e.g., Shamir) to the $k$ parties currently present.

What you would like is that if at some point in the future the $k$ parties want to add an additional party, they can do so, without requiring the dealer to cooperate at that moment in time.

As you mention, one way to do this would be with a general MPC. Another way to do this, would be, if the dealer agrees at the start that some additional shares should be available so that if the $k$ parties want to let another person in, they can, the dealer can generate a few additional shares right off the bat (say $k+t$ instead of just $k$ shares). Distribute $k$ shares to the $k$ parties, then secret share the remaining $t$ shares with the $k$ parties. That way, each of the $k$ parties has their own share, and shares of the remaining $t$ shares. If they want to give someone else a share, they send them a share of one of the $t$ shares. That party reconstructs to get a share of the original secret.

This allows the $k$ original parties to keep their original shares, while giving a new share to a new party. The dealer can also set thresholds on how many of the $k$ parties need to come together to pass out additional shares (it doesn't have to be all $k$).

As I mentioned in my comment, if you remove the requirement that the original $k$ parties can keep their original shares, i.e., you allow them to get a fresh share at the same time that you are generating a new share for the incoming party, Desmedt and Jadjodia's paper on redistributing secret shares is the way to go (malicious model variants have been proposed if necessary).


Showing formally that DDH hardness implies CDH hardness As part of homework problem, I need to show that DDH hardness implies CDH hardness.
Assume $CDH$ is hard relative to some group generator.
The intuition is pretty clear, so I've made the trivial reduction - let $A_{CDH}$ be a PPT algorithm that computes $DH_g(h_1,h_2)$ with probability $\epsilon$, define $A_{DDH}$ as follows:
1) Given $g^x$,$g^y$ and $g^z$, return 1 iff $A_{CDH}(g^x,g^y)=g^z$
Now I look at:
$Pr[A_{DDH}(g^x,g^y,g^z) = 1]$  (the group description is given implicitly)
Where the probability is taken over independent choices of x,y and z.
($D_G$ is a description of the group, a generator $g$, and its size $q$)
I want to express the probability above in terms of $A_{CDH}$, so I've written:
$Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y) = g^z]$
But how can I analyze it? If $g^{xy} \neq g^z$ I don't know the probability that $A_{CDH}(g^x,g^y) = g^z$, I only know that it gives (some) wrong answer with probability $1-\epsilon$
If the details aren't clear let me know, I tried to be as concise as possible. Thanks in advance!

Let me state the precise definition of DDH, to make it more clear: assuming a group an a generator $g$ are fixed, the challenger flips a coin. If he gets 0, he picks $(x,y,z)$ uniformly at random; if he gets 1, he picks $(x,y)$ uniformly at random and sets $z = xy$. It returns $(g^x,g^y, g^z)$. You win the DDH game if you can find out the coin that was flipped with non-negligible advantage over the random guess. Now, you have this adversary $A$ that breaks CDH with probability $\varepsilon$, and you would like to use it to break DDH. So, a challenger flips a coin and sends you a DDH challenge.

I've written:  $Pr[A_{DDH}(g^x,g^y,g^z) = 1]=Pr[A_{CDH}(g^x,g^y)
> = g^z]$ But how can I analyze it? If $g^{xy} \neq g^z$ I don't know the probability that $A_{CDH}(g^x,g^y) = g^z$, I only know that
it gives (some) wrong answer with probability $1-\epsilon$

There are two situations: either the challenger picked $1$, and so it holds that $g^{xy} = g^{z}$. As on input $(g^x,g^y)$, the adversary returns $g^{xy}$ with probability $\varepsilon$, in this case it returns the same $g^z$ that you got from the challenger with probability $\varepsilon$. But if the challenger picked $0$, then by the definition of the DDH game, $z$ was picked uniformly at random, and in particular, totally independently of $x$ and $y$.
So the question becomes: given $g^x$ and $g^y$, no matter how it works and how powerful it is, what are the chances that the adversary outputs $g^z$, which is a uniformly random group element that is not known by the adversary? You should easily convince yourself that the answer is one over the order of the group - a negligible quantity.
Hence, when the coin is $0$, the adversary outputs $g^z$ with negligible probability; when it's $1$, he outputs $g^z$ with probability $\varepsilon$. As the coin is flipped at random, both situations happen with probability exactly $1/2$ - from that, you should be able to measure the probability that you win the DDH game by answering $0$ when $A$ fails to output $g^z$, and $1$ when he succeeds.


RSA private key finding method Bob uses RSA with $p=83$ and $q=103$. His public key is $e=445$.  Alice claims that she can calculate Bob's private key without using the definition $d=e^{−1}\bmod φ(n)$?
But how?

If performing as in a typical description of textbook RSA, Bob has:

secretly drawn distinct primes $p=83$ and $q=103$;
computed $n=p\cdot q=8549$;
computed $\varphi(n)=(p-1)\cdot(q-1)=8364$ where $\varphi(n)$ is Euler's totient function;
chosen $e=445$, as some arbitrary $e>1$ with $\gcd(e,\varphi(n))=1$;
published his public key $(n,e)\;$, which in particular Alice knows;
computed $d=e^{-1}\bmod \varphi(n)\;$ using the extended Euclidean algorithm, giving $d=7537$; Bob's private key is $(n,d)$, and he does its best to keep $d$ secret.

The definition of RSA worded in PKCS#1 allows Bob to choose $d$ as any positive integer less than $n$ such that $e\cdot d-1$ is a multiple of $\lambda(n)$, where $\lambda$ is Carmichael's function, with (since $n$ is the product of distinct primes $p$ and $q$) $\lambda(n)=\operatorname{lcm}(p-1,q-1)=4182\;$. That allows $d=e^{-1}\bmod\lambda(n)\;$, which is the smallest positive working $d$ (here $d=3355\;$), and often gives Bob a little less work when using his private key. Bob would have more than two possible $d$ for some other choices of $p$ or $q$, or if we removed the mathematically arbitrary constraint $0<d<n$. In particular, $d=11719$ or $d=-827$ are functional.

Factorization

One way Alice has to find Bob's private key is to factor $n=8549$, finding it's prime factors $83$ and $103$. She then knows, within order, the $p$ and $q$ chosen by Bob at step 1, can repeat steps 3 and 6, and find Bob's private key as computed in step 6. However that's prohibited by the question's "without using the definition $d=e−1\bmod\varphi(n)\;$". More importantly, if Bob had chosen $p$ and $q$ as random primes of more than 384 bits, Alice would have to perform a factorization more difficult than was ever openly performed. For random 1024-bit primes (a common practice), Bob is likely safe from a factorization of his $n$ directly from $n$, for the time being.

Enumeration

As pointed by poncho, Alice can find by enumeration the smallest positive odd $d$ such that $((r^e)\bmod n)^d\bmod n\;=r$ for $r$ the first few primes. That will give Alice $d=3355$, after in the order of $1700$ modular multiplications (noting that most unsuitable $d$ will be eliminated for $r=2$, and that going from one candidate $d$ to the next can be done with a single modular multiplication by $r^{2e}$). That will give Alice the smallest working $d$ such that $(n,d)$ behaves as Bob's private key. Alice may not have calculated Bob's actual private key, but the difference is semantic and it could be fixed by various methods. However, that way of finding $d$ would be impractical if Bob had chosen $p$ and $q$ as primes of $45$ bits or more.

Other ways

Alice can perform as she claims in several other ways:

coerce Bob to reveal his private key, by force, law, or trickery;
read the information about Bob's private key from the device(s) Bob uses to store his private key or make use of it; absent encryption under a strong passphrase (e.g. stored un-encrypted, or under the protection of a short PIN), only physical security measures can prevent such extraction once Alice gets her hands on the device(s); Alice's job is made significantly easier by the fact that she can verify a guess of $d$ (e.g. by the method used for enumeration);
as a special case of trickery (or law, in some countries and times), steal Bob's private key by using a Trojan horse somewhat planted in Bob's device(s); the insertion could be by Bob unknowingly (letting some vulnerable software) installing the trojan; by some evil maid; during transport of the device before delivery to Bob; or by (exploitation of a weakness left by) the manufacturer of (some part of) the device at time of manufacture (intentionally or not); there are numerous accounts of such practices, and it is extremely difficult to demonstrate one is safe from them (it is easier to be likely safe from them);
as a refinement of read above, analyze the power consumed, the electromagnetic radiation, or perhaps just the noise emitted by Bob's device(s) when Bob uses his private key, which in the most naive implementations of RSA will directly leak the bits of $d$;
other side-channel attacks, including timing, allowing factorization of $n$, then performing steps 3 and 6;
fault attacks: for some possible construction of Bob's device, induce it to make computation errors when using his private key, and exploiting the erroneous results to factor $n$; this is the so-called Bellcore attack: D. Boneh, R. DeMillo, and R. Lipton, On the importance of checking cryptographic protocols for faults (pdf); however if Bob's device checks its results before revealing them, by way of the public key, as it should, this attack simply won't work.


Fault attacks inside a loop I am working on an attack that involves changing a constant inside a loop. Consider the simplified example is as below,

For i=1 to n :
    j=constant;
    for i=1 to n':
        Use J here
        .
        .
    exit for;
exit for;

In my case, I don't want to j to get the correct value of constant.

If n is between 60 to 80, how feasible is to mount a fault attack such that j gets 0 (or other small value) instead of the constant?
If it is not possible to do it for all iterations, can I make this happen for some iterations?
For simplicity, let's assume that all the compiler optimizations are turned off. Or the code is written in assembly to remove any interference from the compiler.

Please let me know if something is not clear or you need more information.
Thanks in advance. :-)

EDIT 1:
the Constant is not ZERO. But rather a 32 bit value.

EDIT 2:
The platform is a microcontroller. Let's say, Cortex-M0 or Cortex-M4

This is rather implementation dependent.

If this is compiled code (and even slightly optimized), I would expect the compiler to perform 'constant propagation'; that is, it would notice that j always has the value of zero, and so remove j (and effectively replace all instances with 0); of course, those 0's would be subject to even more optimizations (for example, a statement of t := t + j may end up being omitted entirely).

If this is interpreted code, well, it might be possible (albeit unlikely); the interpreter would most likely place a 0 in the place where the current 'j' value resides; you might be able to disrupt that write and have it write another value (without disrupting anything else the interpreter is doing); I can't think that'd happen that often.

If it's JIT (just in time compiled) code, well, it's even more complex; you might disrupt the compilation process (that is, when the JIT compiler reads it, it reads something other than j = 0, and compiles it accordingly), or you might disrupt the execution process (which, depending on how much the JIT compiler tries to optimize, might look like either of the above two cases).

However, even at the best, I would be skeptical about the practicality of introducing a fault that has the sole affect of modifying j, and has no other changes.


What is the value of the fpad used in the NMAC? NMAC uses an fpad value that is appended to the output of the Cascade function in the penultimate step of the algorithm (as depicted here, p.63) before it is sent to the last step of the NMAC algorithm to produce final tag.

I found that opad and ipad values used in HMAC are one-block constants (0x5c5c5c…5c5c and 0x363636…3636 respectively). I could not find the same for the NMAC's fpad.

What is the value of the fpad? Is it fixed and well-defined? Is it expected to be defined by the standard/cryptosystem that may decide to employ NMAC?

If you look at the original publication of NMAC & HMAC you will notice that there is no such padding in NMAC and in HMAC the constants are XORed with the key.

I don't know where this fpad comes from. It's not mentioned in the HMAC RFC either.

Found it! It is mentioned in the paper with the update security proofs. But there it is stated that it doesn't need to fulfill any requirements (p. 7). I assume that it is not defined in practice because the practical implementation of NMAC is HMAC and, as also stated in the above paper, leaving it out entirely is fine.


Encryption in popular compression file formats - 7zip, RAR, Zip When encrypting a file say with Winrar you have to enter a password. I am under the impression that this password is not stored anywhere but instead the password together with some other attributes and an IV create a hash of some sort.Is that hash stored or attached to the encrypted file ?

Then when trying to decrypt the file by means of an user fed password, is the hashing process repeated to verify that the stored hash matches the generated hash for the decryption process to begin?

I mean,there has to be something stored in the encrypted file;maybe not the password but a hash...

The hash that is generated from the password is actually the derived key, and is definitely not stored inside the file (there are exceptions). It is not compared to any data, it is used for encryption and decryption.

There does not have to be something in addition to the ciphertext for the software to determine the password is correct. In many cases, decryption follows authentication, but it is not necessary to determine anything. The file will be decrypted, and decompression will most likely fail in the case of an incorrect password, if it does decompress the data will be junk.

That is of course not optimal from a usability standpoint. It is best for the user if they know the password is incorrect. That has to be done in a manner that does not give a huge advantage to an attacker. There are a several easy methods to accomplish this, here are a few of them.

1: A checksum or hash of the compressed data is added prior to encryption. Upon decryption, the data is then hashed, and compared against the decrypted hash. If it matches, it decrypted properly. This can also be done at a block level, such as every 16KB, so the correctness of the decryption can be determined earlier.

2: A "magic string" is the more common method in older encrypted archive formats. The compressed data includes some known prefix or suffix such as 0x52 0x61 0x72 0x21 0x1A 0x07 0x00 and 0xC4 0x3D 0x7B 0x00 0x40 0x07 0x00 in the case of WinRAR, and since the position of these strings should be in an expected location, decryption of those locations will reveal the string if the password is correct and the data is unmodified. This is not necessarily the way WINRAR handles it, but is just an example.

3: A secondary data encryption key is encrypted with a key derived from the password. This allows the password to be changed without reencryption of the data, and will also allow authentication of the data key component to know the password is correct, without having to look at the encrypted data of the archive.


practical use of homomorphic encryption Are RSA and Elgamal partially homomorphic techniques? which one is better if one want to use it for practical purpose? and is there some FHE technique which can be used practically?

Yes ElGamal and RSA (without padding) are both partially homomorphic (wrt. mulitiplication). I can not think of any applications that uses the homomorphic properties of these schemes in practice. However, in terms of efficiency they are probably about equal. Evaluating the homomorphism involves just one multiplication for RSA and two for ElGamal. As for security, ElGamal is the way to go. ElGamal at least provides semantic security which unpadded RSA does not.

Wrt. FHE: the known constructions of FHE are still quite computationally heavy. However, since the first construction in 2009 a lot has happened to make FHE more efficient. At this point it is conceivable to run FHE in practice although it would be very very slow. In this paper
researches evaluated the AES circuit using FHE for example. Whether or not it would be practical to use for any given application of course heavily depends on the application.


Having CBC-MAC of a one block message, forge CBC-MAC of two blocks This whole question pertains to CBC-MAC.

Let's say $a$ is one cipher block long, and the attacker knows the MAC $M(a)$ of $a$, which was generated with a random key. How can the attacker forge the MAC of a two block message under the same key?

For example, if I have $M(a)$, can I forge $M(b||c)$, where $b$ and $c$ are both one block each?

If that is not possible, is it possible to forge $M(a||b)$ or $M(b||a)$?

Given just $a$ and $M(a)$, you can construct the message $a\,\|\,b$, where $b = a \oplus M(a)$, which gives the same CBC-MAC output $M(a\,\|\,b) = M(a)$ as $a$ itself.

Indeed, we can append the block $b$ to the message as many times as we like without changing the MAC value: $M(a) = M(a\,\|\,b) = M(a\,\|\,b\,\|\,b) = M(a\,\|\,b\,\|\,b\,\|\,b) = \dots$

The reason this works should be apparent by looking at the structure of CBC-MAC:

As the diagram shows, a message like $a\,\|\,b\,\|\,b\,\|\,\dots$ is processed block by block.  In the first step, we encrypt $a \oplus 0 = a$ with the block cipher, and obtain $M(a) = E_k(a)$ as the output.  If the message ended here, this would be the resulting MAC value.  However, if the message continues, the next block $b$ is XORed with the output $M(a)$ of the previous step and encrypted with the block cipher again.  If we choose $b = a \oplus M(a)$, then the input to the block cipher will be $b \oplus M(a) = a \oplus M(a) \oplus M(a) = a \oplus 0 = a$ again, and thus the output will also be $E_k(a) = M(a)$ again.


How does Feistel cipher create diffusion between blocks? From what I've read about Feistel ciphers, I can understand that within each block, there is both confusion and diffusion. But it is unclear to me how a Feistel cipher permutates among blocks of data. If a message is longer than the block length, how would changing one part of the message affect the encryption of other parts of the message? If L1 and R1 are considered one block, how would they affect the next blocks or the previous blocks of the message?

If a message is longer than the block length, how would changing one
  part of the message affect the encryption of other parts of the
  message?

That really doesn't depend on the block cipher in use, which may be a feistel cipher like DES or a SP network like AES, but on the mode of operation.

Now the answer to this really depends on the actual mode chosen. Note anyways: The encryption process is never message dependent, only the encryption result shows observable differences between the modes.

If you use CTR or OFB, then any change in the message bits will only affect the corresponding ciphertext bits and no other. The same applies for all modes using CTR internally (e.g. nearly all authenticated encryption modes).
For CBC, this will scramble the current block and thus also scramble the "encoded message" for the next block and thus a message change is fully propagating until the last block in a randomized fashion starting at the block of change (this also makes CBC somewhat suitable as a message authentication code aka CBC-MAC).
As for CFB, it's similar to CBC. A change in the plaintext will propagate infinitely, as this will change the current ciphertext block and thus the "xor-pad" for the next block.
ECB (which you really shouldn't use) behaves much like CTR and OFB in this regard, with a change in the plaintext influencing the ciphertext at block-level granularity instead of bit-level.

  If L1 and R1 are considered one block, how would they affect the next
  blocks or the previous blocks of the message?

This is not well-known or -defined usage of feistel networks. However, you either create a larger block cipher this way and thus "moving" the problem of the mode to a higher granularity or you're defining some sort of mode operating on two blocks of data at once, like $C_1||C_2=E_K(P_0,P_1)||E_K(P_1,P_2)$ which would suffer from similar problems as ECB but at a higher granularity level (e.g. you can detect when a pattern of three blocks repeats).


How to protect key in software I need to encrypt/decrypt data from my software by AES, the problem is how to make the AES key secure, there is no HSM, should I hard code the key in my code? It seems that a hacker can read the key data by reverse engineering the software.

If your software needs to decrypt the data and you want to prevent even those with physical access from decrypting without your software, you are basically out of luck. It is impossible to achieve purely in software, since even if a good white-box algorithm existed, an attacker could copy it into their software and be able to decrypt (without directly knowing the key, but who cares).

However, if you are willing to ignore those attacks and only protect the data against those who do not have access to the exact device and its software, you should use device specific keys, not hardcoded ones. That way even if an attacker would extract the key from their device, they would not be able to use that to attack other devices.


How to Implement Deterministic Encryption Safely in .NET I am trying to implement a deterministic encryption scheme in .NET.  This link suggests I use AES-SIV mode encryption. An alternative is to use AES-CTR [ k1, nonce, message] mode with HMAC[ k2, message] as the nonce. This is effectively the same as AES-SIV.

In .NET, there is no implementation of AES-SIV.  AES-CTR mode is also not available in .NET.  The only .NET compatible library which implements AES-SIV I can find is Miscreant .NET.  This is not FIPS validated.

Does anyone have any suggestions on how to implement a deterministic encryption scheme in .NET?

This post is a continuation of a previous post.

My Project: I have several bankers who will send the balance information for thousands of bank accounts to a server.  The account numbers will be encrypted using this scheme prior to sending to the server for security purposes.  The server deliberately will not have the private key [I'm setting up a zero-knowledge encryption scheme].  On the client side, Banker1 and Banker2 must be able to encrypt the account number in a deterministic way that allows any Banker to decrypt account numbers returned from the server.  For this reason, I decided to use HMAC(message) as the nonce for my encryption scheme and append it to the ciphertext.  AES-CTR[ k1, nonce, message] || HMAC[ k2, message] where nonce = HMAC[ k2, message].

Thank you!

You can safely use HMAC-SHA256 instead of the SIV mode custom PRF to derive the nonce/authentication tag.  There's some caveats:

HMAC-SHA256 gives a 256-bit output; you'll have to truncate it to the nonce size.
HMAC-SHA256 takes in a single bit string, so it can't distinguish the boundary between a header (unencrypted associated data) and payload (encrypted message); the SIV mode custom PRF is defined on a tuple of bit strings.  So make sure that if you compute HMAC over more than just a ciphertext, you uniquely encode the tuple of $(a, c)$ as a bit string you pass to HMAC-SHA256.
Beware limits on total volume of data for AES-SIV or similar!  For example, if your ‘AES-CTR’ takes a 96-bit nonce (as AES-GCM uses), you must limit your total volume of data to well below $2^{48}$ messages, so that there is no danger of nonce collision.  For example, you might limit it to a billion messages, $2^{30}$.

AES-SIV internally uses $\operatorname{AES}_k(n) \mathbin\| \operatorname{AES}_k(n + 1) \mathbin\| \operatorname{AES}_k(n + 2) \mathbin\| \cdots$ with a 128-bit nonce $n$, instead of what is usually meant by AES-CTR, which is $\operatorname{AES}_k(n \mathbin\| 0) \mathbin\| \operatorname{AES}_k(n \mathbin\| 1) \mathbin\| \operatorname{AES}_k(n \mathbin\| 2) \mathbin\| \cdots$ with a (say) 96-bit nonce $n$ and 32-bit block counter like AES-GCM uses.  The details don't matter that much as long as you pay close attention to the advertised adversary advantage and data volume limits.
Make sure to write known-answer test vectors for the system you think you're implementing, using another tool or another library, so that you can do quick self-tests to confirm interoperability.
Avoid the term ‘zero-knowledge’ unless you're actually doing cryptography involving zero-knowledge proofs, which are a specific technical concept involving provers, verifiers, extractors, and simulators.  Saying ‘zero-knowledge encryption’ proudly announces that you have more money for a marketing department than for a cryptography engineering department.

Even if you encrypt identifiers, there's lots of information to be learned from network structures and databases with ‘anonymized’ (really, pseudonymized) identifiers.  So ‘zero-knowledge’ is especially inappropriate here if you're only concealing the labels, not the structure of the database.
In this scenario, I would advise you to either (a) persuade your management to invest more money in cryptography engineering including hiring competent implementors and auditors, or (b) start polishing your CV, because this job is doomed.  This is not a comment on your value or intelligence as a person!  Obviously you're working hard to learn.  But it is not confidence-inspiring to hear that your management are tasking someone who has to ask a pseudonymous forum of strangers on the internet for help with cryptographic basics in order to handle private banking information for thousands of clients over the internet.


Why is AES unbreakable? Why is it said that AES is unbreakable? Brute force attacks would take years to crack it, so is it possible to crack it if the computational speed of machines increase in the following decade?

First, it's not said that AES is unbreakable, merely that none of the currently known attacks reduce the computational cost to a point where it's feasible. The current best attack on AES-128 takes 2^126.1 operations, if we had a computer (or cluster) several million times more efficient than any current computer and could operate at the thermodynamic Landauer limit, it would take 234 petajoules just to increment a counter through every key value. That's about half of the annual electricity consumption of Norway. Actually computing an AES round takes several times that much energy.

Now consider a round. A round in an optimized implementation takes 16 table lookups and 16 exclusive-or operations. Let's just say each operation is fundamental and takes the same energy as incrementing a bit in a counter, so 32 operations per round, times 10 rounds means you're at the annual electricity production of the USA.

Remember that that was with a computer operating at the minimum possible thermodynamic energy requirements. So you probably want to multiply that by a few million, at which point you're reaching the total energy from the sun which hits the earth each year.

Thus, for any practical computer the energy costs are too high, and even for a theoretical computer the costs would be large enough that it would take several years to brute force a single key, even for a very large nation.


Compression-Ratio Side Channel I'm working through the matasano crypto challenges, and I'm onto set 7, where they describe an attack on encryption/compression oracles. I am having trouble understanding the attacks, more so the logic behind the attack and am having difficulty finding any papers on it. If anyone knows about this type of attack and how it works, it would be much appreciated if someone could explain it.

For reference, here is the link to the challenge: http://www.cryptopals.com/sets/7/challenges/51

  Compression Ratio Side-Channel Attacks

  Internet traffic is often compressed to save bandwidth. Until recently, this included HTTPS headers, and it still includes the contents of responses.

  Why does that matter?

  Well, if you're an attacker with:

  Partial plaintext knowledge and
  Partial plaintext control and
  Access to a compression oracle

  You've got a pretty good chance to recover any additional unknown plaintext.

  What's a compression oracle? You give it some input and it tells you how well the full message compresses, i.e. the length of the resultant output.

  This is somewhat similar to the timing attacks we did way back in set 4 in that we're taking advantage of incidental side channels rather than attacking the cryptographic mechanisms themselves.

  Scenario: you are running a MITM attack with an eye towards stealing secure session cookies. You've injected malicious content allowing you to spawn arbitrary requests and observe them in flight. (The particulars aren't terribly important, just roll with it.)

  So! Write this oracle:

oracle(P) -> length(encrypt(compress(format_request(P))))

  Format the request like this:

POST / HTTP/1.1
Host: hapless.com
Cookie: sessionid=TmV2ZXIgcmV2ZWFsIHRoZSBXdS1UYW5nIFNlY3JldCE=
Content-Length: ((len(P)))
((P))

  (Pretend you can't see that session id. You're the attacker.)

  Compress using zlib or whatever.

  Encryption... is actually kind of irrelevant for our purposes, but be a sport. Just use some stream cipher. Dealer's choice. Random key/IV on every call to the oracle.

  And then just return the length in bytes.

  Now, the idea here is to leak information using the compression library. A payload of "sessionid=T" should compress just a little bit better than, say, "sessionid=S".

  There is one complicating factor. The DEFLATE algorithm operates in terms of individual bits, but the final message length will be in bytes. Even if you do find a better compression, the difference may not cross a byte boundary. So that's a problem.

  You may also get some incidental false positives.

  But don't worry! I have full confidence in you.

  Use the compression oracle to recover the session id.

  I'll wait.

  Got it? Great.

  Now swap out your stream cipher for CBC and do it again.

Here's the basic idea. Encryption ideally hides all information about the encrypted data. But in practice, that isn't completely true: encryption reveals the size of the encrypted data, at least within a few bytes. For example, suppose that you know that the answer is “yes” or “no”, and you see the following message encrypted with AES-CTR:

82a801950ca7aaeea0685afc86b44b70 15c0

You know it's a two-byte message (plus 16-byte IV) so it's “no”.

Now suppose that you have a fixed-size message (or more generally a message where the attacker knows the approximate size anyway, because it's given by the protocol), but it's compressed before encrypted. Compression exploits redundancy in the message. So if the encrypted message is a lot smaller than the expected size of the plaintext, that means a highly redundant message; if the encrypted message is about as large as the expected size of the plaintext, that means a message with low dedundancy.

Low/high repetition, on its own, is typically not meaningful to an attacker. But what if the attacker can inject some text into the message? Then the size of the encrypted compressed message reveals redundancy between the part that's injected by the attacker and the confidential part. Now there's room for a damaging attack.

In cryptography, and more generally in the study of computation, an oracle is a black box which receives inputs and produces outputs. The oracle's outputs may not be possible to obtain without the oracle. In cryptography, a common kind of oracle is one that knows a secret key that the attacker doesn't have, but the oracle will only respond in certain specific ways, it won't just reveal the key. For example, a basic encryption oracle is willing to encrypt any plaintext but won't decrypt anything, allowing attempts to perform chosen-plaintext attack.

In this challenge, you're asked to study a particular kind of encryption oracle which combines the submitted plaintext with some fixed confidential text, and compresses the whole message. By submitting a lot of different partial plaintexts, and measuring how the length of the whole message varies depending on the submitted plaintext, the attacker gains information about the fixed confidential part. For example, submit aaaaaaaa, bbbbbbbb, cccccccc, etc. and see how the compressed length varies to get a rough ideas of how many a's, b's, c's, etc. there are in the confidential part. Repeat with digrams, trigrams, etc. If the confidential text is some kind of password $P$, that can turn an exponential attack (try all possible passwords of the known length) into a linear attack (figure out the first character because it's the character $c$ for which $c^n P$ gives the best compression, then repeat for each subsequent character).

The basic principle has been well-known for a long time. It's mentioned in John Kelsey's 2002 paper “Compression and Information Leakage of Plaintext”. But few people thought about the concrete applications until it was widely publicized as the CRIME attack on TLS. CRIME exploits compressed TLS streams which contain both a fixed confidential part (cookie for a web page) and a varying attacker-chosen part (e.g. an injected ad that makes callbacks). If you look around CRIME, you'll find a lot of literature on the topic, including Thomas Pornin's detailed write-up before the attack was published.


How the coin flipping protocol prevent Alice from generating $ n $ from many primes? This is a question from reading the paper 'Coin Flipping by Telephone - a protocol for solving impossible problems'.
The fact that the coin is unbiased is based on the fact that if n is a product of two primes, then there should be exactly four solutions to the congruence $ x^2 = f^2 \pmod n $.
What if Alice is malicious and intentionally want to bias the result towards $ n $ is factorizable. In that case, she could make $ n $ a composite out of a few primes (let's say, 5), then there will be $ 2^5 = 32 $ solutions and it will be highly likely that picking a solution will lead to $ n $ turns out to factorizable?

Note that Step II of the protocol is titled "ALICE TESTS n" and this includes a method for Alice to verify that Bob chose n correctly. This appears on the third page of the paper.


Need Help Reversing my Encryption Algorithm So I wrote a simple encryption algorithm (Not very secure, just a starting point. I don't want criticism on it.) and I have been having trouble finding a way to decrypt the text. The algorithm is here (You may need an ASCII table to understand it):

Key = key
DecimalKey: k + e + y = 107 + 101 + 121 = 329 / 3(Length of actual key) = 110
Each Char: (charDec * keyLength) - DecimalKey

Example: p (112 * 3 = 336) - 110 = 226

Then I would subtract 127 from 226 so it will correspond to ASCII (this will be checked each time with an if statement).

My Java implementation of this is below (Hopefully code is allowed?):

public static String encrypt(String str, String key) {
    String encrypted = "";
    char[] strChars = new char[str.length()];
    char[] keyChars = new char[key.length()];
    int[] strDecs = new int[strChars.length];
    int[] keyDecs = new int[keyChars.length];
    int[] strPDecs = new int[strDecs.length];
    int keyNum = 0;
    for(int i = 0; i < str.length(); i++) {
        strChars[i] = str.charAt(i);
    }
    for(int i = 0; i < key.length(); i++) {
        keyChars[i] = key.charAt(i);
    }
    for(int i = 0; i < strDecs.length; i++) {
        strDecs[i] = Integer.valueOf((char)strChars[i]);
    }
    for(int i = 0; i < keyDecs.length; i++) {
        keyDecs[i] = Integer.valueOf((char)keyChars[i]);
    }
    for(int i : keyDecs) {
        keyNum += i;
    }
    float fTempKeyNum = keyNum;
    fTempKeyNum /= keyChars.length;
    keyNum = Math.round(fTempKeyNum);
    for(int i = 0; i < strDecs.length; i++) {
        strPDecs[i] = (strDecs[i] * keyChars.length) - keyNum;
        while(strPDecs[i] > 126) {
            strPDecs[i] -= 127;
        }
        while(strPDecs[i] < 0) {
            strPDecs[i] = 127 - Math.abs(strPDecs[i]);
        }
        if(strPDecs[i] < 32) {
            strPDecs[i] = 126 - Math.abs(strPDecs[i]);
        }
    }
    for(int i : strPDecs) {
        encrypted += Character.toString((char) i);
    }
    return encrypted;
}

So can someone help me find a way to reverse this algorithm? Sorry if I got some terms wrong, as I am quite new to Cryptography. If more explanation is required I can probably post a bit more.

Unfortunately, you have created an un-invertible cipher, that is why you can't decrypt it.

  Then I would subtract 127 from 226 so it will correspond to ASCII

Since you do charDec * keyLength this will not work when the key is longer (Imagine a 10 char key, you would get 1120 as your intermediate result, you won't get this back into ASCII range with your final subtraction).

So what you would need is to take your result modulo 256 (or modulo 127 if you want to stay in the ASCII range).
But then your scheme will basically amount to a % b = c, where to decrypt you have to recompute a, from b and c. There is an infinite number of solutions. You cannot decrypt.

You could study the design and internal operations of an existing cipher like DES, to see how they achieve invertibility and confusion at the same time.


How WPA2-PSK encryption works? When a new client tries to connect with wi-fi, it enters a password which is provided by the wi-fi owner. I wonder what is so hard to capture this password by a hacker when it is being sent to router for authentication? Client can't encrypt this password because symmetric key for encryption/decryption are not exchanged till yet. Only the password is sent which must be in plain text.

Second thing, now suppose multiple clients are connected with the same wifi. Why can't they read traffic of one-another? Are all of them using different symmetric key?

Is pre-shared key same as the  password which your wifi owner provides you to enter? If it is a password then there is no sense to call it as key because there is a huge difference between a password and a key. Passphrase=Password but both are not equal to key.

You're right that a key is not the same as a password. But a password can be used to derive a key. So some people just call the password a PSK, since it is pre-shared and is all one needs to know to derive an actual key.

In the case of WPA2-PSK, the password is indeed used to derive a key (using PBKDF, a slow hashing function). We call this key the Pairwise Master Key (PMK). Neither the password or the PMK are ever sent to the router. Instead, a four way handshake is used to ensure that the router knows that you know the PMK, and that you know that the router knows the PMK (i.e. a hacker didn't set up a fake router).

This handshake also allows both parties to derive another key, the Pairwise Transient key (PTK). This key is used to actually encrypt the connection.

So basically, no information that a hacker can use is sent over the connection. It only works if you and the router had the same initial password.

This also answers your second question. The PTK is different for every client, since it is based on the client's MAC address and some arbitrary numbers (nonces) sent in the handshake. As a result the PTKs are different for every client.

However, someone who knows the password (and therefore the PMK), and monitors the handshake (i.e. knows the MAC addresses and nonces) has enough information to reconstruct the PTK for another user. So it is possible to decrypt WPA2-PSK traffic provided you know the password.


Does ElGamal Encryption create a different key for each block sent? I ask about ElGamal algorithm. Is ElGamal algorithm used new key for each encryption process. in other word it should we use new key for each chunk? For example, if we have message that has four block each block less than $P$. Where $P$ is the prime number used in ElGamal. How many keys should be used to encrypt this message?

If you have the setting of $G$ being a prime order $p$ group (written multiplicatively) generated by $g$ and your public-secret key pair is $(pk,sk)=(y=g^x,x)$, then encrypting a single message $m\in Z_p$ amounts to choosing $k\in_R Z_p$ and computing $(c_1,c_2)=(g^k,my^k)$.

If you have a message $m=(m_1,\ldots,m_l) \in Z_p^l$, then the ciphertext would be $((g^{k_1},m_1y^{k_1}),\ldots,(g^{k_l},m_ly^{k_l}))$ with the $k_i$'s being distinct (but the public key $y$ is the same, since it is intended for one receiver).

Observe, that when using the same $k$ for two messages, say $m_1$ and $m_2$, then you can infer non-trivial information about the messages from the ciphertexts $(g^k,m_1y^k)$ and $(g^k,m_2y^k)$, since computing $m_1y^k(m_2y^k)^{-1}$ gives you $m_1(m_2)^{-1}$. Consequently, choosing a fresh randomizer $k_i$ for every block is essential.

Nevertheless, if you have to encrypt multiple blocks in practice, you would use KEM/DEM style hybrid encryption for the sake of more efficiency.

A side note: if you encrypt a message $m\in Z_p$ under distinct public-keys $y_1,\ldots,y_n$, then you can re-use the randomness $k$. This means, that instead of choosing $k_1,\ldots,k_n \in_R Z_p$ and sending $((g^{k_1},my_1^{k_1}),\ldots,(g^{k_n},my_n^{k_n}))$, you can choose $k\in_R Z_p$ and send $(g^k,my_1^k,\ldots,my_n^k)$ which saves you computation and bandwidth. You may look here for a general treatment of this so called randomness re-use in multi-recipient encryption: journal paper or the previous paper versions paper1, paper2 for further details.


$\boxplus$- key addition vs $\oplus$- key addition GOST cipher , Hight cipher and SEA cipher use key addition based on modular arithmetic addition (module key size $\boxplus$) compared to many ciphers which use arithmetic addition modulo 2 ( $\oplus$).

Q.1 what is the difference between two operations in term of security evaluation and performance across software and hardware ?

Q.2 why do not we see lots of ciphers apply  $\boxplus$ in key addition ? is it because of lack in mathematical proof?

As pointed out in the comments, one attraction of mixing $\oplus$ and $\boxplus$ is that it makes cryptanalysis harder due to non-associativity.

The differential properties of $\boxplus$ were analysed here and you can find out more by chasing citations to this paper. Massey's PHT (Pseudo Hadamard Transform) is also of interest and was used in SAFER and Twofish.

In terms of key addition using $\boxplus$, the diffusion is slower than XOR when there is no carry, with no added benefits and that is probably why it is not used widely. And the somewhat annoying fact that during decryption, to undo addition of $k$ you must subtract it.


Is it safe to use XOR to encrypt data key using master key I am implementing a hierarchical key system with a randomly generated master key and many randomly generated data keys that should be encrypted using the master key. I am wondering what the best way to encrypt the data keys using the master key is. I am thinking that if I XOR the master key with the data key, that should be simple and safe. Is it? I couldn't find any documentation on this.

XORing a master key (presumably a long term key) with data is a very dangerous idea. If any data key is leaked, then the master key may be easily calculated, thus leaking all keys. ($m$ for the master key, $d_x$ for all data keys)
$$c_x = d_x \oplus m$$
then somehow $d_4$ is leaked
$$m = d_4 \oplus c_4$$
$$d_x = c_x \oplus m$$
You'd be better off applying a block cipher (like AES) instead. One of the main properties of block ciphers is that given the plaintext and ciphertext, it is infeasible to generate the key.
$$c_x = E_m(d_x)$$
then again $d_4$ is leaked (who keeps doing that..) yet $m$ is still hidden.


How to construct Hash function of type $H:\{0,1\}^x \times G \mapsto Z_p^*$? In many cryptographic protocols design, I have seen the statement
'Choose a Hash function $H:\{0,1\}^x \times G \mapsto Z_p^*$ i.e a hash function which takes as input a binary string of finite length and a random element of some group and outputs an element of multiplicative group of prime field. How could I construct such a hash function?

Let $G$ have size $M.$ You can map the elements of $G$ in some order in a one to one fashion into $\{1,2,\cdots,M\},$ which can itself be mapped to a length $k=\lceil \log_2 M\rceil$ bitstring $(g_1,\ldots,g_k)$ where $2^{k-1}\leq M< 2^k$ by the normal encoding of positive integers.

Let $(u_1,\ldots,u_v) \in \{0,1\}$ be the binary string. Apply $H$ to the concatenated string, $$z=H(u_1,\ldots,u_v,g_1,\ldots,g_v),$$ convert the (say 512 bit) output of $H$ to an integer $z$ by the usual encoding. The final output of this process is $z\mod p.$


Why does a primitive root mod n gives a uniform distribution over n? The result from a primitive root mod n seemly has a uniform distribution over n, is it true? For instance, 3 is a primitive root mod 7, and the result seems to be randomly distributed over 1 and 6,

I wonder why is it, or should I just take it as a basic fact of our universe?

From the definition of a primitive root, as recovered by fgrieu:

  A number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$

and following-up from that:

This implies that $f(x)=g^x\bmod n$ is a bijection into $\mathbb Z_n^*$, the set of all integers smaller than and co-prime to $n$ greater than 0, i.e. $\{1,2,3,\ldots,n-1\}$ for a prime $n$. It's a bijection because every element can be reached (surjective) and no element is reached twice (injective) when iterating through all values $x$ just until (exclusive) you hit the first repetition in values. It's also a classic result that applying a bijection to a uniformly distributed variable results in a still uniformly distributed variable, i.e. bijections preserve uniform distribution.


How to prove that weak one way functions cannot have polynomial-sized ranges? I figured how to show that strong OWFs cannot have polynomial sized ranges. But I am unable to prove the same for weak OWFs.

Here is a sketch of the proof, I will let you figure out the details. Let $n$ be your security parameter. If the function $f$ has polynomial size range $\{y_1, \cdots, y_{p(n)}\}$, then its domain can be partitioned as the union of a polynomial $p(n)$ disjoint subsets $S_i$, where each $S_i$ contains all values $x$ such that $f(x) = y_i$. Now, the game is as follows: the challenger picks $x$ at random, and returns $y = f(x)$. The goal is to find a preimage $x'$.

I claim that, except with negligible probability, the set $S_i$ associated with $y$ has inverse-polynomial density over the set of all possible preimages; that is, it contains a fraction $1/q(n)$ of all preimages for some polynomial $q$. This is simply for the following reason: if it is not the case that $S_i$ has polynomial density, then the probability that the value $x$ sampled by the challenger belongs to $S_i$ is negligible, and there are only polynomially many sets.

Now, this suggests a simple algorithm for inverting the function: sample $q(n)\cdot \omega(\log n)$ random inputs $x'$ from the domain, and compute $f(x)$. Then, the probability that none of the sampled inputs belong to $S_i$ is negligible ($2^{-\omega(\log n)}$). Hence, except with negligible probability, this algorithm will invert the function $f$ successfully on $y$, contradicting the claim that $f$ is a weak one-way function.

Of course, this is just a sketch, and some additional work is required to formally prove that everything works out fine, but it should not be too hard.

A little remark on how this should be properly formalized: working with "negligible" versus "non-negligible" would not work, since there can be weird intermediate things between "negligible size" and "inverse polynomial size". The right approach is to start from a specific $1/d(n)$-weak OWF (where each algorithm fails at inverting $f$ on a random output with probability at least $1/d(n)$), and construct through the above approach an algorithm that succeeds with better than $1-1/d(n)$ probability at inverting the function. To do so, consider all sets $S_i$ with density at most $1/(p(n)\cdot d^2(n))$: the union of all those $S_i$ has density at most $1/d^2(n)$, hence the random input $x$ of the challenger will be in a set of density at least $1/(p(n)\cdot d^2(n))$, except with probability $1/d^2(n)$. When this happens, sampling $p(n)d^2(n)\omega(\log n)$ random inputs gives a preimage with overwhelming probability, hence our algorithm succeeds with probability at least $1-1/d^2(n)-\mathsf{negl}(n)$ ($\mathsf{negl}(n)$ denotes a negligible function), contradicting the $1/d(n)$-weak one-wayness.


Simulation-based security? I've been reading Introduction to Modern Cryptography by Katz and Lindell as an introduction to cryptography. The book seems to use the term 'simulator' when it talks about a game like, for instance, how it defines CPA-security as an interaction between an algorithm and a simulator.

Having looked at some crypto papers, it seems like these definitions are actually called 'game-based security definitions'. If this is the case, then what exactly is meant by a simulation-based security definition?

I don't have my copy of Katz & Lindell in front of me, but using the term "simulator" in the context of, say, an IND-CPA definition, is not exactly in line with standard usage in current literature. (But still an ok choice of words which is excusable for a textbook.)

Here's the breakdown of "game-based" vs. "simulation-based" definitions:

Both styles involve a fixed game played with an adversary.

Game-based:

Typically the game is specified as a 2-player interaction. I prefer using the names "adversary" and "challenger" as the names of the players. The game explicitly specifies a goal condition that the adversary is trying to achieve (like correctly guessing a particular piece of hidden information).

In this style of definition, we define security via a statement of the form: for all adversaries, the probability of the condition happening does not exceed some fixed threshold.

Simulation-based:

This style of definition is often called the "real-ideal paradigm," and it has its roots in the work of Goldreich-Micali-Wigderson's 1987 paper on secure multiparty computation.

In this style of definition, the adversary's goal is not explicitly defined. Instead, we define an additional, "idealized" game which often doesn't involve any cryptography. As an example, for a task such as encryption, the "real game" might involve honest parties sending encrypted messages (and the adversary gets to see the ciphertexts), while in the "ideal game" the honest parties might have a secure physical channel, where the adversary is told only that a message was sent (and so sees no ciphertext).

Then we define security via a statement of the form: for all adversaries, there exists a simulator, so that the "adversary in the real game" and "simulator in the ideal game" achieve the same effect. Achieving the same effect typically means that the joint distribution of adversary/simulator's outputs and the honest parties' outputs are indistinguishable.

The term "simulator" is reserved for "an adversary who attacks the idealized game." It's difficult to grasp at first, but think of it this way: (1) Any attack that can be done against the real game can also be done against the ideal game. (2) But the ideal game is really simple, often defined in terms of physical security assumptions in a way that makes it obvious you'd be happy with such a world.

So the main differences are: extra quantifier for the existence of a simulator, and no explicit goal defined for the adversary. The latter condition is important in contexts like secure computation, where there is a wide variety of ways of attacking a protocol, and it's hard to enumerate game-based conditions for each kind of thing that can go wrong. Or at least, it's hard to be sure you haven't missed any subtle thing that can go wrong.


How to use ECDH keypairs algorithm for encryption and decryption same like RSA keypairs without key agreement? Is it possible to use ECDH key pairs (Public and private keys) for encryption and decryption like RSA key pairs in encryption and decryption.
Say for example,
if i have RSA key pairs then i could do below things,

// Encryption
this.cipher.init(Cipher.ENCRYPT_MODE, this.publicKey);
hexEncodedCipher = this.cipher.doFinal(value);

// Decryption
this.cipher.init(Cipher.DECRYPT_MODE, this.privateKey);
hexEncodedCipher = this.cipher.doFinal(value);

So Is it possible to do the same thing for ECDH ?
And is it correct way of doing things ?

Yes. You can for instance use ECIES. As there is no encryption counterpart for ECDSA (for digital signatures) it is however based on ECDH (Diffie-Hellman key agreement). This also means that it is required to send a public key together with the ciphertext.

Basically ECIES performs key agreement in an offline fashion and then encrypts the message with the resulting secret key. This in turn means that a symmetric cipher (stream cipher, authenticated cipher or just a block cipher + mode of operation) is required. It could also mean additional overhead as the public key of the encrypting party needs to be send with the ciphertext.

Using an asymmetric primitive together with a symmetric primitive such as a block cipher or hash is called a hybrid cryptosystem.

Notes:

The sender and receiver need to configure / accept a common set of domain parameters - this are commonly parameters of a named curve.
There is also a DH counterpart called IES, ECDH is based on DH and ECIES is based on IES.
By default many implementations do not offer integrity or authenticity protection and may - in the worst case - be susceptible to plaintext / padding oracle attacks. You may want to use a signature and/or authenticated encryption instead of e.g. ECB or CBC mode encryption.
ElGamal encryption may also be used (as SEJPM notes in his comment) although this may leave you with specifying more of the underlying protocol.


Why are some websites seemingly immune to self-signed certificate MitM attacks? I recently did an experiment using MitM to gain account information (username and password) while accessing websites. I used two PCs in the scenario; one as the target, running Internet Explorer, and one as the attacker, running ettercap. One attempt (pretending to be steamcommunity.com) yielded information; the target accepted the attacker's fake CA self-signed certificate presented via the MitM attack. The other attempt (pretending to be facebook.com) didn't even allow me to add an exception for the self-signed certificate on the target machine. So the question is, why did one website allow me to add an exception while the other one didn't?

The short answer is HTTP Strict Transport Security
.

  When a web application issues HSTS Policy to user agents, conformant
  user agents behave as follows:

  Automatically turn any insecure links referencing the web application into secure links. (For instance,
  http://example.com/some/page/ will be modified to
  https://example.com/some/page/ before accessing the server.)
  If the security of the connection cannot be ensured (e.g. the server's TLS certificate is not trusted), show an error message and do
  not allow the user to access the web application.

(emphasis mine)

On websites that have it configured, many browsers will not let you add an exception for untrusted certificates.


Join Datasets While Protecting Anonymity I've run into this issue a couple of times in my career. I'll see if I can explain with an example (please ignore the fact that this is implausible in the real-world).

Suppose I sell computers, and I have account data on the person that purchased every computer I sell. I also install tracking software on every computer I sell, so that it sends me detailed information about which websites are being visited on that computer.

I would like to set up some sort of system that would allow me to merge account data with usage data in aggregate, but NOT for individual users.

In other words, I don't want to be able to know that John Doe watches cat videos and surfs porn 7 hours a day. I would think that's a violation of his privacy. However, I do want to be able to know that men are 20% more likely than women to visit news sites. This would still require the merging of account data and usage data - I just don't want to be able to see merge results for individual users, only aggregates.

Is there any way to accomplish this? Simply encrypting the key that links the account and usage data is not enough, obviously. The join could still happen. It seems like you need to encrypt usage data in such a way that it can only be decrypted when more than 1 value is aggregated. Is such a thing possible?

If you're okay with getting statistics that are not perfectly exact but noisy, a variant of randomized response could solve your problem. Instead of sending you real information about their usage, your users will send you noisy data. For a given user, you can't know for sure whether their answer to a particular question is exact or is just random (and you get a very solid property to quantify that, differential privacy). But when aggregating all responses, you can get statistics that are close to the real ones.

If you need more than binary questions, take a look at RAPPOR and the related paper — if you have enough users, you can get much more complex statistics (numerical, strings…) with a very decent precision and strong privacy guarantees.

Note that implementing such a system in practice is not trivial: you need to make sure that if you ask the same question twice to the same user (in your case, if the statistics are collected periodically) their randomized answer stays the same — otherwise, the noise cancels itself out over time and you end up learning sensitive information about them.


When will a function $f$ be a truly random function? I'm familiar with a definition of a truly random function:

$f$ is a truly random function if it was selected uniformly from the set of all the functions $f(x):\{0,1\}^{n} \to \{0,1\}^{n}$

But I'm having a struggle to figure out if a new function $g$ that was constructed with some manipulation over $f$ will be also truly random.

For example:
$g(x)=f(x) \oplus f(1^{n})$ isn't truly random because $g(1^{n})=0^{n}$ and that will happens only with a neglected probability if we were choosing $g$ uniformly.
I would be happy to get some intuition for when a function $g$ will likely be truly random and when not.
(maybe we can start with reasoning if $g(x)=f(x)\oplus f(\lnot x$) is random or not.)

definition of a truly random function

The question's definition is restricted to truly random functions from $\{0,1\}^{n}$ to itself, but has an easy and common extension to any to two finite sets.

  get some intuition for when a function $g$ will likely be truly random and when not

I like this intuitive definition: a function $g:\mathcal A\to\mathcal B$ is truly random if and only if, for any $x_0\in\mathcal A$, even with knowledge of $g(x_i)$ for all elements $x_i\in\mathcal A-\{x_0\}$, one can't predict $g(x_0)$ better than by a random pick in $\mathcal B$.

Thus to prove that a function is not truly random, one wants to exhibit a particular $x_0$, a particular subset $\{x_1,x_2\dots\}=\mathcal A'\subset\mathcal A$ with $x_0\not\in\mathcal A'$, and a method allowing to predict $g(x_0)$ with probability better than $1/|\mathcal B|$ given the $g(x_i)$ going with each $x_i$.

Hint to prove that $g(x)=f(x)\oplus f(\lnot x)$ is not truly random: one can pick any $x$ for $x_0$ (when we only need a particular one), $\mathcal A'$ can contain a single well-chosen element $x_1$ (when we could pick $|\mathcal A|-1=2^n-1$), and $g(x_1)$ then allows to predict $g(x_0)$ with certainty (when any probability better than $1/|\mathcal B|=2^{-n}$ is good enough), merely by using commutativity of $\oplus$.


Diffie-Hellman server/client generated secret size So I have implemented a client and a server performing Diffie-Hellmann, however sometimes the symmetric key is not valid?

Example:

Prime: 23
Primitive root: 5
client secret: 14
server secret: 16

This results in a faulty generated symmetric key.

Client shared key:      $${5^{14}\mod 23}=13$$
Server shared key:      $${5^{16}\mod 23}=3$$
Client "symmetric key": $${3^{14}\mod 23}=4$$
Server "symmetric key": $${13^{16}\mod 23}=8$$

So we can conclude that the provided arguments resulted in a faulty Diffie-Hellman since $4\ne8$.

What is the rule for the pseudorandom generated secret keys of the server and the client?

Javascript is used for the calculations, e.g. 13**16%23.

The issue is plain and simply: JavaScript sucks.

In this particular case the issue is that JS has no integer type, so everything is stored as a double. In particular the last calculation $13^{16}$ would yield a 60-bit integer which JS computes as ordered. However double only has 52 bits for the mantissa and so can't possibly contain the full value. So JS rounds. Then it takes the rounded number and applies the $\bmod 23$ reduction yielding some unrelated value to the one you intended to compute.


Fast encryption for Medical System? For part of my bachelor thesis (which will be involved in a commercial product), I need to build a cryptosystem that will be used to encrypt and decrypt continuous medical data that is transmitted from a patient to their doctor. The data must be encrypted and decrypted very fast in case of emergency.

Which encryption algorithm should I use? I think I should use AES. Should I involve a public key encryption to exchange shared keys? But I am afraid it may slow down the system and compromise the consistency of data transfer.

Update: The data will be sent from wearable devices on a patient to their doctor so the computing power might be limited.
My thesis will not touch on the hardware and networking aspects directly. However, they should be included in the discussion and analysis of my report.

The data must be encrypted and decrypted very fast in case of
  emergency.

  Which encryption algorithm should I use? I think I should use AES.

Indeed, symmetric cryptography (such as AES) is a good choice for performances. But a significant factor that you did not mentioned is the platform on which the algorithms will run. Does it contains cryptographic hardware accelerators? If yes, for which kind of algorithms (ECC, AES, RSA, ...)?

That will determine which algorithm will be the most relevant.

For example, if you have hardware accelerators for ECC or RSA, involving asymmetric cryptography to exchange the secret keys used for encryption should not slow down the system that much. In the other case, it can be very challenging to implement it in software with good performances on an embedded device.

This is also the same compromise for the choice of the symmetric algorithm. If you have a hardware accelerator for AES, then you should probably use it. In the other case, AES will not be the fastest algorithm. For efficient software implementations on embedded devices, you can take a look at lightweight ciphers.


Prove there is PRG that is not necessarily one-to-one We assume that there is at least one PRG .Now prove  there is a PRG like $G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)} $ such that it is not necessarily one-to-one.

Suppose $F \colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^{\ell(n)}$ is a secure PRG. Create $G \colon \lbrace 0,1 \rbrace^{n+1} \to \lbrace 0,1 \rbrace^{\ell(n)}$ as follows:

$$G(b ||s) := F(s), \quad b \in \lbrace 0,1 \rbrace, s \in \lbrace 0,1 \rbrace^n.$$

$G$ is as secure as $F$, and clearly $G(0||s) = G(1 || s)$.

To prove the "$G$ is as secure as $F$" part, consider the following proposition$^*$:

Proposition. If there exists a distinguisher $\mathcal{D}$ against $G$,
then we can create a distinguisher $\mathcal{D}'$ against $F$, such that
$$| \Pr[\mathcal{D}'(U_{\ell(n)}, 1^n) = 1] - \Pr[\mathcal{D}'(F(U_n), 1^n) = 1]| > \frac{1}{poly(n)}.$$

Proof. Distinguisher $\mathcal{D}'$ receives as input a string $z \in \lbrace 0,1 \rbrace^{\ell(n)}$. Then he simply forwards this string to $\mathcal{D}$ and outputs whatever it outputs. Since $z$ is distributed exactly like in the distinguishing game $\mathcal{D}$ expects, we have in particular $\Pr[\mathcal{D}'(F(U_n), 1^n) = 1] = \Pr[\mathcal{D}'(G(U_{n+1}), 1^n) = 1]$, and the proposition follows. $\blacksquare$

Note that the above proposition is intuitively correct when you realize that the bit $b$ is independent of the output of $G$. That is, one could think of $G$ as first running $F$ on some input $s \in \lbrace 0,1 \rbrace^n$, and afterwards drawing the bit $b$. Clearly, this shouldn't reduce the strength of $F$ as a PRG.
It should probably also be emphasized that $G$ is as secure as $F$, not more secure. That is, if $F$ has a security level of $n$ bits, then $G$ also has a security level of $n$, not $n+1$ as the longer seed could maybe lead you to believe.

$^*$Technically the proposition does not hold for $\ell(n) = n + 1$, since then $G$ wouldn't actually be a PRG. But I have ignored this above, and simply assumed the more typical case of $\ell(n) >> n$.


What exactly is bootstrapping in FHE? I have been reading about FHE lately, and it seems that bootstrapping is the core concept in order to develop FHE schemes. But, I don't exactly understand the idea behind it. I know that the schemes based on Gentry's design are noise-based, and that the noise increases with each homomorphic operation, and if the noise exceeds certain threshold, then decryption will fail. I guess bootstrapping was developed as a solution to this problem. But what exactly is bootstrapping?

I came across following definition, but I don't understand what it wants to say.

  Definition: A $\mathcal{C}$-evaluation scheme is called bootstrappable if it is able to homomorphically evaluate its
  own decryption circuit plus one additional $\mathsf{NAND}$ gate.

I know what a $\mathcal{C}$-evaluation scheme is, but what exactly it means with "homomorphically evaluate its own decryption circuit", and why the "plus one $\mathsf{NAND}$ gate"?

First off, from your question, it is not clear whether or not you understand the "circuit" part. So I'll start there. With (most) FHE schemes, you are evaluating circuits, or a bunch of gates hooked together. Often, we think of circuits in terms of and/or/not gates. It turns out, however, that you can construct circuits from other types of gates. NAND by itself is functionally complete. So, with just a single NAND gate, you can construct any circuit. That is why we need a scheme that can compute at least one NAND gate (in addition to its own decryption circuit).

As you stated, FHE schemes add noise to the ciphertext. So, you can evaluate a circuit on the input ciphertext(s), but you may add so much noise in the process of doing this that you can no longer decrypt. That is the problem we are faced with. It is important to remember that inputs to the circuits are ciphertexts, and that the output of the circuit is a ciphertext.

What Gentry gave us what a somewhat homomorphic encryption scheme. After evaluating too many gates, the noise becomes too much and we can no longer decrypt. But, he showed that by taking the decryption algorithm for his scheme and converting it into a circuit and passing the circuit a ciphertext and an encrypted version of the private key, what you would get out was a ciphertext of the same plaintext, but with the noise gone. Furthermore, the cipher allowed you to run at least one NAND gate on two ciphertexts (a couple of gates that were equivalent to a NAND) and the decryption circuit without the noise being too much.

So, let's say we can execute one NAND gate and the decryption circuit homomorphically and still be okay noise-wise.  Given a circuit like this (A NAND B) NAND (C NAND (D NAND A)) we would actually execute it as (say DEC is the decryption circuit using an encrypted version of the private key):

DEC(
  DEC(
    A NAND B
  )
  NAND
  DEC(
    C NAND
    DEC(D NAND A)
  )
)

So after every NAND you would insert a DEC to eliminate the noise. I should note that even though the last thing you evaluate is DEC, the value that comes out is encrypted.


Understanding elliptic curve point addition over a finite field I am new to elliptic curve cryptography as well as finite field theory. I am trying to understand point addition in affine coordinates.

I understand, that for an elliptic curve $ y^{2}=x^{3}+ax+b $ over $\mathbb R$ the sum of two points $P=(x_{p},y_{p})$ and $Q=(x_{q},y_{q})$
is $R=(x_{r},y_{r})$:
$$x_{r}=\lambda^{2}-x_{p}-x_{q}$$
$$y_{r}=\lambda(x_{p}-x_{r})-y_{p}$$

with the slope $$\lambda=\frac{y_{q}-y_{p}}{x_{q}-x_{p}}$$

Excluding the cases: $P=Q$ (e.g. tangent slope), $P=0$ and $Q=0$ (e.g. $R=0$). If however the elliptic curve is defined over a finite field with prime size $n$:
$$y^{2}=x^{3}+ax+b\pmod n$$

Can I just compute the slope for the "standard case" as follows (source: Slide 6)?

$$\lambda=\frac{y_{q}-y_{p}}{x_{q}-x_{p}} \pmod n$$

I understand that for an element in a finite field (f.e. point $P=(x_{p},y_{p})$) amongst other things an multiplicative inverse has to exist. However the formula for the slope $\lambda$ does only include coordinates of the point, not the element itself.

Your coordinates are elements of the finite field. For a point $P = (x_p, y_p)$ with $x_p,y_p \in \mathbb{F}_n$, where $\mathbf{F}_n$ is the finite field of order $n$ over which the elliptic curve is defined.

Since $n$ is prime, your slope will also be an element of the field $\mathbb{F}_n$. Even if $n$ was composite and $\gcd(x_q - x_p, n) = 1$, $\lambda$ is still an element of your field since an inverse of $(x_q - x_p)$ would still exist in this case. To compute the slope, you must find the multiplicative inverse of $(x_q-x_p)$ in your field $\mathbb{F}_n$. Then
$$\lambda \equiv (y_q - y_p)\cdot(x_q - x_p)^{-1} \pmod n \text.$$


Why do new versions of TLS use an explicit IV for CBC suites? SSL 3.0 and TLS 1.0 used an insecure scheme to generate implicit IVs when encrypting records in CBC mode: they used the last part of the previous record, a value that can be predicted by the attacker. This attack was demonstrated in the BEAST attack.

To avoid these issues, TLS 1.1 and later use explicit IVs, which are sent as part of the record. This avoids the attack, but also adds a 16 byte overhead to each record.

  [CBCATT] describes a chosen plaintext attack on TLS that depends on
     knowing the IV for a record.  Previous versions of TLS [TLS1.0] used
     the CBC residue of the previous record as the IV and therefore
     enabled this attack.  This version uses an explicit IV in order to
     protect against this attack.

My first idea to fix this problem wouldn't have been explicit IVs, but rather implicit IVs that get derived securely from a shared secret. TLS already defines schemes to generate arbitrary-length pseudo-random data from the master secret (see 5. HMAC and the Pseudorandom Function).

Why did the designers of TLS 1.1 decide to go with explicit IVs, instead of simply replacing the weak implicit IV scheme with a strong one? Do explicit IVs offer any advantage over well-generated implicit IVs?

TLS 1.0 uses initialization vector (IV) to refer to two different processes. TLS 1.1 introduces a new type of IV that causes an entire block to be discarded and isn't directly comparable to the old series of IVs based on CBC residue. By simply changing an operation at the beginning of a record, the hope was apparently to make implementations easy to patch and prevent strain on some systems.

Overview

IVs attempt to prevent any (key, message) pair from producing the same ciphertext on retransmission. They generally need to be unique, preferably random, but shouldn't need to be secret. (A shared secret IV is really just more key.)

There are many ways to try to use an IV. Let's start with ECB (no IV), then examine TLS 1.0 first, then examine how TLS 1.1/1.2 uses its new IV.

I. ECB

If you just broke up a plaintext into chunks and encrypted each chunk, you're going to risk retransmission of the same block if the plaintext repeats. So the way CBC improves on ECB is to XOR the previous block's ciphertext into the current block's plaintext before encryption. That's sufficient to lower the likelihood of retransmission on every block but the first, which aren't XOR'd with anything yet. So you toss in an explicit IV to the first round to get CBC.

II. TLS 1.0 with CBC

In TLS 1.0, each party might like to be able to ensure this first IV is random. So each party proposes an IV. The two IVs are then mixed together through a pseudo-random function.

  Initialization Vector (IV)
  When a block cipher is used in CBC mode, the initialization
  vector is exclusive-ORed with the first plaintext block prior to
  encryption.
  --RFC 2246

The sender then takes the IV and XORs it with the first block of plaintext. This will propagate through the block chain, it should be sufficient to ensure no repeated ciphertext blocks (at least not corresponding to repeated plaintext blocks).

While an IV proper shouldn't need to be secret, BEAST showed it isn't wise to let your attacker anticipate your next IV and also be able to shape your next chunk of plaintext.

III. BEAST

So in the BEAST attack, the attacker gets the IV for the next message, and then tricks the sender into sending some message of the form (not IV xor CPT).

Once the IV (aka 'mask') is XOR'd in before encryption, it cancels (NOT IV). CPT is now some chosen plaintext that will be encrypted (sans any mask). That's bad.

In version 1.1 of TLS, the big change was providing a fresh IV at the start of each record (every 16k bytes).

The TLS 1.0 "IV" for each block is just called a mask in 1.1. The TLS 1.0 IV for the first block can even be optionally kept. So the new IV doesn't actually replace (either of) the old IVs directly, they serve slightly different purposes and are implemented in slightly different ways.

Per RFC 4346, one of the following two algorithms SHOULD be used to generate the per-record IV:

  Generate a cryptographically strong random string R for the IV. Mask the data with R. The first cipher block will be encrypted as:

  E(R XOR Data).
  Generate a cryptographically strong random R and prepend to the plaintext prior to encryption.  In this case the mask can be fixed, or
  the CBC residue from the previous record may be used as the mask.
  Using the residue preserves maximum code compatibility with TLS 1.0
  and SSL 3.  It also has the advantage that it does not require the
  ability to quickly reset the IV, which is known to be a problem on
  some systems.

  The decryption operation for all alternatives is the same: The
  receiver decrypts the entire structure but discards the first cipher
  block, corresponding to the IV component.

The priorities were to preserve as much of the existing spec as possible, making implementation easier.

In TLS 1.1 and 1.2, they're encrypting the IV in the first block, which will be discarded by the sender. The TLS 1.0 IV is now called a "mask." By keeping the old IV as a mask, but introducing a new IV that makes a disposable block, they leave the algorithm changed as little as possible.

The parties no longer cooperate on this new, more frequently generated IV, meaning fewer code changes, and less strain on some systems.

Further reading

Tor on the BEAST attack
Slaying BEAST
Beauty and the BEAST
Security impact of Rizzo/Duong
RFC 2246 (TLS 1.0), RFC 4346 (TLS 1.1)
Block cipher modes of operation


Hardware, Handheld Password Manager I am currently working on a hardware project that will utilize the native USB and keyboard emulation capabilities of the Teensy device. Essentially, the user will store an encrypted password database on a mounted SD card that the Teensy will read and send to the host computer. This prevents the requirement of storing passwords in browsers, or certain managers.

However, I'm having a very hard time finding a secure way of encrypting it.

As of right now, I'm using the SHA256 hash value of the pin code as the AES-256 key.

Pin Code - I am currently using a 4x4 matrix keypad to allow the user to enter a pin code immediately after the device boots up. The available pins for the passcode are (14 characters): 0 1 2 3 4 5 6 7 8 9 A B C D This limited keyspace means that passwords need to be much longer in order to maintain the same amount of security. Otherwise, this is my favorite option. It also allows me to use the keypad for navigation. Adding a salt would better, but exhausting the entire keyspace is very fast.
Fingerprint - This is a neat idea that could potentially be leveraged to allow different users to share a single hardware device. However, this doesn't aid in encryption. I don't know of any implementation of a symmetric encryption algorithm using a fingerprint, or a direct derivative thereof, as a key.
YubiKey - This isn't necessarily a bad option, as it would provide a secure way of handling encryption/decryption of such devices, but that means it requires additional hardware for users. Also, I actually planned on implementing the Yubikey emulation library so the device could, itself, be used as a YubiKey.

Is there a feasible way? Or is this project flawed from the start?

I've decided to allow the user to choose between a pin code and a password.

/*
 * Various authentication types are possible within SneakerPass.
 *
 * For now, I've only implemented PIN (pin codes) and PWD (passwords). Here's how they work:
 *
 * PIN:
 *    For a pin code, the user will enter a pin that can include only what is on the keypad.
 *    THIS HAS LOW SECURITY! On a 4x4 keypad with 0-9 and A-D, that's only 14 possible keys.
 *    You'd need a 20+ digit pin code to have the same security as a 9-character password.
 *    ONLY USE IF:
 *      1) You know the implications of using reduced-keyspaces pin codes
 *      2) You can quickly remove the SD card from the SneakerPass hardware (for destruction, ingestion, etc)
 *      3) You need the speed of a pin code and reduced security.
 *
 *    Instructions:
 *      When the device is powered on, you will be asked to enter the pin code. Each key
 *      press will yield exactly one key. If you make a mistake, use '*' to erase the
 *      previous value and re-enter it. When you're finished, press '#'. If it is correct,
 *      you will enter the SneakerPass menu.
 *
 *
 * PWD:
 *    This is the preferable solution. It definiely takes more time to enter a password
 *    like you're typing a text prior to the invenion of T9. However, the keyspace is greatly
 *    expanded to include uppercase/lowercase numbers, all 10 digits, and 14 symbols.
 *    Below describes what each character maps to. You must keep selecting the same key
 *    to iterate through the values. If you are idle for 1 second, or if you select a
 *    different key, that value will be submitted.
 *
 *    KEY     NORMAL      SHIFT
 *    1       abc1        ABC!
 *    2       def2        DEF@
 *    3       ghi3        GHI#
 *    4       jkl4        JKL$
 *    5       mno5        MNO%
 *    6       pqr6        PQR^
 *    7       stu7        STU&
 *    8       vwx8        VWX*
 *    9       yz9         YZ(
 *    0       0-=         )_+
 *
 *    WARNING: IF YOU ARE USING A 3x3 PIN PAD, YOUR KEYSPACE
 *    WILLE NOT CONTAIN THESE CHARACTERS!!!
 *    A       []\         {}|
 *    B       ;'          :"
 *    C       ,./         <>?
 *    D       `           ~
 *
 *    *       [ TOGGLE SHIFT ]
 *    #       [ SUBMIT/ENTER ]
 */


Number of affine points on an elliptic curve I'm given an elliptic curve $y^2=x^3+ax+b \in \mathbb{Z}_p[x]$ (with numbers $a,b,p$ not greater than $10^6$).

I would like to find, using the naive approach, the number of affine points on the curve without the point at infinity .

My approach is to go through all $x\in\mathbb{Z}_p$ and check which of them have residue (stored in counter. Since each $x$ has either two or zero residues, I multiply the number of $x$ with residues times 2.

To return the number of affine points, the following method is used:

if isSingular(a,b,p):
    return counter*2+2
return counter*2+1

It seems to work for some cases, but not for others. Is there something special we have to consider for singular curves, and why?

The final code that worked for is shown below (published here)

# Returns number of affine points on the elliptic curve (wihout point at inf).
def countResidues(a, b, p):

    counter  = 0
    for x in range(0,p):

        # the curve in
        y2 = (x**3+a*x+b) % p

        # if x^3+ax+b = 0 (mod p), then there exists one point only.
        # i.e. the point is still on the curve even if there is no residue.
        if y2 == 0:
            counter += 1
            continue

        # if quadratic residues exists, two points are on the curve
        # i.e. the solutions to y^2 = x^3+ax+b (mod p)
        if isQuadRes(y2, p):
            counter +=2

    return counter

# Check if a curve is singular by checking that 4a^3+27b^2 = 0
# See p. 255 in course lit.
def isSingular(a, b, p):
    return ( -(4*a*a*a % p)-(27*b*b % p)) % p == 0

# Determines if there exists an x such that x^2=a (mod p), in other words,
# it will return true if the quadratic residue exists.
# Based on Euler's criterion, see course lit p. 180.
def isQuadRes(a,p):
    return squareAndMultiply(a,((p-1)//2), p) == 1

# Convert integer to binary representation
def intToBin(number):
    return '{:b}'.format(number)

# Computes number mod base
def mod(number, base):
    return number - base * (number//base)

# Calculate 'x^c mod n' using square-and-multiply algorithm.
def squareAndMultiply(x,c,n):

    # get the binary representation of c, the exponent.
    b = intToBin(c)

    z = 1

    # the main algorithm, adjusted from p. 177 from course lit.
    for i in range(len(b)):
        z = mod(z*z, n)

        if b[i] == '1':
            z = mod(z*x, n)
    return z

Course lit refers to https://www.amazon.com/Cryptography-Practice-Discrete-Mathematics-Applications/dp/1584885084


Mid-Square Hash Quality From "mid-square random number generation", let me simply define the "128-hash" as
the middle bits of the square of a 128-bit number.

Does this hash have any known collisions?

Are there any known impossible hashes?  In other words, is there a known "128-hash"
which would never occur even if all starting 128-bit numbers were tried?

Does this hash have any known collisions?

Of course; any value with 96 leading zeros (that is, between $0$ and $2^{32}-1$) will middle square to 0, hence that gives a $2^{32}$-wide collision right there.