How can we formally define a Pseudo-Random Shuffle function? My question is related to: When we turn Random shuffle to Pseudorandom Shuffle

The idea is to permute the elements in vector $\mathbf{v}$ pseudorandomly, where $|\mathbf{v}|=n$;

I am aware that we can use Fisher-Yates shuffle for pseudorandom shuffle (in fact we replace the random generator with a pseudorandom one). So we can use a key: $k$, when we want to pseudorandomly shuffle the vector.

Let the pseudorandom shuffle be: $\pi (k,\mathbf{v})$

How to formally define the pseudorandom function? For instance, do we need to say pseudorandom shuffle must be indistinguishable from random shuffle?
Is there any textbook or paper has already defined it?

A PRP (pseudorandom permutation) can be mapped onto the index of each element in vector $\mathbf{v}$ to generate a new index for that element in the shuffled array.

As long as the PRP is secure, the shuffle should be indistinguishable from random. Theoretically, this works if the PRP's input/output is the same size as the number of elements in the array. But in the real world, a PRP construction that can vary it's input/output size for various lengths doesn't exist.

AES-256 could be used as the PRP if there were $2^{256}$ elements in the array. Any stream cipher could be used as long as the size of the vector was a power of $2$. In the real world, there are also memory issues as you have to store values somewhere as you shuffle them. Fisher-Yates solves both these issues by using a PRNG to choose elements to exchange.

That's just my idea of a way to define a pseudorandom shuffle. Using a PRP should make the proof easy. Here's a paper that defines a pseudorandom shuffle in a different way: "The Strength of Weak Randomization: EasilyDeployable, Efficiently Searchable Encryptionwith Minimal Leakage"


Potential Coppersmith's attack on RSA Sorry if I don't express myself well in English.

The solutions $h$ and $k$ of

$$[(h+1)^2]*[(2*h+2)^2/2-1]=X* M$$

and

$$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*M$$

are such that each $M$ number divisible by $9$ has these characteristics:

$$(h+1)/3=(k+1)/6$$

and

$$k+h+2=M$$

and $M$ is a divisor of a sum of odd consecutive cubes from $1$ to $u=2*h+1$ and from $1$ to $v=2*k+1$

So we're going to look for numbers divisible by $9$ in this way:

let $N =a*b$ be a number to be factored then $N-(2 * s)^2-2*s*n=M$

where $n=b-a$ and $s$ goes from $1$ to $8$

Therefore, if $N != 9*c$ we will have $8$ formulas.

Solving:

$[(h+1)^2]*[(2*h+2)^2/2-1]=X*(N-(2*s)^2-2*s*n)$

,

$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(N-(2*s)^2-2*s*n)$

,

$(h+1)/3=(k+1)/6$

,

$k+h+2=(N-(2*s)^2-2*s*n)$

,$h$,$Y$,$X$,$k$

example $N=209$

for $s=1$

Solving:

$[(h+1)^2]*[(2*h+2)^2/2-1]=X*(209-4-2*n)$

,

$[(k+1)^2]*[(2*k+2)^2/2-1]=Y*(209-4-2*n)$

,

$(h+1)/3=(k+1)/6$

,

$k+h+2=(209-4-2*n)$

,
$h$,$Y$,$X$,$k$

We will have:

$-16*n^3+4920*n^2-504282*n+17228405=X*81$

Now comes the part I don't understand, and I thought I'd use the Coppersmith method (if one can use it).

Since the maximum $n$ in a generic number to be factored in the integer part of $N/3-3$, so in our case the integer part of $209 / 3-3$ = $66$.

$[(66^3)/81] = 3549,...$ so we will take $P = 3557$

$-(3557*16)*n^3+(3557*4920)*n^2-(3557*504282)*n+(3557*17228405)=X*(3557*81)$

Now we know that there exists n0 such that |n0|<(3557*81)^(1/3) and that

$-(3557*16)*n0^3+(3557*4920)*n0^2-(3557*504282)*n0+(3557*17228405)=0 \pmod{81*3557}$

Now to use the Coppersmith method my questions are:

should the coefficient of $n ^ 3$ be $1$?
should the $GCD$ of all the coefficients of $n$ and $P * 81$ be $1$?
If we know the factorization of $81*P$, can we benefit from it?
What is the problem with using the Coppersmith method for $N$ with $1000$ digits?

EDIT $13$ September $2019$ :

$-16*n^3+4920*n^2-504282*n+17228405=X*81$

to make the coefficients less than $81$

we can do so

$-16*n^3+4860*n^2+60*n^2-504225*n-57*n+17228376+29=X*81$

$-16*n^3+(60*81)*n^2+60*n^2-(6225*81)*n-57*n+(212696*81)+29=X*81$

then

$-16*n^3+60*n^2-57*n+29=A*81$

Now is it easier to solve it?

I'll try to answer your questions. First I shall write  Coppersmith's Theorem.

Theorem.  Let $0<\varepsilon<1/d$ and $F(x)$ be a monic polynomial of degree $d$ with at least one root $x_0$ in  ${\mathbb{Z}}_N$ and $|x_0|<X =\lceil 0.5N^{1/d-\varepsilon}\rceil.$  Then, we can find $x_0$ in time $poly(d,1/\varepsilon,\ln{N}).$

First, notice that in your polynomial you know the factorization of the modulus. But, in Coppersmith method, you can find a solution $\mod{N},$ even if you don't know the factorization of $N$ (e.g. if $N$ is an RSA modulus).

should the coefficient of $^3$ be 1?

Yes, in the theorem of Coppersmith we deal with monic polynomials.

should the  of all the coefficients of $$ and $∗81$ be 1?

I did not understand what you mean. The gcd of the coefficients of the polynomial with $n?$

If we know the factorization of 81∗, can we benefit from it?

$81*P$ is your modulus. So, no. You can apply Coppersmith without knowing the factorization of the modulus.

What is the problem with using the Coppersmith method for
with 1000 digits?

No problem, if the assumption of the Theorem are satisfied.


Trapdoor implementation Please refer to this secure index paper. On page#6, a trapdoor is defined as

Trapdoor(Kpriv, w): Given the master key  Kpriv = (k1, … , kr) and word w,
output the trapdoor for word w as:     Tw = (f(w, k1), … , f(w, kr))

Can someone please explain it to me using an example?

Let's say we've a word hello for which we want to generate a trap door. So, do I first encrypt it with k1 and then take its hash. And do the same with key k2, k3 etc. Once we have all the hashes, simple concatenate them. Is my understanding correct?

From the paper, $f$ is a pseudo-random function that produces a result of $s$ bits.

You can think of the master key as a vector of $r$ values each $s$ bits long and for pedagogical purposes I'm sure the trapdoor for $w$ could be thought of as the result of hashing the concatenation of each key value $k$ with the word $w$.


Which of the following protocols is susceptible to replay attack? I have a hard time understandin which of the following protocols is susceptible to replay attack:

A   ----->  B username, password
A   ----->  B username, h(timestamp,password)
A   -----> B username timestamp, h(password)
A   -----> B username, h(timestamp), h(password)

I think the answer is 1 and 3

I know 2) is secure because the password and time-stamp are hashed together,
I know 1) is definitely insecure. 3) is insecure if somehow the intruder gets to know the time-stamp he may replay it.
I am slightly confused about 4) while it is true that we can't get the time-stamp from hash.
I was wondering if it is possible to brute force a time stamp.
I think there wouldn't be a lot of time difference between when the packet was sent and the time intruder intercepted it. Is it possible and send all possible timestamps until B accepts it?

Insecure, you just replay $\text{username}$ and $\text{password}$. Password is also sent in clear text.
Secure, if the hash function $H$ used is strong enough to resist bruteforcing of the password. However you'll also need to send the timestamp so that the server can check the auth, so this scheme is better portrayed as $\text{username, timestamp, }H(\text{timestamp}||\text{password})$.
Insecure, you replay $\text{username}$, $\text{timestamp_now}\ $ and $\text{password}$. Password is also sent in clear text.
Insecure, you replay $\text{username}$, $H(\text{timestamp_now})\ $ and $\text{H(password)}$. Password is also sent in clear text.

Make sure to use a secure PBKDF for password hashing, like $scrypt$.


Is it safe to reuse a symmetric key when using asymmetric encryption? I've written a C# Library that I hope will be used for security purposes in a commercial application.  The application will communicate through the internet and not on an internal network.  I am using RSA for Asymmetric Encryption and Rijndael for Symmetric Encryption.  Currently the process I am using is as follows:

The Client sends it's RSA Public Key to the server.
The Server encrypts the Rijndael Symmetric Key using the Public Key and sends the result to the client.
The client decrypts the Symmetric Key and stores it.
When either party sends any data, a new IV is generated each time, but the Symmetric Key remains the same.

I expect the lifespan of the connection between the Client and Server to last for at most 10 - 20 exchanges of information before the connection closes, thus being 10 - 20 sets of data encrypted with the same key, but with a different IV.  Past this, the Symmetric Key is destroyed.  Both Asymmetric Keys, the Symmetric Key and IV are all generated by the classes I'm using.

Is what I am doing safe?  Are there any major security flaws I'm missing?

EDIT: I send the IV along with the Rijndael Encrypted data, where it is seperated from the data and then used by the receiving party to decrypt the data.  I have read elsewhere that this is safe practice?

The use of the AES key many times is not a problem. However, there is a fundamental flaw with your solution. The server has no way of validating that it received the client's authentic public key. In particular, a man-in-the-middle can capture the client's public key, can forward its own public key to the server, and can then decrypt all traffic sent by each party (since it will be able to decrypt the AES key). Also, the client cannot know that it is talking to the authentic server at any stage.

Apart from that, you lose a lot of properties that people like to have in such protocols, like forward security.

In general, it's not a good idea to make up your own protocols (no matter how simple). My recommendation is to just use TLS v1.2 with a forward-secure cipher suite. The best to use are TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256, or TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256. However, you still have to solve the problem of somehow enabling the parties to identify each other, and to be sure that the correct public key is used. This is handled by using certificates.


Steganography Decryption From Completely Black Image I am trying to decrypt a completely black gif that I know has been encrypted by some sort of steganography. I've tried subtracting the bytes of the images with each other, and so far I have gotten a really weird image consisting of seemingly random patterns of black and white pixels. What are the most common techniques to go about decrypting this image?

GIF images use look-up tables to store colours. If two entries in a table contain the same colour, then the pixels assigned to these colour values will be indistinguishable.

For example, here is a one-bit-per-pixel GIF image. It started out as a black and white image, but I edited the colour table so that the white pixels also appear black:

You can retrieve the message by restoring the colour table in a graphics editor like Gimp (Colors → Map → Set Color Map) or by editing the data directly (change bytes 13, 14 and 15 of the file from 000000 to ffffff).

Other possible approaches include storing information in a comment field, or appending it to the end of the GIF data. In animated GIFs, the delay time between frames (in hundredths of a second) is represented by an unsigned 16-bit value, so it's possible to create an image that freezes on an empty frame for almost 11 minutes (655.35 seconds).

(By the way, encryption and steganography are two different things. If your image contains encrypted data, then finding this data is only the first step.)


Tell me about non-MD5/SHA1 key fingerprints I understand there are specifications for public-key fingerprints that use modern hash algorithms like SHA2. What are they?

Any secure hash algorithm can be used to generate a public key fingerprint - your choice depends entirely on which hash is expected by the other party.


How many pairs of ${b_i}^k \equiv g_i\pmod p$ are enough to solve discrete logarithm problem? On the group of multiplication modulo large prime $p$ of $m$ bits

Given
$$ b_1^k=g_1 \;\text {mod}\;p$$
$$ b_2^k=g_2 \;\text{mod}\;p$$
$$ b_3^k=g_3 \;\text{mod}\;p$$
$$ \vdots $$
$$ b_n^k=g_n \;\text{mod}\;p$$

How many pairs are enough to computationally solve $k$ of this discrete logarithm problem? I have this question because if we erroneously use the random number generator in Elgamal encryption The masking key may have relation, e.g. the masking key is the square of previous one modulo $p$. We can decrypt the ciphertext easily, but we may still not know the private key of Bob (the receiver.), but we can know many pairs of relation like equations above. Are the pairs let we solve the private key of Bob(receiver)?

Having multiple sets $b_i^k = g_i$ with a common solution $k$ do not help you recover $k$; it cannot make the problem much easier than if you had the simple equation $b^k = g$.

Here's the proof; suppose that there was an efficient way to recover $k$ given a $n$ different $b_i^k = g_i$ equations.

Then, we can efficiently solve the simple equation $b^k = g$ by doing the following:

We select $n$ random values $r_1, ..., r_n$
We compute:

$$b_i = b^{r_i}$$

$$g_i = g^{r_i}$$

We have our $n$ equations, as $b_i^k = (b^{r_i})^k = (b^k)^{r_i} = g^{r_i} = g_i$, so we use the efficient way to recover $k$ given $n$ equations.

We then know the solution $k$ to the original equation, and the only extra time we took was to the time select $n$ random values and to compute $2n$ modular exponentiations.


What is different below two Ciphersuites? I have two questions;

I need an explanation for the differences of below two cipher suites.
How do they work with SSL/TLS protocol? (my main concern first one doesn't have 'ecdhe_rsa' part )

tls_aes_128_gcm_sha256

tls_ecdhe_rsa_with_aes_128_gcm_sha256

The difference is that tls_aes_128_gcm_sha256 is TLS 1.3 and tls_ecdhe_rsa_with_aes_128_gcm_sha256 is used for the older TLS 1.2. The first cipher suite doesn't specify the key agreement algorithm and the authentication mechanism. Those are likely used, but they are specified / configured elsewhere in the TLS handshake.
TLS 1.3 is basically TLS-done-right; the two protocols aren't compatible, even if the last part of the cipher suite matches. It can however use the same key agreement and authentication mechanisms (and thus the same server certificate and key).

To quote OpenSSL:

SSL_CTX_set_ciphersuites() is used to configure the available TLSv1.3 cipher suites for ctx. This is a simple colon (":") separated list of TLSv1.3 cipher suite names in order of preference. Valid TLSv1.3 cipher suite names are:
TLS_AES_128_GCM_SHA256

OK, so we're talking TLS 1.3 here, let's look there:

Although TLS 1.3 uses the same cipher suite space as previous
versions of TLS, TLS 1.3 cipher suites are defined differently, only
specifying the symmetric ciphers, and cannot be used for TLS 1.2.
Similarly, cipher suites for TLS 1.2 and lower cannot be used with
TLS 1.3.

So we have two cipher suites that are largely identical to the message encryption / authentication used. However, one is for TLS 1.2 and also specifies the key agreement and the other is specific to TLS 1.3 and only specifies the message encryption / authentication.
For TLS 1.3 the reason why the other components are not specified is that they are negotiated during the handshake. This makes TLS 1.3 more flexible as it doesn't seem to specify all possible combinations in the cipher suite. However, you should remind yourself that the cipher suite is far from the only configuration parameter.
From TLS 1.3, section 4.1.1, Cryptographic Negotiation:

...
In TLS, the cryptographic negotiation proceeds by the client offering
the following four sets of options in its ClientHello:

A list of cipher suites which indicates the AEAD algorithm/HKDF
hash pairs which the client supports.

A "supported_groups" (Section 4.2.7) extension which indicates the
(EC)DHE groups which the client supports and a "key_share"
(Section 4.2.8) extension which contains (EC)DHE shares for some
or all of these groups.

A "signature_algorithms" (Section 4.2.3) extension which indicates
the signature algorithms which the client can accept.  A
"signature_algorithms_cert" extension (Section 4.2.3) may also be
added to indicate certificate-specific signature algorithms.

...

so basically the ECDHE option is now in supported_groups (DH is required for TLS 1.3) and RSA is in signature_algorithms, if present.

Short explanation of the components in the cipher suite:

tls : the protocol;
ecdhe : ephemeral-ephemeral elliptic curve diffie hellman for key agreement, which brings forward security;
rsa : signature algorithm when certificate authentication is used (for the server);
aes-128-gcm : block cipher & cipher mode to keep the messages confidential & authenticated;
sha256 : hash algorithm used for the PRF (used for key derivation).

Note that TLS 1.3 uses HKDF instead of a proprietary HMAC based mechanism in TLS 1.2 for the PRF. So although the TLS 1.2 and 1.3 cipher suites you mention may use the same primitives, the protocols differ somewhat (as explained in the initial section of this answer).


Why does NIST say that 2nd preimage resistance depends on the message length In NIST FIPS 202 on the table, It is written as

Function
Output Size
Collision
PreImage
2nd Preimage

SHA-1
160
< 80
160
160–L(M)

SHA-224
224
112
224
min(224, 256–L(M))

SHA-512/224
224
112
224
224

SHA-256
256
128
256
256–L(M)

SHA-512/256
256
128
256
256

SHA-384
384
192
384
384

SHA-512
512
256
512
512–L(M)

with $L(M) = \lceil \log_2(len(M)/B) \rceil$ where $B$ is the block length of the function in bits, i.e., B = 512 for SHA-1, SHA-224, and SHA-256, and B = 1024 for SHA-512.
For the discussion directs to NIST 800-107r1. and it is on the appendix;

The actual second preimage resistance strength for SHA-1, SHA -224, SHA-256 and
SHA-512 is approximately $(L – M)$, where $L$ is the output block size of the hash function,
and the message is $2^M$ input blocks in length.

For example, if a message that is $2^{33}$ bits in length (i.e., a gigabyte long) is hashed by
SHA-256 (whose input block size is $2^9$ bits), the second preimage resistance strength is
$(L – M) = (256 – 24) = 232$ bits (where $L = 256$, and $M = \log_2(2^{33}/2^{9}) = (33 – 9) = 24).$ That is, the amount of work required to find a second preimage is $2^{232}$.

It is important to note that the amount of work is based on the number of compressions
function executions (compressing single message blocks), not on the number of hash
function executions (hashing messages of more than one block in length)

First of all, there is no reference for this claim. Is there any reference for this claim?
Is there a better explanation for this attack?

The reference for the claim is here, titled "Second Preimages on $n$-bit Hash Functions for Much Less than $2^n$ Work" by J. Kelsey, B. Schneier.
The attack is specific to un-truncated Merkle-Damgaard hash functions. I haven't understood the mechanism of the attack, but as far as I understood, it require some unrealistically large working memory for the attack to work, and therefore it doesn't affect real-world security of SHA-1/2 hash functions.


How is the order of a point calculated for elliptic curves over GF(p) My question is about elliptic curves over $GF(p)$: How is the order of a generating element $G$ (which is to my knowledge also the order of the cyclic subgroup $G^n$) calculated? Taking P-256 as an example, I know basically what the base point $G$ is and also what its order is.

But how is the order of any point calculated? The order is really a very big number and I think that its value was not found by brute force.
Under what circumstances is the order of the subgroup $G^n$ the same as the order of the whole group (co-factor = 1) ?
Why must the order always be prime?
is each group for elliptic curves over $GF(p)$ group cyclic? In this case there is a generating point G (a base point) and all sub-groups are cyclically, too.
How are "good" points found and what is the cryprtographic meaning of "good" ?

From group theory I just know, that the order of a subgroup divides the order of the complete group, which gives rise to the definition of the co-factor h, but that doesnt help.

The questions are not of practical interest, but I want to understand what I'm doing. The information I read so far seem to appear from nowhere. If the mathematical background, needed to answer those questions is not totally out of scope for a non-mathematician, where can I read about that?

The Schoof–Elkies–Atkin algorithm (SEA) is an algorithm used for finding the order of or calculating the number of points on an elliptic curve over a finite field. The complexity of this method is in order ${\log^4 p}$. Using SEA you can easily compute the order of group, then with binary multiplication method you can compute the order of arbitrary points. For the meaning of "good"(and another questions), you should read about attacks against elliptic curves.

For more details you can see "Guide to Elliptic
Curve Cryptography, Darrel Hankerson, Alfred Menezes, Scott Vanstone" which is easy and complete book.


Bilinear pairing arithmetic - cryptographic accumulators For calculating accumulated values for set of elements chosen randomly from, say, $\{e_1 ,e_2,...e_n\}\subseteq X$ we use the formula $acc= g^{f(e,s)}$ where $f(e,s)= (e_1+s)(e_2+s).....(e_n+s)$.

Then, the witness for $e_k$ is calculated as $wit_{e_k} = g^{\prod(e_i+s)} $ where $i \ne k $  (i.e., accumulating all values except $e_k$).

This can be calculated by dividing $f(e,s)/(e_k+s)$ (assuming all $e_i$'s and $s$ are known to me) and raising $g$ to it.

My question is not about the application or purpose of cryptographic accumulators but about some mathematical clarifications:

While computing $f(e,s)$, do I have to do modular arithmetic on $P$ where $P$ is a prime number representing the order of group $\mathbb{G}$?
Also, one paper stated that it is impossible to create a witness for an element which is not accumulated into it. Will anybody please elaborate on it?
By dividing $f(e,s)$ by $(e_k+s)$ one can calculate a witness value.
Is there any way to distinguish between the witness (let me call it) values that where computed when $e_k$ is accumulated in $f(e,s)$ and when it is not accumulated $f(e,s)$?

This can be calculated by dividing $f(e,s)/(e_k+s)$ (assuming all $e_i$'s and $s$ are known to me) and raising $g$ to it.

First, if the prover knows $s$, it doesn't need to know the $e_i$'s to create membership witnesses.
It can simply raise the accumulator $\mathsf{acc}$ to $1/(e_k + s)$:
\begin{align*}
\mathsf{wit}_{e_k} &= \mathsf{acc}^{\frac{1}{e_k + s}} = {g^{f(e,s)/{(e_k + s)}}} =  g^{\prod_{i\ne k}{(e_i+s)}}
\end{align*}

This brings me to my second point: knowledge of $s$ allows the prover to create fake membership witnesses for any $e$ that was not accumulated. This is because the prover can compute $\frac{1}{e + s}$ for any $e$.

So, yes, computing $f(e,s)/(e_k+s)$ and then raising $g$ to it is one way to calculate the witness, but it's a bad idea: the prover can easily create fake witnesses for any non-accumulated $e$ if it knows $s$.
Computing witnesses in this way only makes sense when there's a trusted party that knows $s$.
This trusted party computes and outsources witnesses to an untrusted "prover" who merely relays these witnesses to verifiers (i.e., the 2- or 3- party models of authenticated data structures).

Requiring a trusted party that knows $s$ is unreasonable in many applications.
In practice, we want to prevent the (untrusted) prover from faking witnesses, by ensuring it does not know $s$.
We can do this via a trusted setup phase that gives the prover public parameters $\left(g^{s^i}\right)_{0\le i\le q}$ but does not give him $s$.
This trusted setup phase is run by some trusted "guy in the sky," which in practice can be implemented via MPC protocols (see Scalable Multi-party Computation for zk-SNARK Parameters in the Random Beacon Model).
Here $q$ is a strict upper bound on the number of elements you will ever accumulate.

Now, in order to commit to a set $A = \{e_1, \dots, e_n\}, n\le q$ of items, you first have to compute the coefficients of the polynomial $f(e, x)$ using Lagrange interpolation in $O(n^2)$ time, Newton interpolation in $O(n^2)$ time or FFT interpolation in $O(n\log^2{n})$ time.

Note that you don't need to know $s$ to interpolate.
Consider $A = \{1,2,3\}$. Its polynomial $f_A(x) = (x-1)(x-2)(x-3) =
x^3 - 6 x^2 + 11 x - 6$, so its coefficients are $(1, -6, 11, -6)$.

Once you have the coefficients $\{c_1, \dots, c_n\}$ you can compute the accumulator $acc$ by raising the $\left(g^{s^i}\right)_{0\le i\le n}$ public parameters to the coefficients:
\begin{align*}
acc &= \left(g^{s^n}\right)^{c_n} \left(g^{s^{n-1}}\right)^{c_{n-1}} \dots (g^s)^{c_1} \left(g\right)^{c_0}\\
  &= g^{c_n s^n} g^{c_{n-1} s^{n-1}} \dots g^{c_1 s} g^{c_0}\\
  &= g^{c_n s^n+ c_{n-1} s^{n-1} + \dots + c_1 s + c_0}\\
  &= g^{f(e,s)}
\end{align*}

For example, for our set $A$ above, the prover computes its accumulator as $(g^{s^3})^1 (g^{s^2})^{-6} (g^{s})^{11} g^{-6} = g^{s^3 - 6 s^2 + 11 s - 6} = g^{f_A(s)}$.
Note that the prover does not need $s$ to compute $g^{f_A(s)}$ as long as it has the public parameters.
In my experience, most accumulator papers do not explain this step, partly because they only look at the two- or three-party models of authenticated data structures where there actually exists a trusted party that knows $s$.
(In other words, the "Hey, let's play with fire!" model.)

To answer your other questions,

  While computing $f(e,s)$, do I have to do modular arithmetic on $P$ where $P$ is a prime number representing the order of group $\mathbb{G}$?

If you know the trapdoor $s$ (i.e., insecure mode), then yes, computing $f(e,s)$ involves adding and multiplying things modulo $P$ as per its definition.

If you don't know the trapdoor $s$, then computing $f(e,s)$ involves adding, multiplying and inverting numbers (for Lagrange and Newton) modulo $P$. If you're using FFT interpolation, it also involves roots of unity in the field of order $P$ (i.e., the field "in the exponent").

  Also, one paper stated that it is impossible to create a witness for an element which is not accumulated into it. Will anybody please elaborate on it?

As I described before, the prover cannot fake witnesses only when the prover does not know the trapdoor $s$. I can't find the security proof in Lan Nguyen's original paper on accumulators, but it's a reduction to $q$-Strong Diffie-Hellman ($q$-SDH). The intuition behind why membership witnesses are secure is that without the trapdoor, nobody can compute any pair of the form $(e, g^\frac{1}{e + s})$.

  By dividing $f(e,s)$ by $(e_k+s)$ one can calculate a witness value.

Yes, but remember that this requires the prover to know the trapdoor, which is not secure (unless you're in the "Hey, let's play with fire!" model).

  Is there any way to distinguish between the witness (let me call it) values that where computed when $e_k$ is accumulated in $f(e,s)$ and when it is not accumulated $f(e,s)$?

Before I can answer this question, you have to clarify what element(s) these witnesses are for and what does the adversary know? Do they know the elements accumulated in the two accumulators?


Verilog simulation of Data Encryption Standard I am interested in developing DES (in verilog) for my college project. Can I get help in understanding the simulation results of DES encryption and decryption?

This site is an interactive presentation of the various elements in DES, showing each intermediate result for the encryption or decryption of some data and key that you specify yourself. This should help you debug your implementation. There are also test vectors (which help check that your implementation is correct) in various places, e.g. there.


data migration: bcrypt to bcrypt different salts I'm migrating passwords from one system (bcrypt) to another (also bcrypt) differing only in their salting. I noticed that encrypting the same plaintext password on one system generates a different string than encrypting the same plaintext password on the other. However, hashing and copying the resulting encrypted pw from system A into system B still results in successful authentication on system B.

It would appear I can simply migrate the hashed passwords from one system to the other, but I wonder if this is a potential security concern because the salting is different.

What do you mean by "differing only in their salting"? A correct implementation of bcrypt should generate a unique salt for each hashed password. The salt is stored along with the hash itself, so yes, the migration is as simple as just using the old values in the new system.


Robust stream cipher using AES encryption block I am implementing a stream cipher in a microcontroller that only has an AES128 encryption block. According to this page, a block cipher based on an encryption only module can be converted into a stream cipher using CFB, OFB and CTR modes. Assuming I have a unique IV, which is the most robust method to use?

You should use CTR mode. You will not need to have random IV every time, rather you will use incremental counter and set it to zero once you change the KEY. You should not encrypt more than ${2^{n/2}}$ blocks.

CTR mode allows both parallel encryption and decryption without padding. You can even precompute the CTR encryptions in Idle time and just Xor it with input stream to generate ciphertext once required.

OFB mode have cyclic issue and if cycle is small, the generated key stream will start repeating itself.

In fact you should use GCM to get authenticated encryption. see Disadvantages of various Authenticated modes of Operation or how to choose between CCM and GCM

Here is a List of Advantages and Disadvantages of Modes of Operation

For good comparison of mode of operations, please see
Evaluation of Some Blockcipher Modes of Operation


Difference between somewhat homomorphic encryption and leveled homomorphic encryption? Is there any difference between somewhat homomorphic encryption and leveled homomorphic encryption? I heard that leveled homomorphic encryption supports computing circuits of bounded depth on cipher text, and somewhat homomorphic encryption supports computing polynomials of low degree on cipher text. What's the difference? Which is stronger?

Let $\mathcal{C}$ be the set of allowed binary circuits.

Then, a $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ that has (i) correct decryption and (ii) correct evaluation is called a somewhat homomorphic encryption scheme (SHE).

A $\mathcal{C}$-evaluation scheme $(\mathsf{Gen}, \mathsf{Enc}, \mathsf{Eval}, \mathsf{Dec})$ is called a levelled homomorphic scheme if it has (i) correct decryption, (ii) correct evaluation, (iii) takes an auxiliary input $d$ to $\mathsf{Gen}$ which specifies the maximum depth of circuits that can be evaluated, (iv) is compact, and finally requires that the length of the output of $\mathsf{Eval}$ does not depend on $d$.

As you can see, levelled homorphic scheme is an "extended" form of SHE. However, if you allow any circuits with depth at most $d$ in $\mathcal{C}$, then you have a levelled fully homomorphic scheme.

If you want to go a step further, there is also $i$-hop and $\infty$-hop correctness for schemes building on top of SHE/[levelled] [fully] homomorphic schemes.

Now let's come to your questions: bounded depth for levelled homomorphic encryption as well as the difference between both should be clear now. For the degree of the polynomial $p$, maybe you were referring to compactness, since it restricts the output of $\mathsf{Eval}$ to at most $p(\lambda)$ bits, where $\lambda$ is the security parameter. I don't know your definition of strong here, therefore I leave it open to you to choose the "better one".

The following paper may help you further in your questions: A Guide to Fully Homomorphic Encryption


Can timestamping provide evidence of absence before a certain time? Normally trusted timestamping proves that certain information existed at or before a certain time. However, sometimes there is a need to prove the opposite; that something did not exist before a certain time.

Consider that I want to prove by photographs that my house is in a good condition before I rent it out to someone else, i.e. I want to be able to prove that the photos were not taken before the day when i rent it out. The old-school way of doing this is to include for example today's newspaper in the photographs, but now with the emergence of advanced graphic editors it seems like this is not enough for a proof beyond reasonable doubt.

Is there any way to do this cryptographically utilizing a trusted third-party timestamping service?

One application for a randomness beacon is to get this assurance.  A randomness beacon (NIST runs a prototype one) generates a sequence of public, signed, timestamped random numbers on a fixed schedule.  (In NIST's case, it's once per minute.)

The beacon operator is promising that the number won't be known to anyone (outside the machine on which the beacon is running) until the time on the beacon pulse.  As long as the beacon operator keeps that promise, you can know that nobody could have known the value of the beacon pulse at 12:31 GMT June 20, 2017 before exactly 12:31 GMT on June 20, 2017.  The beacon service keeps a record of all these pulses, all digitally signed and hash-chained together.  Sometime soon, we're releasing a new beacon format, and a couple other organizations will be running beacons, so you can choose which beacon you want to trust, or even combine them.

If you don't want to trust anyone to generate those random numbers, you can use something else from the environment.  Some people have proposed using closing stock prices, winning lottery numbers, weather data, and hashes from proof-of-work blockchains.  All of those have some issues in terms of convenience, and potentially a small amount of influence that could be applied by specific trusted people[1], but nobody can exactly predict what they will be even a day in advance.

[1] For example, consider weather data: You're going to define some official source as the place you get your cannonical weather data.  Everyone will notice if this source tells you there was a high temperature in DC of 20 C on a day when it really got up to 30 C, but that source will have some wiggle room in reporting a high of 30 C or 31 C.


AES GCM encryption, authentication and PBKDF2 I'm developing a kind of secret vault server application. The basic principle is similar to DPAPI where each secret will have its own unique random KEY/IV pair and and that KEY/IV pair will be encrypted with a PBKDF2 derived key from user password.

I have doubts as to how properly handle key derivation and authentication.
This is what I came up with:

User registration:

User supplies username and password
Generate random salt using CPRNG. Store the salt with user record.
Derive a KEY and IV from password using PBKDF2
Generate a random master KEY/IV pair and encrypt this master pair with generated KEY/IV pair from step 3 using AES-GCM. Store encrypted KEY and encrypted IV separately in two records, store TAG in third record.

User verification:

User supplies username and password
Use stored salt and supplied password to derive a KEY and IV
Use derived KEY/IV pair to try to decrypt master key. If verification fails, authentication fails and user is not let in

All encryption is done on server side. Communication is secured with TLS but this is not the topic nor is the sizes of key, IV or salt. Let's assume I will choose the sizes correctly.
The scheme I choose to use must protect the data even if database is stolen.

My questions about this are:

Is it safe to generate IV along with KEY from PBKDF2 when using and storing salt for each user or should IV also be randomly generated and stored along with salt? When generating IV from PBKDF2 I'm basically choosing for it to be part of the key, ie a secret. Using a sufficiently large salt per user would guarantee that no two generated KEY/IV pairs exist even if users have same passwords.
Should randomly generated master KEY pair be stored with both KEY and IV encrypted or should IV be stored in plain text?
If you store both encrypted, it is safe to store them in two separate records or should they be encrypted together (concatenated) and stored in a single record? This is regarding IV reuse since two records are now encrypted with same KEY/IV pair.

Thank you!

Is it safe to generate IV along with KEY from PBKDF2 when using and storing salt for each user or should IV also be randomly generated and stored along with salt? When generating IV from PBKDF2 I'm basically choosing for it to be part of the key, ie a secret. Using a sufficiently large salt per user would guarantee that no two generated KEY/IV pairs exist even if users have same passwords.

Sure thing, but I would recommend to use a KBKDF such as HKDF on the output of PBKDF2 instead of generating a larger output. The reason is that PBKDF2 doesn't handle large output well. That is: output larger than the underlying hash size.

  Should randomly generated master KEY pair be stored with both KEY and IV encrypted or should IV be stored in plain text?

Inconsequential. The IV can be stored in plaintext as well. I'd recommend this as key wrapping is often thought as a specific routine, and it won't include the IV. Furthermore, you probably need more than one IV (see below).

  If you store both encrypted, it is safe to store them in two separate records or should they be encrypted together (concatenated) and stored in a single record? This is regarding IV reuse since two records are now encrypted with same KEY/IV pair.

You need to create a fresh IV for each record that you encrypt. If you have trouble storing the IV then you should consider Format Preserving Encryption (FPE).


Difference between "Signature Algorithm" and "Signature Hash Algorithm" in X.509 What's the difference between the "Signature Algorithm" and the "Signature Hash Algorithm" found in an X.509 certificate? Why does it need a "Signature Hash Algorithm"?

Edit:

I'm creating the X.509 cert with PHP 5.2. When I change the 'digest_alg' to 'md5', both properties of the Microsoft Cert Tool changes to md5. So, as mentioned in one answer below, it seems to be an issue/invention of the Microsoft Cert Tool.

Change to md5:

           $configs = array(
                            'config'             => 'test.cnf',
                            'digest_alg'         => 'md5',
                            'x509_extensions'    => 'v3_ca',
                            'req_extensions'     => 'v3_req',
                            'private_key_bits'   => 2048,
                            'private_key_type'   => OPENSSL_KEYTYPE_RSA,
                            'encrypt_key'        =>
                        );

Result:

This has more to do with how Microsoft decided to implemented their certificate inspection GUI, than about the actual fields of the certificate. Most signature algorithm identifiers present in contemporary certificates specify both the public key algorithm (RSA in this case) and the digest algorithm (SHA-1 in this case). The identifier "sha1RSA" is most likely inaccurate in so far that Microsoft has decided to use it for an identifier that is known as sha1WithRSAEncryption OBJECT IDENTIFIER ::= {  iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) 5 } in the standard.
The only semi-common standard signature algorithm I am aware of that actually separates the public key algorithm identifier from the digest algorithm identifier in the signature algorithm identifier of certificates, is PKCS#1 v2 RSASSA-PSS.
Edit:
Consequently, Microsoft follows conventions and the X.509 specification by letting "signature algorithm" mean a combination of a signature public key algorithm and signature hash algorithm, but, firstly, the identifiers they use for these combinations are non standard, and, secondly, adding a signature hash algorithm field is in most cases superfluous and doesn't usually reflect the actual X.509 format.


Anonymous key exchange protocol not secure vs. computationally unbounded adversary Explain why an anonymous key exchange protocol cannot be secure against a computationally unbounded adversary.

This is a homework, and my analysis is poor, but I try, this is what I answered:

In this case as is defined that our adversary is has no computationally limits, unlike real life, and it’s taken away most of the impediments that actually occurred. We can consider that the Key Generator algorithm, has an input a value R (it is conceptualized as a random  number generator), and produces a public key, PK, and a secret SK. A computationally unbounded adversary, possibly will consider all possible inputs of R, and eventually will find out which one generates the PK, so that’s the way for him knowing the SK, because if that R creates the PK therefore can creates the SK, and can be used for decrypting the message. Besides if the private Kay was generated correctly, it will be able to fulfill the next property:  DSK(EPK(M))=M Consequently, we can concluded that the Anonymous Key Exchanged cannot be secure against a computationally unbounded adversary.


Hessian Curve Implementation I tried implementing the Hessian form of an Elliptic curve over the prime field Fp where,
p I have taken as 1051.
The curve equation I took is $X^3 + Y^3 + cZ^3 = dXYZ$ with c = 1 and d = 6. Selected (4,2,6)  as the base point.
Followed the equation (5) and (6) of https://www.iacr.org/archive/pkc2010/60560246/60560246.pdf for point addition and point doubling respectively.
However, when multiplying (4,2,6) with 42, I am getting (0,0,0) after the 30 steps.
For ease of understanding, I am providing the formulae for addition and doubling.
Addition
$X3 = X2*Z2*Y1^2 - X1*Z1*Y2^2$
$Y3 = Y2*Z2*X1^2 - Y1*Z1*X2^2$
$Z3 = X2*Y2*Z1^2 -X1*Y1*Z2^2$
Doubling
$X3 = Y1*(c*Z1^3 - X1^3)$
$Y3 = X1*(Y1^3 -c*Z1^3)$
$Z3 = Z1*(X1^3 - Y1^3)$
All the points have been computed with respect to modulo p.

The user94293's answer is correct, If you look at the equation you will see that the result will be zero if you add the number itself. It is designed for the points $P$ and $Q$ such that $P\neq Q$. If you want to calculate the $P+P$ that is called point doubling and it is written as $[2]P$. There are always special formulas for doubling since it adds the point itself.
The addition formula is optimized and cannot be used for $2[p]$. From your questions and comments, I understand that you are trying to find the scalar multiplication by just adding;
Scalar Multiplication
The scalar multiplication $[k]P$ this actually means adding $P$, $k$-time itself. More formally;
let $k \in \mathbb{N}\backslash\{ 0\}$
\begin{align}
[k]:& E \to E\\
&P\mapsto [k]P=\underbrace{P+P+\cdots+P}_{\text{$k$ times}}.\end{align}
Double-and-Add
To use these formulas correctly, you need the double-and-add algorithm
#Returns [k]G, where p is modulus
#and c is the constant of the Generalized Hessian Curve
doubleAndAdd(G, k , p ,c)
  N = P
  Q = 0
  for i in bits(k)
     if i = 1 then
         Q = point_add(Q, N)
     N = point_double(N)
  return Q

Where the bits convert the $k$ into binary form and started from LSB.

Updates on implementation
I've found a problem during the calculation of the order an element, later figured out the cause. One can reach the codes and explanations on the Q/A from the StackOverflow
The order of $(4,2,6)$ is $77400$ i.e. $[77400](4,2,6) = \mathcal{O}$ and the order factors into $2,2,2,3,3,5,5,43$. Not a good curve.
To run better, the order of the curve must be calculated before and so that one can use $[k]P = [k \bmod order]P$ equality.
Smart's Sample Curve
N.Smart wrote an article titled  The Hessian Form of an Elliptic Curve. In this work first, a curve over $\operatorname{GF}(2^{191})$ on the form $$E': y^2 +xy = x^3 + x^2 + b$$ $$b =  \texttt{0x4DE3965E00F2A1C6C9750156A6FEFBE5EEF780BF3EF20E48}$$ is given, and that then transferred to a Hessian form.
$$x^3 + y^3 + z^3 = Dxyz$$
$$D = \texttt{0x16A4C7C2030FAD1380ABF8C2D47DC3E0C20AF62F6EDD06A7}$$
A point of order $q$ on $C$ is also given by $(x, y, z)$, where
$$x = \texttt{0x52FD0CE78D0651B4F66D2F4E12E170CA3E429F6A06433B22}$$
$$y = \texttt{0x1BECA50368403F3D13173968082B035397C77830A9D90E5D}$$
$$z = \texttt{0x2B08F7C0CCAC86151AA6FECABDD2D052BD60924F28A6A78E}$$
That is not generalized, however, your $c=1$ make is in this case. You can benefit from this curve.


Are relatively prime numbers used in RSA We know that the Totient function is multiplicative. Which means that when $p$ and $q$ are relatively prime, then $\varphi(p q)$ is equal to $\varphi(p) \varphi(q)$. My question is, are only prime numbers used in RSA or can they also be coprime like e.g. 11 and 16? I am asking this because I understand why RSA is multiplicative when p and q are prime but not when they are relatively prime.

are only prime numbers used in RSA ?

That depends on what is meant by "numbers used in RSA". I'll restrict to a reading of the question where these are $p$ and $q$, with $N=p\,q$ the public modulus in the RSA public key.

That also depends of the defintion of RSA. In the original definition, or when we see $N=p\,q$ in an applied RSA cryptography context, we think of $p$ and $q$ primes, large and randomly seeded, and perhaps deliberately distinct. In this case, $p$ and $q$ are primes. They are distinct either deliberately or with overwhelming probability, and distinct primes are coprime.

In some modern definitions including PKCS#1v2.2, RSA is extended to $N$ the product of $u\ge2$ distinct (odd) primes. In this case, when $u>2$ and if we nevertheless still write $N=p\,q$ (which is highly unusual), then at least one of $p$ or $q$ is not prime, but still $p$ and $q$ are coprime.

On the other hand, from a mathematical standpoint, we can define RSA for any positive $N$: if $\gcd(e,\varphi(N))=1$ then the function $x\mapsto x^e\bmod N$ is a bijection of $\Bbb Z_N^*$, that is of the subset of $x$ in $\Bbb Z_N$ with $\gcd(x,N)=1$. That function is also a bijection in $\Bbb Z_N$ if and only if $N$ is square-free (equivalently, if and only if $p$ and $q$ are coprime in any factorization of $N$ as $N=p\,q$). Whenever pulling a factor out of $N$ is hard, overwhelmingly most elements of $\Bbb Z_N$ belong to $\Bbb Z_N^*$, thus the distinction $N$ square-free or not is immaterial for random $x$ (as used in good practice). In that mathematical definition of RSA, we might have $N=p\,q$ with $p$ and $q$ prime or not, coprime or not. For example for $N=11\cdot16$ we can write $N=p\,q$ with $p=8$ and $q=22$, neither is prime, and they are not coprime. Yet $(N,e=3)$ and $(N,d=7)$ are a valid RSA key pair when we restrict to odd integers in $[0,n)$ for message and ciphertext (we can, but need not, exclude multiples of $11$).

  I understand why RSA is multiplicative when $p$ and $q$ are prime but not when they are relatively prime.

RSA is multiplicative no matter what, in the sense that for all $x_0$ and $x_1$ it holds that $E(x_0\cdot x_1\bmod N)=E(x_0)\cdot E(x_1)\bmod N$  for $E$ the function $x\mapsto x^e\bmod N$. That's because $(x_0\cdot x_1)^e\equiv x_0^e\cdot x_1^e\pmod N$, and that holds for all positive $e$ and $N$, without consideration of $N$ being the product of coprime integers, and from what set $x_0$ and $x_1$ are taken.


Would xoring 2 independant AES CTRs to produce p-rand introduce vulnerabilities? Assuming

$$AES_{k_1}(C_1) \oplus AES_{k_2}(C_2)$$

where AES is used in CTR mode, $C$ is a 128 bit incrementing counter, keys and counters for both transforms are random as well as unique, and the XOR occurs on every 16 byte block.

If I did this, would the XORed output be less secure than the size of state used to seed the generator? Does this method reduce security or introduce vulnerabilities to the random output?

No, this is safe.

In fact, if you show a way of distinguish the stream $AES_{k_1}(C) \oplus AES_{k_2}(C)$ from a random stream with fewer than $2^{64}$ outputs, you have just demonstrated a way of distinguishing AES from a random permutation.

Here is how this works: suppose we are given Oracle assess to a permutation $P$, which might be $AES_{k_1}$ for some unknown key $k_1$, or might be a truly random permutation.

Then, we ask the Oracle for the values $P(C), P(C+1), ..., P(C+n)$, select a random $k_2$, and compute the sequence $P(C)\oplus AES_{k_2}(C), P(C+1)\oplus AES_{k_2}(C+1), ..., P(C+n)\oplus AES_{k_2}(C+n)$.  Then, we run our stream distinguisher on that.

If $P = AES_{k_1}$ for some $k_1$, then this is precisely your stream, and the distinguisher will say "Yes"

If $P$ is a random permutation, well, with fewer than $2^{64}$ outputs, we can treat it as a random function (as collisions are inprobable).   With $P$ as a random function, any value $(C+i)\oplus AES_{k_2}(C+i)$ is a random value; hence the whole stream is a random string, and so the distinguisher will say "No".


Audio Encryption in Voip SIP I have some project encrypion real-time. I want use Voip SIP to implement the stream cipher.

What I have done so far :

Simple app android Voip SIP https://github.com/android/platform_development/tree/master/samples/SipDemo
Stream cipher. It can encrypt and decrypt file (but can't open it). It can encrypt .wav audio, you can play it and make weird sound. Also you can decrypt it again and make it back to normal.

My problem :

I dont know how to take audio to encrypt it and how to take the encrypted stream to decrypt it.

You won't be able to use a stream cipher with VOIP, because packet loss will prevent you from properly decrypting data that follows the missing chunks.

It may be possible to work around this issue, if you can figure out the size of the missing data, and assuming your chosen stream cipher does not have feedback, fast-forward to cipher to the start of the next block, all at the cost of wasted computation.

The correct approach that I am aware of, is to use a block cipher in CTR mode of operation, where the counter is based on the sequence numbers stamped in the packet headers. Essentially, you need to use a cipher that supports seeking within the data, without needing to decrypt all blocks prior to the block of interest.


How come Public key cryptography wasn't discovered earlier? I became interested in crypto lately and read about symmetric and public key crypto algorithms. I understand how crucial the discoveries of the 1970s like RSA, DES and DH were in advancing the technology.

I just don't understand how public key cryptography as an idea just came less than 50 years ago while it was a highly desired solution throughout history and kingdoms/countries/intelligence services would pay handsomely to whoever discover this simple yet revolutionary idea.

Things like integer factorization and elliptic curves were studied since the 19th century, how come nobody thought of using such known mathematical problems to create strong crypto systems, especially in WW1 and WW2 where confidentiality and integrity of data could decide the fate of a whole nation, instead of relying on centuries-old futile crypto techniques?

I am sure that this wasn't a lack of human resources, every European country had lots of geniuses, so why  wasn't public key cryptography discovered until so late?

If you read about Merkle's experience with bringing the subject to the mainstream, you might be surprised. His professor rejected his initial proposal and show little interest in any further developments:

...We were required to submit two project proposals, one of which we would complete for the course. I submitted a proposal for what would eventually become known as Public Key Cryptography -- which Hoffman rejected. I dropped the course, but kept working on the idea.

He showed it to a different faculty member and was encouraged to publish it. His proposal to the Communications of the ACM was rejected:

... I showed an early draft to Bob Fabry, then on the faculty at Berkeley, who immediately recognized it as both novel and valuable and said "Publish it, win fame and fortune!" I then submitted it to Susan Graham, then an Editor at the Communications of the ACM in August of 1975. As I was to learn, Fabry's response was rare.
Graham sent my submitted paper out for review and received the following response from an "experienced cryptography expert" whose identity is unknown to this day:
"I am sorry to have to inform you that the paper is not in the main stream of present cryptography thinking and I would not recommend that it be published in the Communications of the ACM."
"Experience shows that it is extremely dangerous to transmit key information in the clear."
With this blanket rejection of public key cryptography by an "expert", she rejected my article. She "was particularly bothered by the fact that there are no references to the literature. Has anyone else ever investigated this approach. If they consider it and reject it, why?"

Novel concepts that aren't "mainstream" can be difficult to accept:

I had failed to provide any references to the prior work on public key cryptography, and the reasons previous workers in the field had rejected it as impossible. I should have looked up "public key cryptography" on Google before submitting my paper. My defense is feeble: there was no Google, the term "public key cryptography" did not yet exist, and there were no previous workers in the field. There were no words for what I had done, and looking up a concept to show that no one had previously thought of it is difficult. This is not a unique problem: it illustrates a problem faced by anyone trying to explain a new idea to an "expert" who expects a properly referenced article anytime anyone tries to explain something to them. The more a new idea is unrelated to any prior idea or concept the more it must appear as a squawling bastard, naked and alone, appearing de novo and lacking any respectable pedigree or family to vouch for its acceptability.
... CACM eventually published the paper, though only after almost three years of delay, and only after others (who were better able to persuade their editors to publish in a timely fashion).

Conclusion
While the utility of public-key cryptography is obvious to us, this was not always the case. Encryption that is secure when you know the key almost sounds like something that can't exist because it would be too good to be true. So you can certainly forgive people for not pursuing the idea seriously.


What is complexity leveraging Complexity leveraging is a technique that is generally used to prove adaptive security of a selectively secure scheme. Eg: We can prove adaptive security of Yao's garbling scheme using complexity leveraging. Many papers mention about complexity leveraging, but does not present in detail. I would be grateful if someone could explain complexity leveraging with a detailed example.

Complexity leveraging is a type of reduction where the "reduction algorithm" runs in a complexity class that is greater than the adversary. For example, one may construct a simulator that runs in time $n^{\log n}$ although the adversary is only polynomial time. When considering the simulation paradigm, this is not very satisfactory. For example, in zero-knowledge, the argument is that the adversary learns nothing since it can generate anything it sees by running the simulator itself. However, when using complexity leveraging, the adversary actually cannot run the simulator (since it is in a lower complexity class). Nevertheless, in some cases, it can be meaningful. For example, let's consider a security notion that is "game-based" or indistinguishability based. We then prove that if an adversary running in polynomial-time can break our scheme, then there exists an adversary running in time say $n^{\log n}$ who can break a hash function (or anything else; this is just an example). Now, if the hash function is assumed to be secure for any adversary running in time $n^{\log n}$ then this is enough to guarantee the security of our scheme.
I am personally not a big fan of complexity leveraging. Beyond the definitional disadvantages in some cases (e.g., with simulation), there is also a big disadvantage in that it requires a much stronger assumption (not that a primitive cannot be broken by poly-time adversaries, but by super-poly-time adversaries for some specific function). However, it has been used successfully to achieve things that are otherwise unknown. In addition, in many cases, a first construction used complexity leveraging, and then later constructions succeeded in getting rid of the assumption.
========
Added later: The reason why stronger assumptions are needed is as follows. Assume that you have a reduction from ZK to OWFs so that any algorithm distinguishing the simulation from a real execution with non-negligible probability can invert the OWF with non-negligible probability. Now, assume that you use quasi-polynomial simulation. In order to argue that the adversary learns nothing, you need to assume that the one-way function is secure against quasi-polynomial inverters. This is because, in order to replace the real proof execution with a simulated one, you need to run in quasi-polynomial time. So, now you have a quasi-polynomial time adversary who is actually running. Then, the reduction to the OWF will only work if the adversary cannot break that OWF. (Of course, this is all handwaving, but this is what happens in proofs.)


ElGamal in a different group Can Elgamal be secure in $\bmod {n^2}$? Meaning instead of using a prime order group to use a group where DCR assumption holds?

There are a number of multiplicative subgroups in the ring of divisor classes modulo $n^2$. One particular subgroup (with easy logarithm) is generated by $(n+1)$. You would not want to use it for ElGamal. Other subgroup (of large enough order) are fine.


Single Party Encryption, Multi Party Decryption I am looking for an adequate protocol for public key decryption, which would allow $n$ parties to jointly decrypt a cipher text. The usage scenario for such a protocol would be a mixnet that wouldn't require the sender to know all mixes in advance. The requirements are:

There is a single externally known long term public key $Y$. Each decryptor $D_i$ has a long term private key $x_i$ and the decryptors do not reveal their respective private keys to each other.
When decrypting a cipher text, it is done in sequence by the decryptors. Let the incoming cipher text be $c = c_0$. $D_i$ decrypts $c_{i-1}$ to $c_i$ and forwards it to the next decryptor.
The order in which the decryptors decrypt the cipher text must be arbitrary, i.e. the encryptor does not have to know in which order the cipher text will be decrypted by the decryptors, or even how the private key is split up between the decryptors.
The pair $(c_{i-1},c_i)$ must be indistinguishable from $(c_{i-1},u)$ for everyone except $D_i$, where $u$ is selected uniformly at random (from the set of intermediate cipher texts).

First question: I am correct that the above requirements might be met using the following protocol based on ElGamal:

Let each $Y_i = g^{x_i} \pmod p$ be known by all decryptors and let $Y = \Pi_{i=1}^nY_i \pmod p$
Let $m$ be the plain text and $c = (Y_0,r_0,e_0) = (Y,g^k \pmod p,Y^kPad(m) \pmod p)$, where $k$ is selected uniformly at random by the encryptor.
$Y_i = Y_{i-1}g^{-x_i} \pmod p$
$r_i = r_{i-1}g^{k_i} \pmod p$, where $k_i$ is selected uniformly at random
$e_i = e_{i-1}r_{i-1}^{-x_i}Y_i^{k_i} \pmod p$
If $Y_i = 1$ then $m = Unpad(e_i)$ else $c_i = (Y_i,r_i,e_i)$.

Note: This is a fragile scheme in many ways, but in particular because it might allow the first and last decryptor to collude. If $D_1$ multiply $e_1$ by a small integer, most $Unpad$ functions (such as PKCS#1 v1.5 and PKCS#1 v2.1) will fail, unless $D_n$ first divides $e_n$ by the same small integer. If this small integer is an identifier for the sender of the message, the scheme is broken.

Second question: Does there exist any similar protocol e.g. based on secret sharing that still meets all of the above requirements, but in addition:

Allows $t \lt n$ of the $n$ decryptors to decrypt the cipher text?
Allows the decryption to be performed in any order not necessarily agreed upon in advance, but still in a finite number of steps bounded by $poly(n)$?
Features robustness, i.e. if a small numbers of decryptors (less than $n-t$) are compromised and participate in the decryption, $t$ remaining decryptors will still be able to eventually decrypt the message?

Check out Pedersen's scheme for threshold ElGamal (link). Also, check out (this) for an application to electronic voting.

Basically, the scheme works like this. There are $n$ parties, out of which at least $t$ must be reliable or else the scheme collapses. They choose a prime $p = 2q + 1$ where $q$ is also prime, i.e.: $p$ is a safe prime. Additionally, they choose a generator $g$ of the $p$-order subgroup.

Every participant $i$ chooses a polynomial $f_i(x) \in \mathbb{Z}_q[x]$ of degree $t-1$ and privately distributes the points $f_i(j)$ to each participant $j$. Each participant $j$ adds together all the points he received: $f(j) = \sum_if_i(j) \mod q$. The participants have now shared a global polynomial $f(x) = \sum_if_i(x) \mod q$ which is uniquely defined by $t$ points. The secret is located in $f(0)$.

In order to make the scheme verifiable, each of these private shares $f_i(j)$ is accompanied by a public commit value $g^{f_i(j)}$. Each participant is commited to his share $f(j)$ in the global polynomial as $g^{f(j)} = \prod_ig^{f_i(j)} \mod p$ is publicly known.

In order to raise a value $h$ to the power $f(0)$, the participants do the following. Each participant raises $h$ to the power of his own share. They publish $h^{f(i)}$ along with a Chaum-Pedersen proof (link) that the exponent in this value with respect to base $h$ is the same as the exponent in the commit value $g^{f(i)}$ with respect to base $g$.

Anyone can now combine the shares and calculate using Lagrange interpolation $g^{f(0)} = g^{\sum_if(i)\prod_{j \ne i}{-j \over i-j}} = \prod_i(g^{f(i)})^{\prod_{j\ne{}i}{-j \over i-j}} \mod p$.

The indexes $i$ and $j$ run over any set of at least $t$ trustworthy participants. This exponentiation procedure is used once for key generation and once for ciphertext decryption. Note that this allows an arbitrary order of contributions from the participants, so long as at least $t$ participants remain uncorrupted. For the rest we follow the regular ElGamal cryptosystem.


Is there any standard present to measure strength of a generated key using true random number generator? I was wondering how to measure the security strength of a generated secret key for the below protocol:
"A 128 bit random number is generated by TRNG and the random number will be used as a private key for Diffie-Hellman key exchange protocol. Two entities generate the shared secret key and that will be used as a session key for symmetric encryption."
My questions are:

Is there any standard way to measure how secure the generated key is?
What are the properties that the generated key should have to be resistant to attacks? Is there any paper/Standard document available that has the list of such properties?

Thanks.

The NIST special publication 800-90B is probably your go to here. It is the approach used to meet the FIPS 140-3 requirements which are accepted by as good assurance by a large population.
Different approaches are taken for TRNGs that are believed to produce independent, identically distributed outputs and others. One of the key measurements is the minimum entropy ($H_\infty$ in the Shannon-Renyi sense) that tracks the most probable output of some fixed size output. If the only information available to the attacker is the minimum entropy of the key, their guessing work should be at least on the order of $2^{H_\infty}$.
ETA: as pointed out in the comments, because your question is specifically about Diffie-Hellman, there are subexhaustive attacks. In particular 128-bit keys can be recovered with 64-bits of group operations using Pollard rho/baby step-giant step/Pollard kangaroo.


Reproducable pseudorandom permutation I there a way to calculate two similar pseudorandom periodic sequences by exchanging some sort of initial value and generator polynomial?

Like a linear-feedback shift register but with a finite field of numbers and each number occurring only once in the sequence?

I'm reading the question as asking for a public pseudorandom number generator seeded by a key $K$, which will output integer values $r_j$ in a specified range $[a,b]$ (here, [1 to 75]) pseudo-randomly according to the key, then cycle after having reached each of them all exactly once. Add that the next output is a function $F_K$ of the previous (rather of some internal state).

All we need is a pseudo-random permutation $P_K$ of the set $[0,n-1]$ with $n=b+1-a$, and it's inverse ${P_K}^{-1}$, from which we define
$$r_{j+1}=F_K(r_j)=P_K({P_K}^{-1}(r_j-a)+1\bmod n)+a$$

In other words, to move to the next number, we

subtract $a$
apply the inverse permutation ${P_K}^{-1}$
add one, and if the result is $n$ replace it by zero
apply the permutation $P_K$
add $a$

This essentially is applying $P_K$ to a cyclic counter, and an offset. The first two steps are unnecessary if we can keep memory of the counter's state.

Constructing pseudorandom permutation $P_K$ is a classic problem of Format Preserving Encryption. One option is a table built with a Fisher-Yates shuffle. Another is to use a block cipher and cycling:

compute $w=\lceil\log_2(n)\rceil$, that is the number of bits in $n-1$
build a $w$-bit block cipher $C$ with key $K$ (assimilate up-to $w$-bit integers to $w$-bit bitstrings per e.g big-endian convention).
compute $y=P_K(x)$ as

$y\gets x$
$y\gets C_K(y)$, that is encrypt $y$ with key $K$ per block cipher $C$
if $y\ge n$, go to the previous step

compute $x={P_K}^{-1}(y)$ as

$x\gets y$
$x\gets{C_K}^{-1}(x)$, that is decrypt $x$
if $x\ge n$, go to the previous step

The encryption and decryption loops always terminate, and are executed few times on average.

To construct permutation $C_K$, we can use a symmetric Feistel cipher, except we want to use $\displaystyle w=\min\left(2\left\lceil\frac{\log_2(n+1)}2\right\rceil,4\right)$ which will ensure that $w$ is even, that the Feistel cipher is not so small as to be degenerate, and that in the case where $n$ is a power of four we use a slightly larger block cipher to compensate for it being an even permutation.

Another option is a near-symmetric Feistel cipher when $w$ is odd, and addition instead of XOR for the round loop (fixing the even permutation thing), which let us use $w=\min(\lceil\log_2(n)\rceil,4)$.

If we are not in a hurry, the Feistel round function for round $i$ can be $F_{i,K}(L)=\operatorname{PRF}_K(i\mathbin\|L)$ truncated to $\lceil w/2\rceil$-bit, for some PRF such as HMAC-SHA-256.

In any case (and especially if we use a simpler/weaker round function), we should use a lot of rounds for small $w$, perhaps $\lceil 6+60/w\rceil$.


Encrypting using "Cryptography.HMACSHA1", how to decrypt (VBA) I have an encryption routine that works very well in VBA. But now I need to program the decryption routine, and I'm stuck. For encryption I'm using HMACSHA1 and transferring the encrypted byte to base 64. I can decode the base 64 and get the same byte array back, but any suggestion on how to use the HMACSHA1 to decrypt? Here's what I have so far (sorry if this is not the right place to ask these kinds of questions):

Private Function fDecrypto(sText As String, sPass As String) As String

Dim encoder As Object
Dim crypto As Object
Dim bEncrypted() As Byte
Dim i As Integer

' base64 to encrypted byte array

Dim objXML As MSXML2.DOMDocument
Dim objNode As MSXML2.IXMLDOMElement
Set objXML = New MSXML2.DOMDocument
Set objNode = objXML.createElement("b64")

objNode.DataType = "bin.base64"
objNode.Text = sText
bEncrypted = objNode.nodeTypedValue

Set objNode = Nothing
Set objXML = Nothing

' decrypt using HMACSHA1

Set encoder = CreateObject("System.Text.UTF8Encoding")
Set crypto = CreateObject("System.Security.Cryptography.HMACSHA1")

' **TODO - decrypt here**

Set encoder = Nothing
Set crypto = Nothing

End Function

Private Function fEncrypto(sText As String, sPass As String) As String

Dim encoder  As Object
Dim crypto As Object
Dim i As Integer
Dim bPass() As Byte
Dim bText() As Byte
Dim bEncrypted() As Byte

Set encoder = CreateObject("System.Text.UTF8Encoding")
Set crypto = CreateObject("System.Security.Cryptography.HMACSHA1")

bText = encoder.Getbytes_4(sText)
bPass = encoder.Getbytes_4(sPass)
crypto.key = bPass

bEncrypted = crypto.ComputeHash_2(bText)

Set encoder = Nothing
Set crypto = Nothing

' encrypted byte array to base64

Dim objXML As MSXML2.DOMDocument
Dim objNode As MSXML2.IXMLDOMElement
Set objXML = New MSXML2.DOMDocument
Set objNode = objXML.createElement("b64")

objNode.DataType = "bin.base64"
objNode.nodeTypedValue = bEncrypted
EncodeBase64 = objNode.Text

Set objNode = Nothing
Set objXML = Nothing

End Function

HMAC is a message authentication code (MAC). MACs produce "tags" that can can be used to prevent a message from being tampered with (sort of like a digital signature). There's no way to "decrypt" an HMAC tag to get back the original message, so it sounds like HMAC is not what you're looking for.

I would suggest using AES-GCM instead, since it's designed to be used for encryption. I'm not sure how to use AES-GCM from VBA: I suggest asking that on StackOverflow (that question would be off-topic here).


How to generate a key using any $m$ passwords out of total $n$? My application requires an AES-256 key K for some secure operation. In order to avoid saving this key in application, I have implemented following scheme:

There are 5 individuals who enters their passwords in application. Lets call them PW1..PW5
Using these passwords, I have generated the key as:

K = KDF(PW1 || PW2 || PW3 || PW4 || PW5)

The problem is that now I need to modify the application such that it works even if only 3 out of 5 passwords are available (but no less than 3). This is required because even if we lose one or two passwords (accident, person refusing to enter password etc.), we are able to recover from that situation.

Please can you advise how it can be achieved?

One option would be to generate a random key, split it using Shamir's secret sharing, then encrypt each of the split parts individually under a key derived from each user's password.

So for example:

key = read from os.urandom()
d1,d2,...d5 = split(key=key,n=5,k=3)
e1 = encrypt(d1, KDF(PW1)), e2 = encrypt(d2, KDF(PW2))...

key can then be derived from all of the encrypted shares (e1, ...) and user's passwords (PW1, ...). You could store the encrypted shares in the application and be confident that without at least three of the passwords you wouldn't be able to derive the key.


Attack on DSA with signatures made with k, k+1, k+2 For homework, I'm asked to find the private key, $x$, in a DSA digital signature scheme. In the particular instance, we are given the parameters $p$, $q$ and $g$, the public key $g^x$, 3 messages $(m_1, m_2, m_3)$, their hash values $(H(m_1), H(m_2), H(m_3))$ and the three signatures $([r_1, s_1], [r_2,s_3], [r_3,s_3])$. What is insecure about this particular instance is that the exponent, $k$, that we use to generate the signatures is $k+1$ in the second message, and $k+2$ in the third message.

I'm trying to figure out how to exploit this. My initial thought was to use the equations for calculating $r_i$ and $s_i$, substituting the appropriate value of $k$, $m$ and $r$ and then adding the equations or using some sort of modular arithmetic to solve the system of equations to first find $k$ in the equations for $r_i$ and then to find $x$ by using $k$ in the equations to find $s_i$. But when I add them together, I'm not able to simplify the equations into anything that can be solved because it is essentially in the same form of the original equation, which I assume can't be solved easily unless the entire algorithm is insecure. Here's what I mean:

The general equation for $r$: $r = (g^k \bmod p) \bmod q$
Adding the 3 $r$'s: $r_1+r_2+r_3 = ((g^k + g^{k+1} + g^{k+2}) \bmod p) \bmod q$

The only value I don't know here is $k$, but since I can't solve it in the first one, I don't think I can solve it in the second one. I think if I found $k$, I'd easily be able to solve for $x$ using the equation for $s$, but I can't find $k$. Do I have the right idea but the wrong math or am I completely on the wrong track?

You got three equations with two unknowns ($k$ and $x$). You only need two signatures to solve the private key $x$:

$s_1k \equiv h_1 + xr_1 \pmod q$
$s_2k + s_2 \equiv h_2 + xr_2 \pmod q$

This might be solved using Gaussian elimination. Step 1:

$s_1k/r_1 \equiv h_1/r_1 + x \pmod q$  - Divide 0.1 by $r_1$
$s_2k + s_2 - s_1kr_2/r_1 \equiv h_2 - h_1r_2/r_1 \pmod q$ - Subtract 1.1 times $r_2$ from 0.2

Step 2:

$x \equiv s_1k/r_1 - h_1/r_1 \pmod q$ - Swap terms of 1.1
$k \equiv (h_2 - s_2 - h_1r_2/r_1)/(s_2 - s_1r_2/r_1) \pmod q$ - Divide 1.1 by $s_2 - s_1r_2/r_1$

Step 3:

$x \equiv s_1((h_2 - s_2 - h_1r_2/r_1)/(s_2 - s_1r_2/r_1))/r_1 - h_1/r_1 \pmod q$ - substitute $k$ in 2.1 for right expression of 2.2


Can RFC 5649 be used to wrap multiple keys with the same KEK? I am unable to convince myself that RFC5649 is secure when storing multiple keys with the same KEK. My point is: RFC5649 uses AES-ECB, therefore the usual weakness of this method applies, namely an observer can deduce equalities among sections of the wrapped keys.

However, the sizes of the wrapped content make it less likely to have collisions (except for the AIV, but I do not believe that that could be an issue), as the payload will be 256bits of random data.

My question is therefore, is it secure to wrap multiple keys with the same KEK? If the answer is no, then what is the point of RFC5649 and what alternatives are there available?

(I believe the same doubt applies also to RFC 3394)

There are basically two purposes for which "ECB mode" encryption (i.e. simply splitting the input plaintext into blocks and applying the raw block cipher encryption function to each block) is safe and useful:

To deterministically encrypt messages up to one cipher block (i.e. 128 bits, for AES) long, in situations where the determinism of the encryption is acceptable (i.e. either it is extremely unlikely for two messages to ever be identical, even under an active attack, or it is acceptable for an adversary to learn if two messages are identical).
As a building block for other encryption schemes with (preferably provably) better security properties.

This is, in fact, what the scheme described in RFC 5649 does.  First, it is a deterministic key wrap scheme: this means that, by design, it does not even attempt to conceal whether or not two wrapped keys are identical.

Second, the scheme described in RFC 5649 only uses AES directly in ECB mode if the key to be wrapped is less than 64 bits long, which means that the key and the 64 bit "IV" together fit in a single 128 bit AES block.  Otherwise, it instead uses the wrapping process described in RFC 3394.  This process is not simple ECB mode encryption, but rather a kind of a wide-block cipher construction built on top of AES.

While RFC 3394 does not contain a security proof for this construction (and if one exists elsewhere, I'm not aware of it), it seems plausible that one could be found, perhaps in a manner similar to Luby and Rackoff's famous 1988 result on Feistel ciphers.  And that's not just my personal guess, either; Rogaway and Shrimpton, who review (and criticize) a version of the scheme in their 2006 paper on deterministic authenticated encryption, also state that:

  "The above criticism notwithstanding, we find it likely that the mechanism is correct. Namely, the modified Feistel network illustrated in Figure 7 is, we conjecture, a secure enciphering scheme (in the sense of a strong, variable-input-length PRP). Scheme AESKW is then seen as an instance of the PTE paradigm, except that the header is folded into the plaintext instead of used to tweak the enciphering scheme."

That said, there's really not much point: in the same paper I just quoted and linked to above, Rogaway and Shrimpton also introduce SIV mode (since then standardized in RFC 5297), which provides a more efficient, flexible and provably secure (in a precise sense also defined in the paper) method for deterministic key wrapping.

As a bonus, in situations where deterministic encryption (and the resulting leak of plaintext equality) is not desired, SIV mode can also be used with an optional nonce to provide a fully CCA secure authenticated encryption scheme.


Why is stateful CTR slightly better than stateless CTR? Does the adversary know the value of counter in CTR mode of operation? This might be a stupid question but is really fundamental in my understanding of CTR (I'm a newbie to cryptography theory).

For CPA security, the adversary only knows the IV, and may query the oracle for random values of IV+$ctr^*$ where $ctr^*$ is the counter.

For stateful CTR, what do we assume is predictable - the nonce or the counter?

For stateful CTR, what do we assume is predictable - the nonce or the counter?

Both. In general, the majority of implementations work as follows:

The input to the block cipher is the combination of IV/Nonce (96-bits) and Counter (32-bits). For each message, the Nonce increments by 1. For each block of a message, the counter increments by 1.

The state kept by communicating parties consists of the key, the last nonce used, and the last counter used. Importantly, keeping track of these ensures that the combination of all 3 is only ever used once, as repetition can allow plaintext recovery if an attacker knows one of the plaintext blocks used with that triplicate.

That predictability is also important for optimization, as both sender and receiver can precompute blocks of a message in parallel while waiting for the message to be received, or in multiple threads to increase throughput.


Does the use of English words weaken diceware passphrases A Diceware passphrase is constructed from a set of words chosen from a 7776-word database, using five dice throws to choose each word. The argument is that each word in the phrase adds about 12.92 bits of entropy since $\log_2(7776)≈12.92$. As Arnold Reinhold, the creator of Diceware, explains, the entropy comes from the size of the database, not from the way in which the elements are represented. So, in principle, it does not matter whether a 7-word passphrase is formed as 7 English words from a Diceware database, the original 7 five-dice throws (in effect 7 five-digit base six numbers with each digit increased by 1), or seven Chinese characters chosen from a database of 7776 Chinese characters. Each would have an entropy of about 90 bits.

Is it not the case, however, that using English words in place of the underlying dice-throw numbers reduces the entropy of the passphrase. The words in the standard Diceware database have an average length of 4.2 characters. This means that the average length of a 7-word passphrase would be about 30 characters. It is said that letters in English text have an entropy of about 1.3 bits each due to the redundancy of the language. This would imply that, analyzed as English text, the passphrase would only have an entropy of 38 bits. Arguably a Diceware passphrase is not typical English text, but presumably one could do a similar analysis to determine the redundancy of text drawn from the Diceware database, but, if my argument is correct, each letter in the passphrase would have to have at least 3 bits of entropy in order not to downgrade the entropy of the underlying Diceware elements.

Reinhold himself glosses over this. He says:

  But, you might ask, Diceware is made up mostly of English words. Doesn't that redundancy affect it at all? Well, it does. The seven word Diceware passphrase we talked about above would average about 30 letters in length (36 if you count the spaces between the words). If those letters were selected randomly, you would get 4.7 bits of strength per letter. That would work out to a lot more than the 90 bits Diceware claims for a seven word passphrase. The difference is the redundancy of English at work. However English redundancy does not affect the calculation that each Diceware word has 12.9 bits of randomness, which is based entirely how many different words there are in the Diceware list. You can rely on that number.

The redundancy of English does not affect the entropy of the Diceware passphrase, so long as you can rely on each letter having 4.7 bits of entropy, or indeed at least 3 bits. But I don't see what guarantee there is that this is the case.

Note that this question is not answered by Can an attacker exploit the nonuniform distribution of letters in a diceware password to improve a brute force search? since this question raises a different argument not considered in that question. The underlying issue is similar, but the question asked about it is different.

I don't believe that looking at the diceware phrase is very helpful.

Instead, look at it this way; there are $7776^7 \approx 2^{90.47}$ possible 7 word diceware phrases, and diceware will select one of those possibilities uniformly.

That means that the probability that one specific phrase is selected is at most $2^{-90.47}$.  Or, in other words, if someone were to guess random diceware phrases, he would make an expected $2^{90.47}/2 = 2^{89.47}$ guesses on average before hitting the right one.

  Is it not the case, however, that using English words in place of the underlying dice-throw numbers reduces the entropy of the passphrase.

No; there is a one-to-one mapping between diceware throw numbers and valid diceware phrases; one can take the phrase, and map it back to the throws that generated it.  And, a one-to-one mapping never effects the entropy.

What it does effect is the 'entropy-per-character' measurement; because the diceware phrase is (usually) lengthy, the 'entropy-per-character' measurement is a bit low.  However, we don't really care about the 'entropy-per-character', instead, we care about the security that the entire passphrase gives us.

Remember, the 'entropy of a passphrase' is a bit misleading; if we talk about entropy, we need to talk about the process that selected the passphrase.  In diceware, we have a very different process than if someone were writing some English text (and so the entropy estimates that may be valid for human generated English text do not apply to diceware generated texts)


How is RSA able to prevent brute forcing using the public key? Bob calculates a private and public key.

Bob sends his public key to John.

Jeff is a third party unwanted member and manages to snatch the public key mid-transfer.

John encrypts his message and sends it to Bob.

Jeff again is able to steal this encrypted message for himself.

Bob can decrypt the message with his private key.

But what about Jeff? So he can't decrypt using the one-way key. But what if he brutes it? So for example John's original value was 2 and the encrypted value is now let's say 200. Jeff can now just count upwards from 1 and encrypt all values with the public key until it matches the value of 200. He finds 2 matches that. So now he has the original value.

I know it's not that simple and easy and it might not even work at all on a real RSA standard but I want to know what the procedure is for stopping this sort of attack.

If Jeff has the public key and an encrypted message, why can't he guess the message, encrypt it with the public key, and see if he gets the encrypted message.

Well, that particular attack is foiled by the RSA padding method.  All RSA encryption padding methods include randomness in the padding (specifically to foil this attack).  Whenever John encrypts a message, he (actually, his crypto library) selects a number of random bits, and pads the message (that is, prepares the message for the core RSA operation) using those random bits. Hence the encrypted message is a function of both the plaintext message and those random bits.

Jeff can certainly take the public key, and encrypt a guess of the message with it; however unless he happens to pick the same random bits that John used, his encrypted message will look different, and so comparing the actual ciphertext to his test one (with high probability) tells him nothing.  And, we use enough random bits so that Jeff can't brute force those.


Group in the context of elliptic curve crypto I understand that the discrete log problem is defined as

$G^y \bmod p = x$

Speaking generally, $G$ here is a generator for the group zp*, where $G$ is able to generate each element in the group for a given prime modulus.

My question is, in the context of elliptic curve cryptography, is the group the entire set of points that lies on the curve being used?

Assuming this is correct, does the prime used for the modulus have to be larger or smaller than this group of points, or even reside in it?

Short answer: the definition you're using (and, in particular, the notation in it) is specific to multiplicative groups modulo $p$.  It makes no sense for elliptic curves, or for most other kinds of groups over which the discrete logarithm problem can be defined.  In particular, for elliptic curves, there is no prime modulus $p$.

(Well, OK, for the elliptic curves used in cryptography, there is a prime modulus involved in the definition of the finite field over which the elliptic curve itself is defined.  The size of this prime depends on the type of finite field used — it can be anything from $2$ up to the size of the field itself — and is only very indirectly relevant to the hardness of the discrete logarithm problem.)

Longer answer: In mathematics, a group is simply any set $G$ equipped with some binary operator $\star$ that satisfies the following properties:

Closure: For every $a, b \in G$, the value $a \star b$ is defined and belongs to $G$.
Associativity: The equation $(a \star b) \star c = a \star (b \star c)$ holds for every $a, b, c \in G$.
Identity: There exists an identity element $\epsilon \in G$ such that $\epsilon \star a = a \star \epsilon = a$ holds for every $a \in G$.
Invertibility: For every $a \in G$ there exists another element $b \in G$ (called the group inverse of $a$) such that $a \star b = b \star a = \epsilon$.

If these properties seem fairly broad and abstract, that's because they are.  Indeed, math is full of things that satisfy the definition of a group.  For a few examples:

The integers $\Bbb Z = \{…, -2, -1, 0, 1, 2, …\}$ equipped with the operation $+$ (i.e. addition) form a group.  The identity element is $0$ and the inverse of $a$ is $-a$.
The positive rational numbers $\Bbb Q^+$ equipped with the operation $·$ (i.e. multiplication) also form a group.  The identity element is $1$, and the inverse of $a$ is $1/a$.
For any set $S$, the set of invertible functions from $S$ to $S$ form a group, with function composition ($\circ$) as the group operator.  This group is known as the symmetric group of $S$.
For any $n > 0$, the numbers $\{0, …, n-1\}$ equipped with the operation $+_n$ defined as $$a +_n b = (a + b) \bmod n = \begin{cases}a + b & \text{if }a + b < n, \\ a + b - n & \text{otherwise} \end{cases}$$ also form a group.  The identity is still $0$, but the inverse of $a \ne 0$ is now $n - a$.  This group is isomorphic to the (additive) group of integers modulo $n$, and indeed is one way to define that group (although a more commonly used definition uses congruence classes instead).
For any prime $p$, the numbers $\{1, …, p-1\}$ equipped with the operation $·_p$ defined as $$a ·_p b = ab \bmod p = ab - kp,$$ where $k$ is the largest integer such that $kp \le ab$, also form a group.  The identity is $1$, and the inverse of any element $a$ can be calculated e.g. using the extended Euclidean algorithm.  This group is isomorphic to (and again, under some definitions, the same as) the multiplicative group of integers modulo $p$.

There are, however, plenty of other ways to form groups as well.  For example, for any elliptic curve, it's possible to define a binary operator that makes the set of points on the curve (including the "point at infinity") into a group.  The definition is somewhat complicated, so I won't attempt to summarize it here, but it can be shown to satisfy all the properties required of a group.

Now, for any group $G$ with the group operation $\star$, we can define an "exponentiation" operator $\uparrow$ that maps a group element $g \in G$ and a non-negative integer $k \in \Bbb N$ into the group element $$g \uparrow k = \underbrace{g \star g \star … \star g}_{k \text{ times}}.$$ (In particular, $g \uparrow 0$ is defined to be the group identity element $\epsilon$.)

For any group element $g \in G$, the set $$g^{\Bbb N} = \{\epsilon, g, g \star g, g \star g \star g, …\} = \{k \in \Bbb N: g \uparrow k\}$$ of powers of $g$ forms a subgroup of $G$.  This is called the subgroup generated by $g$, and also written $\langle g \rangle$.  (For some groups, it's even possible to find a $g \in G$ such that $\langle g \rangle = G$, i.e. $g$ generates the entire group $G$.)

For a given generator $g \in G$ and an arbitrary element $a$ of the subgroup $\langle g \rangle \subset G$ generated by $g$, it's then possible to ask the question: what is the smallest (or even any) number $k \in \Bbb N$ such that $g \uparrow k = a$?  Such a number $k$ is known as the discrete logarithm of $a$ with respect to $g$.

Now, for some groups, computing the discrete logarithm is very easy.  For example, if $G = \Bbb Z$ is the additive group of integers, then $g \uparrow k = kg$, and the discrete logarithm of $a$ with respect to $g \ne 0$ is simply $a \mathbin/ g$.  The additive group of integers modulo $n$ is not much harder: calculating the discrete logarithm of $a$ there just requires solving the modular congruence $a \equiv kg \pmod n$, which can be done using the aforementioned extended Euclidean algorithm.

However, for other groups, no easy or efficient way of calculating discrete logarithms is known.  The multiplicative groups of integers modulo large primes $p$ are one example of a class of such groups; elliptic curves (over a finite field) are another.

For cryptography, the main advantage of choosing elliptic curves over multiplicative groups of integers is that the most efficient known algorithms for finding discrete logarithms over elliptic curves are even less efficient than those for multiplicative groups of integers.  In other words, this means that we can use smaller groups (and thus shorter keys etc.) for the same conjectured level of security.

Of course, technically, we don't know that the discrete logarithm problem is actually hard over either kind of groups, and that there isn't some magic algorithm to solve it efficiently that we just haven't found yet.  But a lot of smart people have studied this problem for both kinds of groups, trying to find such an algorithm, and so far (at least as far as publicly available academic literature goes) they haven't really found one.  And so far, of the two kinds of groups, elliptic curves seem to be the harder nut to crack.


How to generate the SHA-2 constants? The SHA spec states - eg, in the case of SHA-224 and SHA-256 - that the constants "represent the first 32-bits of the fractional parts of the cube roots of the first 64 primes". How are these values "represented"?  Beginning with a prime number, and ending with the hex constant, what is the correct sequence of steps to generate all of the constants as provided in the spec?

It's exactly how it sounds.  Note: 428a2f98 when interpreted as a hexadecimal fraction has the value of 4/16 + 2/(16^2) + 8/(16^3) + 10/(16^4) + ... which is approximately equal to 0.2599210496991873, so when you add back the non-fractional part you get 1.2599210496991873 which is the cube-root of the first prime number (2).

In python:

In [1]: 1+sum([int(c,16)/(16.**(i+1)) for (i,c) in enumerate('428a2f98')])
Out[1]: 1.2599210496991873

In [2]: 2**(1/3.)
Out[2]: 1.2599210498948732

To generate the constants you can the gmpy2 python library with the following code:

from gmpy2 import mpfr, floor, next_prime

def convert_primes_cube_fractional_part_to_hex_constant(prime, hex_chars=8):
    """
    Note if you want the first 8 decimal (base=10) digits of a number,
    you multiply the fractional part by 10**8 and then look at the integer part
    In this case we want first 8 hex digits, so multiply fractional part by 16**8
    and then look at integer part (and return in hexadecimal).
    """
    cube_root = mpfr(prime)**(1/mpfr(3))
    frac_part = cube_root - floor(cube_root)
    format_str = '%%0%dx' % hex_chars
    # format_str will be '%08x' if hex_chars=8 so always emits
    # 8 zero-padded hex digits
    return format_str % floor(frac_part*(16**hex_chars))

def generate_n_primes(n=64):
    p = 2
    i = 0
    while i < n:
        yield p
        p = next_prime(p)
        i += 1

After defining those functions you can run, the following to recreate the table:

>>> for i,p in enumerate(generate_n_primes(64)):
        if i % 8 == 0:
            print ""
        print convert_primes_cube_fractional_part_to_hex_constant(p, hex_chars=8),

428a2f98 71374491 b5c0fbcf e9b5dba5 3956c25b 59f111f1 923f82a4 ab1c5ed5
d807aa98 12835b01 243185be 550c7dc3 72be5d74 80deb1fe 9bdc06a7 c19bf174
e49b69c1 efbe4786 0fc19dc6 240ca1cc 2de92c6f 4a7484aa 5cb0a9dc 76f988da
983e5152 a831c66d b00327c8 bf597fc7 c6e00bf3 d5a79147 06ca6351 14292967
27b70a85 2e1b2138 4d2c6dfc 53380d13 650a7354 766a0abb 81c2c92e 92722c85
a2bfe8a1 a81a664b c24b8b70 c76c51a3 d192e819 d6990624 f40e3585 106aa070
19a4c116 1e376c08 2748774c 34b0bcb5 391c0cb3 4ed8aa4a 5b9cca4f 682e6ff3
748f82ee 78a5636f 84c87814 8cc70208 90befffa a4506ceb bef9a3f7 c67178f2

Note this exactly matches the table in the NIST publication.

You can generate the other SHA-512 constants with the following code.  Note you first have to increase the multiple precision floating point math in gmpy2 to ~100 digits from the default 53 digits, or you'll find the last few hexdigits are always 0 due to loss of precision.

>>> gmpy2.get_context().precision=100
>>> for i,p in enumerate(generate_n_primes(80)):
        if i % 4 == 0:
            print ""
        print convert_primes_cube_fractional_part_to_hex_constant(p, hex_chars=16),


Is the term "Elliptic Curve Discrete Logarithm Problem" a misnomer? I have just started studying Elliptic Curve Cryptography, and I have this doubt. In ECC the group operation is addition (and not multiplication). So, why is ECDLP stated as a variation of the discrete log problem? Wouldn't "discrete multiplier problem" or "discrete factor problem" be more apt?

CodesInChaos has it correct, however since you're just learning, I think I'll lay it out rather explicitly.

When we have an abstract group, there are two ways of expressing operations in the group.

One way is writing the operation as if it were the multiplication operation, for example, if we apply the operation to elements $A$ and $B$ and the result is the element $C$, we would write this as $AB = C$, or alternatively (if we want to emphasize the operation) $A \cdot B = C$.  In addition, the act of performing the operation on $n$ copies of object $A$ is written as
$$\underbrace{A \cdot A \cdot ... \cdot A}_\text{n copies} = A^n$$
When we write a group in this format, we call it a "multiplicative group".

The other way to write the operation would be to write it as if it were the addition operation.  In our example where we apply the operation to elements $A$ and $B$ resulting in $C$, this gets expressed as $A+B=C$.  The act of performing the operation on $n$ copies of the object $A$ is written as
$$\underbrace{A + A + ... + A}_\text{n copies} = nA$$
When we write a group in this format, we call it an "additive group".

Now, the only difference between a multiplicative group and an additive group is how we choose to write it.  For some groups, we traditionally write them in multiplicative form, for other groups, we generally write them in additive form.

One such group that always gets written in multiplicative form is that group $\mathbb{Z}_p^*$, which can be viewed as a set of integers between 1 and $p-1$ where the group operation is $(A \times B) \bmod p$.  This is the first group where the problem "Given $G$ and $H$, it is difficult to find $n$ with $H = G^n$" was exploited cryptographically; because the analogous function in the Reals is called logarithm, as $n = \log_G H$, this problem was dubbed as the "discrete logarithm problem".

Now, we step to Elliptic Curve Groups; those groups are almost always written additively (I have seen it written multiplicatively, but it's rare).  So, the analogous problem is "given points $G$ and $H$, find $n$ with $H = nG$".  Now, if someone wanted to be completely consistent with the terminology, the obvious notational way to express this would be to write $n = H/G$ or this is a "point division problem".  This would appear to make sense, however no one ever uses this terminology.  Instead, everyone calls this the ECDLP problem, even though everything else done with elliptic cures is written additively.  This is inconsistent, but language is like that; if you want other people to understand you, you use the terminology that everyone else does.


Does Grover's algorithm effect block size or only key size? We know that Grover's algorithm can speed up cracking symmetric keys. Basically the keyspace is halved. This means we have to use at least a 256-bit key (to get 128-bit security).

I heard somewhere it also has an effect on the block size (so we should use 256-bit blocks instead of 128)!

Is that true?

It depends on the application. If you are using the block cipher as a hash function or for a MAC (say in CBC-MAC fashion), then it very well could create problems. Preimage attacks would be much easier than they should.

For normal encryption, however, there wouldn't be a problem since the key is not known to the attacker. As evidence of this, consider Triple DES which has a 64 bit block size yet is still sufficiently secure for use today (though I wouldn't recommend it in newer designs).