What are the implications of allowing a zero-length GCM nonce? NIST SP800-38D section 5.2.1.1 is clear that empty nonces are not allowed with GCM, but without explaining the reasoning. My assumption was this is simply because the probability of error (encrypting multiple messages with an empty nonce) would be to high in any system that supported empty nonces at all. As NIST does not allow it, my GCM implementation does not support empty nonces.
However I was recently directed to Apple's CoreCrypto library which has a special function ccgcm_set_iv_legacy to enable empty nonces, and the documentation for this function includes the statement
"Zero-length IVs nullify the authenticity guarantees of GCM."
[https://opensource.apple.com/source/xnu/xnu-4570.41.2/EXTERNAL_HEADERS/corecrypto/ccmode.h.auto.html]
Can anyone explain what is meant by this? Of course if you encrypt multiple messages with GCM using a zero-length IV and the same key you have a serious problem. But is there something more to this warning? In particular can you safely encrypt a message with a zero-length IV as well as some number of messages with non-zero length IVs?

As documented in NIST SP800-38D, GCM works as follows, upon input of block cipher $E$, key $K$, initialization vector $IV$, and plaintext $P$:

Compute the GHASH key $H=E_K(0^{128})$
Compute the initial counter-mode value $J_0$ using some rules which amount to $J_0=0^{128}$ for an (illegal) empty IV.
Encrypt the plaintext using CTR-mode and IV $\operatorname{inc_{32}}(J_0)$, i.e. $C=\operatorname{GCTR}_K(\operatorname{inc_{32}}(J_0),P)$
Compute the polynomial hash (GHASH) over the ciphertext $C\|0^u\|\operatorname{len}(A)\|\operatorname{len}(C)$ using the key $H$ and call the resulting block $S$.
Compute the tag as $T=\operatorname{GCTR}_K(J_0,S)$

Now the key thing to note here is that $\operatorname{GCTR}_K(J_0,S)$ actually amounts to computing $E_K(J_0)\oplus S=E_K(0^n)\oplus S=H\oplus S$. Now we only need to realize that e.g. for a single-block message we have $T=H\oplus S=H\oplus H^2\cdot C\oplus H\cdot L$ where $L=\operatorname{len}(A)\|\operatorname{len}(C)$. As you can probably see the last equation $T=H^2\cdot C\oplus H\cdot L\oplus H$ is actually a quadratic equation where we know every value except $H$.
As we're working over a finite field in the above computation, we can just solve the equation using standard algebra and compute $H$ using the appropriate operators for the field. As you have now recovered $H$, you can change the ciphertext however you want and re-authenticate it at-will and even do that to messages with a different nonce but the same key.
This issue is avoided in "legal" versions of GCM by hashing in the length of the IV for variable-length IVs and for fixed-length IVs by setting the last bit to 1. This then yields a $J_0\neq 0^{n}$ which gets translated to a (pseudo-)random independent-looking value by $E_K(J_0)$.


Is it possible to tweak AES-GCM so that it is satisfactory for whole-disk encryption (like XTS mode)? Is it possible to leverage a preexisting implementation of AES-GCM to provide the key security benefits essential for full-disk encryption (similar to AES-XTS)?

GCM is a popular encryption mode supported by several libraries and with fast implementations in hardware, and on its own GCM has nice properties including parallelism. Because of GCM's built-in authentication functionality and due to its performance, it is beneficial to consider that as a starting point; a hardware implementation may implement AES-GCM as a self-contained performance routine.

But on the other hand, a critical requirement of GCM (essential to its security) is that it must have unique random IVs, just like CCM. So if the IV that is chosen is derived from the sector or block offset (even if there's an intermediate hash), the very fact that on a disk it's common to write and overwrite data in place (coupled with GCM and CCM behaving nearly like stream ciphers) makes it potentially dangerous to derive the IV in that deterministic way. But just like many encryption modes are based upon compositions of cryptographic primitives, I'm wondering if it's possible to start with GCM (and its AEAD property) and build upon that to also attain the secure capability of writing to disk at sector offsets.

The ZFS file system uses AES in CCM or GCM modes.  This works because in ZFS the data and file system metadata is encrypted but the block pointers are in the clear, the AuthTag (MAC) is stored in the block pointer.  ZFS also has a SHA256 based merkle tree based on the block pointers that is used for data integrity for resilvering and navigation purposes.

Note that ZFS is file system (actually object based really) encryption it does not claim to be "full disk encryption".

For more details see here: https://blogs.oracle.com/darren/entry/zfs_encryption_what_is_on

Darren J Moffat (Architect and lead developer for ZFS encryption).


Which algorithm has better performance (HMAC, UMAC, and Poly1305)? I want to implement a protocol which requires Integrity and Authentication for its messages. I found a lot of algorithms such as HMAC, UMAC, and Poly1305 which provide Integrity and Authentication. So I get confused for which one must I use. Please, could I know which one is better?

First of all, HMAC—with any particular hash function, say HMAC-SHA256—is a different type of thing from UMAC and Poly1305.  So it would be misleading to compare them directly.

HMAC-SHA256 is a pseudorandom function family, or PRF, with long inputs and short outputs, meaning a keyed family of functions $H_k\colon \{0,1\}^* \to \{0,1\}^{256}$ such that if the 256-bit key $k$ is uniformly distributed, then $H_k$ appears to be uniformly distributed among all functions $F\colon \{0,1\}^* \to \{0,1\}^{256}$.  You can use this to authenticate messages by using $t = H_k(m)$ as an authentication tag, because an adversary not knowing $k$ can't guess $H_k(m)$ much better than an adversary not knowing $F$ can guess $F(m)$, which in turn they have a $2^{-256}$ chance of guessing in one try.

UMAC and Poly1305 are one-time authenticators.  You can use a key $k$ once to authenticate a single message $m$ by using $t = \operatorname{Poly1305}_k(m)$ as an authentication tag.  If you ever reveal $\operatorname{Poly1305}_k(m)$ and $\operatorname{Poly1305}_k(m')$ where $m \ne m'$, an adversary can trivially compute $k$ and forge authentication tags on any message of their choice.  But you can extend these to work on many messages, each with a distinct sequence number or noncolliding random token $n$ called a nonce, by composing them with a PRF, and instead using, e.g., $t = \operatorname{Poly1305}_{k_n}(m)$, where $k_n = \operatorname{HMAC-SHA256}_k(n)$.  You must never reuse the same $(k, n)$ pair with two different messages.

For more on message authentication codes, one-time authenticators, HMACs, and pseudorandom function families, an earlier question has several good answers.

Typically, these days, Poly1305 is used in a predefined composition called NaCl crypto_secretbox_xsalsa20poly1305 or one of libsodium's variants of it, which uses the PRF XSalsa20 both to derive the one-time keys $k_n$ and as a stream cipher to derive one-time pads for encrypting a message, at the same time.  This authenticated encryption composition, crypto_secretbox_xsalsa20poly1305, is much faster on pretty much any CPU than any authenticated encryption involving HMAC.  (Possible exception: Maybe on a tiny microcontroller you will have hardware support for HMAC-SHA256, but not for XSalsa20 or Poly1305.)

Does that mean HMAC-SHA256 is useless?  No.  You don't always have a message sequence number in a conversation.  For example, if you are distributing a bearer token in a mostly stateless web application, in order to use Poly1305 as an authenticator you would have to include a ${\geq}192$-bit randomly chosen nonce as an input to a PRF to select the key, which together with the 128-bit Poly1305 output would cost 320 bits of space for an authenticator tag, while for essentially the same security (for short messages and low volumes of data) you could use the 128-bit truncation of HMAC-SHA256 instead, or BLAKE2s-128, or KMAC128-128.


Pseudorandom function outputting a field element VS pseudorandom function outputting a string Assume we have two pseudorandom functions $PRF$ and $PRF'$ defined as follows:

$PRF: \{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \{0,1\}^{n}$

$PRF': \{0,1\}^{n}\times \{0,1\}^{m}\rightarrow \mathtt{F}_p$

where $p$ is a large prime number, $|p|=l$, and $l$, $n$ are security parameters.

Question 1: Is $PRF'$ secure and does it meet the standard definition of pseudorandom function?

if yes, then

Question 2: Are these two pseudorandom functions are different in terms of the level of security and the probability that collision occurs?

$F_p$ has a one to one mapping with the set of integers $[0, p)$. $\{0, 1\}^n$ has a one to one mapping with the set of integers $[0, 2^n)$. Their sizes are respectively $p$ and $2^n$.

Both $F_p$ and $\{0, 1\}^n$ are common
(co)domains chosen due to nice properties in either efficiency, easy analysis or ease of use in the greater scheme of things. But to analyse a PRF these are fundamentally the same.

You are mapping one set to another. This mapping must be indistinguishable from a random oracle, within security bounds. For the analysis the only fundamental property are the sizes and distributions of the sets you're mapping, not what those sets actually contain.

The birthday attack on secure PRFs roughly dictates that you'll find a collision after $\sqrt{s}$ random outputs, where $s$ is the size of the codomain. So for your question respectively $\sqrt{p}$ and $2^{n/2}$.


Schnorr signature security level as compared to AES/RSA As per the Schnorr's original paper (1991),

  The Security Complexity $2^t$: We wish to choose the parameters $p$, $q$ so that forging a signature or an authentication requires about $2^t$ steps by known methods. For this we choose $q > 2^{2t}$ and $p$ such that $2^t$ is about $e^{\sqrt{\ln(p)\ln(\ln(p))}}$. ... For $p > 2^{512}$ and $q > 2^{140}$ the discrete logarithm problem requires at least $2^{72}$ steps by known algorithms.

Now I have three questions regarding this.

How does value of $p$ comes to $2^{512}$ for security complexity of $2^{72}$?
What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$ bits and $q$ of $512$ bits?
Since Schnorr is finite field signature scheme, what is the 'field size', 'group size' and 'subgroup size' in case of schnorr signature scheme?

Thanks in advance.

How does value of $p$ comes to $2^{512}$ for security complexity of
  $2^{72}$?

Personally, I couldn't connfirm this number, but rather landed at $2^{66}$. If you don't know how to find this number, just plug the $2^{512}$ into the complexity equation given and take the logarithm to the base two for better readability.

Note that Schnorr's complexity estimate for the field is based on the Index-Calculus Algorithm and doesn't yet take into account the Number Field Sieve (original paper as PDF) against discrete logarithms, which would give a different expression, namely $L_p[1/3,3^{2/3}]=e^{(3^{2/3}+o(1))(\ln p)^{1/3}(\ln\ln p)^{2/3}}$, that would yield a much lower required attack complexity.

  What is the equivalent AES and RSA key-lengths if we use $p$ of $1024$
  bits and $q$ of $512$ bits?

$q$ is the subgroup order and if you get a 512-bit subgroup you'll have roughly 256-bit security for this subgroup. $p$ is the field prime and with it being 1024-bit, you'll get roughly 80-bit security against NFS-based attacks. So the answer is: A 1024-bit RSA modulus will have a comparable security along with AES-128, where 48 key bits are constant zero'ed out. Note that just plugging-in $2^{1024}$ into the complexity equations is a dangerous business, as $o(1)$ hides an implementation-dependenant (constant) factor that was not accounted for. Rather you need a concrete data point as a basis for further extrapolation. Here's a more detailed treatment of keylengths: (simple) (complex) by Lenstra and Verheul.

  Since Schnorr is finite field signature scheme, what is the 'field
  size', 'group size' and 'subgroup size' in case of schnorr
  signature scheme?

$p$ is the field prime and its bitlength is the field size.
$q$ is the subgroup order and its bitlength is the subgroup size.
There's no relevant "group size" in this case (maybe one could say that's equivalent to the field size though)


Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult? I know that if we have a cipher that makes only linear transformations (let's say a bunch of $XOR$s), we break it simply by writing a system of equations with $\oplus$ operation starting from the cipher's scheme.
In the end, we'll have a system of $n$ equation involving the $n$ plaintext bits,  the $n$ ciphertext bits, and the $n$ key bits holding with probability: $\Pr(1)$ and we can solve for the $n$ key bits.
Why with the presence of S-boxes is this not possible in the same way?
Thinking about $DES$, couldn't we just reverse the S-Boxes (which at the end are only lookup tables) to write the same system of equations? In that case, the relations won't be again deterministic? (holding with $\Pr(1)$)
What is the precise meaning of non-deterministic transformation and how is it applied here?
Could you please make me a counter-example of what I'm saying, just to see why this approach couldn't be used as it is, with the presence of S-Boxes?

It is of course possible to write DES or any block cipher as a system of non-linear equations involving the plaintext bits, the ciphertext bits, and the key bits, which hold with probability 1.  In principle, cracking the cipher would then merely involve collecting enough linearly independent equations (e.g. from a couple different known plaintexts) and then solving the system.

However, for any typical block cipher the equations are going to be extremely high degree, involving preposterous numbers of terms.  Solving very high degree systems of equations with large numbers of terms is actually a very hard problem.  Which is to say, while systems of linear equations can be solved in polynomial time (e.g. with Gauss-Jordan elimination), solving systems of non-linear equations is NP-Complete and can take longer than the expected life of the universe to solve.

It is possible to reduce the degree of the system by clever use of intermediate or temporary variables (which also increases the number of equations).  In fact, you can make the system as low degree as quadratic.  But as it turns out, that doesn't help much - solving multivariate quadratic systems is still NP-Complete (this is called the "MQ" problem).

There have been a few papers in recent decades concerning "algebraic cryptanalysis" which purport to solve the specific systems of equations involved in certain ciphers in polynomial time.  The idea with these papers is that while MQ in general is very hard, the specific systems of equations associated with some block ciphers might be sufficiently structured and sparse as to be efficiently solvable by some clever technique or another.  However, none of the techniques thus far been convincing to the cryptographic community.


How to choose secp256k1 private key? The private key is any random 256 bit (but smaller than prime p) number or must be prime or other condition?
For selected $x$ can be found $y$ - decompressing key:
#! /usr/bin/env python3
import binascii
import math
p = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
def decompress_pubkey(pk):
    x = int.from_bytes(pk[1:33], byteorder='big')
    y_sq = (pow(x, 3, p) + 7) % p
    y = pow(y_sq, (p + 1) // 4, p)
    if y % 2 != pk[0] % 2:
        y = p - y
    y = y.to_bytes(32, byteorder='big')
    return b'\x04' + pk[1:33] + y

print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0229b3e0919adc41a316aad4f41444d9bf3a9b639550f2aa735676ffff25ba3898'))).decode())
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('02f15446771c5c585dd25d8d62df5195b77799aa8eac2f2196c54b73ca05f72f27'))).decode())
print(binascii.hexlify(decompress_pubkey(binascii.unhexlify('0279be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798'))).decode())

Only last x,y pair fulfill (x3+7-y2) % p is zero. Two previous pairs are wrong?

You are confusing the concepts; the private key vs the public key. Your private key $k$ is an integer which is selected uniform randomly between $1$ to order of the base point $G$

Basepoint $G$ in compressed for
  0279BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798

The order $n$ of $G$, i.e. $[n]G = \mathcal{O}$, where $\mathcal{O}$ is point at infinity, or the identity element in additive elliptic curve group.
FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C

Your (or any) public key is $[k]G$, which is scalar multiplication and defined as.
$$[k]G = \overbrace{G+\cdots+G}^{{k\hbox{ - }times}}$$
With add double-and-add it can be calculated very efficiently.
Your failures are due to your python coding ( that is off-topic here) where you want to recover the $y$ value from a compressed public key, not the private key. Rasmus Faber's has an answer in StackOverflow. That is the way you need to find it wiht Python.
Note: All parameters of the curve can be found on Certicom's SEC 2: Recommended Elliptic Curve Domain Parameters


How many public keys and private keys are needed for RSA? I am just learning about RSA encrytion and I am somewhat confused.
First two prime numbers $p$ and $q$ must be chosen and multiplied to get $n$. Then we compute Euler function $\varphi (n) = (p-1)(q-1)$.
The public key $e$ is generated by choosing a random number that fulfills the condition $gcd(e, \varphi(n)) = 1$. And the private key $d$ is then computed $d * e \:\: mod\:\varphi(n) = 1$.
So if Alice wants to send a message to Bob, a pair of public and private key is generated. But if Bob wants to send something back to Alice, must another pair of public and private key be generated?
If this is the case, does it mean that for RSA between $x$ parties, there must be in total $x(x-1)$ keys (public and private) generated?

So if Alice wants to send a message to Bob, a pair of public and private key is generated. But if Bob wants to send something back to Alice, must another pair of public and private key be generated?

Yes. Bob's public/private key pair, which protected the Alice-to-Bob transfer, is not usable to send data to Alice. However it's usable by anyone [assumed knowing Bob's public key $(n_b,e_b)$, trusting that to be matching Bob's private key $(n_b,d_b)$, and that Bob will not reveal that private key or use it unwisely] in order to send a confidential message to Bob.
Hence each user may need a single public/private key pair, yet the system allow anyone to send a confidential message to anyone.

If this is the case, does it mean that for RSA between $x$ parties, there must be in total $x(x-1)$ keys (public and private) generated?

No. As far as counting how many public/private key pairs there are, a good analogy is public phone number and private phone: we need as many phone numbers, and corresponding phones, as there are users.


Encryption: am I doing it right? I'm trying to get a per-user encryption key scheme off the ground and need some validation from wiser crypto pros. Consider the following procedure:

User provides registration information to include a password.
Generate a random salt.
Hash the password+salt using bcrypt.
Generate a key to be used for data encryption (known as the DEK).
Generate a second key derived from the hashed password+salt.
Generate a 12-byte IV.
Encrypt the DEK using the AES-128-GCM cipher, the password-derived key, and the IV.
Store the encrypted DEK, the salt, and the IV in the database.

Any time I need to decrypt user data:

Ask for the user's password.
Pull the salt, IV, and encrypted DEK from the database.
Hash the password+salt.
Generate the key to decrypt the DEK using hashed password+salt.
Decrypt the DEK using the generated key and the IV.
Decrypt the user's data.

To my eye, this seems to be the correct procedure to manage encryption keys in a system where the data and keys are stored on the same system. But encryption is hard so I could be getting something wrong. So what say you? Any obvious omissions in this scheme?

Many thanks.

EDIT:
For clarity's sake, this is a web application storing PII in the database as well as on disk. There are no instances where one user should be able to access another user's sensitive data. The user has been warned that forgetting their password means losing access to their data.

It all has to do with your requirements. If you want the server to have access to the data when the user logs in but not allow the server offline access. Then this scheme seems reasonable.
You have a second key which may or may not be needed. If each user has exactly one password and exactly one random key then you could use the password derived key directly.
You did specify how you encrypt the data, but AES GCM again would be reasonable.
You want to make sure you can verify they password. Use of GCM for the key or use of GCM for the data would suffice.
If the data encrypted is large, a second key allows changing password without reencrypting all of it. For small data I may recommend skipping the second key.
Be sure you use secure random number generators.
Be sure the password is sent to the server over a secure line(e.g SSL).
Some would advocate for doing hashing client side, which makes the server never have the clear text, and the client does the heavy computation, preventing some DOS attacks and some timing attacks.


How to find a generator g for a large prime p? Trying to implement ElGamal. I have a 1024-bit prime p and now need to find a primitive root g for it.
How do you find such a g in an acceptable time? It takes so long, my sage server actually interrupts the calculation.

Here's one easy approach: Pick a large safe prime $p = 2q + 1$ for prime $q$.  If you pick $p$ congruent to 1 or 7 modulo 8, then 2 is a quadratic residue modulo $p$, and thus generates a subgroup of large prime order $q$.  If you pick $p$ congruent to 3 or 5 modulo 8, then 2 is not a quadratic residue modulo $p$, and thus generates the entire group $(\mathbb Z/p\mathbb Z)^\times$.  There are, of course, other choices of generator, which you can use the law of quadratic reciprocity to figure out.

For more general primes $p$, if you know the factorization of $p - 1$, then you can compute generators of all the subgroups independently and combine them with the Chinese remainder theorem.  If you look up Schnorr groups, e.g. in DSA parameter generation, you'll find a special case of this for primes $p = kq + 1$ where $q$ is the prime subgroup order of interest: simply pick $h \in (\mathbb Z/p\mathbb Z)^\times$ uniformly at random until you find one with $h^k \not\equiv 1 \pmod p$, and you've found a generator of an order-$q$ subgroup.  You can get this by picking a prime $q$ first and varying $k$ until you find a prime $p$ in the desired range.

If you don't know the prime factorization of $p - 1$, then Sage is probably computing it for you!  That might take a while if $p - 1$ is 1024 bits long.

(Caveat: I don't know whether you mean Elgamal encryption or Elgamal signature, nor whether either one has any requirements other than the decisional DH assumption, because approximately nobody ever uses Elgamal encryption or signature these days.)


State of the art low memory arbitrary-domain PRP? I am wondering what the state of the art is on low memory arbitrary-domain PRPs.

That is, I'm looking for an algorithm that implements bijective function $PRP : \mathbb{Z}_n \times \{0, 1\}^b \rightarrow \mathbb{Z}_n$, where $b$ is an acceptable security level (say, 256 bit).

Such a function is trivial to construct by using a Fisher-Yates shuffle with an appropriate source of pseudo-randomness on a full array of size $n$. However, I'm looking for an algorithm that does not use $O(n)$ memory, but rather on the order of $O(\log n)$.

Even more ideally, I'm looking for an algorithm with a flexible key schedule, such that no precomputation for a certain key is needed. Does this exist, or is it impossible?

Okay, here's the algorithm for "a fixed security level of 2128":

If  n ≤ 2^(2^128)  then sometimes-recurse shuffle with 128 bits of security.

If  2^(2^128) < n  then encryption just outputs the

plaintext and decryption just outputs the ciphertext.

The identity function can trivially be computed in O(1) space, so that algorithm

also uses only O(1) space.  (That's why, for true asymptotic analysis, one must

usually  assume some relation between n and the security parameter.)


Isn't fully homomorphic encryption trivial with a complex enough decryption function? Consider the following exchange:

Alice has some plaintext $x$. She sends the encrypted version $\mathcal E(x)$ to Bob.
Bob returns $(\mathcal E(x), T)$, where $T$ is a turing machine encoding the function he wants to preform on the unencrypted data.
To decrypt this result, Alice first decrypts $\mathcal E(x)$ to get the original plaintext $x$, and then runs the turing machine $T$ with $x$ as the input. The decrypted result is the output of the turing machine.

By sending back $T$, Bob essentially offloads the work of actual computation on the ciphertext to the decryption function. However, from what I can tell, this is technically still a fully homomorphic encryption system, as it allows Bob to execute an arbitrary function on the plaintext, without ever knowing the plaintext himself (since the computation of the Turing machine is done by Alice).

Is this cryptosystem actually considered homomorphic encryption? Is there a subtlety in the constraints for a FHE system that excludes this? Or is it just rejected for being pedantic and useless?

No, this is not considered homomorphic encryption.  This is excluded by requiring that the ciphertext size and running time of the decryption operation be bounded by the security parameter, independent of the circuit size.  Your pathological example is given as the first footnote in Craig Gentry's seminal paper on a realization of FHE.


Does Shannon perfect secrecy imply a deterministic encryption algorithm? Consider an encryption scheme $(Gen,Enc,Dec)$ where $Gen$ is the key generation algorithm, $Enc$ is the encryption algorithm, where $c \leftarrow Enc_{k}(m) $ is taken to mean that the message $m$ in some message space $M$ encrypted with a key $k$ generated from some keyspace $K$ using $Gen$ produces the ciphertext $c$ which belongs to some cipherspace $C$, and where $Dec_{k}(c) = m$ is the decryption algorithm which is always deterministic.

In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic?

i.e. is it impossible that there exist two different ciphertexts $c_{1},c_{2} \in C$ that are both produced by encrypting the same (message, key) pair? It seems once you restrict the three spaces to have equal cardinality, the encryption algorithm must be deterministic, but I cannot seem to prove this formally.

In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic

Actually, the standard definition doesn't actually imply that.  It is necessary that $|K| \ge |M|$ and $|C| \ge |M|$, however in neither case does equality have to hold.

In any case, I'll proceed with the assumption that we have $|M| = |C|$ (the length of the key turns out not to matter for your question)

  Does this imply that $Enc$ is deterministic?

Yes; the pigeon-hole principal is your friend.

Consider any fixed key $k$, and all plaintexts of length $n$ (there are $2^n$ of them).  If you encrypt any one of them with the key, it will result in a ciphertext of length $n$ (and, again, there are $2^n$ possible ciphertexts).

We assume that the encryption process is invertible (that is, $Dec_k(Enc_k(m)) = m$ for any $m$), and so two different plaintexts must result in different ciphertexts.

There are $2^n$ plaintexts mapping to $2^n$ ciphertexts, and so each plaintext must map to precisely one ciphertext (pigeon-hole principle; if there was a plaintext that could map to two different ciphertexts, there must be a plaintext that doesn't map to any, and we assume that doesn't happen).

Hence, the encryption for any specific key is deterministic; that means that encryption for all keys is deterministic.


Why hash function are used in digital signatures? In the lectures I see, hash functions are always used when we want to sign a document $d$. My question is why they are used in digital signatures? Maybe, because it is more easy and fast to calculate the signature when is used a "block" signature scheme? Do you know some formal paper or book where this is described? I need that for my thesis.

Bruce Schneier writes in Applied Cryptography (2nd ed., p. 38f):

  In practical implementations, public-key algorithms are often too inefficient to sign long documents. To save time, digital signature protocols are often implemented with one-way hash functions (...). Instead of signing a document, Alice signs the hash of the document.

The references Schneier cites are:

D. W. Davies and W. L. Price, "The Application of Digital Signatures Based on Public-Key Cryptosystems," Proc. of the Fifth International Computer Communications Conference, Oct 1980, pp. 525--530.
D. W. Davies and W. L. Price, "The Application of Digital Signatures Based on Public-Key Cryptosystems," National Physical Laboratory Report DNACS 39/80, Dec 1980.


Should we use the new CAESAR competition ciphers? At the beginning of this year, the CAESAR competition published the final portfolio for authenticated encryption algorithms.

I'm not a cryptographer and when I look at other applications, almost always AES-GCM or ChaCha20-Poly1305 is used for authenticated encryption.

So, I wonder why that is. Are the new CAESAR algorithms too new, or are there not enough implementations in the different programming languages? Other reasons?

As a programmer: When I design a new system today, should I consider the new CAESAR algorithms? Are there technical advantages/disadvantages?

Also, I heard of the Lightweight Cryptography project organized by NIST. Is not this competition redundant given the category 1: Lightweight applications (resource constrained environments) in the CAESAR competition?

The CAESAR competition took way too long, didn't go as well as expected, and other interesting constructions that would have been worth considering were designed after it started.

Some of these (AES-GCM-SIV) got standardized before the competition was over, and may get more adoption than CAESAR candidates.

The goal of CAESAR wasn't clearly defined. We didn't end up with AES alternatives. If only because AES is well-supported in hardware and has no sign of being broken anytime soon.

I'm not convinced of the practical outcome of the NIST LWCC competition either. AES is here to stay.

To get back to CAESAR, some finalists are interesting.

In particular, AEGIS doesn't change the AES core function, but builds a very fast (faster than AES-GCM) and simple construction taking advantage of the parallelism of some CPUs.

AEGIS-256 has been implemented in libsodium. So, it may get some adoption for applications where speed is the primary concern.


Which is slower, AES or GCM hash (GHASH), if CPU has no special instructions? In an answer to this question: Security of GCM if Implemented with Stream Cipher instead of Block Cipher ...it was stated that:

The GHASH part of GCM is usually the problematic one when it comes to implementation, not the AES. GHASH is very fast on hardware platforms that have dedicated opcodes (x86 with AES-NI, POWER8...) but these platform also provide an AES hardware implementation that outperforms software-based stream ciphers.

Is this really true? Is GHASH really slower than AES, if the CPU has no special instructions for either?

First things first: the passage you quote does not claim that GHASH is slower than AES. What it says is that if you replace AES/CTR with a much faster stream cipher, then the GHASH part will be comparatively expensive.

There are many kinds of implementations, for both AES and GHASH; they have different performance characteristics, and they may be constant-time, or not. I'll use BearSSL here for most measures, because I know how that code works (I wrote it), and I can easily benchmark it. The measure platform here is my laptop (Intel i7-6567U at 3.3 GHz, in 64-bit mode):

AES-128 CTR (big)                170.67 MB/s
AES-128 CTR (ct64)               108.91 MB/s
AES-128 CTR (x86ni)             5307.37 MB/s
GHASH (ctmul)                    214.63 MB/s
GHASH (ctmul64)                  277.17 MB/s
GHASH (pclmul)                  4795.76 MB/s

For the AES implementations:

"big" is a classic table-based implementation (not constant-time).
"ct64" is a constant-time bitslice implementation that uses 64-bit registers and computes 4 AES instances in parallel (which works well with CTR mode).
"x86ni" uses the AES-NI opcodes (it computes four instances in parallel, which maps well to the 4-cycle latency of these opcodes on a Skylake core).

For the GHASH part:

"ctmul" uses 32x32→64 integer multiplications with masking to avoid trouble with carries. It is constant-time.
"ctmul64" uses 64x64→64 integer multiplications with masking; it is also constant-time.
"pclmul" uses the AES-NI opcodes.

The following extra notes apply:

All GHASH implementations in BearSSL are constant-time. It is possible to make non-constant-time GHASH implementations which are faster, by using lookup tables, in particular dynamically generated tables for the specific secret $h$.
There is a constant-time bitslice implementation of AES that leverages SSE2 opcodes, both for extra parallelism (128-bit registers) and more efficient implementation of the linear parts of the algorithm. It would go over 400 MB/s on this machine, and would outperform the constant-time GHASH implementations. Whether it qualifies as "not using special opcodes" is debatable: it is not using the AES-NI opcodes, but not all 64-bit architectures have something similar to SSE2 (it is part of the ABI on 64-bit x86, though).
Combining AES and GHASH may offer speed-ups, if they do not exercise the same compute unit within the CPU. For instance, with the AES-NI opcodes, interleaving the AES/CTR encryption and the GHASH can yield better than the already quite decent 2.5 GB/s that the figures above promise.

An aggregate rule of thumb is that, when using only "basic" operations (i.e. those available in C without inline assembly or compiler intrinsics), you can keep the cost of GHASH to less than half the cost of AES/CTR (if using a non-constant-time AES, it makes more sense to measure against a non-constant-time GHASH).

Now let's compare with ChaCha20 and Poly1305:

ChaCha20 (ct)                    407.74 MB/s
ChaCha20 (sse2)                  590.59 MB/s
Poly1305 (ctmul)                1248.27 MB/s
Poly1305 (ctmulq)               1936.74 MB/s

The "ct" implementation of ChaCha20 uses only 32-bit integer operations; the "sse2" implementation uses SSE2 intrinsics. For Poly1305, the "ctmul" implementation uses basic 32x32→64 multiplications, while the "ctmulq" implementation uses 64x64→128 multiplications (which require some compiler intrinsics or extensions). All of these are constant-time.

What this says to us is the following:

Without AES-NI, ChaCha20 outperforms AES. Actually, constant-time ChaCha20 substantially outperforms all AES, even non-constant-time.
Without AES-NI, Poly1305 is much faster than GHASH.
If you want to make an hybrid out of ChaCha20 and GHASH (this is the context of the previous question that you want to discuss), then the GHASH part is going to be more expensive than ChaCha20, except if you use the AES-NI opcodes for GHASH; but then, if AES-NI opcodes are available, why would you use that ChaCha20 hybrid instead of standard AES/GCM?


For RSA, is there a specified size range for $p$ and $q$ when calculating $N$? Is there a specified size range for $p$ and $q$ when calculating $N$? For example, what size would $p$ and $q$ be when $N$ is 1024 bits?

There is no specific length for $p$ and $q$; however, one must mind the following:

Since $N = pq$, the size of $N$ will be more or less the sum of the sizes of $p$ and $q$ (± 1 bit).
Security of the key relies on the difficulty of integer factorization. The best known algorithms for that have a cost that depends on the size of $N$, but some other algorithms (in particular ECM) have a running cost that depends on the size of the smallest factor. If one of the factors $p$ and $q$ is too small, then it may make ECM practical, leading to a security weakening.
Private key operations with RSA can be expensive (especially on small, embedded hardware). A common optimisation is to do private key operations not modulo $N$, but modulo $p$ and $q$ (the Chinese remainder theorem tells us that it works). Since $p$ and $q$ are smaller than $N$, this is a net gain. The speed-up factor is highest when $p$ and $q$ are both about half the size of $N$.
Some widespread implementations of RSA require the two factors to be exactly half the size of the modulus. This is the case, for instance, for Microsoft's CryptoAPI: when importing a private key, the import format uses fixed-size slots for the factors, that are exactly half the size of the modulus.

Therefore, while the RSA standard does not mandate any specific sizes for the individual factors, the general practice is to make both factors $p$ and $q$ to be exactly half the size of the modulus $N$. So, for a 1024-bit modulus, the factors will be 512-bit integers.

(To be even more precise, it is customary to generate each factor with its two top bits set to 1. If you just take two 512-bit integers, their product may be a 1023-bit integer; by setting the two top bits of each factor to 1, this ensures that the product will be a 1024-bit integer.)


What does it mean that a semi-honest adversary can look at the internal state of a controlled party? I have a doubt regarding the definition of (static) semi-honest adversaries. In this tutorial I read:

  Such an adversary controls one of the parties (statically, and so at the onset
  of the computation) and follows the protocol specification exactly. However, it may try to learn
  more information than allowed by looking at the transcript of messages that it received and its
  internal state.

Does it means that, for example, in the case of a commitment scheme a semi-honest adversary, who controls the party supposed to commit a value, knows the committed value (since it is part of her or his internal state)? However, since the adversary is semi-honest, she or he cannot take advantage of this information to deviate from the protocol in a profitable way.

Yes, this is what it means. A semi-honest adversary knows the entire state of each corrupted party, including its input, any random coin tosses, and all incoming messages from all other parties. However, it cannot deviate from the specified protocol instructions. Note that in the multiparty setting, the semi-honest adversary may corrupt multiple parties. In this case, it sees all of the corrupted parties' states together.


Can the passphrase of a PGP key be deduced from an old backup? Let's assume that Bob, at some point in time, has created a PGP (key length and other parameters are not relevant at this point).  For some reason, he has chosen a very poor passphrase, for instance lemon.  Some time later, Bob realises his poor choice and decides to change his passphrase to something much more secure, for instance There is no doubt that a longer passphrase is more secure than a single word.

There's the catch:  At some point before the passphrase was changed, the private key somehow leaked (e.g. due to a not appropriately secured backup scheme or some other mishap).  Either way, Eve now has Bob's private key, but not its passphrase.  Given the poor choice of the original passphrase, this will just be a matter of time, so for the sake of the discussion let's assume that Eve eventually manages to deduce the passphrase in some way.  She thus has both the private key and its passphrase and will be able to decrypt it.

The key itself of course is compromised at this point, this is without question.  Eve is certainly able to decrypt her (barely protected) copy of Bob's private key, even if Bob's copy is now encrypted in a different manner (read: new passphrase).  So I guess this corresponds to a known plaintext attack on the private key.  Will Eve be able to deduce Bob's /new/ passphrase (and thus possibly other keys where he used the same passphrase) in this scenario?

I'm assuming Bob uses the standard format, OpenPGP aka RFC4880, to store his private key in a private keyfile.

If the adversary Eve somehow obtains Bob's private keyfile, and the passphrase on that keyfile is so short and weak that the adversary breaks it with a dictionary attack or brute force, then -- Things are very bad for Bob.

Bob's best choice of action here is to generate a fresh new second private key, tell everyone (possibly by using messages signed by his original private key) to use the new public key and revoke his earlier key.
(Yet how will people be able to tell that these messages really came from Bob?
Perhaps those messages are actually from Eve, forged to appear as if they came from Bob,
telling everyone to use a public key corresponding to a private key known only to Eve.
All they can be sure of is that the original key has been compromised and should be revoked).

However, in this scenario Bob inexplicably keeps using his original private key, but re-encrypts it using a good passphrase.

Then Eve somehow obtains Bob's new private keyfile, including the original private key (which she somehow guesses is the same as the private key she extracted from the earlier keyfile) encrypted by Bob's new good passphrase.

  Will Eve be able to deduce other secret information, decrypt other things encrypted with Bob's /new/ passphrase, or perhaps even deduce the passphrase itself?

Unlikely.

You are describing a known-plaintext attack: Eve has an encrypted text (the new private keyfile encrypted with the new passphrase) and the corresponding plaintext (the private keys extracted from the old keyfile), and is trying to use that to reveal further secret information.

The standard OpenPGP format encrypts the private keys with (a key formed from a hashed version of) the passphrase using one of several algorithms listed in RFC4880 section 9.2. "Symmetric-Key Algorithms", typically AES.

Known-plaintext attacks were well-known when those algorithms were written.
All of those algorithms were specifically designed to be resistant to known-plaintext attacks.
They are designed such that even after a Eve obtains hundreds of plaintext+ciphertext pairs, all the ciphertext encrypted using the same "good" passphrase, it is practically impossible for Eve to recover that passphrase or decrypt any other message.


Common cyphers where the plaintext is the same length as the cyphertext What are the common cyphers where the cyphertext is always the same length as the plaintext?

I can think of XOR cyphers, and letter-substitution cyphers, what others are there?

Any cipher or cipher mode that implements Format Preserving Encryption (FPE) - by definition.

NIST has created a US standard document called NIST Special Publication 800-38G: Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption. This document lists two modes of operation abbreviated as FF1 and FF3. These are format-preserving, Feistel-based encryption modes. FF1 was previously known as FFX[Radix] and FF2 as BPS.

Stream ciphers or stream cipher modes of operation have the same property, but they have the problem that they require a nonce or IV, which typically has to be send with the ciphertext unless the state is otherwise synchronized between the party doing the encryption / decryption.

ECB and CBC mode have the same property, but the plaintext needs to be a certain number of full blocks and padding should not be applied. ECB is insecure and CBC also requires an IV to be used.

Commonly disk encryption routines have the same property as well, but they may restrict the input to a specific sized chunks. ESSIV for instance uses a hash over the sector number and key to create an IV, sidestepping the issue that CBC requires an unpredictable IV.

So for symmetric ciphers / cipher modes this is a common property except that they often require an IV and sometimes padding. If the ciphertext also needs to authenticated then an additional authentication tag may be required as well.

Asymmetric ciphers commonly have to expand the ciphertext compared with the plaintext to be considered secure. RSA - for instance - could be used to have a ciphertext that is the same size as the plaintext, but the message space would have to be identical to the (randomly generated) modulus, and encrypting the values 0 and 1 would be completely insecure (because the modular exponentiation would not alter the plaintext message).


What is the difference between online and offline brute force attacks? I read some papers saying a certain scheme is secure for offline brute force attacks, but vulnerable to online brute force attacks. I wonder the difference between the online and offline brute force attacks.

An offline attack require work from the attacker only (or mostly), with no (or little) communication with the system (e.g. server) under attack (holding the key). An online attack requires (typically significant) work of the system under attack (including communication).

The computing power or communication bandwidth of the system under attack is typically limited compared to what a resolute attacker might use. Thus even if it requires significantly more effort, an offline attack usually is easier to perform in practice than an online attack, and stands better chance to go undetected.

Note: Online attack refers to communication with an entity under attack, that must be online (and participating) during the attack. An attack using a coalition of adversaries communicating online, with little or no communication with the entity under attack (if any), is an offline attack requiring online communication.

For example, parallel hash collision search is an offline brute-force attack. The attack against HMAC-MD5 that asks for the MAC of random messages ending with the same block until a collision is found (requiring about $2^{64}$ queries), then modifies the last block of the two colliding messages to (likely) get a new collision allowing a MAC forgery, is an online brute-force attack, since there is massive work involving communication with an entity capable of computing MACs (holding the key).


Is it possible to do partial message authentication? I want to authenticate part of a message, not all of it, while creating the MAC over the entire message. Let's say I create a 16B MAC over one hundred message blocks that are 64B each. Then I send one 64B message and the combined MAC to the receiver. The receiver has to verify the 64B using the MAC while it does not have the entire message.
Is there any cryptographic algorithm/way to do that?

My guess is that you want to prove that the message you sent is a part of a bigger message without showing the entirety of the bigger message to prove so.
A solution that comes to mind is to make the authentication hash is the hash of the hashes of the other messages. That way you can confirm that this message is a part of the bigger message you sent without revealing the actual bigger message.


How to attack a fixed LCG with partial output? To show some colleague programmers exactly how broken C's rand() is (at least on Windows) I decided to break it. So everyone knows the exact parameters, MSVC's implementation is as follows:

uint32_t state;

int rand() {
    state = state * 214013 + 2531011;
    return (state >> 16) & 0x7fff;
}

Because the top bit never affects anything but the next top bit in the next state and is never returned you could see this as the LCG $X_{n+1} \equiv (214013X_n + 2531011) \mod 2^{31}$ where at each iteration we only get to see the top 15 bits.

The problem is, I have not found any references that attack fixed LCG's with partial output.

Of course it requires only 2-3 calls of the rand() function to enable a bruteforce attack with at most $2^{16}$ operations on the secret part of the state, but that's hardly a break. Something similar would not be feasible with larger constants and a larger modulus.

So far I've been unable to find a break that shows this generator to be severely broken. I'm interested in results on similar LCG's that can be transformed to an attack on this one.

P.S.: If an attack exists that could be done on a graphical calculator without any programming, it increases how convincingly I can show the generator to be broken. But this is just bonus points.

Notations:

$v=u\bmod m$ means $m$ divides $u-v$ and $0\le v<m$, including if $u<0$.
All variables are non-negative integers (except for the above).
$a=214013$, $b=2531011$ are the LCG parameters.
$X_n$ is the 31-bit state with $X_{n+1}=(a\cdot X_n+b)\bmod 2^{31}$.
$R_n=\lfloor X_n/2^{16}\rfloor$ is the 15-bit output.
$S_n=X_n-2^{16}\cdot R_n$ is the hidden 16-bit portion of the state.

Assume we have the first few outputs $R_0$, $R_1$.. and want to find $X_0$.

We derive:
$$\big((2^{16}\cdot R_1+S_1)\bmod 2^{31}\big)=\big((a\cdot (2^{16}\cdot R_0+S_0)+b)\bmod 2^{31}\big)$$
$$2^{16}\cdot R_1-a\cdot2^{16}R_0-b+S_1\equiv a\cdot S_0\pmod{2^{31}}$$
Using that $S_1<2^{16}$ and defining $r=2^{16}-1-S_1<2^{16}$, that becomes:
$$2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1\equiv a\cdot S_0+r\pmod{2^{31}}$$
Defining $K$ as the quotient of the Euclidean division of $a\cdot S_0+r$ by $2^{31}$, it comes:
$$\big((2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod2^{31}\big)+2^{31}\cdot K=a\cdot S_0+r$$
Using that $r<2^{16}\le a$, we find that $S_0$ must be the quotient of the Euclidean division of the new left side of the equation by $a$, and $r$ the reminder; we derive:
$$S_0=\Big\lfloor{{\big((2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod 2^{31}\big)+2^{31}\cdot K}\over a}\Big\rfloor$$

Therefore the following outputs the possible values for $X_0$ given the first two outputs $R_0$ and $R_1$, by trying all possible values of $K$:

Compute $T=(2^{16}\cdot R_1-a\cdot2^{16}\cdot R_0-b+2^{16}-1)\bmod 2^{31}$
Notice that $T+2^{31}\cdot K=a\cdot S_0+r$ with $S_0<2^{16}$ and $r<2^{16}$
For $K$ from $0$ to $\big\lfloor\big((2^{16}-1)\cdot(a+1)-T\big)/2^{31}\big\rfloor$

If $\big((T+2^{31}\cdot K)\bmod a\big)<2^{16}$

Output $\big\lfloor(T+2^{31}\cdot K)/a\big\rfloor+2^{16}\cdot R_0$

The quantity $(T+2^{31}\cdot K)\bmod a$ tested in the loop is $r$, hence the test's bound. $\big\lfloor(T+2^{31}\cdot K)/a\big\rfloor$ is $S_0$. What's output is a candidate $X_0$, since $S_n=X_n-2^{16}\cdot R_n$. It is easy to filter these candidates using $R_2$.

This works for any $a\ge2^{16}$. With the parameters at hand, the loop is performed at most $7$ times, with typically $2\pm1$ outputs. I can run the algorithm with pen and paper, and some would be able to perform it mentally.

The method works regardless of the bit size $x$ of $X$, an output $R$ with $x/2$ high bits (give or take a constant), and $a$ big enough that the attack works: the cost is $O(x^2\cdot a/2^{x/2})$ using standard arithmetic algorithms. I think we could avoid most values of $K$ that do not pass the test, bringing the cost to $O(x^2)$ even for huge $a$ (and quoting Bruce Schneier attributing that saying to the NSA: "Attacks always get better; they never get worse").

When $a$ is too small to carry that attack, a trivial attack applies, recovering the state $X_0$ from most to least significant bits, at a rate of about $\log_2a$ additional bits for each additional $R_n$.

Improvement: if $a$ is small or otherwise unfavorable, we can use $R_j$ rather than $R_1$, replacing $a$ with $a_j=a^j\bmod2^{31}$ for some $j>1$ giving a favorable $a_j$ (a small maximum $K$), and replacing $b$ with $b_j=b\cdot(1+a+\dots+a^{j-1})\bmod2^{31}$. That allows to efficiently tackle much larger modulus!

Generally speaking, Linear Congruential Generators are very poor from a cryptographic standpoint, even when some post-processing is applied; see this answer for an example.

More often than not, Linear Congruential Generators are not even suitable for simulation purposes. To demonstrate this to the incredulous, generate a million values using the LCG in the question; count how many times each of the 32768 values is reached; and either compute the standard deviation of that, or graph the counts sorted by increasing values; repeat with a sound RNG, and compare.


NIST's Recommendations for Protection of CLASSIFIED Data? In NIST Recommendation for Key Management Part 1 Rev 4, It states in Section 1.Intro

  This NIST Recommendation applies to U.S. government agencies using
  cryptography for the protection of their sensitive, unclassified
  information.

and in Section 1.3Scope

  All cryptographic algorithms currently approved by NIST for the
  protection of unclassified, but sensitive information are in scope.

What are the NIST Recommendations for Protection of sensitive and classified data in terms of Cryptographic primitives

Symmetric Encryption
Asymmetric Encryption
Hash Functions

Suite B has been revised in the light of development of quantum algorithms. Some modifications to ECC standards was in response to the scandal of an apparent weak elliptic curve in the previous standard.

From the NSA IAD website:

  Commercial National Security Algorithm Suite

  The Commercial National Security Algorithm Suite (CNSA Suite) will
  provide new algorithms for those customers who are looking for
  mitigations to perform, replacing the current Suite B algorithms.

  [..]

  Currently, Suite B cryptographic algorithms are specified by the
  National Institute of Standards and Technology (NIST) and are used by
  NSA's Information Assurance Directorate in solutions approved for
  protecting classified and unclassified National Security Systems
  (NSS). Below, we announce preliminary plans for transitioning to
  quantum resistant algorithms.

  Background

  IAD will initiate a transition to quantum resistant algorithms in the
  not too distant future. Based on experience in deploying Suite B, we
  have determined to start planning and communicating early about the
  upcoming transition to quantum resistant algorithms. Our ultimate goal
  is to provide cost effective security against a potential quantum
  computer.  We are working with partners across the USG, vendors, and
  standards bodies to ensure there is a clear plan for getting a new
  suite of algorithms that are developed in an open and transparent
  manner that will form the foundation of our next Suite of
  cryptographic algorithms.

  Until this new suite is developed and products are available
  implementing the quantum resistant suite, we will rely on current
  algorithms. For those partners and vendors that have not yet made the
  transition to Suite B elliptic curve algorithms, we recommend not
  making a significant expenditure to do so at this point but instead to
  prepare for the upcoming quantum resistant algorithm transition.

  For those vendors and partners that have already transitioned to Suite
  B, we recognize that this took a great deal of effort on your part,
  and we thank you for your efforts. We look forward to your continued
  support as we work together to improve information security for
  National Security customers against the threat of a quantum computer
  being developed. Unfortunately, the growth of elliptic curve use has
  bumped up against the fact of continued progress in the research on
  quantum computing, which has made it clear that elliptic curve
  cryptography is not the long term solution many once hoped it would
  be.  Thus, we have been obligated to update our strategy.

  It is important to note that we aren't asking vendors to stop
  implementing the Suite B algorithms and we aren't asking our national
  security customers to stop using these algorithms.  Rather, we want to
  give more flexibility to vendors and our customers in the present as
  we prepare for a quantum safe future. Where elliptic curve protocols
  are to be used, we prefer Suite B standards be used to the fullest
  extent possible as they have a long history of security evaluation and
  time tested implementation that newer proposals do not yet have.

There are links to documents for implementers and users as well.

https://www.iad.gov/iad/programs/iad-initiatives/cnsa-suite.cfm


Choosing an optimal generator for an irreducible polynomial over a binary field? I am reading the Certicom tutorial “An Example of an Elliptic Curve Group over F2m ” and I have following questions:

How do they assume that generator $g = (0010)$ is correct for this polynomial?
How can/should one choose an optimal generator from a group of generators for a specific field?

What you need is a primitive polynomial of degree $m$ (for using with $\operatorname{GF}(2^m)$).

This is an irreducible polynomial whose roots have maximal multiplicative order $2^m-1.$

There are tables of these, at least one is guaranteed to exist for each degree. Alternatively they can be found by randomised methods. Use a polynomial factorisation algorithm to get an irreducible of degree $m$, say $f(X)$  and then check that $$X^i \bmod f(X)\neq 1$$ for any proper divisors $i,~1<i<2^m-1$, of $2^m-1.$

If you know one such polynomial with a root $X$ then its roots are $X,X^2,\ldots , X^{2^{m-1}}$ each with multiplicity 1. By trying $X^u$ with $\gcd(u, 2^m-1)=1$ you may find a lower weight polynomial to enable efficient implementation, just write the new polynomial as
$$
f_u(z)=(Z-X^u)(Z-X^{2u})(Z-X^{2^{m-1}u})
$$
and simplify over $\operatorname{GF}(2).$

Edit: Error in last equation corrected.


Any benefit to encrypting IV and MAC in a mode like AES-GCM or ChaChaPoly? Would there be any benefit to symmetrically encrypting the IV and MAC in an AEAD mode of operation? More specifically would this prevent someone from exploiting the accidental use of a duplicate IV with the same key? Normally with most AEAD modes (and XOR-based stream ciphers) same IV + same key + different message = bad.

Example: let's say you have AES-GCM with a 64-bit IV and a 64-bit MAC / authentication tag. Now let's say after encrypting with AES-GCM you take the IV and MAC together and encrypt both with AES (using the same key or a derived key) in ECB mode (one 128-bit block) and send AES(IV|MAC) instead of sending the IV and MAC. Then at decrypt you AES decrypt that block and then run GCM with decryption and authentication check as usual.

If you duplicate an IV with a different message, the AES(IV|MAC) result will be different and since the IV and MAC are not visible in plaintext they can't be used by the attacker... right? (Obviously if both message and IV are identical the attacker can see that there was a duplicate of the same message, but that doesn't help them attack authentication for other messages.)

Other than costing a little bit of extra CPU does this help security? Am I missing something? This feels too simple to be novel.

If a (nonce, key) is reused with two distinct messages A and B, an attacker can learn A⊕B = E(A)⊕E(B).

So, if either plaintext is known, the other one can be immediately decrypted.

This is why nonce-misuse resistant schemes require two passes: a first pass to compute a hash of the message, the second one to perform the actual encryption with an IV, and possibly a subkey derived from that hash.


Is BBS+ 1. a multi-messages signing protocol or 2. a group signature signed by a member of a group anonymously? There's no doubt that the BBS Signature was born from this classic Short Group Signature paper in 2004. It's capable of Zero-knowledge.
In the paper, section 5, it describes how a member of a group, can sign a message, without revealing which member signed it. But, this group signature can be verified that it was signed by a member of a group (anonymously) through a group public key $gpk$.
However, later, there are some works improving BBS into BBS+. It was first modified and named in Constant-Size Dynamic k-TAA by Au et al. BBS+ was touched again in Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited. Nevertheless, in those two papers mentioned above, it seems the BBS+ scheme is a multi-messages signing protocol. It takes messages $m_1, m_2, m_3,..., m_L$ and produces a single signature $\sigma$.
It can create a proof of knowledge $SPK$ on top of signature $\sigma$, with some messages $m_i$ revealed.
Yet, in work on Enhanced Privacy ID from Bilinear Pairing by intel, it seems their BBS+ scheme becomes as a member of a group signing the message anonymously, same as Short Group Signature paper in 2004.
Therefore, I'm confused about BBS+ protocol. Whether it is

a multi-message $m_1, m_2, m_3,..., m_L$ signing protocol producing a single signature $\sigma$ with signature proof of knowledge $SPK$

or

a group signature signed by a member of a group anonymously using a group public key $gpk$?

I've always used it as #1. Hyperledger Ursa has an implementation in Rust
(see https://github.com/hyperledger/ursa/tree/master/libzmix/bbs).
However, it is a type of group signature which allows the type of signing of multiple messages.
When someone says to me group signature I immediately think your #2. If we look at a paper written by David Chaum (https://chaum.com/publications/Group_Signatures.pdf), He mentions
group signatures are a "generalization" of the credential/ membership authentication schemes, in which one person proves that he belongs to a certain group.
So in effect, the proof being made is proving the messages belong to the signature and the signature allows for a proof of knowledge to be made.
It's a different use of a crypto primitive.
Hope this helps


Why concatenate the key a second time in HMAC? On Wikipedia it is said that HMAC is basically (without taking into account padding):

$H(key\ \Vert\ H(key\ \Vert\ message))$

where $\Vert$ denotes concatenation.

I understand the need to hash twice, but why concatenate the key a second time in the outter hashing?

Why not simply hash twice, but without reusing the key, like this:

$H( H(key\ \Vert\ message))$

A bit like Bitcoin's double-SHA, rumored to be done to prevent length-extension attacks.

As pointed in the question, with common Merkle–Damgård hashes like SHA-256, $H(key\ \Vert\ message)$ is vulnerable to a length extension attack, where $H(key\ \Vert\ message\ \Vert\ pad\ \Vert\ extension)$ can be computed knowing $H(key\ \Vert\ message)$ and the length of $key\ \Vert\ message$ (with $pad$ trivially determined from that), for any known $extension$. Indeed, $H( H(key\ \Vert\ message))$ is enough to block that simple attack.

One good reason to NOT use $H( H(key\ \Vert\ message))$ as a MAC is that we do not have a security proof for that construction, when we have one for HMAC since the origin. Even better, the modern security proof of HMAC gives an argument that HMAC is secure even if the compression function in the underlying hash has properties insufficient to make the hash collision-resistant. In particular, HMAC-MD5 still seems quite strong, even though collision-resistance of MD5 is badly broken.

Both of these security proofs require two hashes each starting with (different variants of) the key. Intuitively: there's a similarity to adding rounds in a block cipher, which makes recovering the key or otherwise breaking the cipher much harder; the outer hash sorts of re-enciphers the result of the previous one.


Security implications of using hash as a MAC What are the security risks, if I use a hash function $H$ such that $Y=H(K||M||N)$ where $K$ is a secret key, $M$ is a message, $N$ is a nonce and $||$ is concatenation operation (where the length of $K||M||N$ is fix and is less than or equal to block size of the hash $H$)?

In general, the construction $H(K||M||N)$ where $H, Y, N$ are known to an attacker is arguably no more secure than $H(K||M)$, which we already know to be broken. For that latter construction, we can easily forge a MAC of the form $K||M||PADDING||Z$ for some message $Z$.

This same attack would apply to the construction proposed in the question, except the forgery would be of the form $K||M||N||PADDING||Z||N$. This attack is feasible on many currently used hash functions, however, is not feasible on the new SHA-3.


Why is it said that if we know few bits of pseudo random sequence we can predict the whole of it? I am new to this cryptography and in the source from which i study it is said that if we know the first few bits of a pseudo random sequence we can predict the whole of it.How is it possible?
The source:http://www.youtube.com/watch?v=NjedHm04ETM
move to 7min 40sec and this is the source.

All psuedo random generators keep some limited state to calculate the next number in the sequence. you can think of it like a function $\delta(S)= \{output, S'\}$ with $S$ the internal state of the generator and represented by a finite number of bits.

This means that the number of states is limited (though it can be very big: a standard mersenne twister holds 2500 bytes of state)

As such if you get $n$ bytes of output with $n$ is larger than the number of bytes in the state then you can reasonably predict the current state of the output given enough time.

Note that if you group 256 bytes of output together and pass it though a sha-256 then it will take a very long time for you to restore first the original output of the generator and then the state when you know only the hash output. This is exactly how a secure PRNG works.


baby-step, giant-step vs Pollard-rho I'm studying algorithms that solve the discrete logarithm problem over elliptic curve. Reading online, it seems that people use the bsgs algorithm when the order of the curve is "low" and P-rho when it's "high".

But nobody says how much is "low" and "high", where I can find some good estimation?
Is this true?

BSGS algorithm requires huge storage space for curves with large order. This storage requirement usually exceeds the total available storage capacity across the whole world by several orders of magnitude.

So, finding an estimation depends on how much memory is available for you. Since you need to store all the generated points in a hash table for BSGS.
If each point requires k-bits of storage and the curve is of order n, the storage requirement is $k * \sqrt{n}$ bits.

Eg: If each points require 32 bits of storage and the curve has order $10^9$ then total storage requirement is approxmiately 4 GB.


How does an oblivious test of plaintext equality work? Assume an ElGamal Cryptosystem. Assume a set of three players, $P_1$, $P_2$ and $P_3$. The private key $x$ is shared among the players. The player $P_1$ has a piece of the private key $x_1$, $P_2$ has the piece $x_2$ and $P_3$ has $x_3$.

Assume the following messages, $m_1$ and $m_2$.

Let $E(m_1)$ and $E(m_2)$ be two ElGamal ciphertexts.

The elements $r_1$ and $r_2$ are random numbers, and $y = g ^ x$, where $g$ is a generator of the group.

Encrypted message m1: $E(m_1) = (g ^ {r_{1}},   m_1 \cdot y ^ {r_{1}}) = (a_1, b_1)$

Encrypted message m2: $E (m_2) = (g ^ {r_{2}},   m_2 \cdot y ^ {r_{2}}) = (a_2, b_2)$

The question is: how can the holders (players) of the private key execute the oblivious test of plaintext equality proposed by Schnorr and Jakobsson? Specifically, how can the three players can determine if $m_1 = m_2$ without revealing the messages?

PS: The protocol oblivious test of plaintext equality proposed by Schnorr and Jakobsson is in the article entitled "Efficient Oblivious Proofs of Correct Exponentiation".

You've messed up your question. Since the two ciphertexts both use the same r, anyone can easily check if $m_1=m_2$. This is not the interesting case.

But if the two ciphertexts are $(a_1, b_1) = (g^{r_1}, m_1 y^{r_1})$ and $(a_2, b_2) = (g^{r_2}, m_2 y^{r_2})$, then the tuple $(g, y, a_1/a_2, b_1/b_2)$ is of the form the mentioned paper deals with.


Strategy for random CTR initial counter values Alice has a secret key which she uses to encrypt messages in CTR mode. CTR mode is critically vulnerable to counter reuse, and Alice has a problem: she has terrible memory and no pen to write anything down. She has good enough memory to send one message, but between messages she sometimes forgets the counter values that she has used. She has the key tattooed on her forearm. She doesn't have a watch that would give her a convenient non-repeating input. She has a balanced coin which she can flip to generate random numbers. She wants to ensure that she won't reuse a counter value, because Eve is lurking around, makes xoring things a hobby and she can even suggest some plaintexts for Alice to encrypt.

In other words, I have an embedded device which has some code and a key in ROM, and a hardware RNG, but no clock (unlike Making counter (CTR) mode robust against application state loss) and no persistent rewritable storage (unlike CTR mode nonce with aggressive key rotation policy). This device emits messages encrypted with AES-CTR, using that one key in ROM. Integrity of these messages is beyond the scope of this question. The device can lose power at any time, and at that point, it loses track of the previous counter value. It typically sends many messages between resets, but in some circumstances an attacker could arrange to cut power off at inopportune times.

What is the best strategy to avoid counter reuse, and after how much traffic does the probability of counter reuse get non-negligible? For example, I can generate a new initial counter for every message, or a new initial counter on every reset. I can start each message at the current counter value, or use a scheme such as 96 bits of randomness and a per-message counter starting at 0. (No message is more than $2^{32}-2$ blocks long.) Does this make a difference in the probability of collisions?

Let $2^m$ be the average message length in blocks.

When using an independent random nonce for the whole 128-bit IV of each block, you would expect a collision after $2^{64}$ blocks, i.e. $2^{64-m}$ messages. (But you double the data size.)

When using a 96-bit nonce and a 32-bit counter, you would expect a nonce collision after $2^{48}$ messages. This is better than the above if $m > 16$ and of course more efficient because fewer nonces are generated.

When using a 128-bit initial nonce for the message that gets incremented for subsequent blocks, the math gets a bit trickier. The probability that two $2^m$-block messages get overlapping counter ranges is about $2^{-(128-m-1)}$ because they overlap when the second message has an initial nonce within $2^m$ of the first in either direction. That would mean at least $2^{64 - (m+1)/2}$ messages, which is better than either of the above if $1 < m < 32$.
The exact message length distribution affects how many blocks vs. messages can be sent, but normally there's a practical maximum on message size which is not orders of magnitude larger than the average, so changing $m$ above to reflect that would give a worst case estimate.

Letting the next message continue from the previous nonce until a reset would be the same as above, but with longer "messages" equal to the concatenation of all those sent between resets. With $2^k$ messages between resets that's at least $2^{64-(m+k+1)/2}$ expected sessions before a collision, i.e. $2^{64-(m-k+1)/2}$ messages, which is better if $k>0$.
However, if you assume an attacker who can control when resets happen, it becomes worse. After each message the attacker can either cause a reset (if no collisions are in the near future) or let the counter continue its journey towards a collision. Reusing the $k$ from above for a normal reset frequency the attacker can expect, two resets would have about a $2^{-(128-m-k)}$ chance of collision so the expected number of resets before collision is on the order of $2^{64-(m+k)/2}$, which is worse than the previous option.

Use the 96-bit nonce and 32-bit counter construction, but keep track of where the previous message ended. As long as there's space for the message within the 32-bit block defined by the nonce, select the IV so that it continues from where the previous message ended. If the block runs out or the device has been reset since the previous message, choose a new one randomly.
In the best case you stuff $2^{32-m}$ messages per nonce and get a collision only after $2^{48+32-m}=2^{80-m}$ blocks, which is better than any of the above. Even in the worst case where an attacker resets the device after each message you are guaranteed the $2^{48}$ expected messages before collision.

In practice I would choose the 32-bit counter, with or without the optimization for continuing from a previous message – i.e. either 2. or 5. above. There's no attack that can make it worse than $2^{48}$ messages and the math is easy.


What is the difference between computational complexity and time complexity? Computational complexity seems to be used quite a lot in cryptographic papers.

The time complexity I am referring to is the one from Computational Complexity Theory.

Are these two the same things?

There are many different cost models for computation, of which time (measured by some clock) is only one.

How many seconds must we wait to run this algorithm? [time, measured in seconds]
How many CPU cycles does it cost run this algorithm? [time, measured in CPU cycles]
How many bits of memory does this algorithm use? [space]
How many NAND gates does it take to represent this algorithm as a logic circuit? [NAND metric]
How many bits are in the description of the program, how many bits of memory does it use, and how long does it take to run assuming a bit operation and a memory reference each take one unit of time? [RAM metric]
How large a silicon die does it take to run this algorithm, and for how long must we power it? [AT metric]
How many joules of energy will it cost to run this algorithm? [energy]
How many yen does it cost to run this algorithm? [pocketbook]

The answer to each of these questions may be a complicated function of the size of the input, or of the input itself.  For example, the worst-case RAM cost of quicksort is a quadratic polynomial function of the input size, $an^2 + bn + c$, for some coefficients $a$, $b$, and $c$ that depend on exactly how we write it, while on optimal inputs the RAM cost is $u n + v$.

Complexity theory is usually not concerned with the coefficients $a$, $b$, and $c$ but with the degree of the polynomial, $O(n^2)$ vs. $O(n)$, or other qualitatively different shapes of growth curves like $O(2^n)$, $O(\log n)$, $O(A^{-1}(n))$ where $A(n)$ is the Ackermann function, etc., in whichever cost model you're considering.

Computational complexity may refer to any of the cost models; time complexity usually just refers to the time-based ones—for example, the time complexity of heap sort is $O(n \log n)$ while the space complexity is $O(n)$, assuming memory access cost is constant, yet in the more realistic AT metric the best-known cost of sorting a length-$n$ array of $n$-bit numbers is $n^{1.5 + o(1)} = (n\sqrt n)^{o(1)}$ owing in part to communication costs on a silicon mesh.

The last three cost models are the really important ones for studying cryptanalytic attacks, because they are connected to real-world economic costs of attacks: the AT metric, which is easy to formalize and study for algorithms, is a good proxy for the energy cost, and energy cost essentially determines pocketbook cost.


Question about Modular Arithmetic I have a question about Modular Arithmetic Cryptography.

How do I calculate $(-5)^{-3}$ or $(-5)^{-4}$ (even or uneven exponent)?

What do I have to do first here ? I can’t ignore the minus?!?

(-5)^(-x) = (-5)^((-1)*x) = ((-5)^(-1))^x

The above link also has a good "Computation" section.


Prove the Security of Schnorr's Signature Scheme I know that Schnorr's signature is important since it is one of the most compact signature schemes whose security has been proved in the random oracle model.

Now, I want to know if such proof is easy and someone could explain it to me, or maybe just point out the main steps of the proof.

For the sake of clarity, the Schnorr's signature scheme I know is the one presented by the Wikipedia page Schnorr signature:

Choosing the parameter: all users of the scheme agree on a group $G$ of prime order $q$, in which the DLP is hard (e.g. $G$ is a Schnorr Group, or an Elliptic Curve of prime ordere $q$), a generator $g \in G$, and on a hash function $H:\{ 0,1 \}^* \rightarrow \mathbb{Z}_q$
Key generation: the signer chooses a secret key $x \in \mathbb{Z}_q$ and makes $y=g^x$ public.
Signing: to sign a message $M$, the signer chooses a random $k \in \mathbb{Z}_q - \{ 0 \}$, computes $r=g^k$, lets $e=H(M||r)$, and lets $s=k-xe$. The signed message is $(M,(s,e))$.
Verifying: anyone can verify that $(s,e)$ is a signature on $M$ by computing $r_v = g^s y^e$ and $e_v = H(r_v||M)$; if $e_v = e$ the signature is verified.

Now, the proof of correctness is quite straightforward (i.e. if one follows the protocol, then the verification equation $e_v = e$ holds), but I don't see how to formally prove the security (i.e. if one doesn't follow the protocol, it is very unlikely that the verification equation will hold, hence it is hard to forge a signature on a message without knowing the secret key).

Any hint or suggested readings will be appreciated!

Pointcheval and Stern [PS00] proved that the Schnorr signature is existentially unforgeable under chosen-message attacks (EU-CMA) in the random oracle model assuming that the discrete-logarithm problem$^1$ (DLP)  is hard.

On a high level, the reduction (from DLP to the EU-CMA-security of Schnorr signature) works as follows. The reduction algorithm $\mathcal{B}$ embeds its DLP challenge $g^\alpha$ into the public key (i.e., sets $y=g^\alpha$) and then  uses the oracle-replay attack to obtain, from the forger $\mathcal{F}$, two different forgeries that share the signing randomness ($r=g^k$). This enables $\mathcal{B}$ to solve for $\alpha$.

For simplicity, let's first focus on a weaker model called the existential forgery under no-message attacks (EU-NMA) and a strong forger that is always successful. We show that a strong forger $\mathcal{F}$ that breaks the Schnorr signature in the EU-NMA model making at most $q$ queries to the random oracle $H$ (i.e., a $(1,q)$-adversary) can be used to break the DLP with probability $1/q$.

This requires two rounds of simulation:

Round 1. $\mathcal{B}$ runs $\mathcal{F}$ on $(G,g,g^\alpha)$; the random oracle $H$ is simulated in the standard manner (i.e., lazy sampling plus a table to ensure consistency). At the end of this round $\mathcal{F}$ returns a forgery $(M_0^*,(s_0^*,e_0^*))$ where $e_0^*=H(M_0^*\|r_0^*)$. For simplicity, it is assumed that $\mathcal{F}$ made the random oracle query $H(M_0^*\|r_0^*)$.
Rounds 2. Now $\mathcal{B}$ rewinds $\mathcal{F}$ to the point where it made the random oracle query  $H(M_0^*\|r_0^*)$ in Round 1 (the "critical" point) and re-runs $\mathcal{F}$ but answering the fresh random oracle queries independent of the previous round.$^2$ This constitutes the oracle-replay attack. At the end of Round 2, $\mathcal{F}$ returns a forgery $(M_1^*,(s_1^*,e_1^*))$ where $e_1^*=H(M_1^*\|r_1^*)$.

There is a non-negligible probability (at least $1/q$, but this has to be argued rigorously) that in Round 2 too $\mathcal{F}$ forges at the critical point (i.e., $M_1^*=M_0^*$ and $r_1^*=r_0^*$) but that the responses to the random oracle query $H(M_0^*\|r_0^*)$ were different (i.e., $e_1^*\neq e_0^*$). The intuitive reason is that $\mathcal{F}$ has to forge on some query, and in the worst case it chooses this point randomly. If this is indeed the case, then
  $$s_0^*=k_0^*-\alpha e_0^* \text{ and } s_1^*=k_0^*-\alpha e_1^*,$$
(as $r_1^*=r_0^*$, but $e_1^*\neq e_0^*$) and $\mathcal{B}$ can solve for $\alpha$
 $$\alpha=\frac{s_1^*-s_0^*}{e_0^*-e_1^*}.$$

The above argument can be strengthened to accommodate a general $(\epsilon,q)$-adversary in the EU-CMA model. To simulate the signing oracle (for the EU-CMA model) the reduction only has to program the random oracle appropriately.$^3$. Bounding the success probability of the reduction for the  general adversary (that is successful with a non-negligible probability $\epsilon$) is quite technical and uses the so-called forking lemma. To be precise, it is shown in [PS00] that an $(\epsilon,q)$-forger $\mathcal{F}$ that breaks the Schnorr signature in the EU-CMA model can be used to break the DLP with probability $O(\epsilon^2/q)$.$^4$

Footnotes.

$^1$The DLP on a cyclic group $(G,g,q)$ requires finding $\alpha\in\mathbb{Z}_q$ given $g^\alpha\in G$.

$^2$That is, the queries up to the critical point are answered consistently, but the fresh queries after the critical point are answered independently of Round 1.

$^3$To generate a signature for a message $M$, select $e,k\in_R\mathbb{Z}_q$, set $r=(g^\alpha)^e\cdot g^k$, and program the random oracle to set $H(M\|r)=e$. Return $(M,(e,k))$ as the signature. It is not difficult to see that the message is valid, and from the right distribution.

$^4$It was later shown in a series of works [PV05,GBL08,Seu12] that the loss is tightness of $\epsilon/q$ is inherent (conditioned on the assumption that the so-called one-more discrete-logarithm is hard).

References.

[PS00] David Pointcheval and Jacques Stern. Security arguments for digital signatures and blind signatures. Journal of Cryptology, 2000.

[PV05] Pascal Paillier and Damien Vergnaud. Discrete-Log-Based Signatures May Not Be Equivalent to Discrete-Log. ASIACRYPT 2005.

[GBL08] Sanjam Garg, Raghav Bhaskar, and Satyanarayana V. Lokam. Improved Bounds on Security Reductions for Discrete-Log Based Signatures. CRYPTO 2008.

[Seu12] Yannich Seurin. On the Exact Security of Schnorr-Type Signatures in the Random Oracle Model. EUROCRYPT 2012.


Registration Code Entropy I'm designing a system where a registration code is generated, it is sent to the user, and then the user registers himself/herself based on this registration code into the system.

The registration code has some expiration time, so that if the user doesn't register within the validity period, the registration code will expire a new registration code needs to be generated.

Is there any standard that would suggest what should be the entropy of such a registration code?

On one hand, it should be long enough so that an attacker can't guess it.
On the other hand, it should be short enough so that the user can enter it easily into the system.

There are length recommendations within the HMAC-based One-time Password algorithm, which is simply explained here, and the detail is here.

The important part of this is:-

  The recommendation is made that persistent throttling of HOTP value verification take place, to address their relatively small size and thus vulnerability to brute force attacks.

Just as a cash machine with a 4 digit PIN. They get angry after 3 bad attempts.  RFC 4226 suggests an increasing delay after each registration failure. If you go with the default 6 digit code, you'd get a tad below 20 bits of entropy. But that's to be viewed in conjunction with throttling.  The code would simply look like 872921.

Also there are RSA hardware tokens that use 6 digits, but with a validity period of only about a minute. Adjust accordingly...

Note. This form of HOTP does not mathematically link the code to the time. You'd have to implement that check separately. I don't want to dwell too much on the mechanics of generating/accepting the token. I'm focusing on the IETF recommended entropy aspect of the question within a rate limited environment.


Protocol Design for IoT devices having PSK using AES-GCM Handshake:

  1) Client To Server: "AES-GCM(Client_random_128bit,client_iv,psk),client_id,tag,client_iv"

  2) Server To Client: "AES-GCM(Server_random_128bit,client_iv++,psk),tag

  Client_key_256bit = Client_random_128bit + Server_random_128bit

  Server_key_256bit = Server_random_128bit + Client_random_128bit

Communication:

$c_{iv}=1, \space s_{iv}=1$

  Client_Encrypted_Message = AES-GCM(Message,$c_{iv} \space$,Client_key_256bit),$c_{iv} \space$,tag;

  Server_Encrypted_Message = AES-GCM(Message,$s_{iv} \space$,Server_key_256bit),$s_{iv} \space $,tag;

For every Subsequent Message $c_{iv}$ and $s_{iv}$ is incremented by $1$ by client and server respectively.

Client and Server makes sure every new massage's $c_{iv}$ or $s_{iv}$ is greater than the previous massage's else the session is terminated. (tcp protocol)

This is because I don't know any other way to make sure the massage/command is executed only once or to prevent replay attack.

Is there better way to do this considering the device can't keep track of time?

Would it be OK if the $iv$ used in handshake gets repeated considering the plain text is a random number?

Is this secure enough?

Here client is referred to iot_device and device_id as client_id.

psk is referred to pre_shared_key configured in the device at company and known to server.

Would it be OK if the iv used in handshake gets repeated considering the plain text is a random number?

No, it would definitely not be OK.  Reusing the IV will allow the attacker to recover the internal GCM H value - this will allow the attacker to make arbitrary modifications to encrypted messages.

For static keying (or anywhere else where it's difficult to avoid repeating the IV), GCM might not be the correct solution.  Perhaps AES-SIV would work better?


Client authentication on limited hardware I'm developing a authentication and authorization protocol for a Bluetooth device. The device should communicate with an Android app and needs to be able to authenticate the app during the connection phase. Some kind of secret or asymmetric pair  is therefore needed to be shared by the app and the Bluetooth device. As apps can be reverse-engineered we need to be able to update this secret.

RSA was the first solution that came to mind. The device can store the public key of some root certificate and then verify the signature of the app certificate like during TLS. The device keeps a list of valid certificate fingerprints.

However, the Bluetooth device is too weak to implement RSA. I need something (much) cheaper. Is there any such protocol?

I'd suggest that you clearly define which kind of Bluetooth device you are using, more specifically what its capabilities are with respect to processing power, etc. Another question, can you enter a number on a bluetooth device (e.g., for a PIN-based authentication, for example)? From what you're writing, I'd assume that RSA won't be a plausible solution, since the smallest key length the constrained bluetooth device will have to deal with is 1024 bit (2048 is actually recommended). ECC is likely to prove unsuitable as well, since despite the fact that the key length is much smaller, the device has to be able to deal with ECC algorithm which may be quite inefficient without the proper hardware support of even not supported by the device at all. In my experience, using ECC instead of RSA on Android platform does not necessarily entail a performance gain, see the discussion here.
Another important conceptual question is: what are the security goals/requirements in your specific case and against which attacker the system has to be secure (the so-called attacker model)?
Taking into account what you've written in your question, I would assume that authentication using one-time PIN may be a better option than using full-fledged certificate-based authentication based on RSA (or on ECC).


Why use a separate key for each file? I'm trying to understand "Option 2: Using a Client-Side Master Key" from https://docs.aws.amazon.com/AmazonS3/latest/dev/UsingClientSideEncryption.html#client-side-encryption-client-side-master-key-intro.

Basically, it seems that the one-use encryption key is generated, and used to encrypt the file, and then the key is encrypted by the master key and attached as metadata.

What is the benefit of using a separate key for each file when having the master key is the only thing needed for decryption either way, be it in one step or two?

The source quoted says:

  The client-side master key you provide can be either a symmetric key or a public/private key pair.

In the later case, the main benefit of using a separate symmetric key is that only the public key (rather than secret information known beforehand) is needed to encrypt a file. That symmetric key is then forgotten, hence the need to make a separate one for new files. Also, the symmetric encryption (made possible by the extra key) is much faster and less size-expanding than the asymmetric one. This is hybrid encryption at its best.

There are other benefits, that still apply when the master key is symmetric:

Assuming all the encrypted files are public, using a separate key for each file gives the option to release the key allowing decryption of a single particular file, rather than the master key which would reveal all files.
Using a separate key for each file reduces the amount of data enciphered using the same symmetric key; this works towards staying below a safe limit per key after which the encryption used might become weaker (e.g. for 3DES in CTR mode, we can distinguish sizably better than random if 16GByte enciphered with the same key was originally all-zero or compressed video, including when split across multiple files with unique IV and no keystream reuse).
As pointed by Ilmari Karonen in comment, it might sometimes be desirable to change the master key, e.g. if it's derived from a user-supplied password that the user wants to change, without fully decrypting and re-encrypting all the files. Using separate file keys is one way to enable this.


Probability for Vigenere cipher given distribution of key lengths Given the exact same question and answer here: https://crypto.stackexchange.com/a/37212/40935.

How does one derive/figure out (using equation, combination of equations, or "knowledge") the bold marked parts in the following:

  How does one know to put 0.5 and 1/(26^2) in the following places:

  Pr[C=ff | M=dd] x Pr[M=dd] = [1/26 x 0.5 + 1/(26^2) x 0.5] x 0.2
  Pr[C=ff | M=de] x Pr[M=de] = [0 x 0.5 + 1/(26^2) x 0.5] x 0.8

I expected the conditional part calculations to be:

  Pr[C=ff | M=dd] = [1/26 x 0.5 + 1/(26) x 0.5]
  Pr[C=ff | M=de] = [0 x 0.5 + 1/(26) x 0.5]

So I would like an "equation" possibly based on the law of total probability and/or Bayes' Theorem (or something which I do not know about), such that I can see the symbolic manipulation/calculations which leads to the simple substitution of values as described above.

Okay, let's take this one apart piece by piece, with $l$ indicating keylength:

You have:

$P(l=1) = P(l=2) = 0.5$
$P(m=dd) = 0.8, P(m=de) = 0.2$
You want to know $P(c=ff)$
Implicitly, we assume that the keys are uniform random (actually not true for Vigenere with actual keywords, but there is no statement in the question).So for any combination of $c,m$, we get a probability of $1/26$ if $l=1$ and $1/26^2$ if $l=2$
Implicitly, the key is independent of the message - pretty standard assumption. And of course $l$ is independent as well.

So let's look at the case $l= 1$. Formally we express that as $P(.|l=1)$. This is a conditional probability, because we place the condition $l=1$.

So: $P(c=ff|l=1) = P(c=ff| l = 1 \cap m=de) + P(c=ff | l = 1 \cap m=dd)$
$  = 0 * 1/26 + 1 * 1/26$   (the $0$ indicates "this is not possible", the $1$ indicates "this is possible with exactly $1$ combination")

Analouge: $P(c=ff|l=2) = P(c=ff|l=2 \cap m=de) + P(c=ff|l=2 \cap m=dd)$
$ = 1 *  1/26^2 + 1 * 1/26^2$ (both possible with exactly one combination, so both $1$s)

Now, we want to get $P(c=ff) = P(c=ff|l = 1) \cdot P(l=1) + P(c=ff|l=2) \cdot P(l=2)$
$= (0+1/26) \cdot 0.5 + (1/26^2 + 1/26^2) \cdot 0.5 = 0.5(1/26 + 2/26^2)$
We just use, that the events $l=1$ and $l=2$ are mutually exclusive. And they happen to be the only possibilities we have to consider.

In the end, we get to the same conclusion as your other questions: You missed the condition on $l$ in your first approach. And then in your solution you incorporated it - but missed out on expressing it in the formulas correctly.


Is a tree of CSPRNGs secure? Given two CSPRNGs $A$ and $B$ (of possibly the same family/algorithm), where $A$ is properly seeded from a high-entropy source, can $A$ be used to seed $B$ without compromising the security of either? Moreover, could a tree of such CSPRNGs rooted at $A$ be formed such that all generators can be used independently without revealing information about any other?
My loose attempt at proving this claim uses properties/assumptions gathered from here, here, and here:

Let $A$ be the root of a tree of CSPRNGs, each seeded by its parent. Assume that given the states of a subset of the non-root CSPRNGs, one can learn some secret property of one of the other non-root CSPRNGs not in the set.
Let $A'$ be an unknown source of randomness. By constructing a similar tree from its output and knowing the states of all non-root CSPRNGs, one can test for the above property to distinguish $A'$ from true randomness with non-negligible probability. This contradicts the indistinguishability of the CSPRNG, so it must be infeasible to find such a property.

Also (less rigorously):

Let $A$ be the root of a tree of CSPRNGs, each seeded by its parent. Assume that given the seeds and states of a subset of the non-root CSPRNGs, one can learn some secret piece of information about the root $A$. Then one can predict with non-negligible probability a bit of $A$'s past or future output other than the known seeds. This contradicts the security of the CSPRNG, so no such information can feasibly be obtained.

Together, these would mean that any CSPRNG in the tree is secure, needing only to trust the CSPRNGs in the path from it to the root.
Are these proofs and my conclusion correct for general CSPRNGs?

Note: A trivial counterexample for non-cryptographic PRNGs is the linear congruential generator, for which $A$ and $B$ would share identical states and produce identical results.

Yes, this is basically the Goldreich-Goldwasser-Micali construction of a PRF from a PRG. All leaves of the tree appear independently random, and furthermore the construction works even if the tree has exponentially many leaves (note that it is possible to compute the value at one leaf without computing the entire tree, by focusing just on the root-to-leaf path).

You can find a formal proof of security for this construction in section 6.3 of my book (PDF link).

  Goldreich, Oded, Shafi Goldwasser, and Silvio Micali. "How To Construct Random Functions." Foundations of Computer Science, 1984. 25th Annual Symposium on. IEEE, 1984.


How to convert from curve25519 33 byte to 32 byte representation According to the curve25519 paper a x25519 public key can be represented in 32 bytes.

The x25519 library I'm using (bouncycastle) however gives me a 33 byte representation according to this standard.

My 33 byte hex representation always begins with the hex 02 or 03.

How do I convert a 33 byte representation to a 32 byte representation?

And when I am provided with a 32 byte representation, how do I know whether to prepend 02 or 03 to it to convert it back to a 33 byte representation?

The second link you provided actually contains all the information you need:

  Note that ECPoint.point differs from the definition of public keys in [Curve25519] in two ways: (1) the byte-ordering is big-endian, wich is more uniform with how big integers are represented in TLS, and (2) there is an additional length byte (so ECpoint.point is actually 33 bytes), again for uniformity (and extensibility).

Beside of those two difference, the rest is the same.

Now, from BouncyCastle code, you can see that:

PO[0] = (byte)(normed.getCompressionYTilde() ? 0x03 : 0x02);
System.arraycopy(X, 0, PO, 1, X.length);

So, you are right, it will always begin with 0x03 or 0x02 and the actual $X$ value is contained as being the 32 last bytes on the getEncoded() return value.
(According to the draft you linked, it will probably be in big-endian, so you might need to convert them into little-endian depending on why/how you need them.)