How can a block cipher in counter mode be a reasonable PRNG when it's a PRP? Wikipedia claims:

  A secure block cipher can be converted into a CSPRNG by running it in counter mode. This is done by choosing a random key and encrypting a 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Obviously, the period will be 2^n for an n-bit block cipher; equally obviously, the initial values (i.e., key and "plaintext") must not become known to an attacker, however good this CSPRNG construction might be. Otherwise, all security will be lost.

Here's a trivial counter-example:

Say I'm interested in generating psuedo-random 128 bit numbers. I'm using this method with a 128bit block cipher, but since the block cipher is giving out essentially a psuedo-random permutation of the counter - all the numbers I get are different! They are obviously not going to pass any basic randomness tests?!

Is this a mistake in Wikipedia (or just a misleading explanation?) or there's something I got wrong here?

If the answer is that it simply wouldn't work for values equal or larger than 128 bits, I would still doubt it would give out good quality output for 64 bits, since it has a very predictable pattern that the concatenation of any two consecutive 64 bit values is unique pattern that would never repeat (if that's a not a "real concern" mathematically, could you explain why? and what about 96 bit numbers?).

And if this is actually the case, are there any alternative examples of CSPRNG constructions that generate quality values for arbitrarily large amount of bits? are secure hashes any better (it seems reasonable I guess..)?

[Note: I've found this answer that very shortly addresses this issue but I didn't find it satisfying enough]

Update: Wikipedia seems to be updated now as a result of this discussion! Many thanks for @CodesInChaos who improved the article. This is useful knowledge for myself and many other people.

For a random function you'd expect all outputs to be different if you generate fewer than $2^{n/2}$ blocks (birthday problem). Thus PRPs and PRFs are indistinguishable unless you observe about $2^{n/2}$, at which point you'd expect collisions using the PRF but not using the PRP.

For a 128 bit cipher this is a lot of data, so we generally don't care about this. But using a 64 bit cipher, you shouldn't encrypt more than a few gigabytes of data using the same key.

  are there any alternative examples of CSPRNG constructions that generate quality values for arbitrarily large amount of bits?

In principle yes. I think using a variant of CTR mode which uses a secret IV and xors the counter+IV into the output might work. It'd get rid of the trivial "no duplicates" pattern, but it might be distinguishable in other ways.

128 bit blocks should be good enough as a stream cipher/CSPRNG. But if it's a bit too low for your taste (Generating $2^{64}$ blocks is feasible with sufficient effort), you can simply use larger blocks. Typically hash functions (like SHA-2), which want to avoid collisions, use 256 or 512 bit block ciphers.

I've changed the paragraph on wikipedia to

  A secure block cipher can be converted into a CSPRNG by running it in counter mode. This is done by choosing a random key and encrypting a 0, then encrypting a 1, then encrypting a 2, etc. The counter can also be started at an arbitrary number other than zero. Assuming an n-bit block cipher the output can be distinguished from random data after around $2^{n/2}$ blocks since, following the birthday problem, colliding blocks should become likely at that point, whereas a block cipher in CTR mode will never output identical blocks. For 64 bit block ciphers this limits the safe output size to a few gigabytes, with 128 bit blocks the limitation is large enough not to impact typical applications.

I mention the $2^{n/2}$ birthday bound limitation. Removed the part about the period, since it doesn't matter in practice (it's far above both practical output size and safe output size). I also removed the part about keeping key and plaintext (what plaintext? It's a CSRPNG, not a cipher) secret. I'm not really happy with the formulation, so feel free to improve it.


Public key verification schemes I have a short question.

Besides PKI, Web of Trust or secure out of band communication. Is there any other way to verify the public key of a communicating party?

In other words, let's assume an active adversary with MiTM capabilities. When we are doing a public key exchange, you have to rely on a trusted third party or any other out of band secure channel to verify to authenticity of the public key. There is no way of using the same channel that you just exchanged the keys.

Authenticating somebody means verifying who they are. This always involves out-of-band information because otherwise you don't even know them.

If you like security games try to distinguish between two people without knowing anything about them. ;)

Even a PKI is a separate channel.

You can consider different authentication factors which are usually split into

Something the person knows (Password-based key agreement)
Something the person has (PKI, their private key)
Something the person is (like a fingerprint)

but in any case you need to somehow be able to verify the information you get using some out-of-band information.

Maybe the 3rd factor "inheritence" deserves a litte more attention. It also includes things that the person does. So you could require that your communication partner behaves in a specific way. However if that behavior is not used to identify somebody you are actually doing fraud detection or intrusion detection and not really authentication.

I suppose you could consider the case where you only know somebody from in-band interactions and you just want to make sure that it's always the same person. In this case you should just do a key exchange on the first interaction.


Is this problem with anti-circulant matrices hard? If there is an obvious way to solve this problem, please give it a chance before downvoting, I beg you. Also, some insight into the resultant asymmetric cryptosystem will be welcomed (described in the link at the end of this question).
We will work with 4x4 anti-circulant matrices of the form:
$$\left (\begin{matrix}
a_0 & a_1 & a_2 & a_3 \\
a_1 & a_2 & a_3 & a_0 \\
a_2 & a_3 & a_0 & a_1 \\
a_3 & a_0 & a_1 & a_2
\end{matrix}\right )$$
With $a_i \in \mathbb{Z}_p$ and with $p$ a large enough prime, say 32-bit. Let's call the invertible subset of such matrices $S$.
Since the product of two anti-circulant matrices is a circulant matrix, we define a matrix that turns a circulant matrix into its anti-circulant equivalent.
$$M=\left (\begin{matrix}
1 & 0 & 0 & 0 \\
0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 \\
\end{matrix}\right )$$
Next, we define a function $f$, which is the product of two matrices turning the result in its anti-circulant equivalent:
$f(A,B)=M A B$
As an anticirculant matrix is defined by its first column, we can alternatively write $f$ just as a function of vectors:
$$
f\left(
\left(\begin{matrix} a_0\\a_1\\a_2\\a_3\end{matrix}\right),
\left(\begin{matrix} b_0\\b_1\\b_2\\b_3\end{matrix}\right)
\right)=
\left(\begin{matrix}
a_0 b_0+a_1 b_1+a_2 b_2+a_3 b_3\\
a_0 b_1+a_1 b_2+a_2 b_3+a_3 b_0\\
a_0 b_2+a_1 b_3+a_2 b_0+a_3 b_1\\
a_0 b_3+a_1 b_0+a_2 b_1+a_3 b_2\\
\end{matrix}\right)
$$
This function is not associative and not commutative.
Next let's define a series using the function just defined:
$k_1,k_2 \in S, s_0=k_1, s_1=k_2, s_i=f(s_{i-2},s_{i-1})$
next we define two result elements for a given $i$:
$r_1=f(s_{i-1},k_1)$, $r_2=f(s_i,k_2)$
Then, for a large enough $i$, the hard problem is:
find the value of $k_1$ and $k_2$ knowing $r_1$ and $r_2$.
If the problem is really hard, it can lead to the cryptosystem described here.
It is also described more simply here.

No, this problem is not hard. Here is algebraic reformulation which leads to efficient key recovery.
Ring representation
Let $R = \mathbb{F}_p[X]/(X^4-1)$. We identify any $a \in S$ with an element of $R$ as follows:
$$
R(a) = a_0 + a_1X+a_2X^2+a_3X^3.
$$
From now on assume that we work with elements of $R$.
Let $rev$ denote the polynomial reciprocal function:
$$
rev(R(a)) = a_3 + a_2X+a_1X^2+a_0X^3.
$$
Then, it is easy to verify that for any $a,b \in R$
$$
rev(a\cdot b) = X\cdot rev(a) \cdot rev(b)
$$
and that
$$
f(a,b) = rev(a\cdot rev(b)) = X \cdot rev(a) \cdot b.
$$
Using the simple fact that $rev(X^i a)=X^{-i}rev(a)$, we can reduce the result of any sequence of operations of $f$ to the form
$$
s_i(k_1,k_2) = X^j \cdot k_1^x\cdot  rev(k_1)^y\cdot  k_2^z\cdot rev(k_2)^w,
$$
where $i,j,x,y,z,w$ are known integers (depending on the number of iterations $i$).
Note that we are given two such values $s_i, s_{i+1}$.
This settles simple (up to $rev$) algebraic formulation of the problem.
Clearly, without $rev$ we would be given a pair $(k_1^xk_2^y, k_1^zk_2^w)$ and it would be easy to recover $k_1,k_2$, excluding corner cases when the matrix
$$
\pmatrix{x & y \\ z & w}
$$
is not invertible modulo $p-1$, in which case we'll have to deal with factorization of $p-1$.
Recovering linear components
Observe that $X^4-1 = (X-1)(X+1)(X^2+1)$. We will consider $s_i \in R$ modulo each of the linear factors and two cases for the last factor depending on whether it splits or not.
Case of $X-1$
Reduction modulo $(X-1)$ is equivalent to computing the trace of the vector: $tr(a) = a_0+a_1+a_2+a_3$. It is easy to see (e.g. by plugging $X=1$ in the polynomial form of $a,b$) that
$$
tr(f(a,b)) = tr(a)\cdot tr(b).
$$
As a result,
$$
tr(s_i) = tr(k_1)^{F_{i-1}}tr(k_2)^{F_i},
$$
where $F_{-1},F_0,F_1,F_2,\ldots = 1,0,1,1,2,\ldots$ are the Fibonacci numbers.
Given $s_i, s_{i+1}$, we can "undo" the iterations via divisions like
$$
tr(s_{i-1})=tr(s_{i+1})/tr(s_i)
$$
and recover
$$
tr(k_1), tr(k_2).
$$
This amounts to inverting the matrix described above
$$
\pmatrix{x' & y' \\ z' & w'} = \pmatrix{x & y \\ z & w}^{-1}
$$
and computing
$$
tr(k_1) = tr(s_i)^{x'}tr(s_{i+1})^{y'},
tr(k_2) = tr(s_i)^{z'}tr(s_{i+1})^{w'}.
$$
Case of $X+1$
Similarly, let $tr'(a) = a_0 - a_1 + a_2 - a_3$. Then we also have
$$
tr'(f(a,b)) = tr'(a)\cdot tr'(b).
$$
The recovery of $tr'(k_1), tr'(k_2)$ is analogous to the case of $tr$, except that we have to track the sign, since $tr'(X) =-1$.
Case when $X^2+1$ splits ($p=4k+1$)
If $p=4k+1$, then $X^2+1$ splits into $(X-i)(X+i)$ (thanks @Mark).
However, reduction modulo $(X-i)$ or $(X+i)$ does not behave very well with respect to $rev$. Let $a = a_0 + a_1X + a_2X^2 + a_3X^3$. Then,
$$
a \mod (X-i) = (a_0 - a_2) + i(a_1 - a_3),
$$
$$
rev(a)\cdot i \mod (X-i) = (a_0 - a_2) - i(a_1 - a_3).
$$
We see that $a$ and $rev(a)\cdot i$ are "complex conjugates" of each other (note that $i$ is actually not imaginary but lies in $\mathbb{F}_p$).
The problem with previous approach is that $a$ and $rev(a)$ are not related by a constant multiplication and so each $s_i$ has 4 variables (whereas previously $k_1$ and $rev(k_1)$ collapsed into one variable).
Now,
$$
a \mod (X+i) = (a_0 - a_2) - i(a_1 - a_3),
$$
$$
rev(a)\cdot (-i) \mod (X+i) = (a_0 - a_2) + i(a_1 - a_3).
$$
Observe that the four expressions $a \mod (X+i), rev(a) \mod (X+i), a \mod (X-i), rev(a) \mod (X-i)$ contain only 2 unique variables. Therefore, $s_i \mod (X-i), s_i \mod (X+i), s_{i+1} \mod (X-i), s_{i+1} \mod (X+i)$ give four equations on the exponents of four variables (a pair of "conjugates" for each of $k_1,k_2$). Therefore, we can invert the respective 4x4 matrix and recover $k_1,k_2$ modulo $(X-i)$ and $(X+i)$.
Now that we have the solution modulo each linear factor, we can reconstruct the keys using the Chinese Remainder Theorem (CRT). This is a complete break for the case $p=4k+1$.
See SageMath implementation of the attack.
Case when $X^2+1$ does not split ($p=4k+3$)
In this case apply the same technique to recover the complex norm of $k_1,k_2$ modulo $X^2+1$, which is multiplicative.
Further, we reuse the previously noted fact that
$$
X\cdot rev(a) \mod{X^2+1}
$$
is the complex conjugate of $a \mod {X^2+1}$. In particular,
$$
X\cdot rev(a) \cdot a \mod{X^2+1} = norm_{X^2+1}(a)
$$
Recall that we have values of the form
$$
s_i(k_1,k_2) = X^j \cdot k_1^x\cdot  rev(k_1)^y\cdot  k_2^z\cdot rev(k_2)^w.
$$
Working modulo $X^2+1$, we can replace $rev(k_1)$ by $norm_{X^2+1}(k_1)/X/k_1$. Similarly with $k_2$. Since the norm is recovered,
we end up with equations of the form
$$
u_1 = k_1^{x'}\cdot  k_2^{y'}
$$
$$
u_2 = k_1^{z'}\cdot  k_2^{w'},
$$
where $u_1,u_2,x',z',y',w'$ are known. This is completely similar to previous attacks, and so we recover $k_1$ and $k_2$ modulo $X^2+1$.
After combining the components using CRT, we recover $k_1,k_2$ completely.
The scheme is broken.
UPD: I just realized that I was recovering $k_1,k_2$ from $s_i, s_{i+1}$ which is trivial to do in any representation by inverting each step. However, for $r_1=f(s_i,k_1), r_2=f(s_{i+1},k_2)$ the attack still works by inversion of the relevant exponent matrix $[[x,y],[z,w]]$ modulo element order of the multiplicative group of the ring (which is $p-1$ for $p=4k+1$ and $p^2-1$ for $p=4k+3$). The only caveat is that in the latter case the matrix is not always invertible modulo each factor of the order. I suppose that the solution is not unique in such cases.


Using a Caesar Cipher with a key higher than 26? When I have experimented with using a key higher than 26 on a Caesar cipher, I have had some very ...interesting... results. The encryption works fine, but when I attempt to decrypt the encrypted message, I am unable to decrypt the message successful.

I understand that a Caesar can theoretically have a key size of 26, I am just curious as to what would happen with a longer key.
Can somebody assist with both the mathematical side, and if it is possible to use the cipher with a key size higher than 26?

EDIT: In my program I am converting the message to ASCII, adding the key size. To decrypt, I convert it back from ASCII to characters.

The Caesar cipher doesn't just add a value to the character value. What it does is the following (per character in the plaintext):

it converts the character to the index of the character in the alphabet, say 0..25 for uppercase characters;
it performs modular addition of the value, using the size of the alphabet as the modulus;
it converts the resulting index back into a character.

For example you add the key 3 to the 'Z' character, then you:

convert the 'Z' character to the index 25 (index starting with 0, so 26 - 1);
add 3 and perform mod 26: $25 + 3 = 28$, $28 \bmod 26 = 2$;
convert the index 2 to the alphabet, 'C' (as 2 means the third character).

In human language, once you're past 'Z', you start with 'A' again.

Decryption is identical, but it uses subtraction of the key instead of addition.

Great, so what if the key is 26 or higher?

Well, because we use modular addition you can simply do the following: $c = p + k (\mod 26) = p + k - n \times 26 (\mod 26)$. In other words, you can subtract 26 as many times as you want until you get in the index range 0..25 again.

In the example above, using a key of 29 is identical to a key valued $29 - 26 = 3$.

A quick mind also notes that $-3 \bmod 26 = 23$. Which means that decryption with key 3 is identical to encryption with key 23. So basically you only have to create an encryption routine.

You'll also notice that a key that is a multiple of 26 (0, 26, 52 will map the index (and thus the character) back onto itself. So those keys are weak keys and should not be used. A key of 13 will make decryption identical to encryption (as 26 - 13 = 13 again).

Now above explains what you do if you keep to an alphabet size of 26 characters. If you have an alphabet of 26 characters. You can also extend the alphabet, e.g. using the "alphabet":

abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ.,0123456789

In that case you can perform modular addition / subtraction with a modulus of $26 + 26 + 2 + 10 = 64$.

To view a good implementation in Python you can have a look here


Given a ciphertext in RSA which is not comprime with our N, can we get the secret key? If we are given a ciphertext which is not coprime with our N (N = p*q), is there any way to get the secret key from this information in RSA?

I first thought you could divide the N by our ciphertext C, giving us a non-trivial factorization of N i.e. C * (N/C). But then we would be stuck trying to find $\phi(C)$ and $\phi(N/C)$, which I suppose is not easier than factoring N in the first place, if they are not primes. Can it be done?

Let $N=p\cdot q\quad,p,q\in\mathbb P$ be a semi-prime (as in RSA). Further let $a$ be any number for now. $$\gcd(a,N)$$ can now take exactly 4 values:

$\gcd(a,N)=1$
$\gcd(a,N)=p$
$\gcd(a,N)=q$
$\gcd(a,N)=N$

because there are no other factors of $N$ which could be the greatest common divisor.
Now let's take $c$ (your cipher text) instead of $a$. We can exclude case 1 because we know $c$ and $N$ are not co-prime (remember how co-prime is defined as $\gcd(a,b)=1$?). We can exclude case 4, because $c$ is an RSA ciphertext and thus was reduced $\bmod N$ before and this automatically ensures that $c<N$. Furthermore $c$ is supposed to be a ciphertext for which the case $m=0$ probably happens with negligible probability and the only encryption that can yield $m=0$ is one of multiple (including 0) of the modulus, i.e. only 0, if we assume $m<N$ as usual (which excludes the case where $m=0$ which would yield $\gcd(c,N)=N$)(thanks poncho and fgrieu). Also note that you don't need to bother with the key at all if $c=0$ because you directly know that $m=0$.

Now we're left with only two possible options: $p$ and $q$. So the $\gcd$ has to be one of that. And if we know one of the factors of $N$, everything else follows trivially.

Also note that "a and b are co-prime" is equivalent to $\gcd(a,b)> 1$ and that this doesn't have to imply $a=k\cdot b$ for some k, because it may also be that $a=pq$ and $b=mp$ which would yield $\gcd(a,b)=p$. For a concrete example consider $a=10$ and $b=15$.


Plain text size limits for AES-GCM mode at 2GB with Sun JCE implementation? The Sun JCE implementation of GCM is hard coded to refuse to encode more than 2 Gb, through the function GaloisCounterMode.checkDataLength() that returns an error message : "SunJCE provider only supports input size up to 2147483647 byte" (the message sounds API generic, but the implementation shows the check is specifically for GCM and some other alg don't have that limitation).

It's documented than GCM has a plain text limit at 64 Gb, but could it be that some of the parameters used in that implementation justify the limit to 2 Gb instead ?
The Bouncy Castle implementation doesn't limit to this size, is this expected ?

Quoting the comment on the limit value:

    // In NIST SP 800-38D, GCM input size is limited to be no longer
    // than (2^36 - 32) bytes. Otherwise, the counter will wrap
    // around and lead to a leak of plaintext.
    // However, given the current GCM spec requirement that recovered
    // text can only be returned after successful tag verification,
    // we are bound by limiting the data size to the size limit of
    // java byte array, e.g. Integer.MAX_VALUE, since all data
    // can only be returned by the doFinal(...) call.
    private static final int MAX_BUF_SIZE = Integer.MAX_VALUE;

In other words, decrypting has to buffer the whole ciphertext (even if you pass to update in pieces) which it does in a Java byte array, and by the long established JVM spec a Java array can't exceed 2^31-1 elements (or available heap space, if less, but you can't generally determine that in advance). This is actually a problem only for decrypting, but they apparently added the check on encrypting so you can't encrypt data and then be unable to decrypt it and thus permanently lose all the data you considered valuable, which some users would consider undesirable. (Although you could work around it using BouncyCastle, which doesn't enforce the 800-36D restriction -- or OpenSSL, ditto, but less easy to use in Java.)

See previous
Encryption of big files in Java with AES/GCM
https://stackoverflow.com/questions/23864440/aes-gcm-implementation-with-authentication-tag-in-java
https://stackoverflow.com/questions/26920906/how-come-putting-the-gcm-authentication-tag-at-the-end-of-a-cipher-stream-require-internal-buffering-


SSL and first step of handshaking When I connect to a secure sever that has is equipped with SSL certificate.

Logically, the first step is the handshake to discuss the cipher suites etc.

However, the very first time my web browser does a DNS request and comes up with the location of the site, and my browser connects to the website even before starting the handshake, is this step secure (encrypted by the public key of the websites web server by getting its public key from the built in keys in the browser) or no?

Update:
What I mean here, what happens the very first thing when I open the browser and type https://randomness.org the very first time my broswer (computer) and the server come in to contact. Is this connection secure?

If we assume that DNS (DNSSEC) and IP (BGP) are well behaved, deployed and used correctly then so far so good. You should be reaching the intended server.

If however there is an adversary between you and this server, then they may interfere with the TLS handshake, including but not limited to altering the chosen ciphersuites and public keys. Any alterations are detectable when we pass the certificate verification, key exchange and authentication steps. However if the client doesn't do all the correct verifications, they may be vulnerable to Moxie's sslstrip tool, which performs various attacks.


Which encryption technique should be adopted to keep the search functionalities? I am in exactly the same situation as described in this post. I must be able to encrypt data from a client workstation then send it to an untrusted server (encrypted at rest), then decrypt it only on the same client workstation. However, the client must be able to continue to do "encrypted" searches based on the cypher text.
AES CBC seems to need a unique IV for each encryption, so I can't use this technique. And all others, CGM, ... and even the asymmetric RSA encryption have the same behavior with a padding which means that the cypher text is never the same for the same plain text ...
It seems that only AES ECB can produce the same cypher text. The important point in my case is that the data that I have to encrypt is all in the format string max 1000 char and also that I have to protect this data from the hoster (at rest), there is no risk the In Transit and the data are not exhibited on the internet. I don't know if I can relay on ECB...
So I ask the question again because 5 years have passed since this post, there may be other options? Can you advise me which technique to use being quite secure and ensuring the non-brute forcing and with which I can continue to search (on cypher text). Can I use AES CBC with the same IV? Can I use AES ECB (256)? Others?
Thank you !

There are two possibilities related to your "search" (partial or exact) and you do not specify which you're using.
Let us imagine the plaintext is ATTACK AT DAWN. Let us suppose that the encryption translates this to QWWQTHXQWXBQNO: each letter is encoded as a different letter regardless of its position (so, A is always encrypted as Q and so on). However obtained, this is a Caesar cipher and is weak. But it allows you to simply search for DAWN because it will always be BQNO.
A different cipher scheme (for example the Vernam cipher) would encode each letter as a different letter depending on its position. So to be sure to find DAWN inside a 1000-character string, you would need to look for 997 different strings - DAWN encoded starting at 0, 1, 2,... 996. This is more secure, and even completely secure if you encode one string. If you encode lots of different records, then this devolves into a Vigenère cipher, which can be attacked. The more the records, the easier the attack.
AES would encode each letter into a different letter depending on its position and what the other letters are. This makes it impossible to look for DAWN because you would need to look for a jillion possible sequences (the encrypted version of DAWN in ATTACK AT DAWN would be be different from the DAWN of RETIRE AT DAWN, even if the word starts at the tenth position in each case).
So, use of a strong cipher means you cannot do partial matches but only full matches.
You can very slightly ameliorate this situation by encoding different, shorter chunks and only looking for matches wider than twice a single chunk. With chunks of 2 characters [only an example, AES won't (efficiently) do that], AW will always be encoded as, say, QR. If you look for DAWN, the plaintext string, once divided in 2-char chunks, will either contain ?D AW N? or DA WN. So you look for DA, AW and WN; if you find the encrypted form of AW, either you retrieve the record, decrypt, and do a plaintext search for confirmation, or you need to also look for additional 625 combinations (from AD AW NA to ZD AW NZ). With bytes, that's actually 65025 combinations. And that's with 2-byte chunks; with N byte chunks you'll need (N-1)^2 combinations, which quickly becomes prohibitive.
And, of course, using short chunks over many records weakens the encryption. In general, the ability of using (arbitrarily small) matches leaks information.
different approach #1
You can perhaps filter the records, without breaking the encryption, and restrict the returned records to a reasonable number. Then, have them transmitted in the encrypted form, and decrypted on the client, and searched again for the string. This allows you zero-trusting the server; the plaintext never exists in the server in any form. You could use a stronger encryption on the records, since you're not going to seach the encrypted returned records and you have to decrypt them all anyway.
different approach #2
With some databases (e.g. MySQL), you can have memory storage transient tablespace, or RAM disks, where the information can be stored in plaintext form.
You can decrypt all the information upon user login and store it in a RAM disk or tablespace, thereby rendering it searchable.
When the system is powered off or brought to rest, that information is lost, unless specific physical attacks are carried out (so-called "cold boot" or "cryo" attacks, involving the rapid refrigeration of RAM chips to preserve their content).
This leaves you vulnerable to the host system being subverted, but if the client's code is sent by the host system (as it usually happens in Web applications), a host subversion will be enough to break the encryption by simply accessing the user's credentials on the client side.
You do have, therefore, to (limitedly) "trust" the server, albeit not at rest.
If the server is just data storage, and the client code is not hosted there, then you can't go this way without implicitly adding trust in the server security.


Is there a hash function which has no collisions? Is there a hash function which has no collisions?

To clarify: it would be some function which would produce variable-length output, and never produce the same output for differing input. It would also be computationally hard to derive the input from the output.

Your hypothetical hash function would need to have an output length at least equal to the input length to satisfy your conditions, so it wouldn't be a hash function. See the Pigeonhole principle.

Remember an n-bit hash function is a function from $\{0,1\}^∗$ to $\{0,1\}^n$, no such function can meet both of your conditions. Essentially, if it has length $n$ bits, it can only guarantee uniqueness for inputs up to $n$ bits, and even then it would not be a good PRF as it would be a permutation - which is not what hash functions are - so you would want the output size to be longer than the input size, which is now really far from the definition of a hash function.

Now, if you are willing to call it something else than a hash function, then, yes, it is possible to construct such primitives, under the assumption that the output length must be calculated in a way that if there are $m$ possible inputs for an $n$-bit output, then $m \leq 2^n$. The obvious one is a block cipher, which satisfies your conditions except that it has the additional property that all outputs have a corresponding input, which may not be what you want.

As you can see, if you don't want a permutation, you are basically left with a function which "expands" the input pseudorandomly, such that all inputs have outputs but not all outputs have inputs. For instance, CodesInChaos's example of $y = g^x \mod{p}$ is collision-free if $|X| \leq p$ where $X$ is the set of inputs to the function and is one-way for sufficiently large prime $p$ (actually, it needs to have a subgroup of large order, generally $p = 2q + 1$ is a common choice for large prime $q$), as you would need to solve the discrete logarithm problem to reverse it.


Question about keyed hash functions Maybe the answer to my question is obvious, but I have doubt...

I have noticed that hash functions are studied in two forms, keyed hash functions or unkeyed. In general, lecture notes present hash function without key.

Is there a key generation algorithm for a keyed hash function?

I think that you may be referring to hash functions with (not secret) keys as presented in any theoretically rigorous text on cryptography. In practice, hash functions do NOT have keys. However, if you try to define collision resistance without keyed hash functions, then it is impossible to achieve. This is because there always exists an adversary who finds a collision (this is an adversary who has a collision hardwired in its code). You may not be able to FIND such an adversary, but they certainly exist. We therefore define hash functions to have keys which are chosen after the adversary is fixed. (See textbooks for more discussion; it's an annoying technicality, but very not trivial.)

There a few ways to bridge this theory and practice. One is to say that the IV in practical hash functions is the key. I like this one, but most people don't (so I'm in the minority). Another is this paper by Rogaway http://web.cs.ucdavis.edu/~rogaway/papers/ignorance.pdf. Anyway, the introduction to that paper will also help explain the problem.


Simple example for CP-ABE (Ciphertext policy attribute-based encryption) I'm currently working on Ciphertext Policy Attribute-Based Encryption (CP-ABE). So far I'm only using it with a basic understanding how it actually works. Now I want to understand it a bit better, but I've never learned anything about bilinear groups or pairing-based cryptography.

To start with I would like to calculate a very simple example on my own. Therefore I'd like to use small numbers and very simple operations (although this definitely won't be secure).

I will just write what I tried to do for the first step (Setup) — would be great if someone could tell me whether it is completely wrong or if it goes in the right direction:

I chose a group generator of $g=7$ and an order of $p=13$. Therefore I got the group $G_0=\{1\ldots12\}$. (Correct so far?)

Then I defined $e(X,Y)=g^{XY}\bmod{}p$

Using this, I can now calculate the Public Key and the Master Key with two random integers $\alpha=3; \beta=4$:

$MK=\{\beta,g^\alpha\}=\{4,7^3\}=\{4,343\bmod13\}=\{4,5\}$

(Still correct?)

$PK=\{G_0,g,h=g^\beta,f=g^{1/\beta},e(g,g)^\alpha\}=\{G_0,7,7^4\bmod13,7^{1/4}\bmod13,7^{7*7*3}\bmod13\}=\{G_0,7,9,??,5\}$

(How can I calculate $7^{1/4}$?)

I hope to be able to do the rest on my own as soon as I understand this part.

I think you have a lack of knowledge on pairings and finite fields. Your definition of the pairing $e(X,Y)=g^{XY} \bmod p$ is not correct.

A pairing is defined as a map $e : \mathbb{G}_1 \times \mathbb{G}_2 \to \mathbb{G}_T$ with the property
\begin{align}\text{for all }g_1 \in \mathbb{G}_1 \text{ and } g_2 \in \mathbb{G}_2: e(g_1^a,g_2^b) = e(g_1,g_2)^{ab}\text{.}\end{align}
For cryptographic usage we also need the properties that the pairing is not degenerated and efficient computable. Your definition of the pairing does not hold all these properties.

Today, pairings are basically implemented with elliptic curves over finite fields ($\mathbb{G}_1$ and $\mathbb{G}_2$) and with an extended finite field ($\mathbb{G}_T$). All the three groups have prime order $p$ so that you can calculate the inverse in the exponent very easily: $g^{1/\beta} = g^{\beta^{-1} \pmod p}$.

I think it is not that easy to generate a toy example for pairing based cryptography, because you need special elliptic curves with known order, embedding degree and other parameters and an efficiently computable pairing function.

If you like to understand pairings better I can recommend the dissertation of Ben Lynn [1]. He also wrote the PBC Library [2] that implements pairings in C and is very easy to use.

[1] https://crypto.stanford.edu/pbc/thesis.html
[2] https://crypto.stanford.edu/pbc/


How much original entropy is lost if a part of the hash is known? You have an entropy source of n bits
You hash it with SHA-512 for example
k bits of the SHA-512 output are publicly revealed, but the SHA-512 hash is also a private key to be protected (k<=512)

The question is how many bits are lost in the original entropy source by revealing/losing k bits in the hash?

Especially: the original entropy source has less entropy than the hash output size. Because if it has more or the same as the hash output then it will be equivallent to 512-k, the question is… what if it's less?

A good hash function like SHA-512 is thought to behave like a random oracle and reveal nothing about it's input, however if the source has less potential entropy (fewer bytes) than the hash output size then this can be exploited as a potential search problem.

If the original source has fewer bytes than the hash output size, and this number of bytes is a computationally feasible search problem (i.e. < 80 bytes) then revealing k bytes of the hash is equivalent to revealing up to k bytes of the input source, since the candidate preimages of the output can be found.

Thinking about the scenario in which fewer bytes of the hash are revealed than there are bytes of entropy in the input source, there will be many inputs which map to the same abbreviated hash output. Ideally however these inputs would be a random distribution from the input source and not reveal any of the source entropy until the hash output size was equal to the input size.

Extending this idea further it's obvious that something about the input entropy is revealed, since as the number of bytes revealed approaches the number of bytes input the number of possible preimages is reduced which reduces the entropy until the stage that there is none and we have (ideally) only one preimage.

I modelled this and found experimentally that for SHA512 the amount of entropy about the input which is lost for each byte of the hash function output known is approximately (ideally) one byte. This makes sense in the context of the definition of a cryptographic hash algorithm.

e.g.

Input value with 6 nibbles of potential entropy: $9840563$

First 6 SHA512 nibbles: $8ae967$

$8: 1049140 \approx 2^{20}$

$8a: 65275 \approx 2^{16}$

$8ae: 4099 \approx 2^{12}$

$8ae9: 270 \approx 2^{8}$

$8ae96: 13 \approx 2^{4}$

$8ae967: 1 = 1$


Why does FIPS 186-4 require specific sizes for keys? In FIPS 186-4, page 32, about FFC crypto it is required that the length of $p$ will be exactly 1024 bit and the length of $q$ will be exactly 160 bit. Why is the requirement not stated in terms of lower bounds?

For instance, any $p$ with length greater than 1024 bit would be good, and any $q$ with length greater than 160 bit would be good. For instance, if $q$ is 170 bit, would that harm security?

I don't remember whether there is an official NIST publication on the topic, but there are definitely advantages to having a small set of possible key sizes. Contrasting RSA and DSA is instructive in this respect. A 170-bit $q$ wouldn't be less secure than a 160-bit $q$ if implemented correctly, but offering the choice is less secure.

Security strength

The lack of guidance on choosing an RSA key size has led to some users picking insecurely low sizes, or occasionally, conversely, needlessly high (and thus slow) sizes. The original DSA standard (FIPS 186-1) allowed a range of $p$ sizes from 512 to 1024; the current version imposes the higher end of the range and does not allow going further. NIST now publishes a list of correspondence between key size and security strength in SP 800-57.

Interoperability

When an algorithm may be instantiated with different key sizes, interoperability requires that all cooperating implementations support compatible key sizes. For example, with a signature algorithm, all verifies must support key sizes that are generated by any signer. This means additional implementation complexity (never a good thing for security, and a pain for implementers anyway) imposed on everyone. This also means that communication protocols may need an extra step to negociate key sizes, which is both extra overhead and a risk of security downgrade if one party is malicious (or due to a man-in-the-middle, but that would mean the protocol is flawed).

Implementation flaws

Allowing variable key sizes means additional implementation complexity, and more complexity means more risk of bugs. FIPS 186-1 already restricted $p$ sizes to a multiple of 32, the word size on many machines, to avoid bugs that were not all that uncommon with RSA implementations in computing the size of intermediate values, the memory requirements, etc. For example, there have been (and probably still are) RSA implementations that don't produce the expected modulus size when that expected size is odd, or that calculate the byte size from the word size by dividing by 4 and rounding down instead of up; DSA is not prone to these particular bugs.

Testing

Given the risk of bugs, every size must be tested, or at least a sufficient sample. Testing every RSA size, for example, is impractical. Testing schemes generally require testing an algorithm at each size they will be used for. This is again extra work which is not required if there is a single standard size.


Key management protocol for end-to-end security on Advanced Metering Infrastructure I am currently working on a research on end-to-end security implementation for Advanced Metering Infrastructure (AMI). Pardon me if I a bit off topic or not asking the right question as I am relatively new in the cryptography field and hope to get more information.

So basically I am to research on implementing security for smart grid system ensuring data integrity, authenticity as well as confidentiality for AMI when message is passed from the smart meters, to a concentrator where it computes and aggregate data received and finally sent to the utility end. One important consideration is that smart meters have limited processing power. As such, the cryptography algorithm should not have a large processing overhead in this case.

So right now I have this in mind after some research and reading relevant literature:

A shared master key across all the devices.
Smart meters authenticate themselves using this master key together with their unique ID.
After which this master key will be used to generate a session key for secure transmission.
Using HMAC and related algorithm to sign data and transmit to concentrator. Concentrator perform checking base on the HMAC received. If integrity is verified, it is then send to the utility.

The usage of a symmetric key (master key) is to ensure that there will be lesser computation as compared to any asymmetric design.

In distributed systems it is often bad practice to have "Shared Master Key". If a bad guy breaks in one of your devices he has the most important crypto piece of the system, and you're pretty much done. Rather have one key per device, and these keys are signed by an Authority I would say.


Should I delete cryptographic data from memory? When dealing with cryptographic data, is there a chance that attacker recovers portion of data I used in my program? Should I try to delete every bit of keys and encrypted data that I used, overwrite it with zeroes?

And one extra, how is situation different in languages with garbage collection like Python or Java?

The book Cryptography Engineering devotes part of a chapter to this topic. Overwriting sensitive data with zeroes is a good start, but there are lots of other considerations.

If you rely on a language's default object destruction behavior to zero the memory, it's possible for an unexpected error to prematurely halt the program's execution without it cleaning up after itself. In Java, exception handling can discard object references without cleaning up the objects themselves. [Not sure if this is still the case]
Sometimes compilers will optimize away the code used to overwrite the memory because it's acting on a piece of memory with no other uses in the program. There are a few ways to trick the compiler into not performing this "dead store elimination".
OS memory management can foil your attempts to delete data by paging it to the system's hard disk. There are ways of preventing this but they are language- and platform-specific.
If the OS does a context switch the values in the registers are stored elsewhere in memory until execution resumes. This can cause sensitive data to end up in strange places. Modern processors also have multiple caches where sensitive data can be held.
In languages where memory management is automatic it's even more difficult to know where exactly in the system your allocated memory is (and for how long). In Java, objects all live on the heap and are reference-counted as a part of garbage collection. When there are no more references to the object, it can be deleted by the next pass of the garbage collector. However, short of calling System.gc() there's no way of knowing when garbage collection will occur. And even if you force garbage collection it still might not execute immediately. This SO question talks a little bit about System.gc behavior.
Cold boot attacks happen when keys are always written to the same physical region of a computer's memory. Over time, the electromagnetic forces can cause the memory to retain a state after the power is shut off.

This probably isn't all in scope for your application, but it should give you a good idea of the capabilities of an attacker with physical system access. The most important thing you can do is know your language and platform very, very well. For further reading, this Wikipedia article should give you a good start.


How much entropy do you need for a secure certificate generation? So in OpenSSL you have the -engine tag for inputting your own entropy as a source for generating whatever.

So if you wanted to generate a 2048-bit RSA certificate how much entropy would you need for it to be secure?
Is 1 truly random byte or even one bit of entropy enough for generating a secure certificate?
Do you need more entropy for bigger certificates?
Is the entropy used raw or is it mixed with something else (in the case of openssl -engine)?

The answer to "how much entropy" is always "128 bits".

The tricky point is that the term "entropy" is very often misused. In general terms, the situation is the following:

A computer is a deterministic machine. From knowledge of its complete state (contents of disk, RAM and CPU registers) at a time $T$, one can compute its behaviour and state at any time $T' > T$, as long as no new unknown information is injected. Conceptually, this is about simulating the machine.
The attacker's goal is to try to recover the state at the time of key generation, in order to be able to simulate the key generation process and thus obtain the private key. However, the attacker does not know everything about the state, so he will have to "guess", i.e. to try possible values for the information he lacks. This is known as "brute force".
"That which the attacker does not know" can be quantified into the notion of "entropy": we will say that the state has an entropy of $n$ bits if the best possible brute force strategy will require, on average, $2^{n-1}$ tries before hitting the right one.

Note that this notion does not require that the unknown information is exactly a sequence of uniformly random bits. The definition is such that if the attacker knows everything except $n$ bits, which are (from the point of view of the attacker) exactly random, uniform, and independent of each other, then the entropy is $n$ bits. In a more practical setup, the "entropy bits" come from measures of physical events (e.g. precise timing of interrupts originating from the hardware); these measure will be encoded over a lot more than $n$ bits. This is not that much a problem since we can always somehow "concentrate" entropy bits by hashing all them together.

If the attacker-unknown data is a single byte, then the attacker will just have to try at most $256$ possible values (and on average $128$) to recover the private key. This is the same as saying that 8 bits cannot contain more than 8 bits of entropy (and may contain less if the attacker has some partial knowledge of the byte, e.g. he knows whether some values are more probable than other).

The amount of needed entropy is basically: "enough to make brute force stupidly expensive". "128 bits" are the traditional value for "way too much" (it's the new tradition; twenty years ago, we would have used 80 bits, but the relentless advances in technology and economics make an $2^{80}$ computation task less ludicrous than what it used to be). If your private key is generated with a cryptographically secure PRNG which is itself seeded with attacker-unknown data that cumulate at least 128 bits of entropy, then, by definition, brute-forcing that entropy is unfeasible (the attacker won't be able to try more than a negligibly small fraction of the space of possible values), and the job is done.

Note that an attacker gets to choose between trying to brute-force the generation seed, and trying to unravel the private key from the public key using its mathematical structure (e.g. trying to factorize the modulus, in the case of RSA keys). He will use the strategy that is easiest for him. In that sense, you "just" need enough entropy to make mathematical breaks easier than PRNG seed brute-force. In practice you inject enough entropy to make brute-forcing unfeasible, and you use asymmetric keys such that mathematically breaking them is not feasible either (e.g. with RSA, use 2048 bits or more).

Some people argue that if quantum computers ever come to fruition, then, in some sense (and with a lot of usually unspoken caveats), an attacker with a quantum computer could quantum-brute-force an $n$-bit PRNG seed with cost $2^{n/2}$ only (with a variant of Grover's algorithm); thus, "256 bits" would be needed to protect against that. On the other hand, a working quantum computer would break through the mathematics of a RSA, DSA, DH or elliptic curve key with extreme efficiency, making the point moot: as long as you use RSA, you are making the bet that quantum computers do not exist (and, for now, this is not that bad a bet).


How do we arrive to the equation for solving D in RSA? We have been shown that DE is congruent to 1 mod phi(n). How do we arrive to the real equation for figuring out d that is d = e^-1 mod phi(n). I want to know the entire process. I am just curious, spending the night studying the workings of the RSA.

Are you asking "given $e$ and $\phi(n)$, how do we find $d$ such that $de \equiv 1 \bmod \phi(n)$"? (which can also be written as $d = e^{-1} \bmod \phi(n)$

The standard way of find such a value is the Extended Euclidean Method; this is a relatively efficient method that results in $d$ given $e$ and $\phi(n)$ as inputs (assuming, of course, that $e$ and $\phi(n)$ are relatively prime; if they aren't, $e$ won't work as a public exponent anyways).

Now,I do have one minor nit which doesn't have anything to do with your actual question: actually, if $d$ and $e$ are RSA private/public exponents, it's not always true that $de \equiv 1 \bmod \phi(n)$.  Now, such a $d$ and $e$ that satisfies that condition will work as RSA private/public exponents (and hence if you are constructing an RSA private/public keypair, using $\phi(n)$ won't break anything).

However it turns out that the weaker condition $de \equiv 1 \bmod \lambda(n)$ where $\lambda(n) = lcm(p-1, q-1)$ turns out to be both necessary and sufficient.  This does not affect your question (because you end up giving $e$ and $\lambda(n)$ to the Extended Euclidean Method). You did mention that you were studying RSA; you should be aware of that.


PRF proof and length-preserving I'm studying for my crypto exam and got stuck on following example:
Is $F'_k(x) = F_k(0||x)||F_k(1||x)$ with $x \in \{0,1\}^{n-1}$ a PseudoRandom Function PRF, under the assumption, that $F_k$ is a PRF?
In the solution, there is a reduction proof stating, that $F_k'$ is a PRF. What gets me confused is the definition for PRF, which states, that $F:\{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$ has to be an efficient, length-preserving, keyed function, in order to be a PRF. In my opinion $F'_k(x)$ is not length-preserving and can therefore not be an PRF. Can someone explain this to me?
(here || denotes concatenation)

A PRF does not have to be length-preserving. We sometimes define it that way for simplicity. In general, $F:\{0,1\}^n \times \{0,1\}^{\ell_1(n)} \rightarrow \{0,1\}^{\ell_2(n)}$ for polynomials $\ell_1,\ell_2$.


What kind of RSA is this? I'm currently trying to write a server emulator for a multiplayer game. I've found what I believe to be the RSA keys. I've found that by editing them I can get the real login server to reject them saying they are corrupt, IE. not encrypted properly. So from that I can confirm they are the correct keys. However, I can't figure out how to generate my own because they are a little weird.

The modulus is 511 bits long and the exponent is 128.
Does this mean they are a 512-bit RSA key? When I generate my own, my public keys exponent is much smaller at only 17 bits long. How can I create my own key pair that is this strange size?

Sorry if this is a bad question, I am new to this.

Does this mean they are a 512-bit RSA key?

No, this means they're using a 511-bit RSA key. A 511-bit key is for all security-related aspects essentially the same as a 512-bit key, but well, technically it isn't.

  When I generate my own, my public keys exponent is much smaller at
  only 17 bits long.

The implementation you used to generate the keys probably picked the standard exponent which is $e=65537=2^{16}+1$, whereas the developers of the key in question probably rolled their own key generation and just generated a random 128-bit exponent, which is valid, albeit quite slow.

  How can I create my own key pair that is this strange size?

What they have likely done is they sampled two primes $p,q$ that satisfy $2^{255}\leq p,q<2^{256}$ and got two primes which are closer to $2^{255}$ than to $2^{256}$ which results in their product only taking up 511 instead of the expected 512 bits. One small scale example for this would be $17$ and $19$ which when multiplied yield $323$, the latter taking only 9 bits to represent and the former two both taking 5 bits each to represent.

What you can now do is to either just break the key-pair they used by factoring their modulus, which would cost about 50-100USD on Amazon's AWS EC2 these days, this may be illegal though. Or you could just instruct your implementation to generate 511 bit keys if you really want to, which should work, otherwise you'll probably have to generate your own primes and just try 256-bit primes until you get a pair that yields a 511-bit product and then do the RSA key generation math, it's no that hard and I think the Java standard library has helper functions for that. Using this way you can also just pick a 128-bit public key. But note that depending on how you implement the prime search the private key may be easily factorable, but then this may not matter to you.


Hardness of CDH in different groups What is the difference of the CDH problem in different groups? In particular, given a group $\mathbb{G}_1$ of order $q$ that is a subgroup of $\mathbb{Z}_q^*$, $q$ prime, and another group $\mathbb{G}_2$ of order $p$ that is a subgroup of $\mathbb{Z}_p^*$, $p = 2^n$, is solving the discrete log problem easier or harder in one or the other?

If a prime $q$ is large enough discrete logs and CDH in $\mathbb{Z}_q$ are traditional hard problems in cryptography.

Your other example $\mathbb{Z}_{2^n}$ is typically easy to solve because it can be solved progressively modulo increasing powers of $2$.

May be you intended to consider the finite field with $2^n$ elements $\mathbb{F}_{2^n}$ and not numbers modulo $2^n$.
If so, you might be interested be this related question: How robust is discrete logarithm in $GF(2^n)$?


How to handle the extra 12451 elements in Sophie-Germain Counter Mode? In Sophie-Germain Counter Mode (SGCM), the $GF(2^{128})$ field multiplication of Galois Counter Mode (GCM) is replaced with normal multiplication $\bmod 2^{128}+12451$.  Because the block size is 128 bits, the extra 12451 elements of the group do not fit in the output.

The SGCM defining document says the following about the extra elements:

  Should the value be equal to $2^{128}$ or larger and hence require more than 16 bytes of storage, the result should be truncated $\bmod 2^{128}$.

That is fine, due to the extremely small probability of wrapping, but there are other parts of the document that aren't straightforward.

The value of the multiplier/start point $H = E_k(0)+2$ prevents the pathological cases $H = 0$ and $H = 1$.  ($H = -1$ is also prevented by the construction because $E_k(0)$ is too small.)  But if $E_k(0)+2$ is either $2^{128}$ or $2^{128}+1$, what is supposed to happen to the math?  Is supporting multiplying by a 129-bit number required to handle this case?

I was considering supporting both GCM and SGCM in a client-server application, with SGCM being used when the client is run on a machine without x86 pclmulqdq / ARM pmull.  I don't think there are security considerations about supporting both based on the client's choice.

Should the value be equal to $2^{128}$ or larger and hence require more than 16 bytes of storage, the result should be truncated $\mod 2^{128}$

Note that this talks about the final tag value $Y_n$.  Truncating the final value will reduce security, but only slightly (e.g. possibly doubling the success probability of a forgery attempt, which is tiny even with a doubling).

Truncating intermediate values could potentially greatly increase the potential for forgeries.  At the very least, if you modify the proof giving a bound on the forgery probability, that bound will turn out to be 1 of a long (e.g. 2kbyte or longer) message.  I'm not certain how one could construct such a forgery, but the entire point of (S)GCM is that there is provably no high probability method.

  Is supporting multiplying by a 129-bit number required to handle this case?

Yup.

As an alternative, you might want to look up the Carter Wegman Counter mode; that is similar to SGCM, but uses the field $GF(2^{127}-1)$ (and divides the message into 15 byte blocks for the authentication pass).


Determining if at least 1 bit is set in the output of SHA256 Given the SHA256 hashing algorithm, is there any shortcut to determine whether 1 bit will be set in the output in a given position (or set of positions)? Relaxing the question a little bit, is there any probabilistic test (simpler than performing a full hash of course) to tell if a bit will be set (with probability 1) or not set (with probability <1)?

No, the output of the hash is indistinguishable from random. If there was a shortcut to determine the value of an output bit given a certain input (other than executing the hash) then the hash would be broken.


Concrete Example of AND Gate Using Garbled Circuit Most of the resources online like the wiki presents the beautiful idea of Garbled circuit in a rather unnecessarily abstract manner. This is the screenshot of Wiki's protocol:

What would be an example of step 2? How does Alice garbles the circuit? Using any public-key crypto or private? Could anyone please give me a concrete example of any gate, say AND using this primitive? Like, at the bitstring level. For example, let's say Alice has bit $0$, Bob has bit $1$. They would like to compute the AND. Thanks!

The main conceptual idea behind garbling is to "label" Boolean values on wires in the circuit with keys of a (symmetric key) encryption scheme.
Computations are then done in terms of these labels, instead of the underlying Boolean values. Throughout the rest of this, I will use $\mathsf{in}_0, \mathsf{in}_1, \mathsf{out}$ to denote the two input wires of the AND gate, and the (single) output wire.
If we view these as directly taking Boolean values, these satisfy the equation:

$$\mathsf{in}_0\land \mathsf{in}_1 = \mathsf{out}$$
In particular, given $\mathsf{in}_0, \mathsf{in}_1$, we can compute $\mathsf{out}$ using this formula.

One way to make this computation "private" would be if instead of directly having $\mathsf{in}_i$ and $\mathsf{out}$ take Boolean values, we "obfuscate" things somewhat.
Generate the keys $k_{\mathsf{in}_0, 0}, k_{\mathsf{in}_0, 1}, k_{\mathsf{in}_1, 0}, k_{\mathsf{in}_1, 1}, k_{\mathsf{out}, 0}, k_{\mathsf{out}, 1}$.
Note that there are precisely 6 keys --- for each of the (three) wires in the circuit, we generate a key for each of the possible values the wire can take.

Now if someone gives me two keys $k_{\mathsf{in}_0, i}, k_{\mathsf{in}_1, j}$, I don't know what the "values" underlying the keys $i$ and $j$ are.
But I also don't know how to compute the AND of the keys, meaning I can't yet compute $k_{\mathsf{out}, i\land j}$.
If I could somehow (without learning the values $i$ and $j$ directly) we'd be done.

Garbling allows us to do this by computing the four ciphertexts $C_{i, j} = \mathsf{Enc}_{k_{\mathsf{in}_0, i}}(\mathsf{Enc}_{k_{\mathsf{in}_1, j}}(k_{\mathsf{out}, i\land j}))$.
If we know both keys $k_{\mathsf{in}_0, i}$ and $k_{\mathsf{in}_1, j}$, we can decrypt the ciphertext $C_{i, j}$ to learn $k_{\mathsf{out}, i\land j}$.
But if I don't know those keys, by the security of the underling encryption scheme I cannot decrypt $C_{i, j}$, keeping "the rest" of the possible computations "private".

So Alice's job (in the garbling step) is to generate all of the above information:

Two keys for each wire in the circuit.
$2k$ ciphertexts for each $k$-arity gate in the circuit.

This process is called "garbling" the circuit.


Can iterated key expansion in Blowfish slow down bruteforce attacks on small key sizes? Suppose I have to use 64-bit keys for encryption (e.g. to comply with export restrictions). For this question, assume this key is truly random, and the encryption algorithm is Blowfish.

Blowfish key schedule expands this 8-byte key into 4168 bytes of state (P-array and S-boxes). Will it slow down bruteforce attacks if I run this expansion a huge number of rounds?

REPEAT rounds
   state := ExpandKey(state, key)
END

(Basically, the scheme is similar to bcrypt if you throw away salt and instead of encrypting a constant to derive a key, use the final state for actual encryption.)

Are there any other practical attacks on such schemes faster than brute force?

Something similar as what you suggest is already known as "Expensive key schedule Blowfish", or "EksBlowfish". It is the encryption algorithm in the core of Bcrypt (a slow hash function designed for password hashing).

It also incorporates a salt, and its setup function is like this (retyped from the paper):

EksBlowfishSetup(cost, salt, key):
   state ← initState()
   state ← ExpandKey(state, salt, key)
   repeat(2^cost):
      state ← ExpandKey(state, 0, salt)
      state ← ExpandKey(state, 0, key)
   return state

InitState() is the same as in Blowfish: It fills the P- and S-boxes with digits of $\pi$.
ExpandKey(state, 0, ...) also works just like the key expansion function of Blowfish - it XORs the P-boxes with (a repeated version of) the key, then encrypts a zero stream in CBC-mode with Blowfish (using the existing state), replacing the boxes with the results after each block is encrypted. The version with a salt parameter simply uses this salt (repeated) as the original value to encrypt.

The actual encryption of EksBlowfish works just like normal Blowfish encryption. In Bcrypt, this is then used to encrypt (64 times in ECB-mode) the 3-block ASCII-string OrpheanBeholderScryDoubt to produce the bcrypt hash, but you can use EksBlowfish also separately.

It can't get worse than "normal" Blowfish, and will get as hard to bruteforce as a bcrypted password with same cost factor.
I suppose you could use a constant salt, but using some random (but not secret) salt delivered with the message looks better (and avoids precomputation). If your performance is critical, you should of course not change the salt with every SSL packet.

There is another problem with Blowfish: It only has 64-bit blocks, and as such can't get more secure than any 64-bit block cipher. Repeating blocks will occur likely after $2^{32}$ blocks (i.e. 32 GB), which might be enough or not, depending on your application. And repeated blocks give points of attack.

You might consider instead using a 128-bit block cipher like AES, and derive your key with bcrypt from the "short" 64-bit key.


Security implications of public nonce I'm planning to use the crypto_box() functions of Nacl (or, alternatively, the crypto_box_easy() functions of libsodium) to encrypt messages as part of a client/server protocol. The server has to deal with multiple clients and each message from a client to the server is encrypted using the public key of the server and signed with the private key of the client.

The cypto_box() functions also require me to provide a nonce. The current message number could be used as a nonce–to my understanding, the nonce is necessarily known to an attacker who is capable of keeping track of how many messages were exchanged. Both, the client and server would then maintain a message counter and simply use the newest counter value as a nonce.

However, I must deal with the case where messages are reordered or lost. Therefore I'd send the nonce in plaintext alongside the encrypted message. As long as the same nonce is not used twice, I don't see any problems with this approach. Did I miss out on something?

The only requirement posed to the nonce in the "Security Model" paragraph of the crypto_box documentation is uniqueness for each pair of communicating parties. In fact, the documentation explicitly recommends incrementing nonces starting from zero (which an attacker could easily brute-force) or random nonces (which need to be transmitted together with the ciphertext anyway).

Therefore, sending the nonce publicly should be secure (unless some underlying primitive is broken, of course).


What's the difference between these hash functions H, H1 and H2? These are hash functions, but I don't understand their notations, can anyone tell me what's the difference between H, H1 and H2?
$\mathbb{G}_1$ is an additive group and $\mathbb{G}_2$ is a multiplicative group. Both groups have the same prime order p and their bilinear mapping is $e: \mathbb{G}_1 \times \mathbb{G}_1 \to \mathbb{G}_2$
Source:https://www.cs.nmsu.edu/~misra/papers/T-ITS-2011.pdf
\begin{align}
H&:   \mathbb G_1\to\{0,1\}^n\\
H_1&:  \mathbb G_2\to\{0,1\}^n\\
H_2&:  \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n
\end{align}

The notation $H:\mathbb G_1\to\{0,1\}^n$ means that $H$ takes as input an element of $\mathbb G_1$, and produces as output an $n$-bit bistring.
The notation $H_1:\mathbb G_2\to\{0,1\}^n$ similarly means that $H_1$ takes as input an element of $\mathbb G_2$, and produces as output an $n$-bit bistring.
The notation $H_2:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ means that $H_2$ takes as input a pair of $n$-bit bistrings, and produces as output an $n$-bit bistring.
If you ask me, the names are not well chosen. It would be more mnemonic to use $H_1$ (resp. $H_2$, $H$) where there's $H$ (resp $H_1$, $H_2$).
But that's far from the worse there is in this paper. Things like

The ECDLP had been proved to be a hard problem [19].

are wrong (what's cited to support this falsehood actually makes ECDLP tractable on some curves). I hope studying this paper was not recommended as part of a course in cryptography. If so, I fear there's something deeply flawed in this recommendation process.

Addition per comment: I do not see that the authors explain how they build their hashes, except for a mention of SHA-1 in section VI. A reasonable implementation with $n=160$ based on SHA-1 could use
$$\begin{align}
H(g)&\underset{\text{def}}=\operatorname{SHA-1}(c_0\mathbin\|\hat g)\\
H_1(g)&\underset{\text{def}}=\operatorname{SHA-1}(c_1\mathbin\|\hat g)\\
H_2(u,v)&\underset{\text{def}}=\operatorname{SHA-1}(c_2\mathbin\|u\mathbin\|v)\end{align}$$
where $\hat g$ is a bitstring uniquely representing (as a fixed number of bits) an element $g$ of $\mathbb G_1$ or $\mathbb G_2$, and $c_0$, $c_1$, $c_2$ are public distinct 32-bit bitstrings tasked with making the three hash functions somewhat independent from the perspective of security analysys.
Note: SHA-256 or better should be used rather than SHA-1, which is obsolete and quite practically broken as a collision-resistant hash when operating on messages sizably larger than 768-bit. But as far as we know, SHA-1 remains 80-bit secure in the above constructions, because what's hashed is short.
Note: This shall not be construed as an endorsement of the article. I do not understand enough about functional requirements of a Pseudonymous Authentication-Based Conditional Privacy Protocol for VANETs to tell if they are met by the cryptography outlined; and only understand some of the crypto involved. The article does not tell enough to convince a cryptographer about the security of the implementation. In particular, I have doubt that the BLS signature based on "the Type-A curve defined in the PBC library with the default parameters" could be fast, 154-bit as suggested (the exact size is not stated), and secure to the 80-bit security level targeted.


Guessing the key in AES256-GCM? I assume that my case is weird but I've the following information:

IV: 0x263e or 0x3e26
Auth tag: 0x25
AES256-GCM encrypted payload: 0x4eec96df534ade4c013a
AES256-GCM decrypted payload: 0x0041e36baf2648090174

Regarding the length of the IV and Auth tag, I'm wondering if it is possible to guess the key used to encrypt the payload ?

No.

The short authentication tag makes for high probability of forgery.  But that's not relevant here.

The short nonce limits the number of messages that can safely be encrypted with the same key—indeed, narrowing it down to two possibilities limits it to two messages.  But you have only one message.

What's left is breaking AES.  Good luck!


How 2 rounds in AES achieve full diffusion? I have read somewhere that 2 rounds is AES provide full diffusion. So I looked it up to find out what it exactly meant. In The Design of Rijndael page 41, section 3.5 and it states that:

  Two rounds of Rijndael provide 'full diffusion' in the following sense:
  every state bit depends on all state bits two rounds ago, or a change in
  one state bit is likely to affect half of the state bits after two rounds.

How does that happen. I would say that it's related with the fact that MixColumns is MDS but why this is achieved in two rounds?

AES diffusion is taking cared of by 3 main functions:

SubBytes
Shift Rows
Mix Columns

SubBytes works as a 8-bit S-box. Thus if one bit change, the 8 bits of the byte are likely to change. With this step, each bit of a byte depend of each other.

This modification on the byte is then translated through the state via Shift Rows (still 1 byte affected) and then through the column (we moved from 1 byte affected to 4 bytes affected).

With one round, we therefore impacted on 4 bytes.

By doing it once again we will be affecting $4 \times 4$ bytes or the full state due to the nice coverage provided by Shift Rows and Mix columns.

Thus after 2 rounds, each bit has an influence on the full state.

This could be summarized by the following image where $\star$ represent a modification of a bit (and then byte).


RNG failing Restart Tests by NIST SP800-22? I have data sample of 1,000,000 bytes generated by a hardware RNG. The device is certified by ENT test suite, NIST SP800-22, DIE HARDER and TestU01.

I have tested my sample by SP800-90B_EntropyAssessment (github.com/usnistgov/SP800-90B_EntropyAssessment). Minimum Entropy Estimate is 7.88237 after which I run Restart Tests.

My sample fails at Restart Testing and the program displays

  Validation Failed, No Entropy Estimate Awarded.

“Analysis and Improvement of Entropy Estimators in NIST SP 800-90B“ (PDF) says

  Randomness has three features: unpredictability, unbiasedness and non-repeatability and and the non-repeatability is validated by restart tests.

I want to know if my RNG is failing Restart Tests, does it mean it offers no entropy at all?

The test that fails seems to be the one in 3.1.4 (Restart Tests) of NIST SP 800-90B (2nd Draft), specifically 3.1.4.3 (Sanity Check - Most Common Value in the Rows and Columns), failing at

  546     If F is greater than U, the test fails.

It can not be concluded that a generator that fails this has no entropy at all. It could well be that it has some imperfection, but still outputs a fair amount of entropy, leaving it perfectly usable to seed a CSPRNG.

CAUTION: this test requires 1000 samples obtained by re-starting the source and collecting 1000 symbols. If the question's 106 bytes are generated by the hardware RNG without restarting it, then the test is abused (if it had succeeded that would be meaningless). But such abuse can not be why the test fails.

It is a common event that Output of RNG fails some Randomness Rest. That can occur for any combination of four causes:

Goof in use of Randomness Rest (or collecting Output of RNG, but here that's unlikely given that other tests have passed); like, the format, size.. of Output of RNG is not as expected by Randomness Rest with the parameters used. The possibilities are endless. This is diagnosed as for 3.
Bad luck. All useful randomness tests are expected to have some rate of false alarm, with a certain probability: the P-value, which any good test documents. Here my reading is that it is 1%. Assuming this, and if possible, re-run Randomness Rest with the same parameters, and a few fresh Output of RNG. If the next two tests fail, we can exclude bad luck with high confidence. Otherwise (that is, if some succeed), we can suspect bad luck (or 1.), and we should use a form sequential analysis to decide. As a rough approximation: run another 997 tests, compute the number of tests out of 1000 that failed (which should be in the order of 10), reject bad luck with high confidence if that's more than 27 (still suspect some issue and investigate thoroughly if that's more than 15).
Goof in Randomness Test (either it's implementation, or definition if that's a draft or has otherwise has not stood intense scrutiny). The general method to detect this is to run randomness test against files generated by a simple (thus hopefully correct and acceptably fast) CSPRNG (one is given below). The proportion that fails should be about the documented P-value.
Defective RNG. Conclude this after having eliminated all the rest.

Here is a simple generator of pseudo-random sequence:

// Simple generator of cryptographically secure pseudorandom sequence.
// The 64-bit block cipher TEA is used in CFB mode to encipher
// plaintext consisting of the block number.
#include <stdint.h>
#include <inttypes.h>
#include <stdio.h>

// For a different sequence, change these arbitrary 32-bit constants,
// used as key for the TEA block cipher.
// Note: in David Wheeler and Roger Needham's TEA, each key has 3 other
// equivalents, as the high-order bits of K0/K1 and K2/K3 cancel out.
#define K0 0x7638d4f2
#define K1 0xabe32749
#define K2 0x56b81d0e
#define K3 0x4ed51d62

// output size, multiple of 8
#define OUTPUT_SIZE 1000000

int main(void) {
    uint32_t j, n, s, y=0, z=0;
    for( j=0; j < (OUTPUT_SIZE+7)>>3; ++j ) {
        s = 0;
        n = 32; do { // 32 pairs of rounds
            s += 0x9e3779b9;
            y += ((z<<4)+K0) ^ (z+s) ^ ((z>>5)+K1);
            z += ((y<<4)+K2) ^ (y+s) ^ ((y>>5)+K3);
        } while (--n);
        z ^= j; // CFB; makes short cycles virtually impossible
        // portably format in lowercase hexadecimal
        printf("%08"PRIx32"%08"PRIx32, y, z);
    }
    return 0;
}

// Generates one million octets expressed as two million characters
// in lower-case hexadecimal on standard output; when expressed in
// ASCII as two million octets, their hash per SHA-256 is
// d5b727ef6a9177c897b68085d60a7660f6f6b1dbf09cb7e91fe59da3a66d4e2d


Who uses the RSA BSAFE library? Who uses RSA's BSAFE library?  Does anyone know what products use it, or have any statistics on how many end users use something that is built on BSAFE?

Background: BSAFE is one of the oldest cryptography libraries, and among commercially available cryptographic libraries, it is well-respected.  However, recent news suggests that BSAFE uses Dual_EC_DRBG as its default pseudorandom number generator.  Dual_EC_DRBG, of course, is the algorithm that is suspected to contain a NSA backdoor.  Previously, cryptographers had suggested that probably no one uses Dual_EC_DRBG, so the suspected backdoor probably doesn't have much practical impact; however, this news about the BSAFE library suggests we might want to re-examine that conclusion.  In particular, it is possible that any backdoor in Dual_EC_DRBG backdoor might affect any products which use the RSA BSAFE library, so to assess the impact of this suspected backdoor, it would be helpful to better understand which products use BSAFE, and how many products and how many people rely upon BSAFE for their cryptography.

My question: Who uses RSA BSAFE?  Which products are built on top of RSA BSAFE?  How do I tell who might be affected by this issue?  There's a big difference between an issue that affects a few internal enterprise tools, vs something that affects products used by millions of end users every day -- I'm trying to get a better sense for the degree of the impact of this issue, and to be in a better position to explain to others whether BSAFE's use of Dual_EC_DRBG is a big deal or not.

A lot of companies use BSAFE: for a long time, BSAFE was the most successful supported cryptographic toolkits: it predates the success of open source software, it predates the availability of crypto APIs in operating systems, and it predates the expiration of patents on RSA and public-key cryptography in general. And it's always been a reliable, well-tested, well-documented, portable library from a company that ported it everywhere there was a customer and provided support. So, it garnered a lot of customers. The number of developers using BSAFE has presumably declined as the patents expired, export restrictions relaxed, allowing OS crypto APIs, and open source ate the market, but I'm sure there's still a very large number of products that incorporate BSAFE.


CoAP authentication using DTLS what is the meaning of this notation ??

  AES{Yi, (Yi XOR Ki | nonce1)}

https://tools.ietf.org/html/draft-bhattacharyya-core-coap-lite-auth-00

It is the encryption using the key $Y_i$ of the constructed message.

The message consists of key $K_i$ XOR'ed (bit for bit) with the previous key $Y_i$, followed by ${nonce}_1$.

  where $K_i$ is the
     potential session key if the handshake is successful, '${nonce}_1$' is
     pseudo randomly generated nonce specific to one authentication
     session. Both $K_i$ and ${nonce}_1$ is 128 bit each. Total message size is
     256 bit.


Bruce Schneier, encryption, public keys and digital-signature. In his book "Applied Cryptography" Bruce Schneier, when talking about public key cryptography, says that:

  If the same algorithm is used for both encryption and digital-signature verification there is a possible attack. In these cases, the digital signature operation is the inverse of the encryption operation: Vx = Ex and Sx = DX.

I'm not sure how that is possible, could you further explain what Bruce is proposing here?

Say you ask the holder of the private key to decrypt something that you've encrypted for him. You've however lost the original data. So the holder of the private key decrypts the seemingly random data and returns the result.

Now imagine that instead of a ciphertext you send a message to be signed or a hash over the message to be signed. The holder of the private key will try to decrypt it. However, because $D(x) = S(x)$ what is returned is a valid signature over the message. This could be the case for, for instance, raw RSA.

However, for most encryption algorithms this won't be possible in real life. For instance, raw RSA is insecure, so PKCS#1 padding is used. Not only is PKCS#1 padding different for encryption and signature generation, but remember that we have to unpad for decryption and pad for signature generation.

So it depends on the algorithm used, but for often-used encryption primitives the problem is usually not applicable. Still, it is always preferable to use a different key pair for authentication, signing (or rather, non-repudiation) and encryption.

If you have to create your own protocol for, for instance, homomorphic encryption, where raw primitives are more common then sure, remember Bruce's advice.


Shuffling: Purpose and formal definition To my understanding, shuffling means simply to permute the elements in vector $\mathbf{v}$ pseudorandomly, using a PRP $\pi (\mathrm{seed},\mathbf{v})$. A secure PRP should yield a permutation indistinguishable from a random one.
However, I'd still have 2 questions on this subject:

Is there a more formal definition to shuffling?

What is the purpose of shuffling? Is it simply to misalign power traces for differential power analysis attacks?

In side channel, shuffling makes correlation attacks harder. For example, if you shuffle the 16 AES S-Boxes in the first round each execution, and you target say first S-Box' output in the attack, at any single point in the trace you will see information related directly to that output only on 1/16th of all traces, and in the other 15/16th traces there will be something else, which qualifies as "noise" for the attack.
Note that this countermeasure is rather weak and is mostly considered complimentary to more sound masking countermeasure. Indeed, after taking 16 times more traces (maybe a bit more), the correlation would become noticeable again. While this adds up to the practical attack complexity, it is impossible to achieve exponential complexity increase, as masking allows.


Linear Approximation and Linear Probability of Camellia Sbox In this article,Analysis of Camellia (para 2. Differential and linear cryptanalysis, page 3), it says

  The maximum bias of a linear approximation through one S-box is $2^{-4}$
  , which gives a linear probability of $2^{-6}$

what does this mean? isn't the linear approximation probability $2^{-4}$?

See This Question Too

Let $LP$ be the linear probability (also called "correlation potential"), $Cor$ be the correlation coefficient and $\epsilon$ be the bias of a linear approximation. Then

$LP = Cor^2 = (2\times \epsilon)^2$.

So, if $\epsilon=2^{-4}$, then $LP = ({2\times 2^{-4}})^2=2^{-6}$.

[1] Daemen, J., Rijmen, V.: Probability distributions of correlation and differentials in block ciphers. J. Mathematical Cryptology 1(3), 221–242 (2007). DOI 10.1515/JMC.2007.011. URL http://jda.noekeon.org/JDA_VRI_Stat_2007.pdf


Uses of digital signature in asymmetric cryptography May I know what could be some advantages and disadvantages of doing the below in an asymmetric crypto process. What could be some of its primary and common uses?

Produce a digital signature on the plaintext, encrypt both plaintext and digital signature, and then produce another digital signature on the ciphertext

The outer signature protects the ciphertext against change. If the signature is verified before decryption then the signature can for instance protect the ciphertext against padding oracle attacks, both on the asymmetric encryption as well as the symmetric encryption that is commonly within a hybrid cryptosystem.

The encryption of the plaintext and inner signature of course offers confidentiality of the message (see the last section why the signature itself also needs to be encrypted).

The inner signature protects the integrity of the message after decryption. Obviously the outer signature (over the ciphertext) cannot be used on the plaintext message.

So you would either have to store the ciphertext (which means you'd have to decrypt the message with your private key each time to view the verified contents) or you would loose the ability to verify the plaintext message.

However, if you sign the plaintext message as well then you can still verify the message using the sender's public key even after decryption.

Note that encrypting the inner signature prevents an attacker of retrieving information about the plaintext. If it was directly available then the attacker could verify hashes over possible plaintext using the public key of the sender.

For instance, an attacker could verify that the message is "Yes" or "No" by guessing either message and then verifying the signature.


Plaintext Size Limit for ECIES with AES-128 CBC mode Using the ECIES (Elliptic Curve Integrated Encryption Scheme), is there a limit size of plaintext? (what is the maximum allowed number of bytes to be encrypted with ECIES).

You are using CBC mode in ECIES. In the CBC mode the $i$-th ciphertext is calculated as

$$c_i = E_k(m_i \oplus c_{i-1})$$

where the $c_0=IV$

Now, there is a problem with CBC mode that is if the adversary can see that $c_i = c_j$ for some $i,j$ with $i \neq j$ then they can calculate:

$$m_i \oplus c_{i-1} = m_j \oplus c_{j-1}$$

and by x-oring both sides they can learn

$$m_i \oplus m_j = c_{i-1} \oplus c_{j-1}.$$

This is ciphertext collision and the probability is given by the birthday bound, $\mathcal{O}(\sqrt{2^n})$, where the $n$ is the block size. So it is not advisable to have more than $2^{64}$ blocks. But in practice, you may reduce this into lower sizes to reduce the change of this attack from 50% to your target security level.


How does the Efficient Fully Homomorphic Encryption from (Standard) LWE work? I am interesting to learn the low level implementation of Efficient Fully Homomorphic Encryption from (Standard) LWE and I am wondering if anyone can answer the following questions:

Does the BV scheme work on binary numbers (0,1) or not?
Does the BV scheme encrypt and decrypt each bit separately?
Is there any difference between the original paper of BV andthe updated version in terms of encryption and decryption processes?

The BV scheme presented in the article works for plaintext messages in $GF(2)$ (that is $m$ $\in$ $\{0,1\}$) but can be extended to support encrypting messages that are in $GF(t)$ where $t$ is prime with the modulus $Z_q$.

This means that if you want to encrypt a message in $\{0,1\}^n$ you have to do it for each bit separately in $GF(2)$ (or in $GF(t)$ and the message $m$ $\in \{0,1,...t-1\}^n$)

The BGV scheme instantiated with the LWE problem is the same as in BV.
The main difference in BGV is that the scheme supports a more general context, namely it could be also instantiated with the Ring-LWE problem providing a more efficient circuit (inner operations are done inside a ring $R$ instead from $Z_q$ as in LWE).


Have crypto side-channel attacks happened in the wild? I'm aware of attacks extracting information via timing and volume. But none that care or attack the actual cryptographic algorithm implementation or end up extracting the key.
Seeking examples if any for such attacks which happened outside the lab, Or evidence where we suspect this was the means of attack used.
Any side channel: timing, sound, power, something else?

None that recover the key?

Osvik, Shamir, Tromer, 2006: Recover AES-256 secret key of
Linux’s dmcrypt in just 65 ms
AlFardan, Paterson, 2013: “Lucky13” recovers plaintext of
CBC-mode encryption in pretty much all TLS implementations
Yarom, Falkner, 2014: Attack against RSA-2048 in GnuPG 1.4.13:
“On average, the attack is able to recover 96.7% of the bits of the
secret key by observing a single signature or decryption round.”
Benger, van de Pol, Smart, Yarom, 2014: “reasonable level of
success in recovering the secret key” for OpenSSL ECDSA using
secp256k1 “with as little as 200 signatures”

Those are all examples of timing attacks that were usable in the wild. Also, they're all timing attacks. Nevermind Spectre, Meltdown, and the plethora of other predictive branching vulnerabilities that followed suit.
There's also the RSA "exponent 3" attack (which I may or may not have exploited myself one or 2 times against web servers' TLS certificates)
(edit: The exponent 3 attack isn't really a side-channel attack but it's so hilarious I couldn't resist.)
In short, most timing attacks can be performed in the wild. There was even an issue with Amazon AWS instances that allowed someone to steal encryption keys from other instances simply by creating an AWS free tier account.
The good news is, usually researchers find them before bad actors and there's time to develop a fix before it gets too crazy. But these attacks are very real and usually crippling; both on paper and in practice.
I might suggest reading this document [PDF] which outlines the nature of such attacks in slightly more detail.


HMAC vs PKDBF2 as the first step towards HKDF I'm implementing an application that from a password has to derive two keys, one for authentication with the server, one for encryption. I'm using Java, with JCA and Bouncy Castle.

So far, to generate a key from the password I was using PBKDF2, like this:

SecretKeyFactory secretKeyFactory = SecretKeyFactory.getInstance("PBKDF2WithHmacSHA512", BC);
PBEKeySpec keySpec = new PBEKeySpec(password.toCharArray(), salt, iterations, keyLength);
SecretKey passwordKey = secretKeyFactory.generateSecret(keySpec);

but in the two examples I found of HKDF:

https://github.com/WhisperSystems/libsignal-protocol-java/blob/master/java/src/main/java/org/whispersystems/libsignal/kdf/HKDF.java
https://www.javatips.net/api/keywhiz-master/hkdf/src/main/java/keywhiz/hkdf/Hkdf.java

they start with HmacSHA256, not PBKDF2. Why is that? What are the pros and cons of these two algorithms in this case?

I don't think you get those "examples": they implement HKDF. The full name of HKDF is HMAC-based Extract-and-Expand Key Derivation Function. They do not use PBKDF2 because they don't implement a specific use case, they implement the algorithm.

So it is perfectly fine to use:

master = PBKDF2(SHA-256, iterations, salt, password, 32)
authKey = HKDF(SHA-256, master, "authKey", 32)
encKey = HKDF(SHA-256, master, "encKey", 32)

This is pseudo code where the configuration options such as the hash function and the output size are also present in the parameters.

Note that although the SHA-256 is specified as configuration option, both PBKDF2 and HKDF will use HMAC-SHA-256 underneath (but HMAC has only one configuration option: the hash function to use, so this is equivalent).


Is a transposition cipher categorized as asymmetric algorithm? Consider a simplest transposition cipher, such as one with block size 8 and encryption key 43725681, the decryption key will be 84215637. As the keys are different, may I say a transposition cipher is an asymmetric algorithm, except for some special values of the keys, such as 87654321?

No, it is not an asymmetrical algorithm, becayse the decryption key can be derived from the encrytion key.

Even in a symmetrical algorithm the encryption and decryption algorithms may be different, and the decryption algorithm might include firct calculating a decryption key from the encryption key. However, the same key can be used for both encryption and decryption in the sense that if you know that key you are able to both encrypt and decrypt messages.

In an asymmetrical algorithm, someone who only knows the public key can not decrypt messages. That is not the case for a transposition cipher.


Post-quantum candidates for asymmetric cryptography with small key sizes One of the things that I have come to like about elliptic curve cryptography is that the key only needs to be twice as long as the desired security level. That's a very small expansion (I also like it aesthetically). The sizes for the public key and private key are also the same. Unfortunately, ECC is not secure against quantum algorithms and quantum computers capable of breaking uses of elliptic curves seem to be coming up within a decade or two. What is more is that many post-quantum cryptosystems—the ones I am familiar with, at least—have idiotically huge keys and signatures. The best key sizes seem to be achieved by lattice-based cryptosystems and one variant of code-based cryptography. Are there any candidates with smaller key and signature sizes? Any as small 10 times larger than the desired security level? Any as small as ECC ones?

It appears that SIDH, or Supersingular Isogeny Diffie-Hellman, is the post-quantum candidate with the smallest key size. When using compression, public key size can be reduced to 330 bytes (2640 bits) to achieve the 128-bit security level. For classical Diffie-Hellman, this value is often quoted at 3072 bits. From the above-linked paper describing the attractiveness of the small public key size of SIDH:

  Not only are high-security SIDH public keys smaller than their lattice- and code-based counterparts, they are even smaller than some of the traditional (i.e., finite field) Diffie-Hellman public keys.

The SIDH-based public key encryption and key encapsulation scheme submitted to the NIST post-quantum cryptography process is called SIKE, for Supersingular Isogeny Key Exchange, and specifies parameters called SIKEp503 to obtain a 378-byte (3024-bit) public key for the 128-bit security target.


How to get the same calculation result on an untrusted computer, while withholding some information? Consider this command on a trusted computer:

result = function(public data, secret data)
or shorter: r = f(p,s).

How could a function on an untrusted computer produce the same result without the secret data being available to the untrusted computer?

Abstract example:

r = f(p, s) = f'(p1, p2, ... pn)
such that one or more of the public p variables are derived in some fashion from s.

Concrete example:

p is a database table, r is a record and s is a lookup criteria. The database server is untrusted.

The term you are looking for is homomorphic encryption. This allows you to evaluate a general circuit (so no branches) on encrypted data without knowing the decryption key.

It works in theory, but to my knowledge no practical applications have been developed yet. They are either incomplete (only allowing addition, XOR, or some other operation) or impractically slow (decrypting costs more time than the actual computation).


Does re-iterate AES-128 with different keys gives any benefict? I'm not cryptography expert but I have this doubt…

Suppose I have 2 different keys:

secretkey1
secretkey2

And a plain text:

myReallySecretPlainText

If I use AES-128 on my plain text with my first key I get this:

U2FsdGVkX19fHxumDqEB9Kuyvhj+aoHpctLCdo2VEvt1danATMo+sBaz3nsCaS/Z

now, if I use on this cipher text my second key I got this:

U2FsdGVkX1/AqJ3w8nTRAHvm1ZbDTdwmq7LTVBDR/z4O9ngaXGuAIqcqTzPj+flPRIV6++twqBnIEHgUVVe7oO1D75VO14ezRX5tqcjBTPUUtr7YDqCks5ZW7fX8crqg

Looks pretty safe, but I have a doubt: does this have the same security of a AES-256? Or does it have the security equivalent to a single 128 bit key?

The idea you describe is vulnerable to a meet-in-the-middle attack that work in approximately $2^{128}$ time and $2^{128}$ memory. The attack assumes knowledge of plaintext/ciphertext pair(s). Given a pair, you encrypt the plaintext with every possible key 1 and store those values. You then decrypt the ciphertext with every possible key 2 and look for a match between the two datasets. Say you find that $E_{k_1}(P)=D_{k_2}(C)$. Likely these are your two keys. This can be validated by looking at additional plaintext/ciphertext pairs.

As codesinchaos says, the attack may not necessarily be applicable with realistic cost models, but it is a theoretical break and is therefore considered weaker than just using a larger key space in the first place. Also, I've got to believe that this idea is slower than just using AES-256.


Curve parameter for hyperelliptic curve cryptography? RFC5639 defines some curve parameter for Elliptic curve cryptography.

Aren't there any curve parameter database for Hyperelliptic curve cryptography? What I can only find was that written in this PDF.

There is no database of hyperelliptic curve parameters because their use is not sufficiently popular. This is because the topic is too new and the advantage of faster calculations doesn't outweigh the disadvantages of novelty and lack of reference implementations.

Another aspect is that with modern computers and algorithms, anyone seriously looking at implementing hyperelliptic curve cryptography can easily generate their own parameters. Contrast this with the early days of elliptic curve cryptography where finding (let's say) a twist-secure prime-order curve of a decent size was a significant computational task.

As soon as hyperelliptic cryptography becomes popular then there will be databases of parameters to ensure interoperability between different implementations. However, I don't anticipate this will happen for a long time because groups of points on elliptic curves are a sufficiently good improvement over groups of integers for cryptographic purposes.

The slides you link to and their paper on the eprint archive are excellent and you should be able to use their parameters with some confidence.


Differential Privacy and appropriate noise distribution In differential privacy solutions and more specifically for queries that they do entail counting the proposed solutions define the Laplace distribution that is best calibrated for low error. Other solutions for non-numerical queries propose exponential distribution. However, it is not clear why noise from a Laplace distribution is chosen for numerical? What is the special property that best suits the Laplace distributrion?

In order to bridge the gap between two worst case scenarios to produce similar distribution of privatized answers certain noise is added. For example the salaries of a CEO (max) and a line worker or who ever gets minimum wage (min) may not be produce similar distribution without the noise.

Random values taken from Laplacian distribution with standard deviation is large enough to cover the gap.

This link has a good beginners tutorial with detailed explanation. Around 15.33 minutes in the video the speaker discusses about the issues like Global Sensitivity and Laplacian Noise.  Subsequently she discusses the proof too.


Why was the winner of the AES competition not a Feistel cipher? The winner of the AES competition has a structure that does not qualify as a Feistel cipher, as explained in answers to this recent question.

However, most many of the AES candidates, and all 3 out of 4 some other finalists (Twofish, MARS) are Feistel ciphers, if we define that as a cipher transforming a block of data using a number of rounds which each can be expressed as:

split all the bits of the block $B_j$ into two disjoint portions $L_j$ and $R_j$ (typically of equal size);
compute some (typically round-dependent) function of $R_j$ and key with output $F_j$ of same width as $L_j$;
compute  $L_j'=L_j\oplus F_j$ where $\oplus$ is binary addition with removal of some carry bits (e.g. exclusive-OR, where all carry bits are removed);
recombine bits of $L_j'$ and the unmodified $R_j$ into a new block $B_{j+1}$.

Note: Serpent and RC6 can not be put in this framework (thanks to @Reid and @J.D. for pointing that). Neither can Rijndael/AES.

At the time of the AES competition, Feistel ciphers already enjoyed a well understood theory. In particular DES was among them, and essentially unbroken in practice except for its small key and block size. It would seem that proposing anything else than a Feistel cipher would be an uphill battle.

Yet, Rijndael won the AES competion, and does not fall under the above definition. Did a desirable characteristic of Rijndael made it preferred to the other candidates despite the apparent drawback of using a relatively untested structure? And if that characteristic could not be matched by a Feistel cipher, why?

DES actually demonstrated that a Feistel structure was not a guarantee against attacks. In "academic" terms, DES is broken by both differential and linear cryptanalysis, because they require, respectively, $2^{47}$ chosen plaintexts and $2^{43}$ known plaintexts, whereas the DES key is (effectively) 56 bits. Of course, for practical attacks, we would brute force the key: computing the function $2^k$ times is vastly easier than obtaining $2^k$ known plaintext/ciphertext pairs (or, even worse, chosen plaintext/ciphertext pairs). But in the usual "academic" evaluation of security, both linear and differential cryptanalysis count as breaks.

Luby and Rackoff have demonstrated in 1988 that given "perfect" round functions, a four-round Feistel structure is secure. However, this proof has two practical issues:

It is relative to the output size of the round function, i.e. 32 bits for a 64-bit block cipher. For 128-bit security, blocks have to be 256-bit wide for the proof to actually apply; but the AES call for candidates requested 256-bit security with 128-bit blocks, not the other way round.
DES has amply demonstrated that concrete round functions cannot be assumed to be perfect.

So while the security provided by a Feistel structure was already quite well understood at that time (around 1997, when AES candidates were being designed), it was also quite known to be "suboptimal" in the following sense: to get the most out of the existing security proofs, you had to go to impractical block sizes or number of rounds. Indeed, many researchers were dissatisfied with the Feistel structure, and eager to explore new structures. The AES competition was at the right time to become a test bed for such novel designs, and the accumulated research has shown substitution-permutation networks (as used by Rijndael) to be valid competitors to Feistel structures.