Actual need of IKEv1 Aggressive mode I know that IKEv1 Aggressive mode is not secure as ID payload is sent out in plain text. Even though it is insecure, it still exists! Can someone tell why exactly do we need Aggressive mode? What is it that Main mode cannot do and Aggressive mode can (other than speed)
From what I know Aggressive mode is to be used for Remote Access VPNs but I am not able to understand the requirement behind this.

Even though it is insecure, it still exists! Can someone tell why exactly do we need Aggressive mode? What is it that Main mode cannot do and Aggressive mode can (other than speed)

Well, the original reason behind Aggressive Mode was, in fact, performance.  Specifically, in used fewer round trips to establish the connection than Main Mode.
The original designers of IKE were well aware that Aggressive Mode had lesser security goals than Main Mode; however they did not know how important those goals were, compared to how important connection set up was.  Hence, they included both options.
When they reworked IKE in IKEv2, they reconsidered the options; they decided that the trade offs inherent in Aggressive Mode were a bad trade off (and telling people to support multiple 'modes' was also not a great design); they were able to rework things to get the performance advantages of Aggressive Mode, and keep the security goals of Main Mode.


Formal Information-Theoretic Key Expansion Definition Is there a formal definition for a protocol that expands keys that are pre-shared among 2 or more parties?
How about an informal definition?

Example:

Alice and Bob pre-share a $n$-bit string $k$.  After running algorithm $\Pi$ Alice and Bob have a common ($n$+$q$)-bit string $k'$, where $q>0$.  In addition Eve learns nothing about $k$ or $k'$. Eve is an an eavesdropper on the channel between Alice and Bob with unlimited computational power.  i.e. If $P_x$ are the odds of Eve learning $x$ then $P_k\le \frac{1}{2^n}$ and  $P_{k'}\le \frac{1}{2^{n}}$.

NIST SP-800 108 seems to have a semi-formal definition in chapter 5.0:

Section 1:

  A key derivation function iterates a pseudorandom function (ed: PRF) $n$ times and concatenates the outputs until $L$ bits of keying material are generated, where $n = ⎡L/h⎤$.

Section 2:

  For each of the iterations of the PRF, the key derivation key $K_I$ is used as the key, and the input data consists of an iteration variable and a string of fixed input data.

But I must admit that this seems more a description of the inner workings of the described KDF's than a formal definition of one, if such a thing exists.

As about any KDF actually works this way it remains to be seen if this isn't enough of a formal description.

The original HKDF paper has this more formal definition:

  Definition 5: A key derivation function (KDF) accepts as input four arguments:

  a value $\sigma$ sampled from a source of keying material (Def. 6),
  a length value $l$,

  and two additional arguments,

  a salt
  value $r$ defined over a set of possible salt values
  and a context variable $c$,

  both of which are optional, i.e., can be set to the null string or to a constant. The KDF output is a string of $l$ bits.


Password hashing security of argon2 versus bcrypt/PBKDF2? I wonder if it can be approximated how much of a security margin the new argon2 hash, winner of the password hashing competition, can give over bcrypt or PBKDF2, for an attacker using large GPU systems.

Practically speaking, if I have had a key-derivation-function running for one second on my server, how much of a security margin am I roughly gaining by running argon2 for one second (e.g. using 2GB of memory, otherwise default settings).

I am looking for more of a theoretical answer / guess based on the cryptographic differences between these schemes.

Coming up with a specific number is hard. Realistically, all three options take you well out of the realm of ever having more than the absolute worst passwords brute-forced by an attacker.
The primary gain of scrypt and Argon2 over bcrypt is a hit to parallelism due to the addition of memory requirements. GPUs with thousands of cores will need (but don't have) absurd amounts of memory, so most of those cores will need to remain idle. FPGAs and ASICs become much more expensive as they have to incorporate large amounts of memory, so you're really just forcing an attacker to trade a significantly larger number of dollars for equivalent parallelism.
The primary gains of Argon2 over scrypt (anyone correct me if I'm wrong):

improved resistance against Time Memory Trade-Off Attacks (TMTO),
better side-channel resistance (scrypt is vulnerable to cache-timing attacks due to secret-dependent memory access patterns), and
the ability to increase CPU and memory requirements independently of one another.


Security of pairing-based cryptography over binary fields regarding new attacks In the last week, the discrete logarithm problem was broken for the binary fields $\mathbb{F}_{2^{(14 \times 127)}}$ and $\mathbb{F}_{2^{(27 \times 73)}}$.

Pairing-based cryptography using binary fields currently relies on fields such as $\mathbb{F}_{2^{4\times353}}$ (80-bit level of security) and $\mathbb{F}_{2^{4\times1223}}$ (128-bit level of security).

Do these new attacks apply for these fields? How much security loss is expected for them? (It seems to me that they are not heavily impacted since there is a "large" prime factor in the exponent, but I don't know how much safer they are.)

While I believe the issue is not yet settled, here are some comments about the issue:

"This should signal the death knell for pairing based cryptography on Type-1 curves in small characteristic." - Nigel Smart

"it is not clear how well Joux's method applies for quasi prime extensions $2^{2\cdot r}$" -
Francisco Rodríguez Henríquez

"one consequence of the new algorithms may be that characteristic 2 and 3 fields are not appropriate for pairing-based cryptography." - Steven Galbraith

Antoine Joux announced the computation of discrete logarithm over $\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography.

According to Joux, "a direct consequence of this record is that supersingular curves (of
genus 1 or 2) defined over GF(2^257) cannot be used securely for
pairing-based cryptography."

It seems now that pairing-based cryptography over binary fields is dead.


CECPQ1 key exchange functionality CECPQ1 (combined elliptic Curve and Post-Quantum Cryptography Key Exchange) is a new key exhange developed by google, which combine X25519 with NewHope (elliptic Curve KE + Post-quantum KE).

Google has implemented CECPQ1 in boringSSL But there isn't a documentation or clarified explanation, how it works.

Looking at the code, I think, there are two key exchanges - X25519 and NewHope. Results of those exchanges are concatenated (here)
Then this concatenation is fed into KDF and used as session key.

So even if NewHope is broken whole scheme is secure, because X25519 is secure. Attacker must break both NewHope and x25519 to break a scheme.

Can Someone confirm that? or give me more details about CECPQ1?

Your understanding is correct. They experimented NewHope RLWE key exchange while maintaining X25519 as backup, in case there is something wrong with NewHope. By combining two key exchange algorithms, it should be good.


Does Goldwasser-Micali only encrypts only 1-bit or multiple? I've read online that the Goldwasser-Micali scheme can only encrypt 1-bit then I read that in another pdf that that scheme can encrypt a message of multiple bits so I'm confused. Can anyone clarify please?

The original scheme by Golwasser and Micali only encrypts one bit at a time.
It is possible to extend it to encrypt multiple bits at the same time using an higher order residue.
Roughly one can encrypt up to $k$ bits using the $2^k$-th residue symbol.


How message digest hash is used in RSA digital certificate verification This is how I understand digital signature verification to work in general:

Plaintext gets run through a hashing mechanism to make a message digest (IBM's terminology, there appear to be plenty of other terms for the hashed data).
Message digest is encrypted using sender's private key.
Both encrypted message digest and plaintext are sent to recipient.
Recipient decrypts message digest using sender's public key.
Plaintext gets run through hashing mechanism to make message digest, as in step 1.
If hashed plaintext and decrypted message digest are equivalent, test passes.

What I can't figure out is how this process is specifically applied in RSA verification of a digital certificate. I can't find the plaintext! If it's generated at random for each request, then what's the point of having a digital signature from the assigning CA in the certificate? If it isn't, then where does whoever is verifying the certificate get the plaintext to compare the signature to? I don't see that it's part of the certificate.

So, first, do I understand the general signature verification process as it applies to digital certificate verification? And if I do, can someone solve the "mystery of the missing plaintext" for me?

Lets fix that description of the signature generation. Please read the PKCS#1 v2.2 specifications to get the full detail.

Canonical binary plaintext gets run through a hashing mechanism to make a message digest (IBM's terminology, there appear to be plenty of other terms for the hashed data).
Message digest is used as input for the configured padding mechanism.
Binary padded message digest is converted to a number.
Number is raised to the power of the private exponent modulo the modulus, either directly or using the Chinese Remainder Theorem.
The number is converted back to binary with the same byte size as the modulus, giving the signature.
Both the plaintext and generated signature are sent to recipient.

As you can see I had to rewrite most of it. The modular exponentiation is commonly seen as the "encryption with private key part", but that's a contradiction in itself; it is just a similar operation and PKCS#1 v2 goes out of the way to explain that. For more information, see my Q/A here.

  What I can't figure out is how this process is specifically applied in RSA verification of a digital certificate. I can't find the plaintext!

The certificate contains a to be signed (TBS) part. This can be found in the X.509v3 standard. This is the plaintext in above signature generation scheme:

The signatureValue field contains a digital signature computed upon
the ASN.1 DER encoded tbsCertificate.  The ASN.1 DER encoded
tbsCertificate is used as the input to the signature function.  This
signature value is encoded as a BIT STRING and included in the
signature field.

  If it's generated at random for each request, then what's the point of having a digital signature from the assigning CA in the certificate? If it isn't, then where does whoever is verifying the certificate get the plaintext to compare the signature to? I don't see that it's part of the certificate.

It's just data, there are no pointers as in: here is the plaintext within the binary or textual description.

  So, first, do I understand the general signature verification process as it applies to digital certificate verification? And if I do, can someone solve the "mystery of the missing plaintext" for me?

Sure see above. But most of this is best found out by reading the standard documents. If you had done that then the mystery would not have existed.


security parameter in lattice cryptography In paper Lattice Signatures Without Trapdoors(Lyubashevsky2012), $n$ is the security parameter,  why the authors set $n$ as 512 but not 80/100/112 to get 80-bit security/100-bit/112-bit security?

A similar question could be asked about RSA --- why use 2048-bit RSA, and not 80-bit RSA?

The answer of course is due to cryptanalytic estimates. In particular, one estimates how difficult the underlying problem is (for factoring, it's roughly $\exp(O(\sqrt[3]{n}))$, and then sets the security parameter such that it takes $\approx 2^{80}$ bit operations to break.

For LWE-based schemes, Albrecht et al. have created the LWE-estimator. This is both a summary of state-of-the-art (at the time, in 2015) attacks on lattice schemes, along with a Sage module (which has been updated since then) that allows you to plug in the parameters of your scheme, and it will estimate the concrete security level.

These estimates are of course just estimates, and its an active area of research to try to get better estimates of the concrete security of lattice-based cryptography. But parameters themselves are chosen such that, when state of the art attacks are applied, it takes $2^{80}$ (or $2^{100}$ or $2^{112}$) bit operations to break the scheme.


Collision or second preimage for the ChaCha core? Daniel J. Bernstein's ChaCha core is an evolution of the Salsa20 core. Both are functions over the set of 512-bit bitstrings, partitioned as sixteen 32-bit words.

Can we exhibit collisions, or second-preimages (with implies the former), for the ChaCha core?

Clarifications: I'm using ChaCha core (which is not formally defined by Bernstein) as being to ChaCha what Salsa20 core (that he defines here) is to Salsa20; thus including combining input and output of a number of rounds using 32-bit additions. I'm not asking about collisions with the output of the ChaCha stream cipher (which keystream generator uses the ChaCha core).

The Salsa20 core has the easily verified property that if we toggle the leftmost bit of each 32-bit word of the input, the output does not change, making it trivial to exhibit second-preimages (thus collisions). These collisions or second preimages are not an issue in the uses of the Salsa20 (or ChaCha) core proposed by Bernstein, because enough input of the core function is fixed to arbitrary values that it prevents (as far as we know) exhibiting collisions and second-preimages matching these added constraints. The question is thus more out of curiosity than anything else.

ChaCha and Salsa20 cores exhibit some other properties that a random function would not, like being stationary at zero, or having remarkable identities between output words when all input words are identical. These are not an issue either, only a consequence of the deliberate design decision of putting the nothing-up-my-sleeves numbers out of the core function, in order to facilitate its analysis.

Update: Perhaps some of my curiosity really comes from briefly being culprit of making (in the context of the use of the Salsa20 core in scrypt) the very confusion Bernstein notes:

  I originally introduced the Salsa20 core as the "Salsa20 hash function," but this terminology turns out to confuse people who think that "hash function" means "collision-resistant compression function." The Salsa20 core does not compress and is not collision-resistant. If you want a collision-resistant compression function, look at Rumba20. (I wonder what the same people think of the FNV hash function, perfect hash functions, universal hash functions, etc.)

Here are both core functions in C99; we are seeking distinct values for in such that the corresponding out are identical.

#define CHACHA  1   // 1 for ChaCha, 0 for Salsa20
#define ROUNDS  8   // number of rounds, must be even; standard values are 20, 12, 8

#include <stdint.h> // for uint32_t

// 32-bit left rotation of v by n bits, with n in range [1..31]
#define ROTL(v,n) ((uint32_t)(v)<<(n) | (uint32_t)(v)>>(32-n))

// ChaCha or Salsa20 core, parameterized by CHACHA and ROUNDS
void djbcore(uint32_t out[16], const uint32_t in[16]) {
   int i;
   uint32_t x[16];
   for (i = 0; i<16; ++i) x[i] = in[i];
   for (i = 0; i<ROUNDS/2; ++i) { // each loop does 2 rounds
        uint32_t t;
#if CHACHA // compiled for ChaCha
#define DJBQ(a,b,c,d) /* quarter round for ChaCha */ \
  t=(x[a]+=x[b])^x[d]; x[d]=ROTL(t,16); t=(x[c]+=x[d])^x[b]; x[b]=ROTL(t,12); \
  t=(x[a]+=x[b])^x[d]; x[d]=ROTL(t, 8); t=(x[c]+=x[d])^x[b]; x[b]=ROTL(t, 7);
        DJBQ( 0, 4, 8,12) DJBQ( 1, 5, 9,13) DJBQ( 2, 6,10,14) DJBQ( 3, 7,11,15)
        DJBQ( 0, 5,10,15) DJBQ( 1, 6,11,12) DJBQ( 2, 7, 8,13) DJBQ( 3, 4, 9,14)
#else // compiled for Salsa20
#define DJBQ(a,b,c,d) /* quarter round for Salsa20 */ \
  t=x[a]+x[d]; x[b]^=ROTL(t, 7); t=x[b]+x[a]; x[c]^=ROTL(t, 9); \
  t=x[c]+x[b]; x[d]^=ROTL(t,13); t=x[d]+x[c]; x[a]^=ROTL(t,18);
        DJBQ( 0, 4, 8,12) DJBQ( 5, 9,13, 1) DJBQ(10,14, 2, 6) DJBQ(15, 3, 7,11)
        DJBQ( 0, 1, 2, 3) DJBQ( 5, 6, 7, 4) DJBQ(10,11, 8, 9) DJBQ(15,12,13,14)
#endif
   }
   for (i = 0;i < 16;++i) out[i] = x[i] + in[i];
}

Can we exhibit collisions, or second-preimages (with implies the former), for the ChaCha core?

No, likely not.

The Salsa20 and ChaCha cores both consist of a large number of "quarter-rounds" each of which is invertible and bijective. The only reason neither core is a bijection (and thus can have collisions) is the final addition of the input elements into the state.

With Salsa20 flipping the high bits works because it doesn't affect the right side of the quarter-round equations:

b ^= (a+d) <<< 7;
c ^= (b+a) <<< 9;
d ^= (c+b) <<< 13;
a ^= (d+c) <<< 18;

Thus, flipping all the high bits flips them all the way through the rounds and is canceled out by the addition of the input data.

The ChaCha quarter-round doesn't have as simple symmetry:

a += b; d ^= a; d <<<= 16;
c += d; b ^= c; b <<<= 12;
a += b; d ^= a; d <<<= 8;
c += d; b ^= c; b <<<= 7;

Different words get affected a different number of times by a bit flip and by a different kind of operation at first, so there is no simple change that would be left untouched by a quarter-round. Finding collisions is probably hard.

I realize this isn't proof, just a sort of handwaving justification.


How does the Flickr length extension attack work? I am currently reading about the length extension attack on Flickr (pdf) but not understanding what's going on there.

m = SECRET || data || padding` and `api_signature = md5(m)

The server sends data and api_signature to the attacker. The attacker now knows:

h = md5(m) = api_signature
data
length of data (Why does he know and why does he have to know?)

Goal of the attacker: append some extra data

How can he do that? He could take api_signature = h = md5(m) and use it as the Initialization Vector of the hash function and hash the extra data and another padding. This is the idea behind the hash length_extension attack, isn't it?

My question: The api_signature will change then because it is calculated like: md5(extra || padding) with the old api_signature as an initialization vector. How is this valid?

And overall: What does the server expect from a "normal" client when he sends this?

How can he do that? He could take api_signature = h = md5(m) and use it as the Initialization Vector of the hash function and hash the extra data and another padding. This is the idea behind the hash length_extension attack, isn't it?

Correct.

  My question: The api_signature will change then because it is calculated like: md5(extra || padding) with the old api_signature as an initialization vector. How is this valid?

That is why knowing the length of the data is important. The attacker can use the length extension attack to calculate the MD5 hash of data||original_padding||arbitrary_data by using the original hash value as an IV to calculate the hash h'(arbitrary_data||new_padding), where the new padding uses the total length of the original padded data and the appended data.

  And overall: What does the server expect from a "normal" client when he sends this?

The server expects a request that is "authenticated" with a hash of secret||request. By adding data to the end of the request and massaging the URL sufficiently, the attacker can compute the hash without knowing the secret value, for sufficiently modified URLs as to allow arbitrary requests. (Due in part to another weakness in how URL parameters were encoded for hashing.)


Why are the initial states of hashes functions (like SHA-1) often non-zero? There is already a question asking "Why initialize SHA1 with specific buffer?" and my question follows on from this:

Why are the initial states of hash functions often non-zero?

For most, I have been able to find a clear explanation of where the initial values come from, and they are frequently nothing-up-my-sleeve values. That is, they are chosen precisely because they have no significant structure. However, if that is the case, why can they not be left at zero? Is it simply that a zero initial state is itself too suspicious?

(Other related question: "Initialising Sha-512")

In early years of hash function design it was unclear how to choose constants (not only initial vectors), and it was widely assumed that the more random they look, the more secure the function is. There is still not much research in this direction. However, there have been several attacks (rotational cryptanalysis, slide attacks, internal difference attacks) that exploited similarity between the constants and their low Hamming weight. It may happen that some choice of constants yields a weakness or even a backdoor that allows a faster collision/preimage search.

Recent attacks on Keccak/SHA-3 would have been slower if Keccak state were initialized with some weird constant, not zero as it is now. This is a property of the Keccak permutation, whereas the encompassing sponge construction is invulnerable to the initial vector choice.

Another reason is to choose distinct IVs to differ functions that are identical, but truncate the output to a different number of bits (like SHA-224 and SHA-256).


Is this definition of an RSA modulus safe? Suggested definition

A positive integer is a safe RSA modulus if, after removing all its prime factors less than 512 bits, it is composite and has size at least 2048 bits.

Discussion

I want to build the smallest-possible safe RSA modulus without a trusted party. (The use case is for an RSA-based verifiable delay function to be used on a blockchain.) The strategy is to randomly sample several random numbers $N_1, ..., N_k$ and multiply them together. Each $N_i$ has some probability $p$ of being a safe RSA modulus so the product $N_1...N_k$ has probability $1 - (1-p)^k$ of being safe.

The above strategy of multiplying randomly chosen integers was pioneered by Thomas Sanders in the context of RSA accumulators. He used a stricter definition of a safe RSA modulus which only looked at having at least two primes above a minimum bit size. The reasoning behind suggesting this less strict definition of a safe RSA modulus is to maximise the probability $p$ so as to minimise the size of the final RSA modulus.

The "512 bits" parameter was chosen (conservatively) to protect against the ECM which has found primes of size up to 273 bits. The "2048 bits" parameter was chosen (conservatively) to protect against the GNSF which factored numbers up to 768 bits.

Is the above definition of a safe RSA modulus actually safe to use in production?

Overall I find the proposed definition and methods satisfactory in principle, barring quantum computers usable for factorization; but the 512-bit limit for factor, and to a lesser degree the 2048-bit unfactored limit, are not conservative.

Unfactored limit

As noted in comment, for long term security or/and convincing security authorities, it's probably best to up the 2048-bit size to 3072-bit, or more. France's ANSSI changed mind and went from year 2020 to 2030 for the limit beyond which 2048-bit is no longer enough, but other authorities stick to earlier dates.

Difficulty of factoring $n$ by GNFS grows with $L_n\left[\frac1 3,\sqrt[3]{\frac{64}9}\right]$ in L-notation, and (ignoring the hidden $o(1)$ term) that tells 2048-bit is roughly 40 Binary Orders of Magnitude (BOM) harder than the RSA-768 landmark of 2009. This is comfortable for now, but not huge. 3072-bit gives 62 BOM, that is huge.

Small prime limit

Difficulty of factoring by ECM grows roughly as $L_p\left[\sqrt2,\frac1 2\right]$ where $p$ is the factor pulled. Neglecting the $o(1)$, that tells a 512-bit $p$ is roughly 28 BOM harder to pull by ECM than the 273-bit record of 2013. That does not look like a comfortable margin to me: Ryan Propper's log and account mention relatively modest resources compared to the RSA-768 effort:

  For this job, I did about 5,000 curves, spanning about 10 days, on the FarmShare compute cluster at Stanford. I guess this was quite the lucky find. :)

and I do not see that the latest theoretical advances (Edwards curves) have been used. Consider more effort, dedicated ASICs, Moore's law at 1 bit per year, and the 28 BOM is about gone. I would not go below 640-bit (>41 BOM) or 704-bit $p$ (>47 BOM) with 2048-bit $n$. 832-bit $p$ gives 59 BOM, that's large.


RSA-CRT exponent reduction In the implementation of RSA-CRT, the exponent d is reduced mod p-1 ($d_p = d \bmod {(p-1)}$). The only proof I've found for that, is the following (considering $d = k\varphi(p) + d \bmod {\varphi(p)}$:
$$c^d = c^{k\varphi(n) + d \bmod {\varphi(p)}}$$
$$(c^{\varphi(p)})^k * c^{d\bmod {\varphi(p)}} \equiv (1)^k * c^{d\bmod {(p-1)}} (\bmod p)$$
Source: https://www.di-mgt.com.au/crt_rsa.html
So $c^d \equiv c^{d(\bmod(p-1))} (\bmod(p))$ However, I can't see why is the Euler theorem valid here, as c is not granted to be coprime with p (as far as I know). Any hint on this?

You're correct, the proof isn't precisely correct, because we don't necessarily have $c^{\phi(n)} = 1$, specifically in the case $c \equiv 0 \pmod p$.

Here is a more correct approach; we have $c^1 \equiv c \pmod p$ (trivially), and $c^{p-1} \equiv c \pmod p$ for any $c$, prime $p$ (Fermat's little theorem [1]).  By induction, we get $c^{k (p-1) + 1} \equiv c^1 \pmod p$ (for any $k$), and hence $c^{k (p-1) + \ell} \equiv c^\ell \pmod p$.

If we designate $x = k(p-1) + \ell$ for $0 \le \ell < p-1$ (and any $x$ can be put in that form), we have $c^x \equiv c^{x \bmod p-1} \pmod p$, for any $x, c$ and prime $p$; in particular, if $x = d$

[1]: The most common expression of Fermat's Little Theorom is that $1 \equiv x^{p-1} \bmod p$ for prime $p$, $x$ relatively prime to $p$.  However, an equivalent formulation (and what Fermat originally stated) is that $x \equiv x^p \bmod p$ for prime $p$, any $x$ - I'm using this alternative formulation.


Why don't the TLS1.3 cipher suites mention the key exchange and digital signature algorithm in names? Does it mean both RSA and ECDSA certificates can be used with the same cipher suite?

Yes. TLS 1.3's cipher suites only specify its symmetric AEAD and hash algorithms. The signature algorithms are specified separately. Several (asymmetric) signature schemes can be used with the same cipher suite.


finding sha256 preimage or secp256k1 private key, which is harder? Is finding a public key that matches hash of pre-commited public key (second layer security) more computationally hard than finding private key to a known public key (attacking secp256k1)?

To the best of our knowledge, finding a SHA-256 preimage is much harder than finding a secp256k1 private key; however both are current infeasible.

For SHA-256, the best known attack is to simply try lots of images until you stumble across one which hashes to the value you're looking for; that takes an expected $2^{256}$ hashes.

For Secp256k1, there are several known generic attacks (Big-Step-Little-Step, Pollard Rho) which reduces the expected complexity of finding the private key to about $2^{128}$ point additions.

Even though a point addition is considerably more expensive than computing a hash, it's not $2^{128}$ times as expensive, and so attacking secp256k1 is the easier option.

On the other hand, $2^{128}$ point additions is far more than is possible with current hardware (even if you had truly massive amounts of computational resources), and so it is safe.

On the third (gripping) hand, if the attacker can wait for a practical quantum computer to be built, that could recover the secp256k1 private key in a reasonable amount of time; no one knows when such a quantum computer will exist; it's likely not to be for the next decade or so.  However, if you need to be secure past then, you might want to rethink what you're doing.


What is the signature scheme with the fastest batch verification protocol for multiple signers? I'm looking for a scheme where signing may be costly (slow) but batch verification with different signers is the fastest possible.

Modified ECDSA allows batch verification for different signers with a 4X speedup [1].

Is there any signature scheme than can do better?

[1] Fast Batch Verification of Multiple Signatures. Jung Hee Cheon and Jeong Hyun Yi

Rabin signatures have a very fast verification algorithm: a simple squaring modulo some integer. RSA signature verification (with a public exponent equal to 3) is also very fast. These signature algorithms are simple to implement and will beat ECDSA for verification speed, even if batch verification is used for ECDSA.

The Niederreiter digital signature scheme should also have a very fast verification (but with a mammoth-sized public key); schemes based on Hidden Field Equations (Quartz and Sflash, notably) also offer a fast verification, albeit with a questionable security (the last decade of research on HFE-based schemes has been a long sequence of break-and-repair cycles). NTRUSign is also supposed to be very fast.

Bottom-line is that ECDSA signature verification is quite slow, compared to other signature schemes (it is still fast in practice, because elliptic curves can be optimized in many ways), so there are many signature schemes which will offer faster verification even without batching.

Another kind of batching can be done with ECDSA, when using a binary curve (a curve defined over the $\mathbb{F}_2^m$ field of characteristic 2, for some $m$) and bitslice code: you represent the complete verification process as a circuit of elementary operations on bits (XOR, AND... ECDSA in a binary field is quite appropriate for that); then you use big registers (e.g. 128-bit SSE2 registers) to perform many such computations in parallel, with bitwise operators (when you XOR together two 128-bit registers, you are performing 128 XOR operations in parallel). Writing out such code is difficult, but can offer some impressive speed-ups; see for instance this article (it will still not beat RSA signature verification, though).

Yet another possible ways to speed up ECDSA is by using Koblitz curves (curves in $\mathbb{F}_2^m$ with equation $y^2+xy=x^3+ax^2+1$ where $a$ is $0$ or $1$) which allow for very fast implementations: the doublings in a double-and-add algorithm can be replaced with simple squarings of both coordinates (in mathematical terms, applying the Frobenius endomorphism), something which can be implemented very efficiently. There are some standard Koblitz curves defined by NIST in FIPS 186-3 (the DSA / ECDSA standard), and the whole thing is described in details in the Guide to Elliptic Curve Cryptography (a very good book which I warmly recommend). Combine that with a recent enough x86 CPU with the AES-NI instruction set (not because of the AES things, but for the pcmulqdq instruction for "carryless multiplication"), and you could get some record-breaking ECDSA code which may be competitive even with RSA verification.

So there are many things which can be done with ECDSA; "mathematical" batching is just one of them, and not the one which may yield the biggest speedup in practice.


Is it safe to assume Salsa20 to be a PRP? Often in security proofs a certain block cipher is assumed to be a pseudorandom permutation or PRP. I wonder if this goes for stream ciphers as well, and specifically for Salsa20.
If we limit ourselves to the scope of one Salsa20 block (64 bytes), being fed 64 bytes of plaintext data, is it safe to assume $Salsa20_{key,nonce}$ to be a (strong) PRP family?
I'd very much be interested in the reasoning why or why not, and whether this extends to other stream ciphers.

Salsa20 is a stream cipher based on a pseudorandom function, not a pseudorandom permutation.

For a fixed key $k$ and nonce $n$, the mapping $PRF^{S20}_{k,n}: \{0,1\}^{64} \to \{0,1\}^{512}$, which maps a "Stream position" to "keystream block", is supposed to be a pseudorandom function. It is not supposed to be injective (i.e. a permutation, even less since the input/output sizes are different), and there certainly is no easy way to produce a preimage, even knowing the key and nonce.

What you propose is the Salsa20 encryption function for the first "block" of plaintext:
$$\def\Enc{\operatorname{Enc}}\Enc^{S20}_{k, n} : \{0,1\}^{512} \to \{0,1\}^{512}$$
$$\Enc^{S20}_{k, n}(P) = P \oplus PRF^{S20}_{k,n}(0)$$

This is obviously bijective (it is its own inverse), i.e. a permutation, but at the same time, it is obviously not a (pseudo)random permutation. In addition to the self-inverse-property, it for example also has the two-time-pad property:

$$\Enc^{S20}_{k, n}(P_1) \oplus \Enc^{S20}_{k, n}(P_2) = P_1 \oplus P_2,$$

which no random permutation would have.


RSA How to select a value K such that $e d = 1 + k \varphi(N)$ holds I am learning RSA cryptography. The part I am stuck on is understanding how k and the public exponent $e$ is selected.

Given the formulas;

Decrypting: $c^d \bmod N = (m^e)^d \bmod N$
Which is equal to m the message

Encrypting:
$m^e \bmod N = c$

My question is when generating the private exponent how do we find what the public exponent should be and what k should be in the formula

$$d = (1 + k*\varphi(N))/e$$

I understand it has something to do with the inverse of modules but I don
t get the math behind it.

You apply the extended Euclidean algorithm to $e$ and $\phi(N)$ (which have to have gcd equal to $1$) and we get $x,y \in \mathbb{Z}$ such that

$$xe + y\phi(N) = 1$$

The $x$ (taken modulo $\phi(N)$, if needed) is the $e$ you are looking for. The $k$ is totally irrelevant for encryption/decryption, but it's actually the $y$ in the above equation (rewrite your equation and see).


Are attacks on AES more efficient now (due to the new paper published at CHES2016??) Recently, there has been a new paper accepted to CHES 2016 called "A High Throughput/Gate AES Hardware Architecture by Compressing Encryption and Decryption Datapaths" by R.Ueno et al.

In one line, they proposed a very efficient AES crypto processing technology via Galois filed arithmetic operations.
I am no professional in this area, but I was wondering

"Does faster computation of AES allows for faster attacks on AES??"

For example lets assume if differential cryptanalysis was feasible for AES (which is not true). Then since one can compute AES on an input in, say half the time of previous computations, would that lead to an attack that is twice as fast??

I am no expert in this area, so I would like to know out of curiosity whether the paper above has any particular impact on cryptanalysis of AES.

Practically not, for two reasons:

the method described mostly speeds up AES computation with repeated use of the same key, rather than AES computation with repeated use of the same data, which is what a brute-force attacker does for key search, and what a side-channel attacker does to narrow a guess (there are other attacks, like detecting collisions in the CBC ciphertext, but a faster AES engine does not significantly help these).
even a speed up by a factor of 4 (more than claimed by the paper) would not qualitatively change the fact that AES key search, or other known AES attacks (excluding attacks on a particular implementation), are hopeless (when a single key is targeted, or when AES-192 or better is used); the technique in the paper reduces the security of AES-128 to 126 bits instead of 128, akin to reducing distance to notable nearby galaxies (excluding the Milky Way where we stand) to that of the Carina Dwarf instead of that to Andromeda.

Note: I have excluded side channel attacks against AES implementations using the technique described, but not use of the technique described to attack other implementations.


In a TLS 1.3 connection, how do the client and server choose a mutual cipher suite? According to KeyCDN, TLSv1.3 connections are established in a single round trip:

  While TLS 1.2 requires two round-trips to complete the TLS handshake, 1.3 gets the job done in just one trip

If that is the case, then the client's first message (after the TCP handshake) must include everything that the server will need for symmetric encryption, including the key and cipher suite. That means that the client would have to choose a suite without any input from the server.

How can the client be sure to pick a cipher suite that the server supports?

The client doesn't - the server now chooses the ciphersuite. The client now sends the supported client suites and the server gets to choose. Fortunately there aren't that many ciphersuites for TLS 1.3 because the server is likely to have a somewhat shorter list (note that there are only two bytes required per cipher suite though).

Similarly, since there is only DHE and ECDHE for key agreement it is relatively easy to "guess" the key agreement protocol. It's pretty likely that a server supports both - and otherwise it just costs another round trip and key pair generation.

An even better explanation can be found here with clear indications of what gets send at what step in the communication between client / server.  Note that "key share" here is not an encrypted key, it's just the public key of the generated ephemeral key pair.


Randomizing Prime Field Elements I need my code to generate random elements from $GF(p)$ ($F_p$ or $Z_p$, if you will).

The Crypto API I have available provides one with random bit strings. To tailor that to my needs, I can think of two possible solutions, each with its downside.

Solution 1: Sample $\lceil\log_2p\rceil$ bits, and reduce its corresponding integer modulo $p$ or $2^{\lfloor\log_2p\rfloor}$. This is efficient and easy but the resulting distribution is not uniform.

Solution 2: Repeatedly sample $\lceil\log_2p\rceil$ bits until the output integer is less than $p$. This gives a nice uniform distribution but is not constant time and may leak something about the internals of the random generator.

Is either of these a good idea, or is another method commonly practiced?

Edit: The accepted answer works for any set of elements (not necessarily a field) of any size (not necessarily prime).

is another method commonly practiced?

Sample $\lceil \log_2p \rceil+64$ bits, and reduce its corresponding integer modulo $p$.

There will still be a bias, but it is tiny.  And, assuming that you use a constant time modulo operation, it's constant time...


Traditional DES scheme in Unix crypt function In a security context course, we need to reproduce the old DES hashing scheme in the crypt program, on an old unix system.

I am actually reading the crypt page on wikipedia:

  The traditional implementation uses a modified form of the DES
  algorithm. The user's password is truncated to eight characters, and
  those are coerced down to only 7-bits each; this forms the 56-bit DES
  key. That key is then used to encrypt an all-bits-zero block, and then
  the ciphertext is encrypted again with the same key, and so on for a
  total of 25 DES encryptions. A 12-bit salt is used to perturb the
  encryption algorithm, so standard DES implementations can't be used to
  implement crypt(). The salt and the final ciphertext are encoded into
  a printable string in a form of base64.

I am not sure to well completely understand the above definition, and I would like to use an example to show you my questions.

So, considering I use the password: foobar12345678.

I will work in hexadecimal, so the password is: 66 6f 6f 62 61 72 31 32
1.The password will be truncated to foobar12.

2.I remove the first bit (not sure?) of every password byte, so my new password will be:

01100110 01101111 01101111 01100010 01100001 01110010 00110001 00110010
==>
11001101 10111111 01111110 00101100 00111100 10011000 10110010

The password in hexadecimal is cd bf 7e 2c 3c 98 b2 and is the 56 bits DES key.

3.The key above is used to encrypt an all-bits-zero block. I imagine the zero block is 56 bits also?

so, using an hypothetical DES scheme encryption function function_DES(hex_message, hex_key), our hash here would be the output of function_DES(00 00 00 00 00 00 00, cd bf 7e 2c 3c 98 b2). imagine that the output is hashOutput1

4.We crypt 25 hashOutput1 with the key cd bf 7e 2c 3c 98 b2 using DES scheme.

  A 12-bit salt is used to perturb the encryption algorithm, so standard
  DES implementations can't be used to implement crypt()

5.What's the 12-bit salt? I imagine it's predefined in linux system? Where can I find it? Imagine the salt is 101010101010 I place it in front of the 25th encrypted DES output?

6.Both hash and salt are comverted to base64 and placed in the /etc/shadow as:

$clearSalt$DEShash

So, during the 56 bits key creation, when we coerce down bits in 64 bits password, is it the first bit of each byte that we need to remove?

Are all-zeros blocks 56 bits (the exact same size than the 56 bits key) ?

What's the salt? Is it predefined in Unix system? Is it the same in all distro?

So, using this technique bruteforce tools should never go over 8 characters?

References:

http://en.wikipedia.org/wiki/Crypt_%28Unix%29 and http://www.kernel.org/doc/man-pages/online/pages/man3/crypt.3.html

edit:

for my salt question, I think I found my answer:

  When you change your password, the /bin/passwd program selects a salt
  based on the time of day. The salt is converted into a two-character
  string and is stored in the /etc/passwd file along with the encrypted
  "password."[10] In this manner, when you type your password at login
  time, the same salt is used again. UNIX stores the salt as the first
  two characters of the encrypted password.

(From: http://www.diablotin.com/librairie/networking/puis/ch08_06.htm)

As for the salt, it is a two-character string chosen from the set of printable characters leading to an effective 12-bit entropy.

The fact that every eigth bit of the password is dropped is due to the DES itself: from the 64-bit key, only 56 bits are actually used, thereby dropping 8 of the bits of the key. So, you just input the 64-bit password as the encryption algorithm secret key.

As for the all zeros block, it refers to the plaintext input to the encryption algorithm, which in the DES is a 64-bit value.

Thus you load the password as the key, an all zeros block as the plaintext into the encryption algorithm.

Now the only thing is the encryption algorithm is a tweaked version of the DES: the salt is indeed introduced during the expansion function $E$ of the DES as described in section 4 of this paper. Instead of the standard $E$, a tweaked version $E'$ is implemented.

All of this is well described in this paper.


Advantages to knowing $p$ and $q$ in Blum Blum Shub? Do you gain any advantage by knowing the factorization of $M$ (over just knowing $M$ itself) in the Blum Blum Shub generator?

The only advantage I see is being able to calculate the $i$-th number directly, as opposed to iterating to it.  This doesn't seem like a very large gain to me.

Short answer: knowing $p$ and $q$ allows building a more efficient generator, including one with random access. Further, for an adversary, at least if $p-1$ and $q-1$ can be factored, that allows finding a period, and at least if the generator allows random access past that, building a distinguisher.

With secret seed $x_0$, the Blum Blum Shub generator computes output $f(x_i)$ for $i\ge1$, where $x_i$ is defined by the recurrence $x_{i+1}={x_i}^2\bmod M$, and $f()$ is some function [such as extraction of the low bit, or eXclusive-OR or all bits], and $M=p\cdot q$ with $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod4$.

That implies $x_i={x_0}^{(2^i)}\bmod M$, but direct evaluation of that expression has cost $\mathcal O(i)$, and is equivalent to directly applying the recurrence.

With knowledge of the factorization $M=p\cdot q$, we can compute the output for large $i$ directly and efficiently [in time $\mathcal O(\log(i))$], by computing ${x_0}^{2^i\bmod(p-1)}\bmod p$ and ${x_0}^{2^i\bmod(q-1)}\bmod q$, then using the Chineese Remainder Theorem to combine them into $x_i$. The CRT may also slightly speed up a generator proceeding using the recurrence, as pointed my mikeaso and made quantitative by poncho in comments (computation time can be reduced by up to $1/4$ with textbook multiplication algorithms).

An adversary (with no access to the full internal state of the generator) knowing the factorization of $M=p\cdot q$, and also able to factor $p-1$ and $q-1$, can compute $u=\lambda(p-1)$ and $v=\lambda(q-1)$ where $\lambda()$ is Carmichael's function [or $u=\varphi(p-1)$ and $v=\varphi(q-1)$ where $\varphi()$ is Euler's totient function], then $\operatorname{lcm}(u,v)$ which is a multiple of the period of the BBS generator, because for all $x$, $x^{(2^u)}\equiv x\pmod p$ and $x^{(2^v)}\equiv x\pmod q$. From that it is trivial to build a distinguisher between

a BBS black box accepting $i>0$ and returning the output of index $i$ in the BBS sequence for some fixed unknown random seed $x$;
a random oracle black box accepting $i>0$ and returning random output if that $i$ was not previously submitted, else returning its previous output for this $i$.

The distinguisher works by submitting $i=1$ and $i=\operatorname{lcm}(u,v)+1$, bets on BBS if the answers are equal, and on random oracle otherwise.

When

the BBS black box only outputs sequentially,
or proceeds sequentially by squaring modulo $M$,
or otherwise bounds $i$ to remain small,
or was built without knowledge of the factorization of $M$,
or $p-1$ or $q-1$ are hard to factor,

then I fail to exhibit a distinguisher (but would no be all that surprised if one could be devised).


Can modular multiplicative inverse be used to create a secure cipher? Let $N$ be a large number; and $(e, d, N)$ be a secret-key; where $e$ is a one-time random factor, and large enough (say the more or less the same number of bits as $N$), where $e < N$ and $e * d \equiv  1\pmod N$

Encryption of a plaintext $m$, where $m < N$, is as follows:

$ c = m * e \bmod N$

Decryption of a ciphertext $c$ is as follows:

$m = c * d \bmod N$

How can we prove, if the above defined cipher is secure (or not) under the following conditions?

Message $m$ is randomly padded to $m_p$ before encrypting, where $m_p < N$, matching the bitlength of $N$
$N$ can be re-used
The secret (and random) factors $(e, d)$ are used only once (once per encryption, session, message etc...)

Note: I'm asking this because, optimizations on this cipher can have a direct use on the protocol defined in the question: Random Masking of Padded RSA Ciphertext through homomorphism

Additional question: Does the choice of $e$ and $N$ affect the security of this cipher?

The question uses the term "cipher" in a non-standard way: in cryptography, a cipher's key is usable for multiple messages, and that's explicitly not the case here. We'll extend the term cipher to something with the restriction that components of the key (here, $e$ and $d$) are used for a single message. We'll assume a supply of distinct random secret one-time key components $e$ and $d$ known to encrypting and decrypting parties.

It is asked if the "cipher is secure (or not)". The most standard modern definition of security of a cipher is indistinguishability under Chosen Plaintext Attack. That defines an experiment where an adversary chooses two plaintexts, gets them encrypted, and tries to match ciphertext and message (we'll ignore that this experiment normally uses ciphertexts obtained under the same key).

In this section, we assume there is no random padding (that is, $m_p$ is defined as $m$).

The cipher as stated is not secure per the modified CPA definition: an adversary can submit $m=0$ and $m'=1$, and can recognize the ciphertext $c$ for $m$ from the ciphertext $c'$ for $m'$, because $c=0$ and $c'\ne0$.

The additional restriction $0<m<N$ is not enough for security: if the adversary knows a divisor $d$ of $N$ with $1<d<N$, then the adversary can submit $m=d$ and $m'=1$ and can recognize the ciphertext $c$ for $m$ from the ciphertext $c'$ for $m'$, because $c\bmod d=0$ and $c'\bmod d\ne0$.

However, if the condition $\gcd(m,N)=1$ is imposed to adversaries, and if $e$ is chosen uniformly at random among the subset $\Bbb Z_N^*$ of integers in $[0,N)$ such that $\gcd(e,N)=1$ (this later condition is equivalent to existence of $d$), then demonstrably the cipher leaks no information about $m$ and is CPA-secure. Proof sketch: for fixed $m$, the function $e\mapsto c$ is reversible onto the finite set $\Bbb Z_N^*$, hence is a bijection, hence $e$ uniformly random implies $c$ uniformly random, hence $c$ leaks nothing about $m$.

Methods to impose the condition $\gcd(m,N)=1$ to adversaries include requiring $0<m<N$ and making $N$ either a hard-to-factor RSA modulus of factorization unknown to adversaries, or a prime. However neither is possible in the context (note: where $r$ and $r^{-1}$ are the $e$ and $d$ of the present question), since an adversary is the holder of an RSA private key for $N$, which allows to efficiently obtain the factorization of $N$ and implies $N$ is not prime.

Now we introduce padding. The question's encryption and decryption equations become
$$\begin{align}
c&=m_p*e\bmod N\\
m_p&=c*s\bmod N
\end{align}$$
All random paddings used in RSA (including OAEP) make $\gcd(m_p,N)=1$ overwhelmingly likely, including for adversaries knowing the factorization of $N$ and able to chose $m$ before padding. Therefore, with $N$ an RSA modulus, and a secure RSA random padding tailored for this modulus and using a random number generator not under control of adversaries, the cipher is CPA-secure (per our modified definitions of cipher and CPA-secure).

The choice of $N$ has no influence on security, and its factorization needs not be kept secret for the security of the cipher in the question.

If we leave the padding unspecified, security can depend on $e$ being uniformly random in $\Bbb Z_N^*$ (which can be obtained by taking $e$ uniformly random in $[0,N)$ until $\gcd(e,N)=1$, with this later condition overwhelmingly likely when $N$ is an RSA modulus). However, with OAEP padding, it is enough that $e$ is chosen in $\Bbb Z_N^*$ using a method yielding large entropy.


Using simple hashing function to expand already secure key Assume I only have only three algorithms available at my disposable: PBKDF2, SHA512, and HMAC-SHA256. (This means I do not have algorithms like HMAC-Expand available.)

Assume I also have a cryptographically secure random 256 bit key. I would like to expand this key to 512 bits, so that I can split this resulting key in half and now have 2 child keys.

The recommended option is to use PBKDF2, but this advice is typically given when stretching a low-entropy, user inputted password. Given that my key is already high-entropy, is there any issue with just using SHA512(key) to expand my key?

The reason I'd rather use SHA512 is that it does not require a salt like PBKDF2 does.

This answer states that it's acceptable to do something like:

child_key_1 = HMAC-256(master_key, "c1")
child_key_2 = HMAC-256(master_key, "c2")

Have I interpreted that answer correctly, and is there a clear winner amongst all my options?

What you are looking for is a "Key Derivation Function" (KDF).  Notice you called out PBKDF - Password Based KDF.   One very common KDF (it's even in NIST standards) is to use the shared secret - your "master_key" - to hmac a counter.  Your proposal is therefore in line with the standard methods of KDF.


Proof that lottery does not know outcome of draw Could a variable participant lottery system cryptographically prove that they have zero knowledge of the outcome of a draw?

Participants do not choose numbers in this lottery and winning numbers are not drawn. Instead, they simply enrol with a wager. Winners are selected by taking all wagers and building an array of 'tickets' where the number of ticket entries per participant is proportional to their wager. A random index is chosen from this array, this is the winner.

I found a similar question but the answers assume that the number of participants is fixed. I'd also like to keep the participants from having to perform bit commitment as some have suggested - for trusting participants this is a PITA.

Protocols for selecting uninfluenced random numbers typically fall into two camps: random beacons and coin-tossing protocols.

A random beacon is a source of randomness that is agreed by everyone to be unpredictable. For example, you can funnel a large amount of financial data into a small random number. While you cannot prove you didn't know what the closing prices would be before they actually closed, can prove that someone who possesses such knowledge can make a lot of money. A coin-tossing protocol is a protocol where everyone chooses random numbers that are combined to form the master random number. This is what is mentioned in the other answer you found.

As you point out, both of these produce a number of predetermined length. But that is ok, once the lottery closes,

Calculate the number of bits you need to select $m$ out of $n$ tickets using a standard selection algorithm (for example, you can run the Fisher–Yates shuffle until you've pulled out $m$ items). Say it takes $N$ bits.
Use either a random beacon or coin-tossing protocol to generate a cryptographic seed for a pseudo-random generator (PRG).
Use the PRG to generate $N$ bits and run the selection algorithm.

Note selection algorithms may be non-deterministic in the number of bits they need, so you can skip step 1 and just run the PRG until the selection has completed.

You must publish beforehand the exact protocol (selection algorithm, beacon/coin-tossing, PRG) that will be used. The only variable will be the secret seed.


Security of a cipher with some imperfection in round function I got specific problem with round function in my symmetric cipher. It works on $128$-bit blocks. Every round got two $128$-bit keys. Block is xored with $k_{1}$ on the beggining of the round. Then it goes into round function (which is using the same $k_{1}$ and $k_{2}$ keys, both $128$-bit long). And then it is xored with $k_{2}$ in the end.
Problem is with round function. Let's asssume that it transom every $128$-bit block into $128$-bit block indistinguishable from random, if you don't have $k_{1}$ and $k_{2}$. But there is one exception. All zeros block is always encrypted into all zeros block (with every key). So only xoring makes it different from all zeros block before it goes into round function.
If we will consider let's say $10$ rounds - is it secure cipher? Is it possible to broke it because of that problem with all zeros block?
EDIT:
I clarified my question, specifically when xoring is performed:
$INPUT \oplus k_{1}$ $\to$ $F_{roundfunction}$ $\to$ $OUTPUT \oplus k_{2}$

If an all-zeroes block creates all-zeroes for every key that's definitely an issue. It's not necessarily likely to be serious, but could leak data about the plaintext and does not qualify as a secure block cipher.
However, the solution is fairly simple... simply XOR one of k1 or k2 with a constant value to turn your all-zero block into something that'll produce a better result. Personally I'd XOR with the current round number in each round because that'll prevent your algorithm from accidentally ending up with another input that produces the same issue.


Can A PRNG Be Used To Generate Multiple Private Keys for ECDSA? Suppose Alice seeds a cryptographically strong Pseudo Random Number Generator with a truly random number, and keeps it secret. Alice then uses the output of the PRNG to generate several 256-bit numbers in sequence. Each of those 256-bit numbers is then used as an ECDSA private key, public keys are generated from them, and those public keys are sent out in the open. The private keys are either kept secret, or destroyed.

An attacker, Mallory, collects a bunch of public keys, some of which belong to Alice. Two questions:

If not told explicitly, can Mallory figure out which keys belong to Alice?
If Mallory does know which keys belong to Alice, can he figure out any of the private keys (or the initial seed)?

My concern is that, since the private keys are mathematically related, information about their relation may be leaked through the ECDSA public key generation (Q = kG). Most implementations of ECDSA I have seen use a PRNG that is frequently re-seeded, like OpenSSL. Presumably, though, one could generate multiple keys sequentially without a re-seed occurring. That being the case, I assume the above is safe. I am, however, having a hard time coming up with a proof for it.

The most important property of cryptographic PRNGs is that it's indistinguishable from true random numbers, unless you know the seed, or you have huge computational resources. Two important consequences of this requirement are:

You can't find the seed from observing the output
You can't predict more outputs from observing some of them.

An attacker who can do either of those, either has broken the cryptography used in the PRNG, or he has computational resources exceeding the security level of the PRNG. For typical security levels of at least 128 bits, nobody on earth has the required resources.


Applications of RSAES-OAEP Cryptography I am trying to do a project on RSAES-OAEP cryptography.Can anyone advice me any good applications where this can be used where there will be a lot to learn about in a programming and application perspective?

RSA is good for short messages, so think about applications involving short messages. e.g.

Key encryption. i.e. use RSA to encrypt an AES key for transport
Credit card data. i.e. encrypting a credit card number for transmission


FIPS 140-2 Compliant Algorithms Is there any reference to check the list of encryption & signing algorithms which are compliant to FIPS 140-2. After an exhaustive search I could find only "AES".

Any suggestions would be much appreciated.

Take a look at FIPS 140-2 Annex A. It lists the following:

Symmetric Key

AES, Triple-DES, Escrowed Encryption Standard

Asymmetric Key

DSA, RSA, ECDSA

Hash Standards

SHA-1, SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, SHA-512/256

Random number generators

See annex c

Message authentication

CCM, GCM, GMAC, CMAC, HMAC


Sender and receiver having different moduli conflicts with encryption and signing in RSA I should implement a security protocol as a part of which I need to:

Encrypt the message with receiver public key.
Sign it with my private key.
Send it to receiver.

Suppose that the system uses a modulus with at least 1024 bits and data is in blocks of 512 bits.

The problem is that when the receiver's n (modulus) is bigger than  my n then the output of step 1 is probably bigger than my n and so step 2 will fail.

With public-key algorithms, you don't do encryption and signing of the message using the public-key algorithms themselves.  Instead, you use traditional symmetric algorithms for encryption and hash algorithms for signing, then apply the public-key algorithms to those results.

What you're asking for here can actually be thought of as two entirely-different processes.  The first is to encrypt the message to the public key of the recipient.  The second is to sign the encrypted message with your private key.

As you noted, RSA can only handle encrypting and signing message sizes up to the sizes of the modulus.  However, it's actually worse than that: using RSA on messages larger than a certain percentage of the modulus size is actually also insecure.  Proper use of RSA requires dedicating a certain portion of the input space - actually, most of it - to data called "padding".  You fill in the low part with the encryption key or hash you're encrypting or signing, then fill the upper part with padding according to the specification you are using.  The recipient then validates that the formatting and padding is as expected on the other end.  You must do this, or your encryption system will be broken by attackers if they want.

A proper implementation is going to require secure random number generation.  Generating the public and private keys has to be done using secure random number generation, but encryption is going to require this as well.  Don't try to implement secure random number generation yourself; let your operating system do that for you.  In Windows, use CryptAcquireContextW and CryptGenRandom; on UNIX systems such as Linux and Mac OS X, open the fake file /dev/urandom and read bytes from it.

To encrypt a message with RSA, select a symmetric encryption algorithm.  I recommend 128-bit AES (Advanced Encryption Standard) in CBC (Cipher-Block Chaining) mode, a very typical setting.  For each message you encrypt, generate a 128-bit (or 16-byte) random encryption key and a 16-byte IV (Initialization Vector).  The key and IV are for this message specifically, and shall never be used again.

Combined with the key and IV, encrypt the message using AES.  AES is a block cipher with a block size of 16 bytes; this means that it can only encrypt messages whose size is a multiple of 16 bytes.  To handle messages that are not a multiple of 16 bytes, a technique called Ciphertext Stealing can be used.  Because we're going to send the IV inside the RSA-encrypted area, you're allowed to change the IV as part of the ciphertext stealing technique if the whole message is smaller than 16 bytes.

With the message encrypted, we now do the RSA encryption step.  With RSA, we can only encrypt a small message, but what will it be?  In this design, our message is 32 bytes: the key, and the IV.  This means that you need a key size of at least 1024 bits (128 bytes).  Let $C = AESCBC(IV, M)$ be the symmetrically-encrypted message.

Look up RFC 2437 and find "RSAES-OAEP".  "Optimal Asymmetric Encryption Padding" is a good choice of how to fill out the number $m$ given the message $K$ $||$ $IV$; that is, $K$ and $IV$ concatenated.  Once that's done, you calculate $c = m^d$ mod $n$ for RSA as you've known.  The total encrypted message is $c$ || $C$.

Next, we sign the combined message $V = c$ $||$ $C$ using the sender's private key.  Since $V$ is probably too long, given that $C$ is the same length as the unencrypted message, instead of signing $V$ directly, we sign the hash of $V$.  Choose a good hash algorithm; SHA-256 is a good choice.

Once again, consult RFC 2437, this time the RSASSA-PSS section.  This section describes a method to generate a signature from a private key and a "message", which in our case will be $M = SHA256(V)$.  This generates the final signature, $S$.

Send $S$, $c$ and $C$ to the recipient.

The inverse on the recipient's side should be straightforward to understand if you've implemented the above.  First, the recipient calculates $SHA256(c$ $||$ $C)$, which is equivalent to $SHA256(V)$ and $H$.  Next, the recipient applies RSASSA-PSS-VERIFY to check the signature.  As on the sender's side, $H$ is the message $M$ when it comes to RSASSA-PSS.  If RSASSA-PSS succeeds, $S$ is an authentic signature of $c$ and $C$.

Now the recipient does an RSA decryption of $c$ to recover $m$ using RSAES-OAEP-DECRYPT.  The low 32 bytes are $K$ and $IV$.  Use key $K$ and initialization vector $IV$ to AES-CBC decrypt $C$ back into the original text; don't forget about ciphertext stealing if you used it.  (You can tell whether the sender used it by whether the number of bytes in $C$ is a multiple of 16.)

If an error is detected at any time, abort.  Don't tell the other side any specifics of why.

I would have given more links if my reputation were high enough to allow it.


(Non-) Perfect Secrecy of Vernam Cipher Using $E(m) = m \oplus k \oplus \operatorname{rev}(k)$ Given the cipher
$$E(k, m) = m \oplus k \oplus \operatorname{rev}(k)$$
where $\operatorname{rev}(k)$ is the reversed binary of $k$, how would one prove that the cipher is not perfectly secret.

I know that the definition of perfect secrecy is $P(M = m \mid C = c) = P(M = m)$ for all $m$ and $c$ and that each key is only used once.

Clearly the intuition comes in when the key is symmetric as then $k \oplus \operatorname{rev}(k) = 0$, but given the definition above how can I show this formally using the definition above?

Thank you! This is a homework question.

My work so far is along the lines of $P(M = m) = 1/2^n$ where $n$ is the number of bits and
$$ P(M = m \mid C = c)
\\= P(M = m \text{ and } C = c) / P(C = c)
\\= 2^n \cdot P(M = m \text{ and } C = c)
\\= 2^n \cdot (1/2^n \cdot 1/2^{n/2})
\text, $$
however this doesn't seem very formal.

While the other answer is correct, there are multiple ways to disprove a theorem.

In your case you want to disprove $$\Pr[\mathcal M=m|\mathcal C=c]=\Pr[\mathcal M=m]$$ holds for $$c=m\oplus k \oplus \operatorname{rev}(k)$$.

The first one is to argue using the probabilities and show that the above equation doesn't hold for this scheme.
The second (formally correct) approach is to find a counter-example. Note that counter-examples alway disprove theorems while they can never be used to prove them (this is how sciences like physics work).

Now consider the following message space $\mathcal M=\{(0,1),(1,1)\}$ with $\Pr[\mathcal M=m]=\frac{1}{2}$ (i.e. both messages are equally possible). For the next step observe that $$c_0\oplus c_1 = m_0\oplus k_0 \oplus \operatorname{rev}(k)\oplus m_1\oplus k_1 \oplus \operatorname{rev}(k)= m_0\oplus k_0 \oplus k_1 \oplus m_1\oplus k_1 \oplus k_0=m_0\oplus m_1$$ as was noted by Maarten in the comments. $m_0,m_1$ here denote the first and second bit of the message space and $c_0,c_1,k_0,k_1$ the respective cipher text and key bits.

Now observe that the first message always yields a $1$ when applying the above $\oplus$ and that the second one always yields $0$ when applying it. So you know that $$\Pr[\mathcal M=m|\mathcal C=c]\neq \frac{1}{2}=\Pr[\mathcal M=m]$$ and thus the scheme isn't perfectly secure. The first probability follows trivially from the fact that you can you know exactly which message was encrypted given a particular cipher text.


Why aren't hash values for "nothing" (empty) defined as all zeros? Any decent hash algorithm will produce basically "random like" values for any given input including the empty input.
For example MD5 produces d41d8cd98f00b204e9800998ecf8427e on an empty input.

I wonder, however, why the MD5 algorithm wasn't defined to have a final step where the output is XORed with d41d8cd98f00b204e9800998ecf8427e.
This should not affect the cryptographic strength of the hash algorithm, and it would have the convenient property that a hash of all zeros represented a zero input.

Would it simply just because adding that step would slow the hash down a bit?

Why would that be a convenient property? It would be pretty annoying if I would test an empty string input, hash that and then XOR it with a value. I would get the same value back. You want the output of a hash function to seem random; getting a value of zero is not what you want at all. You don't want any exceptions to the output of the hash function.

Imagine a crypto currency that requires the first $x$ number of bits to be set to zero for a crypto coin to be mined. You could just input the empty string to be rich beyond belief.

The only thing worse from having an empty string result in $n$ zero valued bytes is to have $n$ zero valued bytes return $n$ zero values bytes. Because in that case $H(0^n)$ would equal $0^n$ but $H(H(0^n))$ would as well, to infinity and beyond.

This would be called a cycle of 1 length; hash functions should never enter a cycle (in practice) when hashing the output of previous hashes. Of course, the hash function would not be considered secure anymore: $H(x) = x$ is called a pre-image and secure hash functions should be secure against pre-image attacks.


What does 2-flat mean when discussing APN permutations? I am currently reading a research paper that uses the term 2-flat. However, I don't understand what this term means.

For example, the paper mentions in its definition of APN that for all distinct $a$, $b$, $c$ and $d$ in $V$,

$$a + b + c + d = 0  \implies f(a) + f(b) + f(c) + f(d) \neq 0$$

i.e. $f$ does not sum to 0 on any 2-flat.

It would be great if anyone could explain what 2-flat means here.

An APN permutation in dimension 6

In the context of Boolean functions, "flat" is usually used as a synonym for "affine subspace of $\mathbb{F}_2^n$". More generally, an $n$-flat in a vector space $V$ (which may be considered as an affine space) is an $n$-dimensional affine subspace of $V$.

Note that a 2-flat of a vector space $V$ over $\mathbb{F}_2$ is then any set of the form

$$A = \{a, a + b, a + c, a + b + c\}$$

with $a, b, c \in V$ distinct. Remark that $\sum_{x \in A} x = 0$ and conversely, any four distinct elements in $V$ that sum to zero form a 2-flat.


Can I make a cipher (ex: Vigenère) harder to break? The Vigenère cipher can relatively easy be broken when the key size is small compared to the size of the message. One first finds the length of the key, and then uses frequency analysis to actually find the key.

How can one "add" something non-complicated to the Vigenère cipher to make it harder to break? Would it for example help to first apply a permutation the message in some way?
Are there any general strategies for this when using other ciphers?

For Vigenère specifically, you can make it harder to break by increasing the size of the key and by making the key truly random.  If the key is truly random, longer than the plaintext and never reused, then Vigenère becomes equivalent to a One Time Pad.

Even without going that far, it is possible to strengthen many, though not all, cyphers by lengthening and/or randomising the key.


Symmetric-keys algorithms with different keys for encryption and decryption The Symmetric-key algorithm article from Wikipedia states:

The keys may be identical or there may be a simple transformation to go between the two keys.

I am not aware of any symmetric-key cryptosystem that uses different keys for encryption and decryption. What are some examples of such algorithms? Is this correct to call them symmetric-key algorithms?

A relevant example where you usually don't use the same key for encryption and decryption is actually AES (and any SPN-based cipher for that matter).
The simplest point here would be that for AES you'd normally store your expanded key in order of usage in memory (to help with things like prefetching). However this would mean that the e.g. 11 round keys are stored in reverse order for encryption and decryption!
Furthermore for actual AES-NI based implementations you'd go one step further and pre-process your decryption round keys due to the way the hardware decryption instructions work (see e.g. this Intel guide (PDF) on how to do that). Due to this your actual key schedule usually looks completely different for the encryption and decryption direction (though you can somewhat easily transform one into the other). But no one would argue that AES is not a symmetric cipher...
As for the more general angle on this question: If the transformation is a simple operation as suggested on Wikipedia, it would usually be "hidden" from the user. That is one would usually specify the faster expansion for encryption and then add a pre-processing step for the key-usage during decryption.


blowfish ecb with openssl doesn't give the expected result I do the following via the Linux CLI:

printf '\xff\xff\xff\xff\xff\xff\xff\xff' > plaintext.txt
openssl enc -bf-ecb -e -in plaintext.txt -out ciphertext.txt -nosalt -K FFFFFFFFFFFFFFFF -p

I then read the contents of ciphertext.txt with <?= bin2hex(file_get_contents('ciphertext.txt')); ?> and I get this:

5aacfb5a8dc0155dd0269124c9e81789

According to https://www.schneier.com/code/vectors.txt, however, the result is this:

51866fd5b85ecb8a

That ciphertext.txt is twice as long as the test vector result makes sense because of padding. But shouldn't the first eight bytes of ciphertext.txt match the test vector?

Doing the above with des-ecb (same plaintext and same key) gives the same output that https://www.cosic.esat.kuleuven.be/nessie/testvectors/bc/des/Des-64-64.test-vectors mentions (Set 3, vector#255) so it seems like my test methodology is correct.

Any ideas?

The -bf-ecb cipher is expanding the key to 128 bits by zero extending it.

The output from -p is the telltale here:

$ openssl enc -bf-ecb -e -in plaintext.txt -out ciphertext.txt -nosalt -K FFFFFFFFFFFFFFFF -p
key=FFFFFFFFFFFFFFFF0000000000000000

Blowfish is defined for 32-448 bit keys, and it appears the OpenSSL implementation chose 128 bits as the size to use, and added zero-extension of shorter keys as a 'convenience'.

Compare this with -des-ecb, where DES is only defined for 64 bit keys:

$ openssl enc -des-ecb -e -in plaintext.txt -out ciphertext-des.txt -nosalt -K FFFFFFFFFFFFFFFF -p
key=FFFFFFFFFFFFFFFF


How to generate a random number so server cannot cheat? Here is the protocol:

Bunch of players connected to server.
Server creates nonce and hashes it - send hash to clients as bit commitment.
Clients make nonces and send hashes to server as their bit commitment.
Unknown to clients one of the clients is the server itself. Server runs through candidate nonces from that client until IT wins game.
Server sends hashes of nonces to all clients. (Clients do not know each other's IP.)
Game is resolved and desired client wins.
Server sends all nonces to clients who verify them, none the wiser.

How do we prevent the server from cheating here, please?

One possibility is the sloth and unicorn approach of this paper.

The idea is essentially to use a slow (but quickly verifiable) hash.  If the sever publishes a commitment to all the shares within a few seconds of the start of the hash computation (which will start at a agreed-to time), and the hash can't be done in less than an hour, then the server can't select its own share to tilt the game in its favor.

The downside, of course, is this is relatively expensive; we're willing to assume that the server will be willing to devote an hour of computation.  For the point of the paper (trusted Elliptic Curve generation), that's reasonable (as you don't do that all often); for other uses, it might not be quite so realistic.


Diffie-Hellman key exchange - why is modulo operation necessary? Could someone explain why it's necessary to have the modulo operation in the Diffie-Hellman key exchange?

Let's imagine we do DH without the modulo operation ($A = g^a, B = g^b$). Would that not work, because the logarithm ($a = \log_gA$) is easy to calculate? And why does the modulo operation have to be done with a prime?

I know it's a basic question, sorry. I understand the protocol, but not the maths around what is easy to calculate and what isn't. I guess we need $A = g^a \bmod p$ instead of just plain $A = g^a$, because $\log_gA \bmod p$ is very hard to calculate... would it be easy to calculate it without the $\bmod p$?

Many thanks in advance.

Would that not work, because the logarithm ($a=\log_gA$) is easy to
  calculate?

Yes, among other things.

We know how to efficiently calculate the logarithm over real numbers (thus this would bear no security).
We can't sample uniformly at random from an infinite range (all natural numbers), that means you can't randomly draw a natural number because every single one will have $0$ probability of being drawn. This makes key-generation hard (yes one could technically limit the length here).
We can't store, let alone transmit, such large numbers. For example assume $g=3$ and now pick a standard-size DH exponent $a$ which has 2048-bit length. $g^a$ will now have $1.5\cdot 2^{2048}$ bit length. We can't store that. We can't even count to $2^{192}$ realistically (with counting being easier than storing).

  And why does the modulo operation have to be done with a prime?

There are a few reasons (why to prefer primes):

It gives us nice mathematical properties. $\mathbb F_p$ is a field, that is every element has a multiplicative inverse, whereas $\mathbb Z_n$ is a ring where not every element has a multiplicative inverse.
It prevents backdoors. If you pick a composite value, the person who knows the factors will have a significantly easier time to compute the logarithm. Picking a prime ensures there's no doubt about anybody knowing any factors if you re-use parameters.


Side channel security of HMAC in software Assume we have a processor with a symmetric co-processor that supports AES. This processor does however not provide co-processor support for hash algorithms such as SHA-1 or SHA-256.

I've got the following strongly related questions:

Would an HMAC implementation based on a hash implementation in software - which is not explicitly protected against side channel attacks - be vulnerable to side channel attacks?
If so, are there reasons why such an attack would be stronger or less strong than e.g. a side channel attack against a symmetric cipher in CBC mode?
Would it be possible to retrieve the key used to key the HMAC algorithm?
Finally, could it be safer to opt for AES-CMAC instead in case an AES implementation in hardware is available?

It is assumed that the comparison of authentication tag values does not leak information. Both DPA and timing attacks could be considered.

The reason I'm asking is because hash algorithms are often not explicitly protected against side channel attacks. HMAC is still often used in this scenario.

I am answering on the basis of this paper (pdf) linked in the comments, as well as some of the related papers it cites or is cited by. I am not aware of more realistic attacks on HMAC.

It assumes a DPA side channel that leaks the number of bits flipped when a new value is read into a CPU register (or in another instruction in some of the papers). I.e. it leaks the Hamming distance between the old value and the new. This allows a direct key recovery attack on HMAC, made easier by the fact that HMAC uses inner and outer keys that are conveniently a known distance apart.

If you assume such a side channel, there is not much you can securely do on the computer. In fact, a typical hardware implementation of HMAC would be almost equally likely to be vulnerable, if you still have to load the key from memory to use it.

  Would an HMAC implementation based on a hash implementation in software - which is not explicitly protected against side channel attacks - be vulnerable to side channel attacks?

I do not think it is a matter of software vs. hardware or even side channel protection. If such a side channel as described above exists, there is not much you can do securely on the CPU. Certainly most conventional data processing with secret values has to be rethought.

  If so, are there reasons why such an attack would be stronger or less strong than e.g. a side channel attack against a symmetric cipher in CBC mode?

Stronger, in the sense that it is a key-recovery attack, unlike e.g. padding oracle attacks that target CBC. But the assumptions are much stronger as well.

  Would it be possible to retrieve the key used to key the HMAC algorithm?

Yes, assuming.

  Finally, could it be safer to opt for AES-CMAC instead in case an AES implementation in hardware is available?

Not necessarily. For example, with AES-NI instructions you have to load the AES key into XMM registers, which has the potential of allowing a key-recovery attack in the same manner.

If you have a dedicated crypto chipset that also stores the keys then it may be a different matter. Of course, there is no a priori reason to assume it does not have the side channel too. And you need to get the keys into it securely.


About using mistakes as part of a code Could a code be developed where one uses intentional errors  say in english, as a text to encode? For example someone might have a message 'Agent X must report to station 5'. This could be distorted to 'A Gentex missed repaired 2 stationS.' The distorted message then encoded. If the distortions are recognizable to the deciferer this might throw off any attempted interceptions. Also aren't decoding methods usually based on the 'regular' use of english (if english is being used) ? I've never heard of anybody trying to use intentional mistakes in a code. Is this idea useful?

The short answer is that such an encoding would not help with encrypting the content.

A good, modern encryption scheme should at least be secure if the attacker can choose the plaintext, let alone know what the plaintext is. Moreover, most of them are secure if the attacker can even ask for the decryption of ciphertexts of his choice (other than the actual challenge message they're trying to decrypt).

It is worth reading up on known-plaintext-attack, chosen-plaintext-attack and chosen-ciphertext-attacks.


Quadruple DES vs AES-128 security I came across this question regarding the security of Quadruple DES (hypothetically DES done four times) in CBC encryption mode vs security of AES-128 in CBC encryption mode.
What parameters help to decide the security, assuming 4 different keys (or other case with k1, k2, k3, k1) so the key length would be 224bits (3DES provides 100-bit security level) vs 128bits for AES.

In some applications, a serious limiting factor for the security of 4DES is its 64-bit block size. In common modes of operation, that limits the security to data sizes that are insufficient for many application nowadays. It makes 4DES much less secure than AES-128 is.
For example, assume a VPN in CBC mode using a fixed key. Assume an adversary injects known traffic consisting of a known repeated byte representing 99.9% of the payload for 64 GiB of reference ciphertext, then gets another 64 GiB of actual ciphertext. With good probability there is at least one match between one of the $2^{33}$ blocks (of 8 bytes) of the reference traffic and the $2^{33}$ blocks of the actual traffic. And any such matching block can be deciphered correctly with >99% probability.
If we want residual risk at most $\epsilon$ that this kind of attack succeeds, we need to limit the traffic with the same key to about $2^{36}\,\sqrt\epsilon$ bytes. For a residual risk of one in a million, that's about 64 MiB, not a lot by modern standards.
While DES-CTR with non-overlapping counter is less susceptible to this attack than DES-CBC, such mode is unusual, impractical, and remains vulnerable to a distinguishing attack at similar data size threshold.


What is the fuss about 'dot blockchain' and music metadata? and how does it work?

http://wmot.org/post/music-money-and-metadata-promise-blockchain#stream/0

claims that this is an answer to the metadata woes of the music/recorded media industry.

I don't see how it can possibly prevent rewriting the file.

What is the fuss about 'dot blockchain' and music metadata?

Publicity man creates his own fuss.

  claims that this is an answer to the metadata woes of the music/recorded media industry.

There are no such woes. Sure there is piracy but that's not because songs can't be identified using a centralized interface (they can, and more efficiently than watermarking).

  I don't see how it can possibly prevent rewriting the file.

It's a watermarking scheme. You can't just get rid of these watermarks by converting to PCM and re-encoding because the watermark is present in the audio data itself. Consider, for example, shifting the center point (DC offset) of the PCM samples slightly - to either "up" or "down" states each lasting a few tenths of seconds, and using this to embed a repeating 128-bit identifier. No quality loss because DC offset is practically ignored by the end output analog playback system and you only shift it slowly.

Then consider fancier tricks like partially undoing the DC shift by selectively amplifying some of the lobes on the other half of the sample space and you get something that requires very advanced processing to remove without introducing artifacts.

The even meaner thing to do if you run an online store is to embed different identifiers for each user when they download the song ... then when some of these downloaded songs, each unique, appears on a file sharing site you can do "traitor tracing" and send in the FBI.

In terms of the other stuff they talk about, enforcing the rights, well, that's just not doable with today's tech because it will come out in analog at some level. Even assuming a secure encrypted link between a computing device and a set of speakers, at the most basic level you can just capture the analog voltage going to voice coil and process that somehow back into an audio file to drop DRM restrictions.

Note however that a good watermarking scheme will survive a few iterations of this. Applying DRM restrictions automatically based on watermarking sort of works in theory but requires a doomsday trusted computing scenario where users have absolutely no ability to run arbitrary programs on their computing devices (i.e., programs that don't necessarily obey DRM restrictions).

Watermarking is quite an old technology. It appears what they consider to be the main benefit of putting the metadata on the public blockchain is that it cannot be revoked (as in, the publisher who applied the watermark going out of business and lookups to their website/API failing to provide data for audio files). This is a mildly interesting idea for Indie media, etc, but of course big media does not assume they are going to go out of business any time soon so there is no impact on their business model from this technology.


RSA and prime difference It is known that the two prime factors $p$ and $q$ of an RSA modulus $n$ should not be too close to each other, otherwise an attacker may factor the modulus. In other words, $\Delta = \left| p - q \right|$ should not be too small.

However, "too small" is a somewhat subjective measure. "Too small" with respect to what? And why?

I do realize that it is considered a best practice - given a modulus $n$ of $k$ bits - to pick $p$ and $q$ as random primes with bit length $k/2$ (see also HAC, section 8.8, note ii).

On the other hand, Section B.3 of the Digital Signature Standard standard recommends $\Delta > 2^{k/2-100} $ when generating an RSA key. That is, $p$ and $q$ should simply differ by a number which is at least 100 bits long somewhere in their 100 most-significant bits (thanks poncho!), independently of the bit length. That is not in contrast to the best practice above, and it could be deemed a redundant check.

However, both approaches seem to imply that a dangerous $\Delta$ is much, much less than $2^{k/2}$. Is there any formal proof of that? And is there any quantification for such dangerous $\Delta$?

This question is only relevant if you choose $p,q$ in a non-standard way.  The standard way to choose $p,q$ is to choose them as two independent random $k/2$-bit numbers.  If you do it the standard way, the question is not relevant (the probability that $|p-q|$ is too small is negligible -- and is dominated by the chances of other kinds of failures).

This question would be relevant if you were choosing $p,q$ in some funny way that had an unusually high probability of making $|p-q|$ be unusually small.  Yes, you can quantify how much easier this makes factoring.  For instance, the Fermat factoring method works as follows: for $a=\lceil \sqrt{n} \rceil, \lceil \sqrt{n} \rceil+1, \lceil \sqrt{n} \rceil+2,\dots$, it checks whether $n/a^2$ is a perfect square; if so, it has factored $n$.

We can analyze the running time of Fermat's method.  Let $\epsilon=(p/\sqrt{n}) - 1$, so that $p=\sqrt{n}(1+\epsilon)$ and $q=\sqrt{n}/(1+\epsilon)=\sqrt{n}(1-\epsilon+\epsilon^2-\cdots)$.  Fermat's method succeeds when $a=(p+q)/2=\sqrt{n}(1+\epsilon^2/2-\cdots)$.  In other words, it requires $\approx \sqrt{n} \epsilon^2/2$ iterations.  So, if you want this to take at least $2^{100}$ time, you need $\sqrt{n} \epsilon^2/2 \ge 2^{100}$, or equivalently, $\epsilon \ge 2^{50.5}/n^{1/4}$.  Since $|p-q| \approx 2\sqrt{n}\epsilon$, this means we need $|p-q| \ge 2^{51.5} n^{1/4} = 2^{51.5} 2^{k/4}$.

In other words, if you want Fermat factoring to take at least $2^{100}$ time, you need $\Delta$ to be at least $2^{51.5} 2^{k/4}$.  For a detailed derivation, see

Cryptanalysis of RSA with small prime difference, Benne de Weger, Applicable Algebra in Engineering, Communication and Computing (AAECC) vol 13 no 1 pp.17-28, 2002.  See Section 3 (much of the rest is not relevant and addresses a different question).

See also the following paper, which says that $n$ can be factored in polynomial time if $|p-q| \le 2^{k/3}$:

The Fermat factorization method revisited, Robert Erra and Christophe Grenier, eprint 2009/318, July 23, 2009.

For instance, the paper gives an example of a 1024-bit RSA modulus ($k=1024$).  It says that if $p$ and $q$ are identical in their 171 most significant bits, then you can factor $n$.  You can compare this to the requirement in the DSS standard, if you like.

But again, the right way to make this attack infeasible is to choose $p,q$ independently at random (as is the standard method).  And if you choose $p,q$ in the proper way, the threat is rendered infeasible, and you don't need to worry about the size of $|p-q|$.  For example, if you want a 2048-bit RSA key, choose a random 1024-bit key $p$, and then choose a 1024-bit key $q$.  Don't worry about their difference; the mathematics say that they will have a sufficiently large difference.

I hope that this answers your question sufficiently.

I see that the DSS standard does contain the requirement that you mention.  I think it is ill-considered, or perhaps not there for the reason you might think it is.  It is true that if you chose a RSA modulus by picking $p$ and $q$ in some crazy way that made it likely $|p-q|$ would be small, then RSA would be insecure (there are factoring methods that can be used to factor $n$ in this circumstance).  However, in that case the problem there would not be that you chose $p,q$ with a small difference: the problem would be that you failed to generate $p,q$ independently at random.  So, don't do that.  As long as you do generate $p,q$ properly, you don't need to separately check any condition on $|p-q|$; if $p,q$ are chosen randomly and independently at random, the chances that $|p-q|$ is too small is negligible (less than the chance of getting struck by lightning several times in a row, less than the chance of someone factoring your RSA modulus, etc.).

Why does the DSS contain this recommendation?  I don't know.  I think the recommendation is misguided and unnecessary.

Bottom line: the best answer to your question is to un-ask the question, as it contains some implicit assumptions that are not valid.


Encrypting a 64-bit binary number to a text containing upper- and lowercase, and digits I am making a tool that generates 16 character long password out of a 64-bit binary number. But I dont know how to make an encryption key for that, or where I can find one.

To show what i mean, here is an example with 8 bits:

I have the binary number: 10110111

The output could than look something like this:

t6Yli12q

And I want the password that gets generated from this: 10010000, to be completely differnt than the password that gets generated from this: 10010001.

Can anyone help me with this, or maybe redirect me to a site that says something about these types of encryption?

Note: I am very new to cryptography, so this might be simple for most of you, or maybe harder than I think.

You can use Key Derivation functions (KDF) to generate secret keys, e.g., from passwords. In 2013 a Password Hashing Competition was organized and the winner is Argon2 KDF. Argon now very popular and it has a new version named argon2i.

From Wikipedia;

  In cryptography, a key derivation function (KDF) derives one or more secret keys from a secret value such as a master key, a password, or a passphrase using a pseudorandom function. KDFs can be used to stretch keys into longer keys or to obtain keys of a required format, such as converting a group element that is the result of a Diffie–Hellman key exchange into a symmetric key for use with AES.

Once a key is generated, you can stip the key into the desired size.

In the end, if you want to human readable generated keys apply Base64 encoding for the derived key. Base64 encoding uses 6-bit to encode data From $A–Z, a–z,0–9$, and $+,/$.


Example of a universal one-way hash function that is not collision resistant hash function In collision-resistant hash function, first, a hash function is sampled and the adversary is allowed to pick a collision $(x, x')$ s.t. $H(x) = H(x')$ and $x \neq x'$.
In a universal one-way hash function, first, the adversary picks $x$, and then a hash function is sampled, and then the adversary is supposed to find $x'$ s.t. $H(x) = H(x')$.
Is there any example of a universal one-way hash function that is not collision resistant?

One can construct such an example artificially. Denote the key to the hash function by $s$ (and recall that this key is public). Now, let $H$ be any universal one-way hash function, and define $H'_s(s) = H'_s(s+1)$. This requires changing just one point in $H$, and so is easy.
Notice that $H'$ is clearly not collision resistant: given $s$, just output the pair $(s,s+1)$. However, I argue that $H'$ is still a universal one-way hash function (often called target collision-resistant). The reason for this is that the only way that this change to $H$ can help is if the adversary chooses $x=s$ or $x=s+1$ before the key is chosen. However, this can only happen with negligible probability, unless the key space is polynomial in size. However, if the key space is so small, then the hash function cannot be secure anyway (basically, in such a case, you can just get rid of the key).


Exact mathematical definition of simulation based security? I've been trying to understand cryptographic protocols and how to define their security. The problem is that while I can understand what the intuitive definition says, I have trouble understanding how this can be rigorously defined in terms of mathematics. In other words, how do we get a definition that can be used in proving something?

For simplicity, let's take a two-party protocol between $A$ and $B$. This can essentially be modeled as a 2-ary function $f(x,y)=(f_A(x,y),f_B(x,y))$, where $x$ and $y$ are the local inputs and $f_A$ models $A$'s output and $f_B$ models $B$'s output.

Now the intuitive definition is that we can have our ideal protocol, where we have a trusted party $T$ and $A$, $B$ just hands over their local inputs to $T$, which replies with either $f_A(x,y)$ or $f_B(x,y)$. The protocols would then be considered secure, if given any adversary $\mathcal{A}$ for the real-world protocol, we can construct an adversary $\mathcal{S}$ for the ideal protocol that ''accomplished the same thing''. While this sounds like what we intuitively want, it provides no bases for really any proofs.

I've seen some alternative definitions where the ideal and real-world protocol output a ''transcript''. The protocol would then be considered secure if e.g. no PPT algorithm can distinguish the transcripts. However, I have no idea what the exact mathematical definition of a transcript is?

I would hope that someone could actually open up these definitions and explain how to make them rigorous. Hopefully also with a concrete example.

Suppose Alice has $x$ and Bob has $y$ in your scenario, and let $\pi =(\pi_A, \pi_B)$ be the protocol machines for Alice & Bob respectively. Here is how you would formally define security of the protocol against a corrupt Alice.

Define the following algorithms / random variables:

${\sf Real}(\pi, y,\mathcal{A},1^k)$:

Internally simulate an instance of $\pi_B$ on inputs $(1^k,y)$, interacting with an instance of $\mathcal{A}$ on input $1^k$.
$\pi_B$ will eventually terminate; call its output $q$ (note, this is supposed to be the output of $f$, or it can be an error indicator). Likewise $\mathcal{A}$ will eventually terminate; call its output $t$.
Output $(q,t)$.

${\sf Ideal}(f, y,\mathcal{S},1^k)$:

Internally simulate an instance of $\mathcal{S}$ on input $1^k$ until it generates an output $\tilde x$.
Calculate $p = f_A(\tilde x, y)$ and $q = f_B(\tilde x, y)$.
Give $p$ to $\mathcal{S}$ and keep running it until it finally terminates; call its output $t$.
Output $(q,t)$.

Then we say that the protocol is secure if:

  For all PPT machines $\mathcal{A}$ there exists a PPT machine $\mathcal{S}$ such that for all $x,y$, the ensembles $\{ {\sf Real}(\pi, y,\mathcal{A},1^k) \}_k$ and $\{ {\sf Ideal}(f, y,\mathcal{S},1^k) \}_k$ are computationally indistinguishable.

I'll assume you're comfortable with the notion of computational indistinguishability.

Some general observations:

The value $t$ is whatever $\mathcal{A}$ decides to output. One reason why it's difficult to understand at first is that we are not specifying a "goal" that $\mathcal{A}$ wants to achieve. It's more general than that. Instead, we're saying that: Any value $t$ that $\mathcal{A}$ can generate by participating in the real interaction, is possible to generate when the only thing you are allowed to do is choose an input $\tilde x$ (once) and get back $f_A(\tilde x, y)$.

Without loss of generality, $t$ can be the entire view (private randomness along with all of the messages received in the protocol) of $\mathcal{A}$, since $t$ would have been efficiently computed from the view. Sometimes the terms view and transcript are used synonymously, though the term view better entails that private randomness is included as well. Also, this is why $\mathcal{S}$ is referred to as a simulator, since it must be able to simulate everything that $\mathcal{A}$ would have seen.

We also include the output $q$ of the honest party Bob in these distribution ensembles. This models the fact that $\mathcal{A}$, in addition to learning no more than is possible in the ideal world, has an effect on Bob that is possible in the ideal world. In particular, $\mathcal{A}$ can't force Bob to output a value that is inconsistent with $f$ (other more subtle attacks are also ruled out in this way).

Of course, even this fairly detailed definition does not include everything tha there is to say. To be absolutely precise you have to specify how the protocol interaction works, whether the adversary has control over delivery of messages, whether the multiple components (adversary, protocol) should be executed in series or parallel, etc.. But once you have conventions for these things, the $\sf Real$ and $\sf Ideal$ processes are well-defined, and everything else written here is pretty sound.

More sophisticated definitions allow $\mathcal{A}$ (and hence $\mathcal{S}$) to communicate online (i.e., during the protocol execution) with an external "environment" ... that introduces a whole lot of other complications. So for the purposes of this response, we'll leave it as a static interaction.