Proving a function is or is not a pseudorandom function F_k(x) = F_k(x)||0 I have 4 functions to analyze. I need to determine if they are or are not pseudorandom and give a proof/counterexample. I'm having trouble just determining if they are - let alone proving or giving counterexamples. For reference, I'm using Katz and Lindell:
(a) $F^1_k(x) = F_k(x) \mathbin\| 0$
I think this is pseudorandom, proving by reduction:
Suppose $F^1$ is not pseudorandom. Then there exists a distinguisher $D'$ s.t. $\forall \mathit{negl}(n)$, $$\bigl|P(D'^{F^1_k(\cdot)}(1^n) = 1) - P(D'^{f(\cdot)}(1^n) = 1)\bigr| > \mathit{negl}(n).$$
We can then use $D'$ to build a new distinguisher that attacks $F$.
Consider discriminator $D$. $D$ gives the oracle input $S$ and the oracle returns output from $F_k$ or random output. $D$ adds a 0 to the end of this output and then asks $D'$ to determine if it is random or from $F'$. If $D'$ says random, $D$ says random. If $D'$ says not random, $D$ says not random. Thus:
\begin{align*}
  P(D^{F_k(\cdot)}(1^n) = 1) &= P(D'^{F^1_k(\cdot)}(1^n) = 1), \\
  P(D^{f(\cdot)}(1^n) = 1) &= P(D'^{f(\cdot)}(1^n) = 1). \tag{$*$}
\end{align*}
So:
\begin{multline*}
  \bigl|P(D^{F_k(\cdot)}(1^n) = 1)-P(D^{f(\cdot)}(1^n) = 1)\bigr| \\
    = \bigl|P(D'^{F^1_k( \cdot)}(1^n) = 1) - P(D'^{f(\cdot )}(1^n) = 1)\bigr|
    > \mathit{negl}(n).
\end{multline*}
Which contradicts that $F_k$ is a pseudorandom function.
On the other hand, clearly, output from $F^1$ always ends in 0, so the discriminator could use this fact to gain an advantage. If the output from the oracle ends in 0 he would guess that the oracle was actually $F^1$, if not he guesses that it is random. He would therefore have a non-negligible chance of getting this correct.
So, my question: is it pseudorandom or not, and where is the error in my thinking in either case?

You have shown a distinguisher for $F^1$ with high advantage that does not involve a distinguisher for $F$, so you can conclude there must be an error in your argument that that any distinguisher for $F^1$ implies a nearly-as-good distinguisher for $F$.

In particular, in equation $(*)$, you have confounded a uniform random function with the codomain of $F$ and a uniform random function with the codomain of $F^1$ by calling them both $f(\cdot)$.  It may be helpful to label the codomain sizes, or at least to call it $f$ vs. $f^1$, and clearly write out the distinction between the two and how your distinguisher acts on $f(x)\mathbin\| 0$, $f^1(x)$, and $F^1_k(x)$.


How does ZK-snark work in zcash? For a public one-way function $f()$, we can use zero proof to prove I know some secret $x$, such that the output of $x$ is a specific number $y$.

However, in zcash, I need to prove that I have some secret $x$, then $cm$ which is the commitment result of $x$ is a leaf in Merkle tree. Here, $cm$ is not a specific number and it is secret.

How should I prove this statement? I cannot figure out the circuit structure and the process using ZK-snark.

"[T]he process using ZK-snark" is to express the statement being proved as an R1CS system, produce proving and verifying public keys, produce and verify a snark-proof. A large non-trivial R1CS system is often expressed in terms of "gadgets" according to high-level "circuit structure".

A popular algorithm/proof was introduced at https://eprint.iacr.org/2016/260.pdf and implemented in libsnark. Zcash-specific "circuit" is documented in their "protocol" paper.


Any theory about period length for AES applied to itself? For example AES-128 starting with a 128-bit message $m_0$ and static 128 key $k$

$AES128(m_0,k)\rightarrow c_0$
$c_0\rightarrow m_1$
$AES128(m_1,k)\rightarrow c_1$
$c_1\rightarrow m_2$
...
continue  until $m_i$ is equal to any $m_j, j<i$

The period length would be $l = i-j$

Any theory about how big that $l$ will be?
Will it be equal for any possible $m_0$?
Is $l=j$ for every $m_0$?

(edit: in AES $j$ is always 0 because symmetric algorithm. Each cipher value has only one possible plain text)

Since AES under any fixed key is a permutation, we necessarily have $j = 0$ and $i = l$—iterating a permutation enough times will always return you to the starting point.

From Harris 1960 (paywall-free), if we model AES as a uniform random permutation, every period length $l$ has equal probability $1/n$ (Eq. 5.2) for any particular starting point, where $n = 2^{128}$ is the size of the domain, so the expected cycle length is $\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{127}$.

(Any substantial deviation from this would imply an attack on AES.)


CCA-2 key recovery attack to an homomorphic scheme? It is known that homomorphic encryption schemes are not secure against CCA attacks. This is because in the security game, the attacker may use homomorphic evaluation to cheat in the the challenges and ask for a decryption of a (homomorphically equivalent of the) challenge itself.

However, I found a key-recovery attack. The attacker adaptively asks for decryption of ciphertexts, and at the end she knows the secret key.

Is this of some actual value? Or, just because the scheme is known to be CCA insecure, the hypothesis of an attacker asking for decryptions is no longer valid?

Or else, maybe I am not aware of generic key-recovery attacks using CCA semantic security attacks? If this is the case, please point out a reference.

An interesting approach would be to determine if your CCA attack can be done in the first or in the second phase of the game. That is, before or after the challenge ciphertext is generated. This corresponds to a CCA1 or CCA2 attack, respectively.

CCA2 as usually understood cannot be attained by HE schemes, but CCA1 can. Therefore, your attack may be trivial if it is actually a CCA2 attack, or not if it is a CCA1 attack.
Anyway, in the end, it all depends on the claimed security notion of the HE scheme. If they never said it is CCA1/2, then there may be little value to your attack...It's like finding a CPA attack on textbook RSA or a CCA2 attack on textbook ElGamal.


What (if any) information can an eavesdropper infer in this scenario when using DES in OFB mode? Assume that a company wants to use DES in order to encrypt messages
to remotely control its manufacturing machines. The company uses different
messages types of 8 ASCII characters length each. The message payloads consist of
simple operational orders like starting machines, stopping them, speeding up, etc.

The company considers to run DES in OFB mode (i.e., as a stream cipher). Assuming
the eavesdropper has somehow figured out that the majority of all exchanged
messages carry the payload INACTIVE. What (if any) information can
an eavesdropper infer?

Any suggestions ???

For DES we generally assume that an attacker can find out all information as the attacker can simply brute force the key. For a more secure protocol you could use another 64 bit block cipher such as triple DES (in three key mode, i.e. with keys of 168/192 bits) or another cipher such as Blowfish. However, if you want to use a streaming cipher you could also use AES, e.g. CTR or CFB mode; OFB isn't used all that often anymore and may not be available in all runtimes.

A block cipher is deterministic. This means that any repeating 8-byte message that is directly encrypted with it will result in the same ciphertext as the previously encrypted message with the same contents. This will therefore leak information to an attacker. Modes of operations such as OFB require a unique IV for each message so that this information is hidden. So no information can be inferred if the IV is indeed unique (assuming that the message size is indeed always constant).

Notes:

Note that encryption does not automatically protect the message for integrity / authenticity. You need a MAC or authenticated encryption (e.g. GCM mode) for that;
You may need to keep in mind that you should design for key change. If you for instance use a 64 bit (8-byte) random value then you may run into collisions after many messages and this will completely destroy the confidentiality of those messages in OFB mode;
You clearly need expert help. If you cannot afford that you may want to look into using transport security such as TLS or SSH or a lightweight protocol for embedded systems instead of trying to figure our your own protocol.


How effective is quantum computing against elliptic curve cryptography? I've been reading the Wikipedia page on Elliptic-Curve Cryptography and I came across the following.

  in August 2015, the NSA announced that it plans to replace Suite B with a new cipher suite due to concerns about quantum computing attacks on ECC. Elliptic-Curve Cryptography

My question is, how vulnerable is ECC to quantum computing?

Elliptic curve cryptography is not presently vulnerable to quantum computing because there are no quantum computers big and reliable enough to matter.

But it would be vulnerable to quantum computers big enough to run Shor's algorithm.  All elliptic curve cryptography* is based on the difficulty of finding a secret integer $n$ given the scalar multiple $Q = [n]P = P + \cdots + P$ of a base point $P$ on an elliptic curve, say $E/k\colon y^2 = x^3 + 486662 x^2 + x$ where $k$ is the prime field $\operatorname{GF}(2^{255} - 19)$, a curve popularly known as Curve25519.†

On a capable quantum computer, Shor's algorithm would rapidly find a period $(\delta, \gamma)$ of the function $(a, b) \mapsto [a]P - [b]Q$.  Any such period satisfies $$[a - b n]P = [a]P - [b]Q = [a + \delta]P - [b + \gamma]Q = [a + \delta - (b + \gamma)n]P$$ for any $a$ and $b$ including zero, so that $0 \equiv \delta - \gamma n \pmod \ell$, where $\ell$ is the order of $P$, from which we can trivially recover $n \equiv \delta \gamma^{-1} \pmod \ell$.

The number of qubits, and number of gates, and running time to compute this is a small polynomial function of the number of bits in the order $\ell$, which is ~256 in typical cryptography.  Most of the quantum circuit would be devoted to computing scalar multiplication, just like computing scalar multiplication on a classical computer, costing $O(\operatorname{poly} \log \ell)$ quantum gates just like it costs $O(\operatorname{poly} \log \ell)$ time and memory on a classical computer; the magic happens in the quantum Fourier transform to find a period, which costs only $O(\log \ell \cdot \log \log \ell)$ quantum gates.

The danger today is primarily for long-term secrecy of documents and conversations in the face of future quantum cryptanalysis: TLS key agreements with elliptic curve Diffie–Hellman, for example, could be attacked with Shor's algorithm, just like finite-field Diffie–Hellman, enabling retroactive decryption of TLS sessions.  (The ‘forward secrecy’ property of DH—or really, the erasure of session keys by all parties involved—is of no use if the adversary can break the key agreement cryptography.)  For authentication and signature, e.g. Ed25519 signatures, the danger is not so much as long as you have an upgrade path for changing the signature scheme by the time Shor-capable quantum computers become feasible.

* I am not addressing isogeny-based cryptography, such as SIDH or CSIDH or SIKE, which also involve elliptic curves but which are all based on problems other than elliptic curve discrete logs—problems that are conjectured to remain infeasible to break even if Shor-capable quantum computers were practical.

† This is not the only way to attack elliptic curve cryptography.  There are many other issues to worry about, as catalogued in SafeCurves.  But in a well-designed protocol with a well-designed curve, the best known way to break the cryptography is to compute discrete logs.


Is randomsound for increasing entropy pool not doing what it is supposed to do? I am using randomsound because I thought it would be a good idea to inject some additional entropy into the entropy pools of my linux machines (clearly those machines have a corresponding sound card).

(Un)fortunately, I am a quite paranoid person, and, therefore, I am reviewing the source of randomsound in the moment and got stuck at the following code pieces:

In randomsound.c, there is the structure

struct injector {
  int ent_count;
  int size;
  union {
    int ints[128];
    BitField bitfield[512];
  } value;
} random_injector;

which is used to transfer the noise from the sound card to /dev/random

if (ioctl(randomfd, RNDADDENTROPY, &random_injector) == -1) {
  perror("ioctl");
}

However, it is said explicitly (https://stackoverflow.com/questions/17118705/using-rndaddentropy-to-add-entropy-to-dev-random) that injector must match random.h's struct rand_pool_info.

This struct is filled with data via

for (i = 0; i < depositsize; ++i) {
  bitbuffer_extract_bits(buffered_bits, random_injector.value.bitfield + i, 8);
}

which obviously only works on injector's BitField.

So the actual problem is this ints-array in injector, which is always of size 128 int and is never used in the code. The default size of depositesize is 64. And as far as I can tell, with this configuration, the entropy pool is increased by 64*8 bit and 64 bytes are written to the entropy pool. But those bytes belong to ints which is never touched.

So my main question is: Is the default configuration of randomsound always injecting the same bytes to the entropy pool? Or am I simply wrong with my interpretation of the code.

Ah ... I see. I am not a C/C++-expert.

So the union in injector "projects"ints on bitfield and vice versa. That is, the start of ints and bitfield in memory is the same. Writing on bitfield automatically writes on ints.

See http://www.wachtler.de/ck/8_7_struct_union.html (in german).

So everything is fine.


Encrypt a file once with 50 characters password or twice with 25 characters? What better Encrypt the file once with 50 characters password or encrypt it twice each time with 25 characters password.

Layering encryption doesn't effectively concatenate the keys (despite what intuition may suggest). The attacker can still attack the two passwords separately, such as by using a meet-in-the-middle attack. This means the effective key space (that is, the number of possibilities for the combined password that the attacker must try) is much lower for the double-layer scheme.

Because the keys can be attacked separately, two half-length passwords do not offer as many effective combinations as one full-length password. If each character in the password has $n$ possibilities (for example, a standard keyboard might offer 26 uppercase + 26 lowercase + 10 numeric + 30 symbols = 92 characters), the 50-character password has $n^{50}$ possibilities, whereas the two 25-character passwords only provide security equivalent to $2 × n^{25}$ possibilities. Using our example numbers, that's $90^{50}$ for the single long password vs $2 \times 90^{25}$ for the two shorter ones.

For perspective, the 50-character password has about the square of the number of possibilities for two 25-character passwords. It's a lot more.


Relative security of this polyalphabetic cipher system? A friend described this cipher to me the other day, but if it has an official name, I'm unaware of it.
The same 26 cipher alphabets that are used in the Vigenère cipher are used here, but rather than using a code word to determine which alphabet is used for a given character, the previous characters of the plaintext are used. The numerical value of every letter which comes before a given letter (a=1, b=2 etc) is added - for example, if the first letter of plaintext is H, then the 8th alphabet is used to encrypt the second letter. If the first five letters of plaintext are HELLO, then the 26th alphabet is used to encrypt the sixth letter (8+5+12+12+15 = 52, 52-26 = 26). A randomly chosen alphabet, agreed upon by sender and receiver, is used to encrypt the first letter.
How secure is this? Just relative to other polyalphabetic ciphers, like Vigenère, not modern encryption methods, which I know are arbitrarily more secure.

This is in fact the original Viginère method with a one-letter key.

The system as proposed by him, use a keyword $K$ of length $n$ for the first $n$ letters of a text, and then used the plaintext (from the start onwards) as the key for the rest. (it'a a "plain-autokey" cipher). He did not repeat the keyword, which is a somewhat weaker system, which is how his cipher is often represented nowadays.

It's still statistically weak, by autocorrelation it's easy to find the length of the keyword, and then it's reading in depth, essentially. Friedman wrote about this method on it in one of his cryptanalysis books.

Your friend's system only has a 1-letter (or one-alphabet) keyword, essentially. It doesn't matter if we use some random alphabet for the first, you just try all first plain letters and decrypt from the second letter onwards. Only one will make sense, normally.
At least Viginère' system is not directly brute forcable in that way for long keywords.


Why does Learning With Errors require a bunch of samples? Solving Learning with Errors(LWE) with average case complexity is as hard as solving the SVP with worst case complexity.

LWE requires $n$ dimensional lattice and $m$ samples of it, and Decisional-LWE is form of

$(\mathbf{A},\mathbf{sA+e}) \approx (\mathbf{A},\mathbf{r}) $

My question is why the random matrix is the form $\mathbf{A} \in \mathbb{Z}_q^{m\times n}$ ($m >> n$)?

Is $m=1$ easily solved?

I think in the case of Ring LWE, $m=1$ can work.

The number of rows in matrix $\textbf{A}$ shows the number of LWE samples and $m=1$ means the adversary has access only to one sample. This would be a naive adversary model and would not be suitable for assessing the true hardness of the Problem.
To consider a more powerful adversary model, a (seemingly) stronger definition is to assume that the adversary has access to arbitrary $m$ independent samples.

In the case of R-LWE, a single sample ($m=1$) takes the place of $n$ (correlated) LWE samples.
Even if we assume that the adversary has only one sample, then just as in LWE, finding the secret seems (intuitively) to be harder.


Convert ciphertexts of one encryption scheme to another without decryption I want to convert ciphertexts of one encryption scheme to another without decrypting them under the first scheme and then encrypting with the second scheme.
For example convert OPE encryption to Paillier without decryption. Does anyone have any idea?

I know of a proposal from Matsuo in 2007, called "Hybrid Proxy Re-Encryption", which allowed to transform PKE ciphertexts to IBE ciphertexts. This proposal is designed for a specific PKE and IBE scheme, not for generic ones. Note also that this is not what we usually understand by the term "proxy re-encryption", which is devoted to transforming ciphertexts from one key to another.

The only way to do what you ask with arbitrary schemes (e.g., OPE to Paillier) is to use fully homomorphic encryption. See these two answers (1 & 2) that could give you a hint of how to do this with FHE.


Sigma protocol for AND-composition involving the same secret Say we have two public cyclic groups $G_1$, $G_2$ of corresponding prime orders $p_1$, $p_2$, and known generators $g_1$, $g_2$.
Say $g_3$ is also a generator of $G_2$.
For publicly known $C_1$ and $C_2$, and secret $r$ and $m$, I want to prove:
$POK\{(r, m): C_1 = g_1^r \land C_2 = g_2^rg_3^m\}$
Note here that $C_2$ is a Pedersen commitment using the same $r$. How can I prove this statmement?

I know proving Discrete-Log is easy using Schnorr's identification protocol [1], proving knowledge of both factors in Pedersen commitment is also possible using Sigma protocols [2], and using a common challenge we can build AND-composition [3].
The challenge here is to prove for the same $r$.

Bonus: how can I prove it in zero-knowledge (instead of with honest-verifier-zero-knowledge)?

[1] https://pdfs.semanticscholar.org/8d69/c06d48b618a090dd19185aea7a13def894a5.pdf
[2] https://courses.cs.ut.ee/MTAT.07.003/2017_fall/uploads/Main/0907-sigma-protocol-for-pedersen-commitment.pdf
[3] https://www.math.leidenuniv.nl/~edix/oww/mathofcrypt/schoenmakers/sigma-Leiden2003.pdf

Proving this statement for groups $G_1, G_2$ of different order is a bit tricky. If the groups are of the same order, one can simply use EQ-composition (see [4], which are the lecture notes corresponding to reference [3] above).

For groups of different prime orders $p_1, p_2$, a simple $\Sigma$-protocol runs as follows. Let $n=p_1 p_2$.

Prover sends announcement $(a_1,a_2)$, where $a_1=g_1^u$ and $a_2=g_2^u g_3^v$ with $u\in_R\mathbb{Z}_n$ and $v\in_R\mathbb{Z}_{p_2}$.
Verifier sends challenge $c\in_R\mathbb{Z}_{\min(p_1,p_2)}$.
Prover sends response $(r_1,r_2)$, where $r_1=u+c\,r \bmod n$ and $r_2=v+c\,m \bmod p_2$. Verifier accepts if $g_1^{r_1} = a_1 C_1^c$ and $g_2^{r_1} g_3^{r_2} = a_2 C_2^c$.

To show special soundness, consider accepting conversations $(a_1,a_2;c;r_1,r_2)$ and $(a_1,a_2;c';r'_1,r'_2)$ that share the same announcement $(a_1,a_2)$, but have distinct challenges $c\neq c'$. Hence, we have:
$$g_1^{r_1} = a_1 C_1^c,\quad g_2^{r_1} g_3^{r_2} = a_2 C_2^c,\qquad g_1^{r'_1} = a_1 C_1^{c'},\quad g_2^{r'_1} g_3^{r'_2} = a_2 C_2^{c'}.$$
Dividing these onto each other leads to:
$$C_1 = g_1^{\frac{r_1-r'_1}{c-c'}}, \qquad C_2 = g_2^{\frac{r_1-r'_1}{c-c'}} g_3^{\frac{r_2-r'_2}{c-c'}}.$$
The witness is extracted by setting $r=(r_1-r'_1)/(c-c')\bmod n$ and $m=(r_2-r'_2)/(c-c')\bmod p_2$.

Note that the statement has to be interpreted with care: the values of $r\bmod p_1$ and $r\bmod p_2$ will in general not be equal, so the actual numbers appearing in the exponents of $g_1$ and $g_2$ may be very different from each other!

[4] https://www.win.tue.nl/~berry/CryptographicProtocols/LectureNotes.pdf


Best differential characteristic for this PRF Consider the following construction of a PRF $F: \{0,1\}^{128} \times \{0,1\}^{64} \to \{0,1\}^{64}$ on 64-bit messages and 128-bit keys.  Define $f:\{0,1\}^3 \to \{0,1\}$ by

$$f(c,x,y) = \begin{cases} \neg(x \land y) &\text{if $c=0$}\\
\neg(x \lor y) &\text{if $c=1$.} \end{cases}$$

Define an (unkeyed) round function $R_i: \{0,1\}^{1024} \to \{0,1\}^{768}$ by

$R_i(S[0..1023])$:
For $j := 0,1,2,\dots,767$, do:
   $S'[j] := f(c_{i,j},S[r_{i,j}],S[r'_{i,j}])$
Return $S'[0..767]$.

Here the $c_{i,j},r_{i,j},r'_{i,j}$ are design-time constants chosen randomly at design time, from $c_{i,j} \in \{0,1\}$, $r_{i,j} \in \{0,1,\dots,1023\}$, $r'_{i,j} \in \{256,257,\dots,1023\}$.  These design-time constants are public and known to everyone.

Finally, define the PRF by:

$F(K,M)$:
$S_0 := K||M||M||K||M||M||K||M||M||K||M||M$.
For $i := 0,1,2,\dots,47$, do:
  $S_{i+1} := K||M||M||R_i(S_i)$.
Return $S_{48}[256,257,\dots,319]$.

My question: What is the probability of the highest-probability differential characteristic in this PRF?  Of course the answer will depend on the random choice of the design-time constants, but I'm looking for a typical answer or "average-case" answer.  I am excluding related-key attacks, so I care about

$$\Pr[\Delta M \to \Delta Y] = \Pr_{K,M}[F_K(M) \oplus F_K(M \oplus \Delta M) = \Delta Y].$$

Is there a clean way to analyze this?

(Bonus question: are there any simple ways to decrease this probability significantly, without increasing the circuit depth of this construction?)

The function $f$ is biased towards the complement of the input $c_{i,j}$, assuming the other two inputs are approximately randomly distributed.

As all the values $c_{i,j}$ are public, this means that the output of the function $R_i$, and hence the function $F$ is strongly distinguishable from random (being biased towards a known bit pattern). This isn't an answer the specific question you've asked, however it would appear to be a more severe weakness than a high-probability differential would be.


Background: Secret Sharing and Multiplication Triples I know that a nearly identical question was asked in (Secret Sharing and Multiplication Triples), but I am a few points shy of asking follow up questions in the comments, so I understand if this is closed soon afterward.

First and foremost, just to clarify, the use of a multiplicative triple in this secret sharing problem is solely as a vehicle for the sharing no? I cannot see any other motivation for the triple other than facilitating the protocol.

Second, in @Guut boy's comment he mentions that the previous asker was mistaking the "notation for XOR'ing with a public value", but I don't see how this is true. The previous asker seems to imply that:
$d_a = x_a \oplus a$ and $d_b = x_b$, similarly for $e$.
If this is so then the XORing with the public value $a$ was done correctly and I still get the extra $ed$ at the end of the calculation because:
$$z_a = c_a \oplus ex_a \oplus dy_a \oplus ed$$
$$z_b = c_b \oplus ex_b \oplus dy_b \oplus ed$$
because $ed$ is not defined in $[z]$ with XOR notation brackets it is given as
$$[z] = [c] \oplus e[x] \oplus d[y] \oplus ed$$

Basically, I don't understand why the last $ed$ still exists any help is appreciated and I apologize in advance for the follow up to a previously asked question.

For the second question. The mistake was exactly that the asker did the XOR as
$$
d_a = x_a \oplus a \\
d_b = x_b \oplus a
$$
But the correct way is
$$
d_a = x_a \oplus a\\
d_b = x_b
$$
Thus to compute the shares for
$$
[z] = [c]\oplus e[x]\oplus d[y]\oplus ed
$$
You would set
$$
z_a = c_a \oplus ex_A \oplus dy_a \oplus ed\\
z_b = c_b \oplus ex_b \oplus dy_b
$$
You can check that this gives the expected result.

I am not sure what you first question is about. The purpose of the having secret shared a random multiplication triple $[a],[b],[c]$ is solely to use it later in this protocol to perform a multiplication operation (in this case AND). Not sure if this answers you question.


In use of AES CBC, can a cipher text signature be replaced with appending a known string to the plain text? Would appending a known string to the end of plain text then validating the string after decrypting adequately verify the authenticity of the cipher text?

Would appending a known string to the end of plain text then validating the string after decrypting adequately verify the authenticity of the cipher text?

No.

Here's what CBC-mode decryption looks like

Consider what happens if the attacker modifies the the first ciphertext block shown (as marked in red).

Then, the decryption of that block produces something unpredictable; that block turns into an unpredictable (by the attacker) value; the corresponding plaintext block is unpredictable.

For the second plaintext block, the modified first ciphertext block is xor'ed in with the unmodified decrypted second ciphertext block, the result is original plaintext block, except that the bits the attacker flipped in the ciphertext block will be flipped.

As for the rest of the decrypted plaintext, there are totally unchanged.

Hence, if you were to append a known string at the end, that part would decrypt properly, and hence your check would not detect the modifications done earlier.


it is possible to use quantum algorithm search (Grover's algorithm) for new searching strategies for differential and linear attacks I am trying to use Grover's algorithm to find  Differential characteristic of Feistel and SPN structures block ciphers. basically, which is Finding a good differential characteristic with high probability in the (related-key) differential attack

For example, using  Matsui’s Algorithm to Search for related-key differential
characteristics in DES-like ciphers by Alex Biryukov, Ivica Nikolic.:  FSE 2011

also using Integer programming-based method ( Differential and linear cryptanalysis using mixed-integer linear Programming ) by Nicky Mouha, Qingju Wang, Dawu Gu, Bart Preneel Inscrypt 2011.

my question

can construct Grover's algorithm to find  Differential characteristic of Feistel and SPN structures block ciphers?

Grover's algorithm is a probabilistic quantum algorithm that finds (with high probability) the unique input to a black box function that produces a particular output value, using
$$
O({\sqrt  {N}})
$$ evaluations of the function, where the fuction has domain of size $N$.
is the size of the function's domain.

Keeping in mind the fact that the spedup is only quadratic, unlike Shor's algorithm which provides exponential speedups on a different problem,  it can be applied to any search problem over a finite domain.

The normally suggested countermeasure to this algorithm in the symmetric crypto setting is quite mild: symmetric key lengths can be doubled to compensate for the risk.

Edit: For multiobject search for $\ell$ objects, Boyer et. al. in 1 proved the following theorem, which as pointed out by @poncho in the comments, is a bit counterintuitive.

Theorem: (paraphrased) Assume that $\ell/N$ is small. Then
any search algorithm for $\ell$ objects, in the form of [grover search]
takes on average $O(\sqrt{N/\ell})$ iterations in order to be successful with positive probability $>1/2$
independent of $N$ and $\ell.$

M. Boyer, G. Brassard, P. Høyer and A. Tapp, Tight bounds on quantum searching, Fortsch. Phys. 46 (1998), 493–506. See related paper on arXiv here


Token generation using Mac? I'm writing a web service that gives a unique token per client connection.  And the following are the desired properties.  I'm assuming server's issued token db is lost and untrustable client presents the token to the server.

Server should be able to tell if the token is previously issued by the server or not.
Server should be able to tell when the token was issued.

So I'm thinking generating tokens based on timestamp & count using Poly1305 so that server can see the timestamp without maintaining token db.  For example:

token1 = Poly1305("2017-04-25T21:12:32Z 1")
token2 = Poly1305("2017-04-25T21:12:40Z 2")
token3 = Poly1305("2017-04-30T22:12:32Z 3")

My questions are:

Is this safe? (including reusing key & nonce for all the tokens)
Am I doing something dumb or is there a better way?

Thank you.

Is this safe? Am I doing something dumb?

Well, I don't think it's actually safe; however why it's not safe would depend on the details of what your library has implemented within the Poly1305 function.

Straight Poly1305 isn't a MAC; it's actually a universal hash.  That is, it takes a message and a key and produces a value; however (unlike a MAC) it's sole guarrantee is that, for two different messages $M, M'$, we'll have $\text{Poly1305}_K(M) = \text{Poly1305}_K(M')$ for only a tiny fraction of the keys (and so if the key $K$ is selected randomly, this is quite improbable.

What this doesn't guarantee is that someone looking at $\text{Poly1305}_K(M)$ values for various $M$'s would have any difficulty whatsoever about recovering $K$, and for the Poly1305 function itself, recovering $K$ is easy.  Hence, if your Poly1305 function implements only the universal hash function itself, well, it's broken that way.

Now, this use of Poly1305 doesn't actually use a nonce, and so I'm not sure if you're using it straight.

To use Poly1305 as a MAC, what we do is compute the Poly1305 of the message, and then encrypt the tag with the nonce, using some cipher (AES or ChaCha, most typically).  This is safe; the Poly1305 prevents someone from producing two messages that will have the same MAC (because with an unknown Poly1305 key, that's unlikely), and the AES/ChaCha cipher will prevent someone from seeing the Poly1305 output directly (and so recovering things that way).

However, we do this encryption by taking the nonce, sending that through the cipher, and then adding that to the Poly1305 output; if we use the same nonce repeatedly, that means that we'll be adding a constant value to the Poly1305, and the attacker can adjust to that.

On the other hand, things doing this generally call out the cipher being used, say, as Poly1305-AES or Poly1305-ChaCha

So, I'm not sure why what you're doing isn't safe; but it doesn't look good.

  Is there a better way?

If you find it inconvenient to use a different nonce for every token, might I suggest using HMAC (based on some reasonable hash function, say SHA256)?  That doesn't need a nonce, and hence you're secure (or, at least, as long as you can keep the key secret).  It's not as fast as Poly1305; it wouldn't appear you care about that.


How CL-signature can act as positive & additive accumulator? A paper (http://ieeexplore.ieee.org/abstract/document/7961987/) proposes a Braavos (adaptively sound dynamic positive accumulator).

Braavos uses two other accumulators. One is adaptively sound positive additive accumulator $ACC_A$ and the other is an non-adaptively sound positive dynamic accumulator $ACC_{NA}$.

In the paper, the authors says that they uses Camenisch-Lysyanskaya (CL) signatures (http://dl.acm.org/citation.cfm?id=1766811.1766838) as $ACC_A$.

I cannot understand how CL signature can be adopted as $ACC_A$.

$ACC_A$ requires {Gen, Add, Del, MemWitUpOnAdd, VerifyMem} protocols, but in the CL protocol they does not exist. {only Gen, Sign, and Verify}

My goal is to implement Idemix with Braavos (same as the paper).

Does anyone can let me know how can I implement $ACC_A$ using CL signature.

Any signature scheme can work as an accumulator: when elements are signed with the manager's secret key, signature works as a system membership witness (positive acc). It is also additive because you can only add elements in the system by signing them, you cannot cancel a signature in the future (to delete them).


Back up an information as $n$ pieces and require exactly $n-1$ to recover it Let $X\in \Bbb F_2^p$ be some information.

How do I create $Y_1,\dots,Y_n \in \Bbb F_2^q$ so that having less than $n-1$ of the $Y_i$s gives you no information on $X$ but having $n-1$ of them allows you to recover $X$?

I first though of error correcting codes, but I don't think those would be able to ensure that having less than $n-1$ of the $Y_i$s would give no information.

My second thought was to use some kind of one time pad. For a given $r\in\{1,\dots,n\}$ (which is the index of the $Y_i$ we won't use to recover $X$), you could let $Y_r=0$, let $n-2$ of the remaining $Y_i$s be random elements of $\Bbb F_2^p$ and let the last $Y_i$ be the sum (meaning XOR) of the other ones and $X$. Then you could concatenate that for every $r\in\{1,\dots,n\}$. In other words, you use $n-2$ of the $Y_i$s to create a one time pad and use it to encrypt $X$ in the last $Y_i$. But that seems a bit brutal to me. You would need $q=np$.

I was wondering of there was a way to do it so that $q=\mathcal O(p)$ (meaning it doesn't depend on $n$).

The first thing that comes to mind is to make the $Y_r$ with three elements: its index, one random element of $\Bbb F_2^p$ and the sum of $X$ and the $n-1$ $Y_i$s that after this one including it (so $Y_r,\dots,Y_{r+(n-2)}$, where you reduce the indices modulo $p$ in the obvious way). This way, when you have $n-1$ of the $Y_i$s, you can find which index $r$ which is missing and then sum the third part of $Y_r$ with the second part of $Y_r,\dots,Y_{r+(n-2)}$ and recover $X$. That would be $\mathcal O(p\log n)$ (because of the index) which is acceptable. But I feel like you could recover part of the message with less than $n-1$ of the $Y_i$s because you kind of used the one time pad several times.

Edit: I'll use it in https://github.com/xavierm02/combine-keys

What you describe is known as Threshold-secret-sharing, for which a good candidate is the threshold version of shamir-secret-sharing.
In particular, for your use case I would recommend implementing an "n-1 out of n threshold sharing scheme".

Shamir Secret Sharing $(n,k)$-threshold scheme.
Shamir's $k$ of $n$ threshold sharing scheme is based on the observation that a $k-1$ polynomial over a field is determined by $k$ points, and yet cannot be determined with fewer than $k$ points. If we let $k=n$ then this reduces to Shamir's original sharing scheme.

Choose $q$ such that $\mathbb F_q$ be a finite field (the size of $q$ will specify how secure the scheme is).
Sample $a_1,\dots,a_{k-1}$ uniformly from $\mathbb F_q$.
Let $a_0=s$ be the secret you wish to share.
Let $f(x)=\sum_{i=0}^{k-1} a_i x^i$.
For each of the $n$ people, let share $i$ be the pair $(i,f(i))$.

To decrypt, we use polynomial interpolation to reconstruct the polynomial $f$, which requires at least $k$ shares, and then simply read off the coefficient $a_0$.
Security:
No information about the $a_0$ coefficient is leaked until the polynomial is completely recovered, the scheme is informationally secure. As such, the size of the finite field will be the same as the security margin presented, because the best attack will be to directly guess the secret. nb: This assumes that an adversary must treat the secret as if it were uniformly sampled from all possible field elements - obviously if your secret $s\in\{0,1\}$ your security is bounded by that!


Encrypt a file in a way that decryption requires every recipient's cooperation The best related concept I can think of is the two-man rule. https://en.wikipedia.org/wiki/Two-man_rule.

To put it simply, n people are required to give their authorization before a system / secret can be used.

If I have a file (say an encrypted password or private key) that allows me to access a server with sensitive information. I will require a key from the data privacy officer and the lead engineer.

Does anyone know a way I could implement this using existing tools and maybe some systems language (read: go) to tie it all together?

I'd imagine there are multiple systems involved in making this work, but what I'm mostly curious about the cryptography.

Thanks in advance!

There are various ways to do this, but one of the most flexible ways is to use a secret sharing scheme.  These are mathematical methods that allow a secret value (such as a symmetric encryption key, or even an entire file) to be split into multiple "shares", such that a certain number of shares (which does not necessarily need to be all of them) is required to reconstruct it.

For example, a simple $n$-out-of-$n$ secret sharing scheme like you describe can be obtained by taking $n-1$ random bitstrings (from a cryptographically secure true RNG) of the same length as the secret, and constructing the $n$-th share by bitwise XORing together all $n-1$ other shares and the secret.  It's not hard to prove that this last share is then also indistinguishable from random, and in fact that knowing no set of $n-1$ or fewer shares yield any information about the secret (other than its length, that is).  But if you have all $n$ shares, you can just XOR them together to get the original secret value back.

Once you've split the secret into $n$ shares, you can of course then e.g. encrypt each share with a different person's key.  Or you could just directly send each share to the person it belongs to for safekeeping, if that's more practical.

The real power of secret sharing schemes, however, is that you don't necessarily have to require all shareholders to cooperate in order to reconstruct the secret.  Specifically, there exist efficient threshold secret sharing schemes, such as Shamir's scheme, which work basically just like the simple XOR scheme described above, but allow the secret to be reconstructed from any subset of $k \le n$ shares, where $k$ is an arbitrary threshold set when the shares are created.

The mathematics involved are slightly more complicated than in the basic XOR scheme above, but they provide essentially the same guarantee: any $k$ shares uniquely determine the secret, whereas $k-1$ shares do not reveal any information about it whatsoever (not even if the attacker has infinite computing power!).

For example, to implement a general "two-person rule" for accessing some sensitive data (which could e.g. be a key to something else), you could use Shamir's secret sharing with a threshold of $k = 2$ to split the data into $n$ shares, and distribute these among all authorized persons.  That way, any two authorized persons could combine their shares to reconstruct the data.  But as far as a single person acting alone is concerned, their share is just a random number that reveals absolutely nothing about the data unless combined with another share.

There are also hierarchical secret sharing schemes that allow more complex access structures, such that one could require e.g. "any two people in group $A$ and any three other people in group $B$" to access the secret.  I could go into more detail, but we actually have an entire secret-sharing tag with plenty of good questions and answers that you might want to take a look at.


Seemingly simple decryption question Forgive the very novice question, but...

Given an algorithm which, upon inputting an unchanging 4-character string, generates a variable 6-character string, but having no idea what the algorithm is other than it is at least partially based on the date, is it possible/practical to discover the algorithm based on 15 or 20 previous results?  I guess this would be "known-plaintext"?

How would you go about experimenting with this?  Are there programs or calculators out there that would attempt to "crack the code" given a list of right answers?

Given the small number of input characters and output characters, each limited to the letters of the alphabet, it doesn't seem to me that it would be a terribly complex or unbreakable algorithm.  Still, I'm a novice, I don't know where to start.

Is it doable or am I wasting my time?

Additional info:  The four-character code is constant per machine; on another machine the four-character code would be different, but each machine would have an unchanging four-character code.  The six-character code, generated using the four-character code, allows a machine access to the device for a variable length of time, after which point another six-character code is required.

The four-character code is always four characters; the output code always six characters.  All alphabet, no numbers or symbols.  I don't think it's case-sensitive.  I do not know if the codes expire if not used immediately.

So give it up, huh?  So even if I had a thousand previous results, still not doable?

Are there additional clues I could try to find out that would turn it from not doable to maybe doable?

If I interpret your question correctly, your unchanging 4-character input is probably just a PIN code that unlocks the use of the device. In this case, the sequence of 6-character strings is a series of one-time password to unlock access to a remote device.

Under this assumption, they is no simple way to predict the rest of the sequence. Indeed, it is easy to design secure device of this type. A simple solution is to output a hash of some inner state and then update the state using a secret key algorithm keyed with a key shared by the device and its remote partner. The most difficult issue is to solve desynchronization problems (e.g. what happens if you advance your local device 1000 times without transmitting anything, will the 1001-th code work ?)

Of course, it is also possible to construct insecure devices of this type. So if you have luck your exact device might be attackable.

However, the short answer is: no, in general, this is not doable.


What does "sequential memory-hard" mean? I found this term in Scrypt's paper.  I have several questions about its meaning, ranging from how to parse it, to theoretical bounds:
Q1: How to parse it?

Is it read (sequential memory)-hard?
Or sequential (memory-hard)?

Q2: What does it mean?

Does it mean that as space is linearly reduced, then penalty is that is exponentially increased?
Can we tell what is that exponent?  Or does suffice to simply be an exponent, regardless of which exponent?
In current practice, can we say something more specific about what that exponent for state-of-art functions beyond just "it's exponential"?  I think it is within reach to make more specific claims.
Ideally, is there any theorem that shows an upper bound for this exponent?  E.g. can we say, for every reduced single unit of memory, amount of computation performed doubles?  Tripples? Quadruples? ...?

Q3: Any better name?

Is the name used in Scrypt's paper still the most accurate name?
Is there a better name for it that the cool kids like to use nowadays more?  In Argon2's paper, as well as Here, it seems to be called memory-hard.  Does it mean that memory-hard is the better name to adopt?  E.g. what do the coolest gurus in top cryptographic journals tend to use?
Optional: any reason the Scrypt paper didn't call it memory-hard?  Or was it just the randomness of life?

Appendix
I did look at previous related answers, and I found these:

This only asks about such functions in relation to another function.  Thus doesn't dig deep into what such functions are in themselves.
This only asks about the motivations of such functions.
This asks whether his function is a good one among such functions.

The Scrypt paper here defines memory-hard and sequential memory hard, and accordingly explains why one was used over the other.

Definition 1. A memory-hard algorithm on a Random Access Machine is an algorithm which uses $S(n)$ space and $T(n)$ operations, where $S(n) \in \Omega (T(n)^{1-\epsilon})$

Definition 2. A sequential memory-hard function is a function which  (a) can be computed by a memory-hard algorithm on a Random Access Machine
in $T(n)$ operations; and  (b) cannot be computed on a Parallel Random Access Machine with $S∗(n)$ processors and $S
∗(n)$ space in expected time $T∗(n)$ where $S∗(n)T∗(n) =\mathcal{O}(T(n)^{2-x})$ for any $x > 0$.

Put another way, a sequential memory-hard function is one where not only the
fastest sequential algorithm is memory-hard, but additionally where it is impossible
for a parallel algorithm to asymptotically achieve a significantly lower cost. Since
memory-hard algorithms asymptotically come close to using the most space possible given their running time, and memory is the computationally usable resource
general-purpose computers have which is most expensive to reproduce in hardware
, we believe that, for any given running time on a sequential general-purpose computer, functions which are sequential memory-hard come close to being the most
expensive possible functions to compute in hardware.


Can AES GCM mode detect an incorrect key and refuse to decrypt? I understand that AES in GCM mode produces an authentication tag that is used to ensure that a tampered with cipher text is not decrypted. However, if I pass the wrong key will AES in GCM mode detect that I am using the wrong key and give me an error message or will it give me back garbled data because I used the wrong decryption key?
Does the AES-GCM spec say that an error will be raised if the wrong key is used?
UPDATE The error does not have to indicate that the key was wrong, just that decryption should fail so incorrect clear text is not returned to the caller.

An AES-GCM-encrypted message is obtained per an encryption key $K_0$. As for any correct implementation of AES-GCM, we assume that legitimate encryption of multiple ciphertexts with $K_0$ uses $\text{IV}$ such that the counters (obtained by increment of the $\text{IV}$) do not overlap; and that the implementation of decryption gives an error message when the authentication check fails.

will AES in GCM mode detect that I am using the wrong key and give me an error message (..) ?

No, with strictly only what's stated. It is possible to exhibit a ciphertext (including $\text{IV}$) and two distinct keys $K_0$ and $K_1$ that both decipher successfully (and a plaintext that, encrypted with key $K_0$ and $\text{IV}$, encrypts to the ciphertext including $\text{IV}$ and authenticator tag, thus matching the wording in the above re-statement of the question).
But yes, if the ciphertext was prepared legitimately (which was my assumption in a first version of this answer). An attack against a given ciphertext, aiming at exhibiting $K_1$, has cost $p\,2^k$ AES encryption for probability $p$ of success and $k$-bit authentication tag, even if multiple ciphertexts are available. Prepared legitimately holds at least if one (or both) of the following holds:

The key $K_0$ is chosen uniformly at random independently of $\text{IV}$ and the plaintext (even if the plaintext, $\text{IV}$, and $K_1$, are chosen maliciously). That includes any case where $K_0$ is kept secret from adversaries at least until production of the plaintext, which is a standard assumption.
The $\text{IV}$ is chosen uniformly at random independently of $K_0$ and the plaintext (as is the case in some but not all legitimate uses of AES-GCM encryption); that's even if the plaintext, $K_0$, and $K_1$, are chosen maliciously.

Argument: from the structure of GCM it can be shown, under a model of AES as an ideal cipher, that the AES-GCM authenticator tag is a PRF of the key and $\text{IV}$, for any fixed message (plaintext, or ciphertext excluding $\text{IV}$ and authenticator tag).

Conclusion: AES-GCM encryption with secret key $K_0$, or with random unpredictable $\text{IV}$, makes it infeasible that later (including if $K_0$ leaks) anyone could find (much less encounter by accident) another key $K_1$ that allows decryption of the unmodified ciphertext (including $\text{IV}$ and authenticator), yielding almost certainly corrupted deciphered plaintext. However, that can be defeated by the party choosing $K_0$/doing the encryption/choosing the message; and the essential unmodified ciphertext hypothesis is artificial, for it goes against the rationale of using authenticated encryption.


Can I generate OTP secrets by using a hash? Since I learned about one time  pads in last security lecture, I'm quite fascinated how easy the concept is, but how it still is absolutely safe.

Learning from implementing a multi time pad  attack, an OTP is not safe if the key is reused. I understand why this is the case. Also encoding large messages requires a large secret, so I tried to think about, how to solve this.

This is what I came up with:

Consider we have a Hash Function $H:= A^k \rightarrow A^l$ were $A$ is an alphabet, and $k$ and $l$ are arbitrary lengths. For example  we can use md5 for my purpose.
Next we have an secret $s_0$ with a length that is not sufficient to encode our message $m$. What if when I run out of characters/bytes of my secret to encrypt my message, I'll take the next characters/bytes from $s_1 = H(s_0)$. I could then repeat that process until I have a sufficient length of the secret $s_0 + s_1 +  ...$.

Also a possible variant would be to generate $s_{i+1}$ by taking the concatenation of the hashed characters of $s_i$.

Example: $m = thistextistoolongforthesecret$ , $s_0=short$. I can encrypt t with s, h with h, and so on until I have no more characters left for the e. I would calculate $s_1=4f09daa9d95bcb166a302407a0e0babe$ (md5). Then I could use the 4 of $s1$ for encryption of the e.

What are the security implications of this? I have the feeling that this has some serious downside, that eventually will lead to a possible multi time pad attack, but I can't show any reason for that. My knowledge is only superficial, since I only heard about OTP 2 days ago.

Say the adversary is giving you $m_0$ and $m_1$, two arbitrary messages. You draw a random $sk$ and a random $b\gets\{0,1\}$ and output $E_{sk}(m_b)$.

So the adversary takes $ct=E_{sk}(m_b)$ and computes the XOR between the first $n$ bits of $ct$ and the $n$ first bits of $m_0$ (where $n$ is the original key length). Then, he does the same thing for $m_1$, so now he has two options for the secret key, $sk_0$ or $sk_1$. So far everything is good, because they are both equally possible, but now the problems begin: the adversary computes $md5(sk_1)$ and $md5(sk_2)$ and XOR the results with the bits $ct[n+1:n+\texttt{md5-length}]$. With a very high probability, only one of the options will make sense, meaning it would be the bits $m_i[n+1:n+\texttt{md5-length}]$ of some message, so he will know what you encrypted.


IND-CCA Security of a encryption scheme which is combination of two schemes I have two public key encryption scheme $\Pi_0$ and $\Pi_1$ and one of them is IND-CCA secure, another one is IND-CPA secure. Let $\Pi$ be a public key encryption scheme, which is a combination of $\Pi_0$ and $\Pi_1$. As IND-CCA security implies IND-CPA security, so $\Pi$ is IND-CPA secure.  Is $\Pi$ is IND-CCA secure? How to prove or disprove it?

You should really specify how are they combined. If it is just composition, you should analyze the cases $S_1=\Pi_0\circ \Pi_1$ $S_2=\Pi_1\circ \Pi_0$, $S_3=\Pi_0\circ \Pi_0$ and $S_4=\Pi_1\circ \Pi_1$, where $\Pi_0$ is CCA and $\Pi_1$ is CPA. If you manage to prove a security type all four cases, you may establish rules for a general composition. However, you may also consider the meet in the middle case when composing if that is your definition of IND-CCA.


RSA - twin primes, two modulus I'm working on this problem. I'm given

$\begin{align*}
n_1 &=pq\\
n_2 &=(p+2)(q+2)
\end{align*}$

where $p$ and $q$ are twin primes, i.e. $p$ is prime and $p+2$ is also prime; similar for $q$.

Also, I have a fixed value of $e$ and a message $m$ encrypted with $e^{-1} \bmod (p-1)(q-1)$ and then encrypted with $e^{-1} \bmod (p+1)(q+1)$.

How can I get $p$ and $q$?

As already hinted at in the comments, this is really just a matter of getting an equation in one unknown and then solving for the unknown. We start with:
$$\begin{align}n_1&=p\;q\\n_2&=(p+2)(q+2)\end{align}$$
One method is to turn the later equation into $q = \frac{n_2}{p+2} - 2$ and substitute in the other equation, to get an equation in one unknown:
$$n_1 = p\left(\frac{n_2}{p+2} - 2\right)$$

Multiplying both sides by $p+2$ and getting everything on one side, we obtain this equation, implied by given equations:
$$2p^2 + (n_1 - n_2 + 4)p + 2n_1 = 0$$

This is a quadratic equation with unknown $p$ and coefficients computable from the givens $n_1$ and $n_2$. One of the solution will be $p$, and the other will be $q$ (since $p$ and $q$ have symmetrical role in the problem). Note that this math is not using modular arithmetic, it is just algebra of the variant learned in grade school for real numbers, which also works for integers.

As an example, suppose $p = 5, q = 11$ which means $n_1 = 55, n_2 = 91$. Plugging into our equation we get $2p^2 - 32p + 110 = 0$. With such small numbers, we can plug this into a quadratic equation solver and voila, we get values $5$ and $11$ as roots, and have successfully factored $n_1$, and $n_2$.

The rest of the problem only asks performing textbook RSA decryption knowing public key, having factored the public modulus.


Semantic security of the OCB mode As defined in the specification of OCB, the tag depends only on the checksum (that is just the binary sum of plain blocs), so if we construct two messages that have the same sum (this is very easy to do), we can get two different ciphertexts that have exactly the same tag.

So we can easily mount a ciphertext integrity attack against OCB and the game of the semantic security can be win with a probability one (we can construct a new valid ciphertext using a previously obtained one).

What am I missing that OCB is still considered secure?

I finally found the problem: there is an error in the course about the OCB mode presented in Coursera Cryptography 1 (by Pr. Dan Boneh). When I consulted the official specification of the OCB mode (RFC 7253), I found that the value used for the tag construction is the number of blocks m and not 0 as presented in the course (see the figure below), otherwise the scheme becomes insecure (an integrity attack can easily be mounted against the semantic security game!).


Can I shorten the large ECDSA public key output file from OpenSSL? I am working in a very bandwidth restricted environment where I from time to time have the need to distribute public keys. The distribution happens in bit format, so there is no need for encoding, at best I would like all my data "raw".

It is my understanding that the public key, in compressed form, takes up the space of the curve size+1, e.g. 160 bit curve gives 161 bit public key. However, the output from OpenSSL gives me a much larger key size, e.g. 904 bits for the secp160r1 curve. I reckon there must be a lot of metadata involved.

Edit: I removed the "--- Public key starts here ---" etc and that almost cut the file in half ahem. But still there are 60 bytes/480 bits, a lot more than what I would think of as necessary.

Can I somehow reduce this size, getting rid of metadata? For example extract the key components of the signature and reassemble it in a compatible format on the receiver side? I assume DER encoding also adds overhead, but hardly this much?

Here arethe commands I use, in Cygwin:

$ openssl ecparam -out private.pem -name secp160k1 -genkey
$ openssl ec -in private.pem -pubout -conv_form compressed -out public.pem

Asn1parse to the rescue.

Most of the overhead is from the base64 encoding and the PEM header and footer.

The raw size of the compressed form ASN1 encoding is just 44 bytes for my dummy key.

And 22 of those bytes are for the 161 bits of the actual public key.

$ openssl asn1parse -in compressed_public.pem -i -dump
    0:d=0  hl=2 l=  42 cons: SEQUENCE
    2:d=1  hl=2 l=  16 cons:  SEQUENCE
    4:d=2  hl=2 l=   7 prim:   OBJECT            :id-ecPublicKey
   13:d=2  hl=2 l=   5 prim:   OBJECT            :secp160k1
   20:d=1  hl=2 l=  22 prim:  BIT STRING
      0000 - 00 03 ca f2 7b b8 4c 3c-99 b2 7a 6f fb f3 cf 8f   ....{.L<..zo....
      0010 - 95 b8 77 61 76 dc                                 ..wav.

And if you turn the PEM encoding into raw DER encoding like so...

$ openssl ec -pubin -in compressed_public.pem -outform der -out compressed_public.der
read EC key
writing EC key

...then 44 bytes is the size of your file.

$ stat compressed_public.pem | grep Size
  Size: 113             Blocks: 1          IO Block: 65536  regular file

$ stat compressed_public.der | grep Size
  Size: 44              Blocks: 1          IO Block: 65536  regular file

And just for another look at this: using "dumpas1n", you can see exactly where those 22 non-pubkey bytes went:
(Note: dumpasn1 skips the "00" byte at the beginning of the 22 byte "BIT STRING" object and does not display it. And openssl asn1parse does not.)

$ dumpasn1  | head -n2
DumpASN1 - ASN.1 object dump/syntax check program.
Copyright Peter Gutmann 1997, 1998.  Last updated 27 July 1998.

$ dumpasn1 compressed_public.der
   0 30   42: SEQUENCE {
   2 30   16:   SEQUENCE {
   4 06    7:     OBJECT IDENTIFIER ecPublicKey (1 2 840 10045 2 1)
  13 06    5:     OBJECT IDENTIFIER '1 3 132 0 9'
            :     }
  20 03   22:   BIT STRING 0 unused bits
            :     03 CA F2 7B B8 4C 3C 99 B2 7A 6F FB F3 CF 8F 95
            :     B8 77 61 76 DC
            :   }

0 warnings, 0 errors.

So to answer your question:

  Can I somehow reduce this size, getting rid of metadata?

Yes. You could cut the size down to just the 22 bytes (or 21 bytes if you exclude any leading 00 bytes).

(If you want yet another tool to look at ASN1: Here's that key in asn1js online.)


Decryption using affine cipher I am doing probabilistic decryption, I was given that A and E had the highest frequency count in the plain text. H and X have the highest frequency in the encrypted text. So in solving for a and b I got a=4 and b=7, but that a won't work because there is no inverse of 4 in mod 26 (which I need for the decryption parameters) What can I do from here?

Maybe you should read up on solving congruences modulo composite moduli like $26$.
There are some examples here, or slightly easier here etc.

Note that A,E,H,X correspond to the integers $0,4,7,23$ respectively.
Suppose that $c(x) = ax + b$ where $x$ is the plain letter and $c(x)$ the corresponding encryption, $a,b \in \mathbb{Z}_{26}$.

If we assume $A \to X, E \to H$, we get the equations (for $a,b$, using $x=0,4$):

$$
\begin{align}
c(0) =& 23 \equiv a\cdot 0 + b \bmod{26}\\
c(4) =& 7 \equiv a \cdot 4 + b
\end{align}
$$

which gives $b = 23$ and $4a + 23  \equiv 7 \bmod{26}$, or $4a \equiv -16 \equiv 10 \bmod{26}$.

This last equation has two solutions as $\gcd(4,26) = 2 | 10$, and we find they are $a=9$ and $a=22$. Only $a=9$ has an inverse modulo $26$ namely $3$ ($3\cdot 9 = 27 = 26 + 1$). You can then find the decryption formula and try other letters to check whether the assumption $A \to X, E \to H$ was correct.

If however you'd assume $A \to H, E \to X$ we'd have gotten the equations:

$$
\begin{align}
c(0) =& 7 \equiv a\cdot 0 + b \bmod{26}\\
c(4) =& 23 \equiv a \cdot 4 + b
\end{align}
$$

which gives $b=7$, and $4a \equiv 16 \bmod{26}$ and this last equation has two solutions again: $a=4$ and $a=17$, of which only $a=17$ is a potential candidate as it has an inverse in $\mathbb{Z}_{26}$ of $23$. So again compute the decryption formula for this case to check this hypothesis on other letters as well.

Note that if there is at least $1$ solution to $4a = x$ modulo $26$ it has $2$ that differ by $13$, corresponding to the theory I referred to. So you either have $0$ or $2$ solutions to such linear equations in one variable. This is why you're better off working over prime fields (add a space as an extra character and some more to work module $29$ or $31$ or some such idea).


Seeding the Fortuna PRNG for the first time I am trying to understand how the Fortuna PRNG should be seeded correctly for the first time.

Let's assume that we do have a large-enough seed file available, but not any entropy sources during first boot. To my understanding, I would:

initialize the PRNG (section 9.5.4)
load the seed file (section 9.6.2)
produce random numbers (section 9.5.5)

The last step would produce an error: the check on the end of the pseudo-code in section 9.5.5 would assert that ReseedCnt is zero: PRNG not seeded yet.

When I track the usage of ReseedCnt, I observe the following:

ReseedCnt is set to zero during initializiation.
When reading the seed file, ReseedCnt is untouched.
When generating random data, ReseedCnt is incremented when enough entropy is available in Pool[0] and enough time has passed (not the case during first boot).

So, is the paper missing some steps on what to do in this situation? Section 9.6.6 about first boot explicitly states: 'Having an outside source of randomness to create the first seed file is probably the best solution.'

You have to appreciate that Bruce and Niels' paper isn't source code. They wrote "We assume there are several sources of entropy in the environment" and "feel free to
choose AES (Rijndael), Serpent, or Twofish for this function".  It's a bit of a concept paper without a hard implementation.  That's been left to others.

An example of this is on Silicon Labs micro controllers.  That implementation is ultimately seeded with real entropy from reading the internal temperature sensor.  Those tend to jitter somewhat, creating true randomness. Even they though add this proviso: "The user is encouraged to implement additional entropy
sources."  The implementation of FreeBSD palms this off to various device drivers to call the random_harvest_*() function themselves.

This entropy input step is outside of the Fortuna construct. They clearly couldn't predict where Fortuna would be running so it was correct to leave this to particular implementations.  It could easily be avalanche diodes, keyboard key scanning firmware or even the internal temperature sensors that are scattered throughout desktop motherboards these days.


How to compromise the privacy of NaCl encrypted messages, when nonce is reused? I want to know to how break NaCl encryption when a nonce is used more than once for a given key private key. According to PyNaCl docs:

  It is VITALLY important that the nonce is a nonce, i.e. it is a number used only once for any given key. If you fail to do this, you compromise the privacy of the messages encrypted.

NaCl's public key authenticated encryption uses a stream cipher for symmetric encryption (after key derivation using Curve25519). Like all synchronous stream ciphers, it produces the same keystream when you use the same nonce.

That means you are in the same position as when a one-time pad has been reused. (Having a known plaintext would make things even easier than mentioned in that link, since it would just reveal (a part of) the keystream.)


Elliptic Curve Cryptography - When to use p and when to use n Im currently playing around with ECC, in particular the ECDSA scheme on a brainpool P256R1 curve. While implementing the signature verification function, I've stumbled upon a few problems.

So far I've understood that there's a prime $p$ and the order of the elliptic curve $n$ (such that $n * G = \mathcal{O}$).

For the modular arithmetic functions inside my ECDSA verification function we have to use the group order $n$. But for our elliptic curve functions such as point addition and point doubling we need to use $p$. I was wondering why its the order for curve operations and the prime for the other in order to make the system work.

A possible analogy is two layers in a communication protocol, with $p$ and $n$ the maximum packet payload for the lower and upper layer. They need not be equal (in communication protocols, typically due to overhead added by the upper layer, reducing its maximum packet payload compared that of the lower layer). We use limit $p$ or $n$ depending on if we deal with payload of the lower or higher layer.

In the question's example of ECDSA with a prime field, the lower layer is the base field $(\mathbb Z/p\mathbb Z,+,\cdot)$ with $p$ prime, where $+$ is modular addition modulo $p$, and $\cdot$ is modular multiplication modulo $p$.

The higher layer is the elliptic curve group $(E,+)$ (or a subset of that generated by a particular $G$, but for the curve considered there is no such restriction and I discard it for simplicity). Elements of $E$ are points of the elliptic curve (when using rational coordinates: defined by two coordinates in the base field matching the curve's equation, or as the neutral element), and $+$ is point addition. While doing point addition, we are dealing with coordinates, which belong to the base field, and thus must use $p$ as the modulus.

The order $n$ of $E$ depends on the curve, and there's no reason that it would be exactly $p$. One way to look at it is that we are starting from $p^2$ pairs of coordinates, filtering these per the curve's equation, and adding the neutral element. We can define scalar multiplication $\times$ on that group, and the natural modulus for the scalar multiplicand is the order of the group, that is $n$, rather than $p$.


Patterns flaw to sign a counter with public key encryption protocol In modern asymmetric encryption protocol, like secp256k1, are there any flaws if you want to sign a counter?
i.e: use a private key to sign from 1-n is that any chance make n+1 easier to guess?

Terminology issues:

one does not sign with an encryption protocol, but with a (digital) signature scheme.
secp256k1 is neither of these. It is an elliptic curve.

Thus it is wanted to ask if in modern (asymmetric) (digital) signature schemes, like ECDSA on elliptic curve secp256k1, there is any flaw in signing a counter.

The answer is no, for proper implementation. That would go against the theoretical definition of a signature scheme's security. And there is practical insurance that the scheme does not become insecure when a counter is used as message: in all modern signature schemes with appendix (including ECDSA), the message is hashed, the resulting hash is the only input to the rest of the signature scheme, and the hash of a counter has no remarkable property (for a secure hash).

The only remarkable things are that

The messages are predictable. It allows the signer to prepare the signatures in advance. If either comes with a risk, it is not one specific to the signature scheme.
The messages are heavily constrained, which can only raise the difficulty of signature forgery, compared to other predictable messages.


How do public key rings work in cryptographic applications? I am wondering if there are any links to articles or resources available online, or explanations that you can give, that would help me to understand the concept of a public key ring, and why I might (or might not) want to publish my public key to one or another of them.

In other words, I have a basic understanding (I hope) of how PKI works and why I'd publish my public key to a keyserver so people can find me, but I'm unclear on what these different rings mean, or what their application is.

I'm wondering what would be a good analogy for them?  Like, Google+ circles?  I am looking for a better understanding of this concept.

It's shockingly simple. It's a file. It has public keys in it.

The traditional PGP Key Ring is a sequential file with a sequential list of keys in it. It's not even a database.

Slightly more advanced key rings, such as those used in Key Servers actually use a database.


Three party coin flipping protocol with only 2 active participants Is there a coin flipping protocol where:

Alice, Bob and Carol don't trust each other, and
The coin is flipped only by Alice and Bob, and
The result must be trusted by all three participants.

Your requirements are not terribly precise, so here is what I think you mean:

"The result must be trusted by all three participants" ==> Even if Alice & Bob are both malicious & colluding, the output of Carol should be uniform. Also, all 3 should get the same output.
"The coin is flipped only by Alice and Bob" ==> Alice & Bob do all the work. At the most Carol should just send some information to them beforehand, and get some information from them afterwards.

In that case, it's impossible. Alice & Bob can collude and do the following to force the coin toss to be whatever they want. Suppose they want it to come up heads:

Receive the initial message from Carol.
Run the protocol between the two of them until they are just about to send the final messages to Carol. By our assumption, Carol is not involved in this part.
At this point Alice & Bob can compute what the output is going to be. They both get output eventually (by correctness, it must be the same output Carol will get). But they will receive no more messages from Carol so they must be able to compute their output without her.
If the output is going to be tails, repeat part 2 fresh. Since Carol has no input to the protocol during step 2, correctness of the protocol requires that doing this is undetectable. This must result in a completely fresh outcome, otherwise there is an attack where Carol can fix the outcome of the coin.
If the output is going to be heads, send the final message to Carol.


Generating HMAC(SHA256) keys using WebCrypto deriveKey() API I am using the javascript WebCrypto API window.crypto.subtle.deriveKey() API to generate HMAC keys like this:
this.key = await window.crypto.subtle.deriveKey(
  {
    name: "PBKDF2",
    salt: someSalt,
    iterations: 50000,
    hash: "SHA-1"
  },
  keyMaterial,
  // default length value!
  { name: "HMAC", hash:"SHA-256"},
  true,
  [ "sign", "verify" ]
);

now, here is what the documentation on the MDN site
https://developer.mozilla.org/en-US/docs/Web/API/HmacKeyGenParams
mentions about the key length:
HmacKeyGenParams
The HmacKeyGenParams dictionary of the Web Crypto API represents the object that should be passed as the algorithm parameter into SubtleCrypto.generateKey(), when generating a key for the HMAC algorithm.

Properties
name
A DOMString. This should be set to HMAC.
hash
A DOMString representing the name of the digest function to use. You can pass any of SHA-1, SHA-256, SHA-384, or SHA-512 here.
length Optional
A Number — the length in bits of the key.
If this is omitted the length of the key is equal to the length of the digest generated by the digest function you have chosen.
Unless you have a good reason to use a different length, omit this property and use the default.

It basically says that the default length of the key is the length of the digest (in bits).
I was expecting a key length equal to 256 bits assuming that the digest size in bits for SHA256 is 256. However, dumping the object returned by deriveKey() into the developer console reveals a length of 512 bits (both for chrome and firefox - pretty recent versions).
Leaving apart that this kind of issues are difficult to discover and debug (since initially you see that some message digest computed somewhere else does not match the one computed in the browser), after fixing the issue (by using an explicit length of 256 bits) there are some things which I still do not understand:

Which standard recommends the key length for HMAC based signing, authentication aso?
Is there a bug in the WebCrypto API documentation or in its implementation?
Which is the optimal/recommended key length for HMAC(SHA256) based signing?

deriveKey() is documented here on the MDN site:
https://developer.mozilla.org/en-US/docs/Web/API/SubtleCrypto/deriveKey

NIST SP 800-107, section 5.3.4 which reads

Let C denote the bit length of the internal hash value that is
denoted H in FIPS 180-4. (This H is often called the “chaining value”
in descriptions of Merkle–Damgård-style hash functions.) Note that C
is not (necessarily) equal to L, the bit length of the hash function’s
output (see, for example, SHA-384 or SHA-512/t for any t < 512, for
which L < 512 = C). In all currently approved hash functions, L ≤ C
(with L = C for SHA-1, SHA- 256, and SHA-512).
The effective security strength of the HMAC key is the minimum of the
security strength of K and the value of 2C. That is, security strength
= min(security strength of K, 2C).

It looks like the API aims to produce HMACS with security strength of 512-bits according to the NIST document, though it also appears that the API comments do not reflect this. I would assume that the intent is to follow NIST and the documentation is at fault.

Following the NIST publication, a uniform random 512-bit key would be required to make best use of the full security offered by the SHA-256 algorithm.


An arithmetic circuit for the indicator function? The indicator function (or characteristic function) is defined as
$f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisying that
$f_{t^*}(t)=1$ if $t^*=t$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.)
I am dealing with transforming the function into an arithmetic circuit with addition gates and multiplication gates.
I know that if $t^*, t\in \{0,1\}$ then we can use a single NAND gate (in  Boolean Algebra) for this function. However, using arithmetic circuits, the transformation seems not to be trivial.
Could you please help me about this?
Thank you very much!
Updated:
The (one-variable) indicator function (or characteristic function) is defined as
$f_{t^*}:\mathbb{Z}_q\to \mathbb{Z}_q$ satisying that
$f_{t^*}(t)=1$ if $t=t^*$ and $f_{t^*}(t)=0$, otherwise. (Here $t^*\in \mathbb{Z}_q$ is given to define the function.) More generally, in the case of multi-variable, we define $f_{t^*}:\mathbb{Z}_q^d\to \mathbb{Z}_q$,   $f_{t^*}(t_1, \cdots, t_d)=1$ if $\exists t_i$ such that $t_i=t^*$ and $f_{t^*}(t_1, \cdots, t_d)=0$, otherwise.
I am finding polynomials that can be used to represent these functions.
So far, I have found some for the one-variable case:

Using Lagrange Interpolation: As $t, t^* \in \mathbb{Z}_q=\{0,1, \cdots, q-1 \}$ then such a polynomial should go through the points $(0,0), (1,0), $ $\cdots, $ $(t^*-1,0), (t^*, 1), $ $(t^*+1, 0),$ $ \cdots,$ $ (q-1,0)$. We can construct $f_{t^*}(t)=\frac{t(t-1)\cdots (t-t^*+1)(t-t^*-1)\cdots (t-q+1)}{t^*(t^*-1)\cdots (t^*-t^*+1)(t^*-t^*-1)\cdots (t^*-q+1)} (\bmod q)$ via the Lagrange Interpolation method. However, the polynomial has degree of $q-1$ and looks complicated to analyze.
Using Fermat's Little Theorem: The Fermat's Little Theorem states that if $q$ is a prime number, then for any integer $a$ not divisible by $q$, the number $a^{q-1}=1 ~(\bmod q)$.  Then we can construct $f_{t^*}(t)=1-(t-t^*)^{q-1}~ (\bmod q)$, if $q$ is prime. This polynomial looks simpler but may still be not helpful in case $q$ is a very big integer.

The question is that is there any more polynomials that are simpler than those above.
This question raised when I was trying to apply the idea at Section 4.2-4.3 of paper: https://www.iacr.org/archive/eurocrypt2014/84410298/84410298.pdf to the indicator function.

Any degree $d$ polynomial (over a field) has at most $d$ roots (unless it is identically zero). As the indicator function has $q-1$ roots, one gets that it must have degre $\geq q-1$.
There are generalizations of this to multivariate polynomials (the best known is Schwartz-Zippel). You could potentially try to generalize to non-fields, but one quickly runs into odd behavior --- say over $\mathbb{Z}/6\mathbb{Z}$ the linear function $f(x) = 3x$ has $\geq 1$ root. This is because it is "identically zero in a CRT component" though, but I do not know of the proper generalization to avoid issues such as this.


Weaknesses of RFC6628 In RFC6628 section 2.2, they say:

  w = The password remembered by the user.
  W = The password verifier registered in the server. W = g^w mod p, where g and p are agreed upon in advance.

They claim resistance against server compromise. But if an attacker gains access to the password verifier W, how much work is the attacker required to do per password guess, in order to conduct an offline brute force dictionary attack?

If I'm not mistaken, the answer to this question is: The work required for each password guess is to raise a single large exponent, and compute a single large modulo-division. This is not comparable to pbkdf2, bcrypt, scrypt, or similar, and probably should not be considered a strong enough rate-limiter to protect a low entropy password against server compromise.

Yes, the protocol in RFC6628 (and SRP) is vulnerable to brute force password search in the event of server compromise.
As Thomas Pornin puts it: for all password-based authentication protocols, what the server knows must allow for offline dictionary attacks, since an attacker who could get a complete snapshot of the server could simulate a client and a server on his own machines, and see when the simulated server accepts the password provided by the simulated client. This is rather unavoidable; thus, it is not a vulnerability of RFC6628/SRP specifically, but rather a vulnerability of authenticating clients with passwords.

That fact is acknowledged by a creative definition of resistance to server compromise:

  An augmented PAKE protocol is said to provide resistance to server compromise in the sense that the attacker cannot impersonate the user without performing off-line dictionary attacks on the password verifier.

The only thing I can think of to improve on that is replacing the password on the server side by a conventional entropy-stretched (purposely slow) hash (such as scrypt) of the password, with salt set to username and serverid, computed on client side at each use. So we have that entropy-stretching hash as the last line of defense in case of server compromise. That would require trusted and reasonably efficient code implemented on the client side, which is hard to get with the current browser architecture.

Update: There's room to add such entropy-stretching in RFC6628. As an option, RFC6628 allows for use of a so-called effective password which is $w'=H'(\text{0x00}\|U\|S\|w)$ (where $H'$ is a hash function; $U$ is the user's identity; $S$ is the server's identity; $w$ is the password remembered by the user, after normalization per RFC4013), then used to compute $W=g^{w'}\bmod p$. So if we use that effective password option, and use an entropy-stretching hash for $H'$ (that is: a slow one, at least for input starting in $\text{0x00}$), we have some serious protection. A brute force password search would require one evaluation of $H'$ per $U\|S\|w$ tested, and some extra work involving modular arithmetic to test against $W$.

Without the effective password option, the amount of work to test a password in an off-line password search attack following server compromise can be down to near one modular multiplication: we can express most passwords $w_j$ that we want to test as $w_i+\delta$ with $\delta$ in a small set, implying that $W_j=W_i\cdot\Delta\bmod p$, with $\Delta=g^\delta\bmod p$ precomputed.


What is the relevance of "physical layer security" to cryptography? I found that there are quite some active research activities in a field named "physical layer security", with in particular some types of codes that apparently are different from those commonly treated in the conventional textbooks on coding theory.

Could someone kindly explain the relevance, if any, of that field to cryptography, i.e. to issues of interest to our community (and eventually give a little bit of introduction to that field)?

edit:

Though having no prior knowledge in that field, I did attempt to read a bit of the corresponding literatures but found it too hard to really proceed with my humble knowledge (among other causes: lots of math). A perhaps understandable "reaction" of mine was that I asked myself:

"The physical layer needs 'merely' to transmit the bytes from the sender to the receiver error-free and that's obviously a type of task already successfully achieved via the (conventional) error-correcting codes etc. long before that new field came up. Now, since modern cryptography (as we commonly understand the term) has already provided lots of sufficiently fine techniques for achieving good security for the users, why does one need (at all) any additional theory to be applied, as well as additional work to be done, elsewhere (i.e. in the physical layer) in the entire processing of the messages of the users?"

In other words, I thought that the status-quo of cryptography is good enough and hence the raison-d'etre of the said field would possibly be questionable.

However, it is on the other hand entirely obvious to me that this kind of "personal" (emotional) thinking of mine can be no scientific argumention at all to "devaluate" that apparently fairly active new scientific research field, with lots of papers to be easily found via Google and even some published books written by univeristy professors.

I found subsequently in our library two books:

M. Bloch and J. Barros, Physical-Layer Security (sub-title: From Information Theory to Security Engineering), Cambridge, 2011,
X. Zhou et al. (Ed.), Physical Layer Security in Wireless Communications, CRC Press, 2014.

So currently I believe the real situation is as follows: Both (a) the (conventional) cryptography as treated e.g. in HAC of Menezes et al. and underlying the discussions of our community up till now and (b) the said new field of research are at the foundation based on (the same) Shannon's theory and they have merely different realms of applications in practice. This means that, for the benefit of the general readers of our community, it would be highly desirable that an expert who has good knowledge of that new field and who happens to be also in our community kindly volunteer to spend some of his time to post a short but helpful review of the research results of the new field that are presumably yet unknown to the majority of us.

Driven by the saying "secure by design", scientist start thinking about how they gonna secure the network while they are designing it. Cryptography is happening in the network layer. Scientists wishing that, by adding some security features in the physical layer, this will improve the security of the information in the upper layer and overall. In the future, millions of devices will be connected together and crossing each other… securing them by cryptography alone is a scary idea.


Is a chosen ciphertext attack on PGP still possible? In a paper from 2002 (pdf), Jallad et al describe a chosen ciphertext attack on PGP by taking advantage of the CFB mode that the block ciphers use under PGP. It's quite a devastating attack.

Is this attack still viable in 2016 or has PGP made changes?

RFC 4880, OpenPGP (superseded RFC 2440 which was up to date in 2002) contains a chapter on security considerations, which also discusses the decryption oracle attack Jallad et al described:

  In late summer 2002, Jallad, Katz, and Schneier published an
       interesting attack on the OpenPGP protocol and some of its
       implementations [JKS02].  In this attack, the attacker modifies a
       message and sends it to a user who then returns the erroneously
       decrypted message to the attacker.  The attacker is thus using the
       user as a random oracle, and can often decrypt the message.

  Compressing data can ameliorate this attack.  The incorrectly
       decrypted data nearly always decompresses in ways that defeat the
       attack.  However, this is not a rigorous fix, and leaves open some
       small vulnerabilities.  For example, if an implementation does not
       compress a message before encryption (perhaps because it knows it
       was already compressed), then that message is vulnerable.  Because
       of this happenstance -- that modification attacks can be thwarted
       by decompression errors -- an implementation SHOULD treat a
       decompression error as a security problem, not merely a data
       problem.

  This attack can be defeated by the use of Modification Detection,
       provided that the implementation does not let the user naively
       return the data to the attacker.  An implementation MUST treat an
       MDC failure as a security problem, not merely a data problem.

  In either case, the implementation MAY allow the user access to the
       erroneous data, but MUST warn the user as to potential security
       problems should that data be returned to the sender.

  While this attack is somewhat obscure, requiring a special set of
       circumstances to create it, it is nonetheless quite serious as it
       permits someone to trick a user to decrypt a message.
       Consequently, it is important that:

  Implementers treat MDC errors and decompression failures as
       security problems.
  Implementers implement Modification Detection with all due
       speed and encourage its spread.
  Users migrate to implementations that support Modification
       Detection with all due speed.

As a consequence, the OpenPGP packets "Sym. Encrypted Integrity Protected Data Packet (Tag 18)
" and "Modification Detection Code Packet (Tag 19)
" have been introduced, together forming an modification detection system (which is the proposed mitigation by Jallad et al):

  NON-NORMATIVE EXPLANATION

  The MDC system, as packets 18 and 19 are called, were created to
        provide an integrity mechanism that is less strong than a
        signature, yet stronger than bare CFB encryption.

  It is a limitation of CFB encryption that damage to the ciphertext
        will corrupt the affected cipher blocks and the block following.
        Additionally, if data is removed from the end of a CFB-encrypted
        block, that removal is undetectable.  (Note also that CBC mode has
        a similar limitation, but data removed from the front of the block
        is undetectable.)

  [...]

At least GnuPG uses these packets per default, which you can verify through gpg --list-packets or pgpdump:

$ echo "foo" | gpg --recipient a4ff2279 --encrypt | pgpdump
Old: Public-Key Encrypted Session Key Packet(tag 1)(524 bytes)
    New version(3)
    Key ID - 0xCC73B287A4388025
    Pub alg - RSA Encrypt or Sign(pub 1)
    RSA m^e mod n(4093 bits) - ...
        -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02
New: Symmetrically Encrypted and MDC Packet(tag 18)(63 bytes)
    Ver 1
    Encrypted data [sym alg is specified in pub-key encrypted session key]
        (plain text + MDC SHA1(20 bytes))

In GnuPG, you can enforce usage of the new packets through the --force-mdc option (which can also be applied permanently in gpg.conf). From man gpg:

  Force  the use of encryption with a modification detection code. This is always used with the newer ciphers (those with a blocksize greater than 64 bits), or if all of the
                recipient keys indicate MDC support in their feature flags.