Why are Random Oracle not achievable in practice? I am not really sure where I read that, but I have been thought that Random Oracles cannot be used in practice.

Then, I stumbled upon this paper that says: "Random Oracles are Practical:  Paradigm for Designing Efficient Protocols" which totally confused my understanding

Why do they not exist in practice?
Why do we end up using them in practice anyway?

We don't use random oracles. They are not practical. What we really do is modelling our theoretical work after the random oracle model.

There are many schemes which use hash functions. For some of them we have a proof of security, but only with some special cases. For example the padding scheme Optimal asymmetric encryption padding (OAEP) is proven to be semantically secure under chosen plaintext attacks - but only in the random oracle model. OAEP uses hash functions to randomize the message before encrypting with an asymmetric cipher, but what if these hash functions are not secure? Are they secure? We don't know, but probably not. Many were broken, like MD5 or SHA-1.
How can we prove that a scheme is secure if we are not sure that our underlying algorithms are secure? We can't. That's the reason why we have the random oracle model.

In the Random Oracle Model we just do everything like we always do, but there is a "magical" algorithm which represents a proven secure, perfect hash algorithm. In practice that's not really doable, because for this algorithm to work we need a true random number generator and a (nearly) infinite list of input und output values. That's already hard to do, but what's even more problematic is that every program / person who uses this algorithm has to have access to this number generator and list. How should that be done? Most likely with a central position which accepts messages and outputs the hashes for them. But how would you secure the connection between your program and this central position? It's just not practical doable to get a random oracle as your hash function in algorithms. It's like the one-time pad - nice to look at, provable secure and fully useless except for really special cases. We want fast and easy encryption for our bank details, not secure the Moscow–Washington hotline.

What we really do is just pretending to use them. We create our protocols and say "here we use a random oracle" if we need a secure hash function. Now we can try to prove our protocol and sometimes are even succesful with it. In most cases that works only because we used a random oracle. In reality we still implement something like SHA-256 or SHA-3 then and just ignore the possible problems - as long as nobody knows how to break our hash function and it works indistinguishable like a random oracle we should be save. Having a prove also helps to rule out mistakes in our protocol itself. Either we have a secure scheme or there's a problem with the hash algorithm. Without a prove there could also be a small, but fatal mistake nobody has thought of.

See also the article series "What is the Random Oracle Model and why should you care?" from Matthew Green.


What does St denote? I am reading a paper and notice that the term St is used without being defined. I suspect it is a common notation that I am not aware of.

It is used in the following paper:
https://eprint.iacr.org/2015/482.pdf

The first instance of it appears in Section 2.1, in the formula used in Definition 2.

What does the St denote?

Thanks

In this case it denotes arbitrary state passed from $A_0$ to $A_1$. This is a common idiom in interactive security game definitions.

Conceptually a security definition should involve a single adversary who plays some game. The adversary is modeled as arbitrary algorithm. If there is some query/interaction adversary can do repeatedly, we often model this as giving oracle access to some function.

But suppose the game has a significant event that should happen only once (in this case, asking for and receiving a challenge ciphertext). This is not so easily modeled by providing oracle. Instead, it is common to formalize the situation like the authors have done here. $A_0$ is the part of the adversary that runs up until requesting the challenge ciphertext (it terminates by giving the two chosen plaintexts). $A_1$ is the part of the adversary that runs after receiving the ciphertext. To follow our intuition that there is just a "single adversary" this whole time, we allow $A_0$ to pass arbitrary information (without loss of generality, its entire internal state) to $A_1$. That's what $st$ is here.


Digital signature for an expiring password I would like to create a publicly available tool that is used to generate a password that gives a limited time access to a resource.

My idea is to digitally sign the current date with a private key entered by the user, generating a message that is sent to the resource that verifies it with the public key. If valid, the access is granted if the date matches the current date.
The only secret element is the private key.

My constraints are:

as the private key has to be memorized and typed, it should remain short (10 characters)
the generated message should be as short as possible, to be manually typed

What is the best security level that can be reached with these constraints?
What algorithm can be used?

So, let's see if we can build something from the ideas in the question and the ones collected in the comments.
While the plain keys for asymmetric signature schemes need to be quite long (longer than normal humans can memorize), creating an asymmetric key pair from a password is doable [as pointed out by fgrieu in a comment]. Here is what Alice (or some program in her control) would do when first signing up:

Alice feeds the password and some other data, like her user ID (what Alice uses to login), system ID (an identifier for the server/system/...), system parameters, maybe some random salt from the user database, etc. as input to a key derivation function like PBKDF-2, bcrypt or scrypt, with suitable work factor so this takes as long as Alice is normally ready to wait whenever giving out a new authorization (this might be 10 seconds, for example), and obtain a 256-bit number $s$.

Alice uses this number $s$ as the seed to some (deterministic) cryptographically secure random number generator.

Alice uses the generator to generate a key pair. The exact procedure will depend on the algorithm in use - for RSA, Alice would generate two numbers $p$ and $q$, and check them for primeness (using more random numbers from the same generator) - if one of them turns out not to be prime, repeat. Then Alice creates their key pair from these in the normal way. (There are known standards for this, this is just a sketch.) For (EC)DSA or ElGamal, she just takes some random number $x$ from the generator, and calculates the public key $y = g^x$ in the group in use - nothing more to do.

She now gives the public key from this key pair to Bob (Bob is the "resource administrator" here.)
The private key will not be stored anywhere - whenever Alice needs it (e.g. to create a token), she will do this whole procedure again.

As all inputs are fixed and everything is deterministic, the key pair will only depend on the password (and Alice's user ID, so other users will have other key pairs).
How to create the token:
To generate a token, Alice takes all the necessary data together:

Alice's user ID
the ID $X$ of the resource which is to be accessed
Some form of the validity time (could be the current date in the simplest form)

Hash these together, and sign it with the private key (recreated from the password as above).
Now encode enough of the information mentioned before (the user ID could be enough) together with the signature in a token, and hand this token to Charles.
Charles takes the token, and shows it to Bob to access some resource $X$.
How to check the token:
Bob gets the token (and the resource ID $X$), extracts the user ID, and looks up the Alice's public key (and checks if she is actually permitted to access the resource, and to authorize such access to others).
Then Bob hashes together the user ID, the resource ID $X$ and the current date. Then he checks (with Alice's public key) if the signature is a valid signature for this message, and only then allows Charles access to $X$.
This scheme is extensible to other validity time spans - either encode the validity date into the token, too, or let Bob check the last some days as input.


Symmetric Encryption, meet in the middle attack, effective key length What is the effective key length of a deterministic encryption scheme, given a meet-in-the-middle attack scenario when you encrypt five times (64 bit keys for each)?
.
Say the encryption scheme has |key space K| = |plaintext space M| = |ciphertext space C| , all keys are 64 bit length, and $k1,k2,k3,k4,k5$ are all different (no key reuse like in some DES key options).
$c = E_{k5}(E_{k4}(E_{k3}(E_{k2}(E_{k1}(m))))$
You know that double encryption would not result in $|K|^2$ possibilities, but in fact due to the mitm attack the possibilities the attacker is forced to iterate over is only around ~2*K. You also know that triple encryption is much better, as it forces the attacker to have to iterate a total of ~$|K|^2$ even with the mitm tactic. What is the effective key length then when using double encryption, triple encryption, and x5 encryption respectively when using the above scheme?

I believe I have settled it, please comment below if I have inaccuracies or am missing something:
c=Ek5(Ek4(Ek3(Ek2(Ek1(m))))
We can also represent these as the following: (by applying the appropriate decryptions to either side)
Dk4(Dk5(c)) = Ek3(Ek2(Ek1(m))) _____ OR ______  Dk3(Dk4(Dk5(c)))=Ek2(Ek1(m))
Effective key length: with the mitm attacker, it would take 2^192 operations on one side of the equation to find the "collisions" in the stored lists and determine a set of proper keys by brute force, and 2^128 operations on the other side.
Stated more abstractly, approximately ~|K|^3 + ~|K|^2, but in big O notation O(|K|^3)


Whitening and randomness extraction The Von Neumann randomness extractor is explicitly mentioned in the randomness extractor page of Wikipedia, but strangely enough that page does not contain any reference to whitening the results of an entropy source.

Two intrinsically related questions:

Is this Von Neumann randomness extractor indeed a form of whitening?
Is whitening simply a part of randomness extractor, or is there another relation between whitening and randomness extraction?

I would say that whitening is a more general concept than randomness extraction.

In randomness extraction you have an input with some entropy that isn't perfectly random and an output that should be perfectly random and full entropy. In whitening there is not necessarily an entropy requirement on the output, it just needs to look perfectly random to an adversary.

For example, suppose you have a $b$-bit input $I$ with at least $e$ bits of entropy:

A randomness extractor would map it to at most an $e$-bit output, for example the first $e$ bits of $H(I)$. (Better yet, an $\frac{e}{2}$-bit output, as NIST recommends in 800-90B.)
A whitener could instead use encryption with a secret key $E_k(I)$. This gives a $b$-bit output that may only have $e$ bits of entropy, but still looks random as long as the key is secret.

With the above definitions, Von Neumann is both a randomness extractor and a whitener (when the input is a Bernoulli sequence).


Question about hash collisions If we have a hash function $h(x)$ and then a hash function $H(X) = h(h(X_0) || h(X_1))$ where $X_0$ is the first half of $X$, $X_1$ is the second half of $X$ and $||$ is concatenation. Then assuming we can easily find a collision for $H$, then it would be easy to find a collision for $h$ as well - Therefore finding a collision for $H$ is as hard as finding one for $h$.

Why is this? I can to some extent understand why that might be the case, but I can't logically connect the dots. Can anyone help me with some logic or math behind it or link to some resources where it is explained. I have tried google, but without the precise correct terminology I'm having a hard time finding the right pages.

Thanks

The general idea is that either one of the inner hashes, or the combining hash must collide, since there is not other place to introduce the collision.

Assume we found a collision for H. This means we have X, Y with $X \neq Y$ such that:

$h(h(X_0)||h(X_1)) = h(h(Y_0)||h(Y_1))$

Now we define: $A = h(X_0)||h(X_1)$ and $B = h(Y_0)||h(Y_1)$

This gives us a new equation h(A) = h(B)

If $A \neq B$, we found a collision, and are done.
If $A=B$ we know that $h(X_0)||h(X_1) = h(Y_0)||h(Y_1)$, which we can split into $h(X_0)=h(Y_0) \land h(X_1)=h(Y_1)$. From $X \neq Y$ follows $X_0 \neq Y_0 \lor X_1 \neq Y_1$. Thus at least one of $h(X_0)=h(Y_0)$ and $h(X_1)=h(Y_1)$ has different inputs on both sides of the equation, and thus represents a collision.


When was a RSA Private Key Introduced? I'm doing some research into the RSA cryptosystem but I just need some clarity on how it worked when it was published in the 70s. Now I know that it works with public keys but did it also work with private keys back then or did it use a shared public key first and then private keys were introduced later?

RSA never was intended as a symmetric/secret key cryptosystem, or extensively used as such. Public/Private key pairs have been used for RSA from day one.

A very close cousin of RSA, also using Public/Private key pairs, was known (but not published) at the GCHQ significantly before RSA was published. See Clifford Cocks's declassified A Note on 'Non-secret Encryption' (1973). Public-key cryptography was theorized at the GCHQ even before, see James Ellis's declassified The Possibility of Secure Non-Secret Encryption (1969), and his account in the declassified The history of Non-Secret Encryption (1987). See this question for more references on these early works.

As kindly reminded by poncho: the Pohlig-Hellman exponentiation cipher is a symmetric analog of textbook RSA. It uses as public parameters a large public prime $p$ with $(p-1)/2$ also prime, and two random odd secret exponents $e$ and $d$ with the relation $e\cdot d\equiv1\pmod{(p-1)}$; encryption of $m$ with $1<m<p$ is $c\gets m^e\bmod p$, decryption is $m\gets c^e\bmod p$. By incorporating the computation of $d$ from the encryption key $e$ into the decryption, and using cycle walking to coerce down the message space to bitstrings and remove a few fixed points, it becomes a full-blown block cipher by the modern definition of that. Security is related to the discrete logarithm problem in $\mathbb Z_p^*$ . An algorithm for solving that is the main subject of the article, and what Pohlig-Hellman now designates. The encryption algorithm has little practical interest, because it is very slow for a symmetric-only algorithm. It never caught in practice, and I believe never was intended to do so.

I found no earlier reference than: Stephen C. Pohlig and Martin E. Hellman, An Improved Algorithm for Computing Logarithm over $GF(p)$ and Its Cryptographic Significance published in IEEE Transactions on Information Theory, Volume 24 Issue 1, January 1978.

RSA was clearly known to the authors when they submitted this correspondence. They make explicit reference to:

Ronald L. Rivest, Adi Shamir, and Leonard Adleman, On Digital Signatures and Public-Key Cryptosystems, Technical Memo MIT/LCS/TM-82, dated April 1977 (received by the Defense Documentation Center on May 3, 1977; publication date unknown).
Ronald L. Rivest, Adi Shamir, and Leonard Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems published in Communications of the ACM, Volume 21 Issue 2, February 1978 (received April 4, 1977; revised September 1, 1977).

Note: I discovered (1.) only because it is referenced by Pohlig and Hellman; it has a number of rough edges fixed in (2.), including a byzantine and unnecessary complication in the handling of messages not coprime with the public modulus, that are telling of the novelty.

I refer to poncho's account on chronology.


Optimal MDS matrix - circulant or recursive? One of the special matrix in $GF(2^q)$ is MDS matrix which can be used in the cryptography like mix column of AES. Two forms of MDS matrices are circulant  and recursive.

Which form of MDS matrix (circulant or recursive) is suitable for a cryptographic hardware implentation? Meaning: which of them is optimal?

my answer is extension to circulant and recursive.

one property measure to the optimal implementation of MDS matrix in cryptography is the cost of xor (number of xors required to fully implement the MDS matrix ) , depth (number of stages) and the field size (usually 4 or 8 )

according to this paper MDS Matrices with Lightweight Circuits, the native implementation of AES MDS matrix costs 152 xors , with the improved algorithm is reduced to 97 xors and depth of three stages.
they searched for others MDS with different structures such as Toeplitz and Hadamard.

Figures below show better MDS matrices in term of implementation compared to circulant AES MDS .

In addition to hardware cost, the security aspect of MDS matrix has appeared in this paper : MixColumns Properties and Attacks on (round-reduced) AES with a Single Secret S-Box, which takes advantage of MDS values.

At the end , it is your call which MDS matrix to be implemented , you need to look it from security and hardware implementation cost.


Why doesn't preimage resistance imply the second preimage resistance? Let the preimage resistance be defined as »given a hash value $h$, it is hard to find any message $m$ such that $\operatorname{hash}(m)=h$«, and let the second preimage resistance be defined as »given a message $m_1$, it is hard to find any message $m_2$ such that $\operatorname{hash}(m_1)=\operatorname{hash}(m_2)$«.

Then if you are given a preimage resistant hash function $H$, what modifications could we do in order to make a hash function $H'$ that is preimage resistant, but not second preimage resistant?

Someone suggested that we could do the following:

  Take a preimage resistant hash function; add an input bit $b$ and replace
  one input bit by the sum modulo 2 of this input bit and $b$.

But I am not sure if that will work, could anybody explain to me why that makes $H'$ not second preimage resistant?

Consider the function $H$ transforming a message $m$ to the SHA-512 hash of the first 1024 bits of $m$ (right-padded with $1024-n$ zero bits if the bit length $n$ of $m$ is less than 1024).

$H$ is first-preimage resistant, but not second-preimage resistant: once you have a first preimage $m_1$, it is trivial to get another $m_2$ with the same hash (e.g. append a zero bit, $m_2=m_1||0$).

Edit: what was suggested to huyichen also works: the hash function $H'$ constructed as suggested is such that for any preimage $m_1$, there is a different preimage $m_2$ with the same hash, obtained from the first by complementing the added input bit $b$, and the other input bit which is combined with $b$.


Attacking 2DES efficiently Meet in the middle on 2DES uses $2^{56}$ memory.
Given the fact that the attacker has only $2^{45}$ memory.
How can the attacker adjust the attack so even with this memory limit, it will still be more efficient than looking after all the existing keys?

I guess you can separate this to a few lookups - a few tables - each time containing a different subset while making sure each row get compared. which should still be more efficient than $O(n^2)$. Is this the answer?

We are talking about attacking double-DES here, which encrypts a 64-bit block $P$ with two 56-bit keys $K_1,K_2$ as $C = E_{K_2}(E_{K_1}(P))$. As noted by Diffie and Hellman already in late 70s, to attack it with a one or two plaintexts as follows. Suppose we know that $P_0$ is encrypted to $C_0$, then

for all possible $K_1$ compute $E_{K_1}(P)$ (partial encryption) and store the intermediate state $S$ and $K_1$ in a hash table;
for all possible $K_2$ compute $E_{K_1}^{-1}(C)$ (partial decryption) and store the resulting intermediate state $S'$ and $K_2$ in another table;
check if exist such $S = S'$. If so, a pair $(K_1,K_2)$ is a candidate pair of keys.

Since the states are 64-bit, our filter yields $2^{56+56-64} = 2^{48}$ candidate key pairs, which can be tested on a second (plaintext, ciphertext) pair. The complexity of the attack is $2^{56}$, hence Double-DES provides only 56 bits of security.

Meet-in-the-middle attack can be done memoryless in the same way as memoryless collision search with the Pollard's $\rho$-method. Let's recall it.

The collision search for function $F:\{0,1\}^n\rightarrow\{0,1\}^n$ works as follows: start with random $x$ and iterate in parallel $x\rightarrow F(x)\rightarrow F^2(x)\rightarrow \ldots$ and $x\rightarrow F^2(x)\rightarrow F^4(x)\rightarrow \ldots$. When two iterations collide after $i$ steps, we get that $F^i(x) = F^{2i}(x)$, which in turn implies that $F^{i-1}(x)$ and $F^{2i-1}(x)$ are collisions for $F$. This method works for most randomly-looking $F$ and has complexity $O(2^{n/2})$.

For the meet-in-the-middle attack you slightly modify the algorithm. Suppose that you have to find $x,y$ such that $G(x) = H(y)$. In our Double-DES example $G(x) = E_{x}(P)$ and $H(y) = E_{y}^{-1}(C)$. Then you define

$Q(z) = G(z)$ if $z$ ends with 0 (or any other predicate)
$Q(z) = H(z)$ if $z$ ends with 1.

Then you iterate $x\rightarrow Q(x)\rightarrow Q^2(x)\rightarrow \ldots$ and $x\rightarrow Q^2(x)\rightarrow Q^4(x)\rightarrow \ldots$. When you get a collision $Q^i(x) = Q^{2i}(x)$ then with probability $1/2$ the last call for the first iteration was with $G$ and for the second iteration with $H$ or vice versa, so you actually have $G(Q^{i-1}(x)) = H(Q^{2i-1}(x))$, which solves the meet-in-the-middle problem.

Note that we implicitly converted states to keys. This is easy as states are wider, and can be done by simply trimming any 8 bits. If states were shorter, then a more sophisticated procedure had to be used, and the complexity would grow.


KPA on Feistel cipher? I heard that DES is technically “broken” because of attacks involving large amounts of known plaintext. These attacks are obviously academic and highly complicated, so for some intuition I was hoping that somebody could explain (for example) how much plaintext is required to determine the key in a generic/simple Feistel scheme with mangler function very simply linear in the key and so on?

Feistel networks were broken in DES but not triple DES. Some final AES candidates not approved also used Feistel networks $2^{36}$ plain text attacks. Reduction of $2^{16}$ possible keys for single DES: $4^{48/6} = 4^{8} = 2^{16}$.

First for a one round Feistel network: $R_0$ and $f (R_O, k_1) = R_1 \oplus L_0$, $k_1$ becomes known.

For two round Fiestel: Use the same method twice: $$(R_0, f(R_0,l_1)=L_2 \oplus L_0) \ (L_2,f(L_2,K_2)= R_2 \oplus R_0)$$

A nice reference would be CryptoLecture 04 (PDF) from Daniel Boneh's crypto course on Coursera.


What is the difference between a PRF and a PRF+? What is the difference between a PRF and a PRF+?  I am understanding them to mean the same thing, but I imagine that is because I don't understand their differences.

The IKE RFC defines a PRF as:

  This pseudorandom function (PRF) takes as input a secret, a seed, and
     an identifying label and produces an output of arbitrary length.

The TLS 1.2 RFC defines a PRF as:

  prf(key, msg) is the keyed pseudo-random function-- often a keyed
       hash function-- used to generate a deterministic output that
       appears pseudo-random.

The IKEv2 RFC defines a PRF as:

  The PRF is used for the construction of keying material for all of
     the cryptographic algorithms used in both the IKE SA and the Child
     SAs.

The IKEv2 RFC defines a PRF+ as:

  Since the amount of keying material needed
     may be greater than the size of the output of the PRF, the PRF is
     used iteratively.
  The term "prf+" describes a function that outputs a pseudorandom stream based on the inputs to a pseudorandom function called "prf".

IKEv2 uses the term PRF to refer to a negotiated keyed random-looking function (for example, possibly HMAC-SHA256).  IKEv2 uses the term PRF+ to refer to a specific construction based on that underlying negotiated function, as defined in section 2.13:

prf+ is defined as:

prf+ (K,S) = T1 | T2 | T3 | T4 | ...

where:
T1 = prf (K, S | 0x01)
T2 = prf (K, T1 | S | 0x02)
T3 = prf (K, T2 | S | 0x03)
T4 = prf (K, T3 | S | 0x04)
...

The term PRF+ has no generally accepted meaning outside of IKEv2.


In the SIKE known answer tests, why is there only one secret key? I'm looking at the SIKE known answer tests and am realizing that I'm confused on all the different terms in a Diffie-Hellman key exchange.

From the Wikipedia page, I would think there would be a public key and 2 secret keys, then a shared secret. However, the KAT provides a public key, a secret key, a shared secret, and a ciphertext. What exactly is the ciphertext, and where is the secret key?

This Wiki page describes SIDH, a key exchange protocol.

SIKE is a key encapsulation mechanism, like all entries in the NIST PQ competition, it has a different API.


How hard is the DLP in that simple group? Let $p=4q-1$ be a prime with $q$ an odd prime. Let $G=\{0,1,\dots,p-1,\infty\}$. The following law $*$ makes $(G,*)$ a commutative group of order $4q$ with neutral element $\infty$:
$$a*b=\begin{cases}
a&\text{if }b=\infty\\
b&\text{if }a=\infty\\
\infty&\text{if }a\ne\infty\text{ and }b\ne\infty\text{ and }a+b\equiv 0\pmod p\\
{ab-1\over a+b}\bmod p&\text{otherwise}\end{cases}$$
The inverse of $a$ for law $*$ is $p-a$, with the exceptions of $0$ and $\infty$ which are their own inverse. Proof of associativity requires care, and uses $p\equiv3\bmod4$ at some point.

Computation can be simplified by keeping an element of $G$ as an integer fraction $x\over y$ with $x$ and $y$ integers modulo $p$, and the neutral element $\infty$ represented as $x\over0$ with $x\not\equiv0\pmod p$. The group law becomes, without any special case:
$${x_a\over y_a}*{x_b\over y_b}={(x_ax_b-y_ay_b)\bmod p\over(x_ay_b+y_ax_b)\bmod p}$$
and we need only 4 multiplications, 1 addition, 1 subtraction, and 2 modular reductions for $a*b$; down to 2 squarings, 1 multiplication, 1 doubling, 1 subtraction, and 2 modular reductions for $a*a$.

Since we have a group law, we can define exponentiation. Exponents can be reduced modulo $4q$, the order of the group.

Let $g$ be an element of order $q$. It can be found heuristically, perhaps starting from $g=2$ incrementally and checking $g^4\ne\infty$ and $g^q=\infty$ (Poncho's comment gives a faster way when we don't care that $g$ is large).

Question: How hard is the Discrete Logarithm Problem in the cyclic subgroup of prime order $q$ generated by $g$? Is it somewhat related to a well known group?

Update: The formulas $x_{a*b}=(x_ax_b-y_ay_b)\bmod p$ and $y_{a*b}=(x_ay_b+y_ax_b)\bmod p$ are the same as for complex multiplication in cartesian coordinates, except they are for integers modulo $p$. Now associativity is less surprising.

By going thru polar coordinates, we can express of $g^k$ for law $*$ without iteration: that's $((y^{-1}\bmod p)x)\bmod p$ for $x=(g^2+1)^{k/2}\cos(k\cot^{-1}g)$ and $y=(g^2+1)^{k/2}\sin(k\cot^{-1}g)$. Quantities  $x$ and $y$ are integers even though intermediate values use reals. This is computationally impractical, because we need so extreme precision. And it does not lead to a trivial way to solve the DLP.

That group embeds in  $F_{\hspace{-0.02 in}p}[i\hspace{.02 in}]$$^{\hspace{.02 in}*}$  via the Möbius transformation given by

$f(x) = \dfrac{x+i}{x-i}$  (and  $\hspace{.04 in}f(\infty) = 1$ ),  and that embedding has a left-inverse

(that is not injective and is not necessarily a homomorphism) which is the

Möbius transformation given by $\;\;\; g(z) \: = \: \dfrac{z+1}{z-1} \cdot i \;\;\;$ (and  $g(1) = \infty$ ).

Their partial-inverse-ness can be used to find the range of that embedding

(namely, that range is the set of fixed-points of that embedding composed with $g$);

solving reveals that it's exactly the points $z$ such that $g(z)$ is in the embedding's domain.

Further solving then gives that for all elements $c$ and $d$ of $F_{\hspace{-0.02 in}p}$,

$g(c\hspace{-0.03 in}+\hspace{-0.03 in}(d\hspace{-0.06 in}\cdot \hspace{-0.05 in}i\hspace{.02 in}))$  is in that embedding's domain if and only if $\;\;\; c^{\hspace{.02 in}2}\hspace{-0.04 in}+d^{\hspace{.02 in}2} \: = \: 1 \;\;\;$.

Therefore your group is efficiently-equivalent to the mod-p circle group.

The latter is an efficiently-decidable subgroup of the multiplicative group of an efficient field,

and that efficient field is a simple quotient of the Gaussian integers,

which is a Unique Factorization Domain whose number of units is small.

Thus, by trying to find the discrete log of both inputs in the subgroup with

respect to the same generator of the whole multiplicative group, one should be

able to attack the subgroup's Discrete Logarithm Problem with index calculus,

using $i$ and non-associate Gaussian primes as the factor base.

For that reason, although I don't know how GNFS works, I'd imagine the hardness of

your group's DLP is at most not much more than for the standard DLP mod primes.

I'm not aware of any faster-than-SNFS DLP algorithms for any

[subgroups whose order has a large prime factor] of multiplicative groups of an efficient field, so in particular, I'm also not aware of any such algorithms for your group.

On the other hand, I also don't know how SNFS works.


How do I calculate e, d and N based on raw and encrypted message in RSA? I've got raw and encrypted message, which contains only numbers. For example:

Message: 32016550980634121428089400169, encrypted: 35682226122303060179704449482

I've written such an algorithm:

d = 1
n = enc+1

for k in tqdm(range(1, 10**7)):
  e = k * n
  if pow(msg, e, n) == enc:
      print("WE")

But looks like I've mistaken somewhere. How do I make it work?

In general, you can't do that.  You have one equation and two unknowns (not three, since $d$ is uniquely determined by $n$ and $e$, even if actually computing it without knowing the factors of $n$ is difficult), so the solution will in general not be unique.

Of course, you could guess that $e$ might be one of the common values (e.g. 3 or 65537) and try to solve for $n$.  But that only works if you guess the right $e$.  And even if you do manage to determine $n$ this way, you'll still have to factor $n$ to be able to calculate $d$.

As for your code, it has many mistakes.  I have no idea why you're setting n = enc+1 or e = k * n, for example — neither of those make any sense whatsoever.  It looks as if you may be missing some fairly basic knowledge of either Python programming or the mathematics behind RSA.

As I can't really tell from just your code what it is that you might be missing, all I can suggest is finding some good tutorials and revising the basics.  And maybe ask for help from your instructor / TA / tutor / etc., if you have one available.


is this RSA private key valid? is this RSA private key valid?

First, here's the RSA private key in question:

-----BEGIN RSA PRIVATE KEY-----
MIICXwKBAQACgYDDlegCjkr+Fwf48IVDJimiQdYrpDbrlyMazVeP88ELQLQrTUp/
BrCeC82CUFOyjjbuJagixYsuHhgueS3g/NXrR7XulWBjE2BruSeek8hmK+Ch+jzu
SMT+WbFIiUDHfJoERUHF02nJ12vFSuJ435/4+7vr/7zAo2M2E76et7a92wKBAwEA
AQKBgKuL7kVfnPMkLD/yZlAxRs8kQ79fdzRICehWNvjx6V3/UIeycSbdLUhSPdyQ
q/iuuAtFSCXHcn3us3L/onf2C4GZgMwh3n7022SXm3iQztSWPE4ei6CFjzG6NB2+
hXjcRoq/En/FD+65PXvnNxOJAhHSrS+kGLmNTeHMZIj4jJGBAoFA98V8RkdOgb6I
XRX/PQCI3215ODIHeqV7SZiw9TXM4dHRFYc19cXXPGffwNAi2hkOkClBRcrZT96u
AOO9Lam9uwKBQMoUvqYplONRc0JGA2+m8kUrMmaO+xKRGVQ1qkxaU5H5vKShHpPv
aO598i8yWE0rOxkEX72IawAUAv2sHxLm7mECgUBwwO5NDSYs5QgpVFlS6WtgQfFo
IVxF9Aim9VWSQWl7WoBLy7xCnEXWt26b0BwMJFr8P8n0eNtr/Wox/XGZ1iUBAoFA
O+fSbKe+/3RR2r+unRa8k0yu8EBKpcJl49TU2zWbuJZ0Gcm5qtk6HhkwBlXCX34F
UvE9AI7ESY2lJVY1EAFtgQKBQBNf1NuWHXts0msdOnCHzcb1g+CqhdUnknW5dHf4
nFKr9b9fq3f2kpqFwPUC5Ea+tocL7bwN4kgfFLJMMaLwr6A=
-----END RSA PRIVATE KEY-----

Here's the ASN.1 parsing of that key:

    0:d=0  hl=4 l= 607 cons: SEQUENCE
    4:d=1  hl=3 l=   1 prim:  INTEGER           :00
    8:d=1  hl=3 l= 128 prim:  INTEGER           :-3C6A17FD71B501E8F8070F7ABCD9D65DBE29D45BC91468DCE532A8700C3EF4BF4BD4B2B580F94F61F4327DAFAC4D71C911DA57DD3A74D1E1E7D186D21F032A14B84A116A9F9CEC9F9446D8616C3799D41F5E05C311B73B01A64EB776BF388365FBBABE3A2C963628943AB51D8720600704441400433F5C9CC9EC416148494225
  139:d=1  hl=3 l=   3 prim:  INTEGER           :010001
  145:d=1  hl=3 l= 128 prim:  INTEGER           :-547411BAA0630CDBD3C00D99AFCEB930DBBC40A088CBB7F617A9C9070E16A200AF784D8ED922D2B7ADC2236F54075147F4BAB7DA388D82114C8D005D8809F47E667F33DE21810B249B6864876F312B69C3B1E1745F7A70CE45CBE2417A8723B97540ED803AF01146C28418C8EC76FDEE2D52D05BE74672B21E339B7707736E7F
  276:d=1  hl=3 l=  64 prim:  INTEGER           :-083A83B9B8B17E4177A2EA00C2FF77209286C7CDF8855A84B6674F0ACA331E2E2EEA78CA0A3A28C398203F2FDD25E6F16FD6BEBA3526B02151FF1C42D2564245
  343:d=1  hl=3 l=  64 prim:  INTEGER           :-35EB4159D66B1CAE8CBDB9FC90590DBAD4CD997104ED6EE6ABCA55B3A5AC6E06435B5EE16C109711820DD0CDA7B2D4C4E6FBA0427794FFEBFD0253E0ED19119F
  410:d=1  hl=3 l=  64 prim:  INTEGER           :70C0EE4D0D262CE50829545952E96B6041F168215C45F408A6F5559241697B5A804BCBBC429C45D6B76E9BD01C0C245AFC3FC9F478DB6BFD6A31FD7199D62501
  477:d=1  hl=3 l=  64 prim:  INTEGER           :3BE7D26CA7BEFF7451DABFAE9D16BC934CAEF0404AA5C265E3D4D4DB359BB8967419C9B9AAD93A1E19300655C25F7E0552F13D008EC4498DA525563510016D81
  544:d=1  hl=3 l=  64 prim:  INTEGER           :135FD4DB961D7B6CD26B1D3A7087CDC6F583E0AA85D5279275B97477F89C52ABF5BF5FAB77F6929A85C0F502E446BEB6870BEDBC0DE2481F14B24C31A2F0AFA0

Here's what RFC3447 says the format of a private key is:

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL

So pretty much the key has a negative modulus.  Seems to me that as such it's a bad key.  That it needs to have a zero before it.

From X.690-0207.pdf...

  The contents octets shall be a two's complement binary number equal
  to the integer value, and consisting of  bits 8 to 1 of the first
  octet, followed by bits 8 to 1 of the second octet, followed by bits 8
  to 1 of each octet in turn up to  and including the last octet of the
  contents octets

So given all this, why does the following work?:

openssl rsautl -inkey privatekey.txt -encrypt -in plaintext.txt -out ciphertext.txt

Quoting more from RFC3447:

   RSAEP ((n, e), m)

   Input:
   (n, e)   RSA public key
   m        message representative, an integer between 0 and n - 1

So basically, the function that does the exponentation isn't supposed to allow numbers less than zero and yet that's what we have here.

Any ideas?

This is, as you guessed, an incorrectly encoded key.  I suspect that OpenSSL ASN.1 decoder is written to assume that the modulus (and other parameters) is always positive, and so interprets them as if they were (that is, interprets them as if the leading 00 byte was there); hence it just happens to work.

Now, what do you do about it?  Well, if it's basically working for you, I suppose there's no urgent need to "fix" it.  On the other hand, what you're using isn't standard ASN.1; if you need to give the private key to someone else (or even update the version of OpenSSL you're using), it might stop working.  I'd personally suggest that you track down who generated the key, and tell them to fix their ASN.1 encoder.


How does $g$ being a generator imply Diffie-Hellman's correctness? In the Diffie-Hellman protocol for key exchange over an unsecured channel, we choose $p$ and $g$, where $g$ is a generator of $\mathbf{Z}_p^*$. However I want to know why this assumption makes the equation below true, assuming Alice and Bob choose $a$ and $b$ as secret keys:

$$(g^b)^a \equiv (g^a)^b \pmod p.$$

In other words, how does the assumption that $g$ is generator of $\mathbf{Z}_p^*$ make the above equation true?

It does not; the equation holds for any element $g$. The fact that $g$ is a generator means only that every element of the group can be obtained a key. This is not at all necessary for the protocol.


How is an AES S-Box cyclically shifted to the left? I'm trying to an implement an enhanced version of AES which was proposed recently. The link to the paper is here: http://sdiwc.net/digital-library/enhancing-aes-using-novel-block-key-generation-algorithm-and-key-dependent-sboxes

In their proposed algorithm, a unique S-box is created for each round by XOR'ing all 16 bytes of the round key, and cyclically shifting the original static S-Box to the left by that value. I'm new to cryptography in general, and I understand the original AES algorithm well, but I don't understand what the authors mean by cyclically shifting the S-Box. Obviously, each individual byte can't be shifted, since the shift values produced are as high as 127. Is it each row of the S-Box that has to be shifted, or are all 256 bytes lined up somehow and shifted?

Yes they are talking about shifting each individual byte.

In the example in the paper, s-box input 00 becomes input A4 (output 63), 01 becomes A5 (7C), and so on. This is a 92 byte left rotation of the s-box elements, which is equivalent to a 164 byte right rotation, all done mod 256.

Without going into extreme detail, I would strongly recommend against using this... ever, it is not a good idea, and actually makes the cipher weaker. There are only 255 new s-boxes generated using this method, and they are all weaker than the original.

The example s-box given shows the following properties:

Differential Uniformity: 8 (lower is better)
Non-linearity: 94 (higher is better)
AutoCorrelation: 88 (lower is better)
SSI: 260608 (lower is better)

The AES standard s-box has these values for the same properties:

Differential Uniformity: 4 (lower is better)
Non-linearity: 112 (higher is better)
AutoCorrelation: 32 (lower is better)
SSI: 133120 (lower is better)

The new s-box also inherits the undesirable properties of the original, such as simple algebraic representation and CCZ equivalence.


Finding output given an S-box input of 8 bits I'm given the following table:

I'm told to find the output given an hexidecmal input of 2B.
 I know that 2B in binary
= 001 01 011

So I took the first two and last two outer bits (0011) to find the first row which is row 3.Then I took the remaining bits (10 10) to find number 10 on the top row. Matching up the values I get a final answer of 3, which is 11 in binary. But the correct answer is 1001 which is 9 in decimal. I have no idea where I have gone wrong here. I followed the procedure for 6 bit number, but I do feel like I'm missing a key element on how to solve this for a 8 bit number.

The S-Boxes of DES map from 6 bits to 4 bits. $2b$ written in binary representation is $10\ 1011$, not $001\ 01\ 011$ as you said. Now taking the first and last bit (as usual for DES S-boxes) yields us $11_{bin} = 3_{dec}$ which is the last row in your table. Taking the middle 4 bits equals to $0101_{dec} = 5_{dec}$. Now we can read the final result from the table as $9_{dec} = 1001_{bin}$


AES GCM : is it acceptable to return the wrong plaintext if the tag is incorrect? Let's start by saying I'm no cryptography expert, I'm just a developer, so feel free to correct me (using words, not downvotes) if what I'm saying is non-sense.
Context: I'm doing some crypto as a service for embedded devices. Users of this service don't have access to any key. They're only able to tell the device "use the key <index> to encrypt/decrypt this".
According to the NIST (Chapter 7.2), when decrypting a cipher using AES GCM, if the tag is wrong, the cipher should not be returned :

if they are identical, then the plaintext is returned; otherwise, FAIL is returned

This raises two questions.
First: how bad is it to return the wrong plaintext anyway? (but still returning an error, it would be up to the user to check it). Is there any mathematical reason for that? Could an attacker somehow leak the key by trying to decrypt forged ciphers?
Second: if the answer to the first question happens to be "it doesn't matter whether you return the wrong plain or not" then this is not an issue anymore. But otherwise: our AES driver is written in C, how can we prevent the cipher from being returned in case the tag is wrong? As far as I understand, to compute the tag the decryption process must be done entirely. The thing is the destination buffer of the decrypted cipher is a shared memory a potential attacker could have access to. Having a temporary buffer to store the resulting plaintext in order to compute the tag is not considered as it would not fit the device memory.

There is an article* that answers the question in the negative for GCM and CCM. The article introduces the first formalization of the Releasing Unverified Plaintext (RUP) setting. The related security notion is the Ind-RUP.
The security question is can an adversary forge messages with unverified messages? In this game, confidentiality is not relevant, since in the game the adversary is accessing the plaintext of the chosen messages. AES-GCM fails to satisfies this.

How to Securely Release Unverified Plaintext in Authenticated Encryption by Elena Andreeva and Andrey Bogdanov and Atul Luykx and Bart Mennink and Nicky Mouha and Kan Yasuda

AE schemes such as GCM [34] and CCM [49] reduce to CTR mode in the RUP setting. This is because the adversary does not need to forge a ciphertext in order to obtain information about the corresponding (unverified) plaintext.

Your questions:

It is very dangerous. AES-GCM internally uses CTR mode and bit flipping is very easy in the CTR mode. An attacker can easily change the ciphertext bit on their advantage. This is catastrophic if the structure of the message is known.
One must never ignore the tag invalid!
It is not about the leak of the key, CTR mode is IND-CPA secure. It is about changing the messages. This is why CTR mode can't have IND-CCA. GCM provides integrity and authentication and authenticated encryption > IND-CCAs

For the second part you may benefit from is Q/A which provides a solution for the limited chunks for the GCM;

How to securely encrypt/decrypt data with a maximum chunk size?

Also for general guide

What are the rules for using AES-GCM correctly?, and
Deep into bounds Does GCM (or GHASH) only provide 64-bit security against forgeries?

*Thanks to Squeamish Ossifrage for pointing the article.


Using a round function intended for an SP network in a Feistel network? If I use the round function from a secure SP network (such as AES)  and use it in a Feistel netwok, is this a good starting point for the second cipher?

My thought is "yes" because:

it already has good diffusion and confusion
it doubles the block size, so the number of rounds can be doubled at no perf cost.

There is only one requirement for a Feistel round function and that is a good diffusion and confusion. It is not required for the round function to be invertible in a Feistel network. You can use (as asked) a secure mini SPN or even a hash function (Sha3...)

  it doubles the block size, so the number of rounds can be doubled at no perf cost

If you meant to use that $n$-bit secure SPN (such as Rijndael) in your Feistel $2n$-block-cipher, then you will have to make a sufficient number of rounds (at least 4 to get full diffusion : see p. 41). Therefore compared to a parallel CTR encryption method just using that $n$-SPN, you are 2 times slower and you don't really have a gain in security in term of key as the space is the same.


Advantages of encrypting a symmetric key with a public key vs using a fixed symmetric key I am new to cryptography concepts.

I am trying to protect some firmware download.

Reading some Wikipedia pages, I understand that asymmetric cryptography is time consuming, so, if I want to protect my download not only for authentication (I think I understood what to do for that), but also for sniffing, I need to crypt the download with a symmetric key.

This symmetric key can be either:

fixed and known by both parties;
or it can be crypted by the source with a public key and decrypted by the destination with the corresponding private key.

What is the real advantage of option 2?

If somebody has the firmware package (or reads it while it is downloading), a lot of machinery and time, he should be able to decrypt the message anyway, because it was crypted with a symmetric key.
The only advantage I see is that once he has decrypted firmware package version 1, if the symmetric key changes in a newly released firmware package version 2 some months later, all the job must be repeated.
So what I think is that option 2 is really useful only if sent messages are frequent, so decrypting one message won't help for the subsequent ones.

Am I right? Are there other advantages?

What is the real advantage of option 2 (asymmetric encryption of firmware)?

As correctly pointed by the question, not much. All I can think of:

It allows to change the symmetric key at each firmware release (actually, the firmware will be encrypted with a random symmetric key, sent asymmetrically encrypted in a header). This advantage is mitigated by the fact that the asymmetric private decryption key can hardly be changed at each release, and must be secret.
The developer/party encrypting the code needs no secret for that. This advantage is mitigated by the fact that the developer/party signing the code needs a private key, which must be secret.


How to derive the curve Ed25519 from Curve25519? According to the paper "Faster addition and doubling on elliptic curves" by Bernstein and Lange, the Montgomery curve (Curve25519) $$v^{2}=u^{3}+486662\cdot u^{2}+u$$ is birationally equivalent to the Edwards curve (Ed25519)
$$x^{2}+y^{2}=1+(121665/121666)\cdot x^{2}y^{2}.$$The paper says that the transformation is easy and can be done with$$v=\sqrt{486662}\cdot u/x$$
$$u=(1+y)/(1-y).$$
However, when I try to do this transformation I do not obtain the Edwards curve, but I get
$$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$ with $d=486662$.

So I wonder how, starting from Curve25519, I can get to $e=121665/121666$ and
$$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}?$$ Thanks!

The detailed transformation:

First off, your equation is correct and there seems to be no calculation mistake.

To understand on how to get from
$$(2+d)x^{2}+dy^{2}=d+(d-2)x^{2}y^{2}$$
 to
$$x^{2}+y^{2}=1+e\cdot x^{2}y^{2}$$
one first needs to observe that $e=(d-2)/(d+2)=121665/121666$ holds.

The next step is to consider:
"What operations are actually allowed with birational equivalence?". According to this presentation on a similar topic, linear transformations in the coordinates don't break the birational equivalence as do simple equivalence transformations (the ones having takens us here).

So the substitution $x^2:=x^2\cdot d/(d+2)$ is allowed. If you now perform the substitution, you'll observe
$$dx^{2}+dy^{2}=d+d(d-2)/(d+2)x^{2}y^{2}$$
and dividing by $d$ yields the desired equation.


How is it decided if $G_1$ and $G_2$ are two “additive” or “multiplicative” cyclic groups? According to wiki's definition of Bilinear pairing…

  Let $G_1$ and $G_2$ be two additive cyclic groups of prime order $q$, and $G_T$ another cyclic group of order $q$ written multiplicatively. A pairing is a map: $e: G_1 \times G_2 \rightarrow G_T$
  but, there also have different definition such that $G_1$ and $G_2$ be two multiplicative cyclic groups.

How is the decision made if $G_1$ and $G_2$ are two additive cyclic groups or multiplicative cyclic groups?

Notation is basically a free choice of the author, as they describe functionally the same. And there is no fixed definition for this. However, common practice in mathematical publications is:

Multiplicative notation for arbitrary groups
Additive notation for commutative groups

This can be found here: math-SE,  wolfram

Wikipedia also states, that additive notation is primarily used for modules and rings. However, that is quite obvious because for those you need both types of notations.

Interestingly, in cryptography we rarely see any non-abelian groups except matrix multiplication, yet multiplicative notation is quite common. The emphasis here might be on the difficulty of the discrete logarithm problem: If a group has the property, that calculating DLOG is difficult, we tend to use multiplicative notation. Additionally, we note generic groups in multiplicative notation mostly.

Additive notation is used mostly just for elliptic curves, or of it is actually a group operation derived from the addition of integers. In that case it might be used to emphasize: In this group the DLOG problem is easy.


What's a good strategy for the game "spyfall"? https://boardgamegeek.com/boardgame/166384/spyfall

There are n players (n > 3), and n-1 of them know a secret string (the location). The nth player is the "spy", and does not know the location.

The non-spies has to guess which player is the spy, and the spy has to determine the location.

Players cannot communicate at arbitrary times. Only one person (the player who's turn it is) can communicate, all players will hear the information this person is communicating. The player who's turn it is also gets to choose the next player.

The tricky part is that there are only 30 locations, so it's easy to iterate over them all. This is why, for example this strategy will not work:

generate a random string r, and, when it's your turn to communicate, say  (r, Hash(r + location)). The person who is unable to say this is the spy.

This will not work because the spy can compute hash(r+location) for each location, and the location that matches the given hash value is the correct location.

The spy can win with probability 1/30 by guessing a location and then acting as if that location is the correct location. Is there a protocol for the non-spies to find the spy with probability negligibly close to 29/30? (assuming that all non-spies follow this protocol but the spy can do whatever they want).

I think the following protocol works:

Let's take a group where discrete logarithm is hard (say, a classic elliptic curve); I'll note the curve law with additions. Let $q$ be the group order (prime). Let $G$ be a conventional generator for that group. Let $H$ be a hash function whose output is a group element (the value $H(x)$ for an input $x$ should be such that nobody has any clue as to the discrete logarithm of $H(x)$ in base $G$). Let $h$ be another hash function that produces bytes (like SHA-256).

Each player $i$ generates a random value $x_i$ modulo $q$, and publishes (i.e. announces) $P_i = x_iG+H(loc)$ (where $loc$ is the secret location).

Once all $P_i$ have been broadcasted, each player $i$ then computes, for all other players $j$, the values $s_{i,j} = x_i(P_j-H(loc)) = x_ix_jG$. The important point here is that $s_{i,j} = s_{j,i}$ for all pairs $(i,j)$.

Then, each player $i$ publishes the list of values $t_{i,j} = h(i||j||s_{i,j})$ for all $j\neq i$. Each value $t_{i,j}$ can be computed by the player $i$ and the player $j$.

Each player $i$ recomputes all the $t_{j,i}$ and compares them with the received values. If all players follow the protocol, then they should all match, except the one from the spy (if the spy did not guess the location correctly when computing his own point $P$). The player $i$ can then detect the spy, and, in that situation, all other honest players have also detected the spy, so they all agree when he is accused.

On the other hand, if the spy did guess the location properly, then he will notice that all the received $t_{j,i}$ match his own recomputed $t_{j,i}$, confirming his guess, and he can proceed to winning the round. I don't think this case can really be avoided, on a general basis: the spy can always get lucky with his initial guess, in which case he cannot be uncovered by any protocol, and thus he can infer the correctness of his guess by his own survival.

The protocol above is an extension of the Encrypted Key Exchange, the first PAKE protocol to be published, by Bellovin and Merritt in 1992.

It's clear that the $P_i$ points reveal no information on the secret location. If $h$ behaves like a random oracle, then the spy may extract information from any published $t_{i,j}$ value only by guessing exactly the value $s_{i,j}$, i.e. by breaking the EKE between $i$ and $j$.


Should we trust the NIST-recommended ECC parameters? Recent articles in the media, based upon Snowden documents, have suggested that the NSA has actively tried to enable surveillance by embedding weaknesses in commercially-deployed technology -- including at least one NIST standard.

The NIST FIPS 186-3 standard provides recommended parameters for curves that can be used for elliptic curve cryptography.  These recommended parameters are widely used; it is widely presumed that they are a reasonable choice.

My question. Can we trust these parameters?  Is there any way to verify that they were generated in an honest way, in a way that makes it unlikely they contain backdoors?

Reasons for concern.
Bruce Schneier has written that he has seen a bunch of secret Snowden documents, and after seeing them, he recommends classical integer discrete log-based cryptosystems over elliptic curve cryptography.  When asked to elaborate on why he thinks we should avoid elliptic-curve cryptography, he writes:

  I no longer trust the constants. I believe the NSA has manipulated them through their relationships with industry.

This suggests we should look closely at how the "constants" (the curve parameters) have been chosen, if we use ECC.  This is where things look concerning.  I recently read a message on the tor-talk mailing list that seems to suggest the NIST curve parameters were not generated in a verifiable way.  That message examines how the parameters were generated:

  I looked at the random seed values for the P-xxxr curves. For
  example, P-256r's seed is c49d360886e704936a6678e1139d26b7819f7e90.  No justification is given for that value.

and ultimately concludes:

  I now personally consider this to be smoking evidence that the
  parameters are cooked.

Based upon my reading of FIPS 186-3, this appears to be an accurate description of the process by which the P-xxxr curves were generated.  So, should people be concerned about this?  Or is this just paranoia based upon loss of trust in the NSA?

See also these slides from Dan Bernstein and Tanja Lange, particularly pp.6-7, 8-10, 14-17 for further discussion about the NIST parameter choices.

Edit: I have made some tests and I found something weird. See at the end.

Initial answer:

At least the Koblitz curves (K-163, K-233... in NIST terminology) cannot have been specially "cooked", since the whole process is quite transparent:

Begin with a binary field $GF(2^m)$. For every m there is only one such field (you can have several representations, but they are all isomorphic).
Restrict yourself to prime values of m to avoid possible weaknesses by plunging into sub-fields.
Consider curves $Y^2+XY=X^3+aX^2+b$ where $b \ne 0$; this is the normal form of non-supersingular curves in binary fields.
You only want curves where $a = a^2$ and $b = b^2$, so that you can speed up computations with the Frobenius endomorphism (basically, you replace point doublings with simply squaring both coordinates, which is very fast).
When $a = 0$, the curve order is necessarily a multiple of 4; when $a = 1$, necessarily a multiple of 2.

Then you want a curve order which is "as prime as possible", i.e. equal to $2p$ or $4p$ for a prime $p$ (depending on whether $a = 1$ or $0$). For $m$ ranging in the "interesting range" (say 160 to 768), you will not find a lot of suitable curves (I don't remember the exact count, but it is something like 6 or 7 curves). NIST simply took the 5 of them corresponding to the $m$ values which were closest to (but not lower then) their "security levels" (80, 112, 128, 192 and 256-bit "equivalent strength"). There is no room for "cooking" here.

So I would say that at least Koblitz curves are demonstrably free from all these "cooking" rumours. Of course, some other people argue that Koblitz curves have some special structure which might be leveraged for faster attacks; and that's true in two ways:

Faster computations mean faster attacks, mechanically;
One can solve discrete logarithm "modulo the Frobenius endomorphism" which means that K-233 is about as strong as a 225-bit curve (because 233 is an 8-bit number).

I still consider such curves to be reasonable candidates for serious cryptographic work. They have been "in the wild" for more at least 15 years and are still unscathed, which is not bad, as these things go.

Edit: I have made a few tests, enumerating all Koblitz curves in $GF(2^m)$ for $m$ ranging from 3 to 1200. For each $m$, there are two curves to test, for $a = 0$ and $a = 1$. We consider the curve "appropriate" if its order is equal to $4p$ (for $a = 0$) or $2p$ (for $a = 1$) with $p$ prime (this is the "best possible" since the curve is always an extension of the same curve in $GF(2)$, so the curve order is necessarily a multiple of the curve in $GF(2)$, and that's 4 or 2, depending on $a$). For the "interesting range" of $m$ between 160 and 768, there are fourteen appropriate curves:

$m = 163$, $a = 1$
$m = 233$, $a = 0$
$m = 239$, $a = 0$
$m = 277$, $a = 0$
$m = 283$, $a = 0$
$m = 283$, $a = 1$
$m = 311$, $a = 1$
$m = 331$, $a = 1$
$m = 347$, $a = 1$
$m = 349$, $a = 0$
$m = 359$, $a = 1$
$m = 409$, $a = 0$
$m = 571$, $a = 0$
$m = 701$, $a = 1$

NIST's target was their five "security levels" of 80, 112, 128, 192 and 256 bits, and a curve would match that level only if its size is at least twice the level. So the standard curve for each level ought to be the smallest curve which is large enough for that level. This should yield Koblitz curves in fields of size 163, 233, 277, 409 and 571 bits, respectively.

Strangely enough, this matches NIST's choices except for the "128-bit" level, in which they chose $m = 283$ instead of $m = 277$. I don't know the reason for this. For both field sizes, the smallest possible reduction polynomial is a pentanomial ($X^{277}+X^{12}+X^{6}+X^{3}+1$ for $m = 277$, $X^{283}+X^{12}+X^{7}+X^{5}+1$ for $m = 283$), so neither field is at a computational advantage on the other is using polynomial bases (well, the 277-bit field is a bit shorter, so a bit faster). With normal bases, the 277-bit field is actually more efficient, because it accepts a "type 4" Gaussian normal basis, while the 283-bit field is a "type 6" (smaller types are better for performance). The list of all suitable Koblitz curves is easy to rebuild and, indeed, NIST / NSA did it (e.g. see this article from NSA-employed J. A. Solinas -- search for "277").

Why they chose the 283-bit field is mysterious to me. I still deem it very improbable that this constitutes "cooking"; this is a backdoor only if NIST (or NSA) knows how to break Koblitz curves in a 283-bit field and not in a 277-bit field, which not only requires an assumption of "unpublished big cryptanalytic advance", but also requires that supposed novel breaking technique to be quite weird.


Relevance of Input and Ouput size of PRF on CTR mode I'm working on exercise 3.25 on Katz' book (2nd ed):

  Let $F$ be a pseudorandom function such that for $k \in \{0, 1\}^n$ the function $F_k$ maps $\ell_{\text{in}}(n)$-bit inputs to $\ell_{\text{out}}(n)$-bit outputs.

  (a) Consider implementing CTR-mode encryption using $F$. For which
  functions $\ell_{\text{in}}$, $\ell_{\text{out}}$ is the resulting encryption scheme CPA-secure?

  (b) Consider implementing CTR-mode encryption using $F$, but only
  for fixed-length messages of length $\ell(n)$ (which is an integer multiple of $\ell_{\text{out}}(n)$). For which $\ell_{\text{in}}$, $\ell_{\text{out}}$ does the scheme have indistinguishable encryptions in the presence of an eavesdropper?

My answer is that it really does not matter: any combination of $\ell_{\text{in}}$, $\ell_{\text{out}}$ and $\ell$ will yield the mentioned security. Why do I think this? well, the proof that CTR mode is CPA-secure is presented in the book as theorem 3.32 and I'm pretty sure it only requires $F$ to be a PRF, with no restriction on the input and output sizes (even though it is presented with length-preserving PRF's), this should answer (a).

For part (b) I think something similar: the proof is not dependent on the message length (as long as it is polynomial in $n$, of course), so fixing a particular $\ell$ should not lead a vulnerability on CPA-security (let alone EAV-security).

Where am I failing? Intuition says this is not the case! for instance, if $\ell_{\text{in}}(n) = 1$ (for all $n$), then the counter can only be increased once and from there it will cycle
$${\tt ctr}, {\tt ctr}+1, {\tt ctr}, {\tt ctr}+1,\ldots,$$
which should lead to an attack, doesn't it? The proof should take out these cases somehow, but I just can't see it, it seems to work without even in this case.

My solution

I think I've found a solution, there was a lack of comments/answers so I will post it as an answer in order to conclude this.

I'll begin with part (b).

Cycles in the counter must be avoided, that is, it must be ensured that ${\tt ctr}, {\tt ctr}+1,{\tt ctr}+2,\ldots$ never reaches ${\tt ctr}$ again. Notice that ${\tt ctr}\in \{0,1\}^{\ell_{\text{in}}(n)}$, so it must be ensured that the maximum block length $\ell(n)$ does not exceed $2^{\ell_{\text{in}}(n)}$. That's a constraint between ${\ell(n)}$ and ${\ell_{\text{in}}(n)}$. $\ ^{1}$

On the other hand, in the proof of the CPA-security of CTR mode the "birthday" term $2q(n)^2/2^n$ appears bounding the probability of a successful attack compared to guessing, where $q(n)$ is the maximum number of blocks (so $q(n) = {\ell(n)}/{\ell_{\text{out}}(n)}$).
This term must be negligible, and that is the restriction between ${\ell(n)}$ and ${\ell_{\text{out}}(n)}$.

Regarding part (a), I claim that there is not any constraint between $\ell_{\text{in}}$ and $\ell_{\text{out}}$ as long as $\ell(n)$ satisfies the conditions mentioned above. This can be seen by revisiting the proof and checking that it holds independently of the polynomials $\ell_{\text{in}}$ and $\ell_{\text{out}}$ (so yes, the ratio $\ell_{\text{in}}/\ell_{\text{out}}$ can be anything).

$^{1}$This is assumed in the proof of CPA-security on Katz' book when they say: the values $f({\tt ctr}^∗ + 1),\ldots,f({\tt ctr}^* + \ell^*)$ used when encrypting the challenge ciphertext are uniformly distributed and independent of the rest of the experiment


HMAC SHA256 for deriving session keys using random nonce I need to derive session key in order to create an application layer secure channel between mobile app and a bluetooth device. My scheme is similar to
this scheme that uses a HMAC and counter.

Provided that between mobile app and BLE device have already share a same key $K$ (256-bits) through provisioning process, I plan to derive session key with these steps:

Let $A$ be 16-bytes of generated random number from mobile app and $B$ be 16-bytes of generated random number from BLE device. Both are treated as nonce or IV.
Mobile app sends random $R_A$ to BLE device $A$ and BLE device sends its random $R_B$ to mobile app $B$ on unsecure communication channel.
Both mobile app and BLE device derive session key using:

Session Key = $\text{HMAC-SHA256}(K, R_A||R_B)$

The random $R_A$ and $R_B$ are both concatenated.

Now both parties will share the same session key for upcoming communication using AES. I use this scheme because my BLE device is limited on its processing power for asymmetric method.

Is it safe to implement this scheme for deriving session key?

Yes, it is secure, as the KDF is secure, as the answers to the question you linked to indicates.

However, there are some things that you should keep in mind:

The result of the KDF is not validated; if the initial shared key is incorrect you will only find out once the session keys are used. This is tricky to implement if you want to use the session key for authentication (you may want to use explicit authentication rather than implicit authentication during the session).
Both parties now share a single session key, so you may need to be careful when using encrypt-then-MAC.
Both parties use share a single session key, possibly for communication in both directions, which means you can have messages replayed not just from $A$ to $B$, but also from $A$ to $B$ and then replayed back to $A$.
The scheme will not provide any forward secrecy that ephemeral Diffie-Hellman could provide.

You can e.g. use a single byte tag in addition to calculate both an encryption key and a MAC key, possibly a third one to create a value that can be exchanged to authenticate the entities.

You could include the identities $ID_A$ and $ID_B$ in the MAC calculation, e.g. $ID_A || ID_B || R_A || R_B$ for sending from $A$ to $B$.


HMAC construction based on the combination of two hash functions I would like an $\operatorname{HMAC}$ that's based on two different hash functions ($H_1$ and $H_2$), so that a break of the combined $\operatorname{HMAC}$ would imply a break of $\operatorname{HMAC}(H_1)$ and of $\operatorname{HMAC}(H_2)$.  The combined HMACs in TLS and SSL have attempted to achieve this property, but according to Anja Lehmann's dissertation, not very well.  Lehmann suggests a construction for combining $H_1$ and $H_2$ to make a generic $H_*$, but with considerable complexity and expense.

I was wondering if there is a construction specific to $\operatorname{HMAC}$ that's simpler and cheaper.  One I thought of is something I call $\operatorname{HMAX}_{H_1,H_2}(k,M)$, which derives $\mathrm{ipad}$ and $\mathrm{opad}$ from $k$ as in standard $\operatorname{HMAC}$, then computes

$$\mathrm{inner} = \mathrm{opad} \operatorname\| H_1(\mathrm{ipad} \operatorname\| M) \operatorname\| H_2(\mathrm{ipad} \operatorname\| M)$$

and then outputs:

$$H_1(1 \operatorname\| \mathrm{inner}) \oplus H_2(2 \operatorname\| \mathrm{inner})$$

This construction seems to capture the collision-resistance of the concatenation hash combination and the PRF-amplification of the XOR hash combination. It also doesn't inflate its output length. I don't have a proof that it works though.  Does this seem like a good or bad idea?

Edit: Add "$1$" and "$2$" to the outer hashes to prevent an answer of $0$ when the same hash is used for $H_1$ and $H_2$.  Thanks to Paŭlo Ebermann for pointing out that corner case.

This is proabably a bad idea.

There are several results that indicate there are problems with this design:

While $\oplus$ preserves the PRF property, it is not a robust combiner: it requires that $H_1$ and $H_2$ are independent to guarantee the PRF property is preserved.
i.e. consider what happens to your design if $H_2$ is defined as $H_2(2 \parallel data) = H_1(1 \parallel data)$
Boneh06 and Pietrzak07 proved a lower bound on the size for collision resistance preserving combiners, showing that they can't be significantly, i.e. $\theta(log_b)$, smaller than the concatenated size of both hash functions. These papers don't seem to directly address $HMAC$ style key data, but they appear to be quite general results.
Mittelbach13 removed the concatenated size limit for collision resistance preserving combiners, but at the cost of significant time complexity (well beyond the $Comb_{4P}$ combiner introduced in Lehman10 and the combiner you have described) and specific restrictions on the hash functions and the proof.
Part of your motivation for this design appears to be the complexity and expense of the $Comb_{4P}$ combiner, but aside from output size (2 x for $Comb_{4P}$) the schemes appear similar.
i.e. assuming hash functions like SHA-256, with a $block size = 2 \times  output size$, $Comb_{4P}$ requires hashing $M$ with both $H_1$ and $H_2$, followed by 4 further hash blocks and 5 $\oplus$s. With a similar instantiation your design appears to hash $M$ with both $H_1$ and $H_2$, followed by 6 further hash blocks and 1 $\oplus$s.

I'm still trying to get my head round all this, so I could be a little off-base with some of these, but in general this doesn't appear to be an area where easy shortcuts can be taken.

I'm not quite sure what to make of the $HMAC_{H0}(k_0,m) \oplus HMAC_{H1}(k_1,m)$ construction described by Ricky Demer - it looks like it would preserve the PRF properties well, but on the surface it seems to violate the Boneh result on the lower bound for a combiner that preserves collision resistance.


Can a digital watermark be still extracted from the reprinted digital watermarked image? If I'm able to extract a watermark from a printed watermarked image, will I be still able to extract the watermark information if I first scan the printed watermark image and reprint it (make a copy of printed watermarked image with high quality scanner and printer)?

Yes it can. But it's very difficult to resist the printing process.

You can find useful information here:
http://jultika.oulu.fi/files/isbn9789526200583.pdf


Is it usual for a signed message to contain the public key of the signer? In protocols/systems which use ECDSA, is it common for the message to contain the public key of the message signer?

If not, how do recipients know that the message has been signed by the correct private key, and how do they know which public key to use to verify the signature?

I'd say that most of the time the signature is accompanied by the certificate of the signer. This certificate contains the public key. Most container formats such as CMS (used in S/MIME, also known as PKCS#7) or XML digsig contain specific fields that may contain certificates - and usually do.

When the certificate is received the Public Key Infrastructure (PKI) can be used to verify the certificate. In case of X.509 PKI that would for instance include verifying the chain of certificates leading to a trusted certificate (probably published by a Certificate Authority and included in a browser or system key store). Of course additional validation/verification should be performed, such as testing validity of the certificate and the revocation status. As you already noted, the other way is to validate the certificate or public key through a web of trust, such as used for (open) PGP.

The PKI is indeed a trust framework, although I would not directly call it a "trusted channel".

For specific protocols it may be that the public key is simply looked up in a trust store based upon a user name or key id. This is for instance the case in SSH, where the public keys are stored in a file containing trusted public keys and bound to the specific user.


How to check the strength of an encryption algorithm? I asking for advice on how to check strength of an encryption algorithm.

The first step is to write a new question on crypto.stackexchange.com asking for advice on how to check whether if it is secured enough (or not).

The second step is to stop, throw away everything you've done and become an expert in GPG and then port GPG to your platform.

The rationale for being so discouraging is that if you have to ask how to check whether it's secured enough you obviously don't know nearly enough to even start writing an app that encrypts text securely. Many people who would have a very good idea about how to check the security would balk at the task of writing something like GPG themselves.


Calculation-Intensive Decryption I'm looking for an encryption scheme that has the following properties:

Decryption is CPU intensive, so decrypting an encrypted text may take some time (relatively, of course). Preferably, encryption should be negligible.
The time to decrypt can be easily raised.
The time to decrypt can be easily lowered.

Naively, I could accomplish #2 and #3 by re-encrypting the data n times and increasing and decreasing n to raise or lower the decryption time.

Is there any such encryption method?

You could throw away bits of the encryption key so that there is a brute-force portion to decrypting e.g. encrypt with a 128-bit key but only share 96 bits.

Or protect the key using something like an RSA time-lock puzzle. The benefit of this is recovering the key cannot be sped up with parallelism.


Functional difference between stream cipher, XOF, seed expander, KDF, etc This question is a request for terminology clarification.

In a canonical XOF interface, the output can be extended as much as needed, but does input has to be variable-length or can be fixed-length in certain constructs?

SHAKE{128|256} are the first well-known standardized XOFs, there are many ad-hoc constructs before it such as OAEP-MGF, AES-CTR, RC4/ChaCha20-based arc4random() function.

For AES-CTR and RC4/ChaCha20, are they also XOF in any sense? If not, what are they strictly speaking?
What does a seed-expander do? Does it take a fixed/variable-length bitstring as input and produce another fixed/variable-length bitstring as output?
What exactly is the relationship between XOF, Seed-Expander, (optionally bring up KDF).

Before we start answering the subquestions, let's bring up some background knowledge.

The sponge construct was first proposed by the Keccak team as a bridging element in a security proof for the older RadioGatún hash function. On their web page, they describe it as a generalization of both hash function (var->fix) and stream cipher (fix->var).

Since SHAKE-128/256 are directly based on sponge constructs, we'll just assume for now that the authors intended XOF as the generic term for their trademark product Sponge.

type                input                  output
stream cipher       fixed-length key       variable-length key-stream
xof                 variable-length data   variable-length data
hash function       variable-length data   fixed-length digest

So question 1 can be answered as follows: no, that would violate the definition of XOF.

And question 2: no. They're stream ciphers, two of which use the counter construct.

If you search "cryptographic seed-expander" on Bing in 2018-02, then the first few results unrelated to Crypto.SE refer to the NIST page for post-quantum cryptography. The story goes like this:

Back in the early days of preparing for the contest, NIST specified that submitters obtain randomness source for their keygen-signing-encrypt functions using libc rand(). This was correctly met with protest by notable participants on the official mailing list.

After discussion, it was decided there would be separate randomness calls for 1.) generating small amounts of keying material sufficient for a given security level, and for 2.) expanding keying material into a longer bitstring from which mathematical objects could be extracted.

The latter has since been called "seed expander" in official NIST documents, which roughly corresponds to DRBG.

So question 3 can be answered as follows: It does what a DRBG/PRNG does. The interface of a DRBG applies.

I'd like to answer question 4 as follows: It doesn't make sense to compare them, because their purposes are different. And this difference in purpose makes their programming interface different as well. For example, the typical interface for a XOF function is much simpler than that for a DRBG, and has many fewer parameters to tune than KDF.


Effective key length in DESX variant We are given a variant of DESX, where $ENC(M)= DES_k(M \oplus k_1)$ (keys are 64bits). In DESX effective key length is $119-lb(M)$ according to wikipedia, but I have not found how this is calculated. I know that the effective key length should be less than that, but how do we find the exact length?

The security of this variant is no better than regular DES. To see this, consider an attacker with access to $\text{ENC}(M) = \text{DES}_k(M \oplus k_1)$ and $\text{DEC}(C) = \text{DES}^{-1}_k(C) \oplus k_1$, its inverse:

Obtain one (or more) plaintext-ciphertext pair $M, C$;
Iterate through all $2^{56}$ DES keys;
For each candidate key $k$, obtain $k_1 = \text{DEC}(C) \oplus \text{DES}^{-1}_k(C) = M \oplus \text{DES}^{-1}_k(C)$;
For the correct key $k$, $k_1$ is also correct. This can be confirmed by checking against a few known plaintext/ciphertext pairs.

DESX avoids these trivial attacks by making it impossible to obtain $k_1$ without knowing $k_2$, or vice-versa. Hence DESX's security for $56+64+64$ bits of key being only $2^{56 + 64}$ instead of $2^{56 + 64 + 64}$. The paper by Kilian and Rogaway goes into detail on this, but the gist of it is: iterate through $k$ and $k_1$, and get $k_2$ for free, as above.


Prime factorization of RSA modulus Consider RSA public-key encryption with public modulus $N=3953$.

Suppose we know that the public keys $e_1=337$ and $e_2=23$ correspond with the decryption information $d_1=3385$ and $d_2=2663$. That is: $e_1d_1=e_2d_2=1$ mod $\phi(N)$ and $m^{e_1d_1}=m^{e_2d_2}=m$ mod $N$, for all integers $m$ that are relatively prime to $N$.

How do I find the prime factorization of $N$ from the above information? I want to find the prime factorization without any brute-force method.

I have noticed that $m^{e_1d_1-e_2d_2}=1$ mod $N$. I have also noted that $e_1d_1-1$ is a multiple of $\phi(N)$. Does this say somehting about the prime factorization of $N$?

Edit:

$gcd(e_i,\phi(N))=1$ and $e_id_i=1$ mod $\phi(N)$ by assumption, for $i=1,2$.

If you knew $pq$ and $p+q$, you could find $p$ and $q$ by algebra. If you knew $pq$ and $(p-1)(q-1)$, you could find $p+q$. Now $e_1d_1-1$ and $e_2d_2-1$ are both said to be multiples of $\phi(n)$, so their greatest common divisor should be a (smaller) multiple of $\phi(n)$, from which you could easily guess $\phi(n)$.

I've probably said too much already, given that this is a homework assignment.


Finding a Caesar cipher key given encrypted message and part of decrypted message? How can I find the Caesar cipher key if I have an encrypted message and part of the decrypted message? For example: I know that the message ends with a constant set of words, but the length of the key is not known.

I have tried using the Kasiski test to check for repeating strings in the encrypted message, but the message i have is a very small one (around 200 characters) so i don't see any useful patterns that might help me narrow down on the length on the key.

For the Caesar cipher there are only 25 possible keys (and the key $k=0$ which degenerates into the identity function, ciphertext = plaintext).

Just try all possible shifts one by one starting from $k=1$ to $k=25$ (this constitutes a brute force attack). After each shift you need to validate that it results in an intelligible plain text by decryption of the ciphertext. For the Caesar cipher brute force attack is efficient.

Now if you have plaintext and corresponding ciphertext pair work become more easy you don't need to do brute force attack. As in generic Caesar cipher encryption/decryption is defined as

$$C = (P + K) \bmod 26$$

$$P = (C - K) \bmod 26$$

Then from above $K = C - P$ (for each corresponding ciphertext / plaintext character).

For example if the plaintext is "abc" and the ciphertext is "def". Then teh 'd' zero-based index is $3$ within the alphabet. And the and 'a' location is $0$ then $K=3-0=3$


Security of this PRF Given $F$ a secure PRF with input size $\lambda$. Define $F'$ as

$F'(k,x||x') = F(k, 0||x)\oplus F(k, 1||x')$

with $x$ and $x'$ of $\lambda-1$ bits.

Is $F'$ a secure PRF?

No, $F'$ is not a secure PRF. There exists an efficient distinguisher $D$, which can distuingish between $F'$ and $f$ with overwhelming probability.

Imagine D asks her two oracles for the value of $F'(k,x'\mathbin\Vert x')$ and $f(x' \mathbin\Vert x')$.

$D$ additionally asks the following queries from her oracle:
$$F'(k,x\mathbin\Vert x')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x')  $$
$$F'(k,x\mathbin\Vert x'')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x'')  $$
$$F'(k,x'\mathbin\Vert x'')=F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x'')  $$

Finally if she xor's all three of these values she can obtain $F'(k,x'\mathbin\Vert x')$:
$$F'(k,x\mathbin\Vert x')\oplus F'(k,x\mathbin\Vert x'')\oplus F'(k,x'\mathbin\Vert x'')=F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x')\oplus F(k,0\mathbin\Vert x)\oplus F(k,1\mathbin\Vert x'')\oplus F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x'')=F(k,0\mathbin\Vert x')\oplus F(k,1\mathbin\Vert x')=F'(k,x'\mathbin\Vert x').$$

Therefore she can distinguish between $F'$ and $f$ with overwhelming probability. $D$ is trivially efficient (runs in polynomial time), as it only uses $3$ oracle queries.


How does the nonlinear function of KeeLoq work? I want to know how the nonlinear function of KeeLoq works.

Here at Wikipedia it says that:

  The NLFSR feedback function is 0x3A5C742E

I understand that F(a,b,c,d,e) = 3A5C742E.

Now, he did not say anything about encoding of a, b, c, d, e. I consider them as in ASCII. But each letter will have 8-bit. So total would be 40. Could someone explains to me how to compute this function or what is the encoding scheme of a, b, c, d, e in order to apply Karnaugh map?

Suppose you want to compute $F(0,0,0,1,0)$, then note that $00010_2 = 2_{10}$ so the result is bit $2$ (counted from $0$ from right to left) of 0x3A5C742E, or in C terms just (3A5C742E >> 2) & 1 = 1 This is the standard convention when encoding such Boolean functions.

As another example F(1,1,1,1,1) = (0x3A5C742E >> 31) & 1 = 0 as $11111_2 = 31_{10}$ etc.


Derive $x$ when given $g,g^x$ and $g^{(1/x)}$? If an adversary has access to the generator g of a group G and is given access to $g^{x}$ and $g^{(1/x)}$, will it make it any easier to derive the value of $x$ compared to when he had access to only $g$ and $g^{x}$?

EDIT: My question is different from “Can we reduce Diffie-Hellman problem to “Discrete-log inversion” problem?” as in this case the adversary has the values and does not need an oracle to derive it

Any group where you can derive $x$ from $g, g^x, g^{1/x}$ would also have the Discrete Log problem be equivalent to the (computational) Diffie-Hellman problem.  Since this is not known to be true in general, we don't know of any general method for deriving $x$ from those values.

This equivalence is quite simple to demonstrate; if it based on the fact that solving the cDH program allows us to compute $g^{1/x}$ given $g, g^x$.  So, if we assume we can recover $x$ from $g, g^x, g^{1/x}$, then we can solve the Discrete Log problem (given $g, g^x$) by first recovering $g^{1/x}$ (using our cDH Oracle), and then given $g, g^x, g^{1/x}$, recover $x$


Is this correct way to generate stream cipher using AES CTR mode? We are implementing searchable encryption techniques proposed by Song et al in Java for a paper[1]. The schemes need a Stream Cipher for achieving search over encrypted data.
The stream of random bits should be reproducible later while decryption given the same "Seed".

Now we plan to generate the stream of random bits using AES in CTR mode. What we don't understand is what is considered as "seed". Is "seed" the random 64 bits prefix part of the IV / Nonce ?

What would be the plain text  CTR mode while generating random stream ? Can we give some hard coded string as plain text as we don't really care what we are encrypting, all we want is random stream of bits that could be reproduced later

Or what is considered a secure way to generate random stream of bits ?

[1] Song, Dawn Xiaoding, David Wagner, and Adrian Perrig. "Practical techniques for searches on encrypted data." Security and Privacy, 2000. S&P 2000. Proceedings. 2000 IEEE Symposium on. IEEE, 2000.

The seed should be the key and the nonce or IV. Those input parameters determine the value of the key stream. Note that the nonce may be implied if the key is not reused, in that case the key may be the only seed, with the nonce having a static value (you should however make sure that you are not vulnerable to multi-target attacks if you use a static IV, see the comment of CodesInChaos below).

For most stream ciphers - such as CTR mode of encryption - the key stream is used to encrypt the plain text by XOR'ing the plain text with the key stream. Obviously if you are just interested in the key stream of N bits then you can simply encrypt a plain text consisting of N bits set to zero (as zero is the identity element for XOR). Depending on the implementation the underlying key stream may also be available directly.


Reasonable Password Entropy given a certain Set of argon2 Parameters I followed the recommendation of choosing threads, memory consumption and the number of iterations (in that order) on my machine. But now I wonder which passwords (by means of entropy) are actually secured by this set of parameters.
Clearly, a single letter is not secure, regardless of the parameters; but on the other hand, using a 256-bit entropy password renders the usage of argon2 pointless. So the security of my hash certainly depends on the relation between password strength and argon2 parameters. Since I am using old and not powerful hardware I am concerned, that the time it takes for me to calculate the hash is negligible for a large scale attacker. (This might be even worse for hashing on mobile phones or embedded devices.)
So the question is: Given a certain set of argon2 parameters, what is the minimal entropy a password should have so that the hash can be assumed to be secure?
Alternatively: Given a certain set of argon2 parameters, how many passwords can the fastest supercomputer available today (in 10/20/50 year) check in a second?
Edit: I am using a strong (>= 128-bit) password for locking my password manager, but entering this several times is tedious. So I thought using a key file that is protected by a simpler password. Since I am syncing stuff to the cloud, the hash of the simpler password can not be considered a secret. In order too choose a simpler password that is still considered secure, I need to be able to estimate the protection gain from using a strong KDF (e.g. argon2).
Edit 2: This question and answer tackle my question in a general context (not Argon2 specific) very well.

You should have ≈128 bits or more entropy in any password you want to remain secure regardless of the password hashing function.

Rationale: slow password hashing functions only add a constant-time factor to brute-force search. Since you don’t know the processing capabilities of any potential attacker, the only safe path is to use a very high-entropy password Such a password would be securely stored even if hashed with a single iteration of MD5 without salt.

So what do fancy iterated, “memory hard” functions buy us?

They help against, but do not prevent, attacks on low entropy passwords, the sort that humans can actually memorize. In effect, they increase the work factor required for a dictionary, brute-force, or hybrid search by a fixed amount. You could view this as “extra bits of security”, but you’ll only know how many bits you still need “to be secure” if you know with fair certainty  the computational abilities of your attacker.

If your adversary is a nation-state’s security apparatus, the number of “bits of entropy you need” in the password differs vastly from that when your adversary is me. So the only truly safe thing to do is to always use a high-entropy input password, which renders the fancy hash function pointless.

Slow password hashes are implemented to mitigate the costs to users of a breach of the password hash database. They cannot make low-entropy passwords “always secure” unless they themselves utilize 2^100 operations, making them completely impractical.


Advantages and possible usages of encryption schemes with probabilistic decryption We can define deterministic and probabilistic encryption;

Deterministic $c = E(k,m)$, and

Examples are textbook RSA, block ciphers in ECB mode.
Deterministic encryption fails to achieve CPA security.
Deterministic encryption is insecure and we don't want to use/advise to use ( there are bad exceptions for this like SIV mode doesn't have CPA security if you keep the nonce fixed don't ever do that ((see note 3)), however, AES-GCM-SIV is a non-misuse resistant scheme that prevents the IV-reuse problem of the AES-GCM )

Probabilistic $c \stackrel{R}{\leftarrow} E(k,m)$

Public schemes like Elgamal, RSA-OAEP, Pailler, and private schemes like CBC, CTR, CGM, SIV, etc.

In the case of deterministic, there is one ciphertext that decrypts to the message and in the case of probabilistic, there are many to be expected.
From the correctness requirement, we want

for deterministic case $m = D(k,E(k,m))$
for probabilistic case $c \stackrel{R}{\leftarrow} E(k,m)$, $m' = D(k,c)$ with probability 1.

The probabilistic encryption is preferable since it can provide semantic security or its equivalent and easy to use version is the indistinguishability.
Now, what if set the definition for probabilistic decryption to more than :$$\Pr[D(k,E(k,(m))=m] = 1 - negl(k)$$
instead, making it:
$$\Pr[D(k,E(k,(m))=m] = p$$
An example of this is the Rabin cryptosystem (see note 2) where $p = 1/4$ since we end up with four possible $m$. It is suggested to add some auxiliary data to plaintext to resolve. Note that Rabin cryptosystem is not randomized encryption where an IV/nonce is usually needed to achieve that. The decryption still produces randomized decryption.

Are there any other examples of randomized decryption schemes other than the half randomized Rabin Cryptosystem?

Is there any advantage or usage of randomized decryption schemes?

Notes:

This is asked as a fundamental question for clarification of the probabilistic decryption which is simply discarded in the textbooks.

Actually, Rabin has not defined an encryption scheme on their seminal paper. They defined the first secure signature scheme and hashing is a part of it. The Wikipedia article is misleading about this.

One should never use the AES-GCM-SIV with fixes nonces, one should use unique/random nonces and AES-GCM-SIV and it doesn't fail like AES-GCM if the nonce repeats under the same key.

Since when decrypting we always want to get the correct message back, there's no reason why we would want to make this ambiguous. It would have no security advantage (if the adversary can guess with any non-negligible probability, you have already lost, so ambiguous decryption can't make that harder). Thus, unlike probabilistic encryption, which is needed for security, probabilistic decryption is an undesired property that sometimes arises when trying to construct schemes. For example, with the naive Rabin, it just happens to be a property of the number theory used. The additional work required to make Rabin a trapdoor permutation is necessary to make it useful.
Thus, the only reason why randomized decryption (with a probability of error) exists is when this is what some constructions unfortunately give us. (This can be viewed in some sense as an advantage - if we weren't able to allow decryption errors, we wouldn't be able to build these schemes, some of them having advantages.) There are some examples of this: NTRU and the Ajtai scheme based on lattices. As a result, there has been some theoretical work on removing errors from encryption schemes that have them. Most notably, I recommend reading the paper Immunizing Encryption Schemes from Decryption Errors by Dwork, Naor and Reingold.


How to encrypt incomplete block with RSA as a block cipher? I have a question about an RSA academic example.
If we are using block-RSA with a block-size of 3 and we have this message: "android". It is broken into 'and', 'roi', 'd'.

How to encrypt the last character 'd'?

With such a small block size there is no way to employ RSA padding modes such as PKCS#1 v1.5 padding or OAEP. You could however see the encryption as ECB mode encryption. In that case you could apply padding mechanisms that have been constructed for symmetric block ciphers.

Those padding modes however have been defined for bytes rather than characters. That's no problem - let's just assume ASCII text so we can convert the text to bytes without issue. Within many programming environments you may not even have to perform the conversion explicitly (e.g. C has char*).

OK, so after the conversion you have multiple options (values are in hexadecimals):

PKCS#5 padding: a padding where each added byte has the value of the size of the padding in bytes (i.e. 01, 0202 or 030303 in your case).
Bit-padding: just add a single 1 bit and then zero's up to the end (i.e. 80 8000 or 800000 in your case).
Zero-padding: just add zero bytes until the next boundary, i.e. $\varnothing$ (nothing), 00 or 0000. This one is probably used most for textbook RSA.

Zero padding is non-deterministic as it may strip off 00 valued bytes at the end of the plaintext after decryption. It has however the advantage that you don't have to pad when the plaintext is already correctly sized.

Furthermore, at least for ASCII (and UTF-8) you won't find any zero bytes in printable text. Zero byte value is often seen as end-of-string marker - especially in the C language. Don't forget that your string may need to end with a 00 in those kind of environments (so make your buffer one byte larger and set the rightmost byte to 00 before or after decryption).

If the zero's are not stripped off automatically by the runtime then you usually have right-trim function such as rtrim(plaintext, '\0') available to you.

After conversion you need to convert the 3 byte sequences into unsigned integer before you can feed them into your function that performs modular exponentiation with the public key. PKCS#1 defines a method on how to do that called OS2IP (and I2OSP to convert back).

Make sure that the resulting integer is always smaller than the modulus (ASCII is 7 bit, so a 24 bit modulus should be sufficient).


How does a Padding Oracle Attack work in practice? I have understood how the padding oracle attack works in theory. Now, I am trying to visualize it in a real scenario.

Can someone please give a real scenario in which an attacker can insert himself in the channel and send cipher texts and be able to receive the error messages indicating success or failure of encryption? I am struggling to establish how this attack would work.

Here's a real-world example: A captcha service behaves as follows. First, it generates a distorted image of some known text $t$. It sends then image to a web browser, and waits for a response. It compares the response to $t$ to decide whether the captcha is successful.

In a stateful solution, the captcha service itself would have to store $t$ while the web browser would keep some sort of identifier. This leads to all sorts of bookkeeping by the captcha service.

A better approach is to make the captcha service stateless. To do this, you must store the correct solution $t$ to the captcha puzzle in the web browser client! Obviously this solution should be encrypted. The idea is to give the client an image and a ciphertext that encrypts the solution (under a key known only to the captcha service). The client presents the claimed solution along with the ciphertext, and the service just needs to decrypt in order to verify.

But nothing prevents the client from presenting some other ciphertext! This fact (along with poor choice of unauthenticated encryption and error messages leaking padding validity) has led to padding oracle attacks against captcha services. With a standard padding oracle attack you can actually systematically decrypt ciphertexts, hence obtain the captcha solution. Here is a video (loud annoying music) demonstrating a proof-of-concept on a real captcha service.


LWE secure with one entry without noise I'd like to know, is Learning With Error (LWE) (with modular noise) "secure" if one entry has no noise?

More precisely, I have:

a random matrix $A \in \mathbb{Z}_q^{m \times n}$
a random string $s \in \mathbb{Z_q}^{n\times 1}$
and a "small" noise vector $e \in \mathbb{Z}_q^{m\times1}$, such that the first component of $e$ is $0$, i.e. $e_{1,1} = 0$.

Then, can I distinguish between $(A, As+e)$ and $(A, b)$, with $b \in \mathbb{Z}_q^{m}$ chosen uniformly at random?

Yes. This problem is roughly equivalent to LWE.

If you have an oracle to solve $LWE_{n, q, m, \sigma}$, then you can solve an instance $(A, b := As + e)$ of your problem just by sampling a Gaussian $e_1$ and add it to $b_1$, that is, defining $b' := b + (e_1, 0, 0, ..., 0)$.

Of course, $(A, b')$ is a legitimate instance of $LWE_{n, q, m, \sigma}$ and can be solved with the oracle.

On the other hand, if you have an oracle to your problem, then given an instance $(A, b := As + e)$ of $LWE_{n, q, m, \sigma}$, you can try values to $e_1$ in order to produce a new error vectors with a zero in the first entry.

For typical LWE instances, $q$ is polynomially big in $n$ and the Gaussian parameter $\sigma$ is $\alpha \cdot q$ for some $\alpha$ between zero and one. Therefore, the errors values are also polynomially big in $n$ (they are bounded by $k \cdot \sigma$ for some very small constant $k$ with probability exponentially close to 1).

If you do a loop through those possible values of $e_1$, always defining $b' := b - (e_1, 0, 0, ..., 0)$, at some point, you will subtract the correct value and produce a legitimate instance of your problem, which the oracle will then be able to solve.