Why does RSASSA-PSS produce different signature each time even if I use same salt and same message? I understand that RSASSA-PSS is not deterministic. But I see that in message encoding, MGF and SHA functions are deterministic. So even if I keep default salt length, it produces different signature.

Where is the randomness introduced?

You aren't using the same salt.

The randomness is introduced with the salt: it is generated randomly. The input to the MGF is calculated from the hash and the salt. Thus, if you sign the same message twice, you get different signatures, because the salt is different each time. For the details, see PKCS#1 (RFC 8017) §9.1.1.

There are only two ways to use the same salt with any sane implementation of RSA-PSS.

If you choose a salt length of 0, then the salt is always the same, and PSS becomes deterministic.
If you can set the state of the RNG, using the same message with the same RNG state will result in the same signature.

Otherwise, if the salt length is $n$, there are $2^{8n}$ possible salts, and the probability that two given signatures would use the same salt is $2^{-8n}$, which is negligible (unless $n$ is very small, but in practice it isn't).

The default salt length is the length of the hash in most implementations. More precisely, most implementations use the maximum possible salt length, which is usually the hash length but can be shorter when using a large hash with a small key (the salt plus the hash plus two bytes must fit in the key size in bytes, so a 1024-bit key with SHA-512 only leaves room for a 30-byte salt). The general rationale is that if you wanted your signature to be deterministic, you'd use PKCS#1v1.5; and if you're going to use a salt, the cost of making it longer is negligible, so you might as well make it maximum-length.

On why you'd want a signature algorithm to be non-deterministic, see Why use randomness in digital signature algorithms? (which mostly covers RSA-PSS). On the salt length in RSA-PSS, see RSA-PSS salt size


ECIES is must with Symmetric?(ECIES-AES or ECIES-TDES) I can't understand the ECIES algorithm.

I saw two different ECIES algorithms:

Using only Public key

Key generation:

$A_{pri} : n_A$
$A_{pub} : n_A G$

$B_{pri} : n_B$
$B_{pub} : n_B G$

Encryption:

Select a random $k$.

A -> B to Cipher C : $\{kG, \text{message} + k B_{pub}\}$

Decryption

$\text{message} + k B_{pub} - n_B kG = message + k n_B G - n_B k G = \text{message}$
Using Symmetric key(AES)

what is real?

Yes, ECIES is essentially a more practical implementation of ElGamal, a hybrid cryptosystem.  It uses symmetric encryption following an ephemeral key exchange.

Refer to : https://en.wikipedia.org/wiki/Integrated_Encryption_Scheme

Compare it with : https://en.wikipedia.org/wiki/ElGamal_encryption

The only difference is that instead of using KDF+XOR or AES+GCM as the symmetric cipher, ElGamal specifies a different symmetric step mapping the message to a point and using inverse modulo to recover.

Once of the oddities is that using a KDF and then using XOR was the most popular version of ECIES for a number of years.   If used carefully, it's OK, but without properly padding the message, things can get ugly (chosen ciphertext attacks, etc.)

Ditching XOR and using AES/GCM with the shared secret seems, to me, like the better move, shifting responsibility for the authentication onto the symmetric layer.  The use of KDF/XOR is still prevalent in modern libraries, mostly because some XOR variants were FIPS certified.


How is the SHA-1 collision detector so fast? The google collision website shattered.it refers to a collision detector: https://github.com/cr-marcstevens/sha1collisiondetection.

It claims a false positive rate of $2^{-90}$ and to take less then twice the time of regular SHA-1. But the counter-cryptanalysis paper mentions that the false positive rate is $C \cdot 2^{-160}$ and it takes $C+1$ times longer then regular SHA-1 - and they suggest using $C=14$.

What am I missing? How many triplets does the detector use? Is there another paper explaining a more advanced technique that explains the performance?

One trick used by the collision detector you mention is to check for "unavoidable conditions", described in the paper here: http://oai.cwi.nl/oai/asset/23932/23932A.pdf

Essentially, the unavoidable conditions are a faster check, but may have false positives. If a given block meets these conditions, the detector then runs the full check. Per the paper above, the total cost of doing this is only 1.96 times the regular SHA-1 runtime.


How to decrypt a substitution cipher using a Base64 alphabet Let us consider a cipher that works like the following:

Plaintext is encoded to Base64.
The characters in the encoded plaintext are substituted with a randomly shuffled character set (a-z, 0-9, A-Z, /, +).

The shuffled alphabet are the key. How do I decipher it to get the base64 encoded string without knowing the shuffled character set?

Base64 encoding regroups three consecutive 8-bit values (0-255) into four 6-bit values (0-63). Each value is used to index of a small ASCII array which is typically sequential, such as,

var base64Map = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=';

Base64 decoding is the reverse process. Each character's position is an indexof a matching ASCII array which results in a 6-bit value. Four of these are regrouped into three 8-bit values.

In your case, I suspect the base64Map was shuffled, rather than a separate shuffle operation of the encoded plaintext. If this is the case, then you need to match the order of the encoding array. If truly random, this would become a monumental effort. Perhaps try a Caesar Shift of the array.


Replacing the Rijndael S-Box? The Rijndael S-Box design generates a permutation cycle of type $2+27+59+81+87$. What effect would replacing that permutation with a cycle of type $256$ have on the security of AES?

The security of a block cipher is, based on what we know, invariant to the permutation cycles of the S-box. This is because the values are always transformed (by a fixed function or a keyed function) before going through the S-box again in the next round. Furthermore, many S-boxes are functions not permutations (i.e., output size is different from input size), so the property does not apply.

The permutation cycles of the entire cipher (with respect to a fixed key) are of interest. I am aware of a number of papers that examine this for DES (see last paragraph of page 277 in Handbook of Applied Cryptography).

The AES S-box does have a design behind it, both in terms of the steps take to generate it and in terms of its structure with respect to linear/differential/algebraic attacks. If you maintained these properties and only modified the permutation cycles, the security should be equivalent.

There is some work on using permutation polynomials to create s-boxes that may have some further insight into whether it is generally a good or bad approach. However I am not familiar enough to comment.


Question about SSH host key algorithms I'm currently writing a report for my Master's degree on the SSH protocol. Quite interesting!
However I'm having trouble getting into the inner workings of the host key algorithms.
For example, according to RFC4253, "ssh-rsa" is a key format where the server generates an RSA keypair. So far, so good. However, I don't seem to understand where SHA-1 comes into the play.
RFC8332 says

"SSH originally defined the public key algorithms "ssh-rsa" for server and client authentication using RSA with SHA-1".

My understanding is that the server computes a hash of the public key using SHA-1 and when appropriate, sends both the public key part and its SHA-1 computed hash with to the client.
Am I correct?
This isn't in any way related to the fingerprint shown when we connect to an SSH server for the first time, is it? If not, how can I calculate it (without ssh-keygen)?
Many thanks!

The principle of SSH is to implement secure (i.e. confidential and authenticated) communication channels in a client–server session. The new release of SSH (known as SSH2) uses public-key infrastructures in order to authenticate servers. This is typically heavy stuff, but the user can easily bypass it: he just has to click “OK” anytime there is a ,security warning.

SSH2 uses DSS for server authentication and Diffie-Hellman key agreement for setting
up a symmetric session key (previous versions were entirely based on RSA). Both
are based on some generator g which generates a subgroup of Z∗
p of prime order q.

The client picks a random ${x ∈ \{1,..., q − 1\}}$, computes ${e = g^x mod p}$, and
sends it to the server.

The server picks a random ${y ∈ \{1,..., q − 1\}}$, computes ${f = g^y mod
p}$ and ${K = e^y mod p}$.

Now server computes the Hash H using various other values and signs it, ${s=sig(H)}$.where ${K_S}$ is his public key, and sends
${K_S}$, f , and the signature s to the client.  This H could be generated from SHA-1.
Now, When you connect to a machine for the first time you will be told that the authenticity can't be established and presented with a key fingerprint to check.
This fingerprint is generated from the server public key may be SHA1 or SHA256.
you can use:-  $ ssh-keygen   -lf   ~/.ssh/id_rsa.pub


Pseudo random permutation for arbitrary size domains Popular block ciphers like AES or Twofish are keyed pseudo random permutations on the domain $\{0,1,\dots,2^{k}-1\}$ with $k\in\{128,192,256\}$ or similar.

I'm interested in pseudo random permutations on domains whose size is not a power of two: Are there any fast (in the ballpark of AES) keyed pseudo random permutations that operate on $\{0,1,\dots,n\}$ with $n\in\mathbb{N}$ being an adjustable parameter?

Ciphers with Arbitrary Finite Domains by Black and Rogaway have some options like Prefix Ciphers, Generalized Feistel networks , Cycle walking etc.

Also Format preserving encryption has traits that you are looking for , but NIST standardized ones are patented by Voltage Inc.

In general Feistel networks + Cycle walking would give a good option for any arbitrary length (even or odd) domains .

This question has much better answer
Is there a length-preserving encryption scheme?


How can I use SSL/TLS with Perfect Forward Secrecy? I'm new to the field of cryptography, but I want to make the web a better web by setting up the sites that I host with Perfect Forward Secrecy.  I have a list of questions regarding the setup of Perfect Forward Secrecy.  Here it goes:

Can my choice of certificate authority hinder the use of Perfect Forward Secrecy?
How can I create the strongest certificate using ONLY Perfect Forward Secrecy (meaning if the browser can't use PFS, it won't load anything)?
Are there any extra settings that I need to know about for configuring my sites to use these certificates (especially since I only want PFS)?
Anything else that I should know, feel free to tell me.  I'm completely new to this idea.

In the beginning SSL handshake, the client sends a list of supported ciphersuites (among other things). The server then picks one of the ciphersuites, based on a ranking, and tells the client which one they will be using.

This step is the one that determines whether or not the future connection will have perfect forward secrecy. Note that, at this point, certificates have not entered the picture at all. This is because whether or not a connection has perfect forward secrecy is determined by how the session key is derived. And how the session key is derived is determined by the ciphersuite in use. So, the ciphersuites that use ephemeral Diffie-Hellman (DHE) or the elliptic-curve variant (ECDHE) will have perfect forward secrecy while the other options will not.

Thus, in order to configure PFS for your site, what you want to configure is your web server's ciphersuite-selecting options. More on this below.

  Can my choice of certificate authority hinder the use of Perfect
  Forward Secrecy?

No. Perfect forward secrecy protects against the revelation of master keys. CAs do not have access to private (master) keys; a certificate from a CA is a signed public key. The CA is there to say "okay, client, I have verified that the public key here is indeed associated with <host>, it's safe." (Or, rather, the fact that it's signed by the CA says this.) Thus, your choice of CA will not impact PFS in any way.

  How can I create the strongest certificate using ONLY Perfect Forward
  Secrecy (meaning if the browser can't use PFS, it won't load
  anything)?

As you can see, certificates are unconnected with the choice of ciphersuite (and hence PFS).

Instead, the web server you use probably has a ciphersuite configuration in its SSL configuration. There are usually two relevant options: first, the ciphersuites that you want your server to use, and second, how the server picks the ciphersuite. Here is the relevant section in my nginx configuration:

ssl_protocols TLSv1 TLSv1.1 TLSv1.2;
ssl_ciphers ECDHE-RSA-AES128-GCM-SHA256:ECDHE-RSA-RC4-SHA:ECDHE-RSA-AES128-SHA:RC4:HIGH:!MD5:!aNULL:!EDH;
ssl_prefer_server_ciphers on;

The first line tells nginx to use those four protocols, as is apparent. The third line tells nginx to prefer its own ciphersuites over the client's. The point here is that we want to control exactly which ciphersuite will be selected. A client may send an ordering that suggests a non-PFS ciphersuite; hence, we trust the server.

The second line is where the magic happens. Note that I manually specify that I want those three ECDHE-* schemes first if they are supported by the client. From there, I fall back to the usual schemes. I feel the need to emphasize that I don't disallow clients that don't support PFS; some encryption is better than no encryption at all. Not all clients do support PFS, so this is pretty important. I realize your question said you want only PFS ciphersuites, but I would advise against that. With the above nginx configuration, the vast majority of connections' selected ciphersuites will have PFS. The configuration for Apache is apparently quite similar, which is not surprising given that both use OpenSSL.

To that end, a useful tool: the SSL Labs SSL Test. It gives you a basic grade on your SSL configuration. See, for example, Google's grade (click on one). It has a little green box under the grade informing you that the site supports PFS for all its tested browsers, and if you scroll down to 'Configuration', you will see a ciphersuite priority list, including which ciphersuites have PFS, as well as "simulated handshake" for the common browsers of the day.


Pipelined architecture for secret key block ciphers I want to implement a pipelined architecture of AES128; and I couldn't figure out the number of the pipline stages. As I undestand, it is possible to make the piepline stages inside the round, or outside it or both. What I don't understand is if the I chose to make them inside a round, why the number of stages must be a divisor of number of rounds? I understand that it must be a divisor if the pipelined stages are between the rounds. Correct me if my understanding is wrong.
I think that since there is 4 operations inside every round then it is possible to make 4 stages? but what about the last round?
Here what I have read:
A traditional methodology for design of high-performance implementations of secret-key block ciphers, operating in non-feedback cipher modes is shown in Fig. 21. The basic iterative architecture, shown in Fig. 21a is implemented first, and its speed and area determined. Based on these estimations, the number of rounds K that can be unrolled without exceeding the available circuit area is found. The number of unrolled rounds, K, must be a divisor of the total number of cipher rounds, #rounds. If the available circuit area is not large enough to fit all cipher rounds, architecture with partial outer-round pipelining, shown in Fig. 21b, is applied.

the number of stages must be a divisor of number of rounds

That applies to pipelined and to iterative implementations where one stage implements $k\ge2$ rounds out of $K$, and we want each of the $K/k$ stages needed for a full block cipher strictly identical. That requirement could be waived by making less rounds in the last stage, or in an iterative implementation using an extra multiplexer extracting the output after $K\bmod k$ rounds in the last of the $\lceil K/k \rceil$ stages. That requirement does not apply at all to implementation with a single round, or less, per pipeline stage.

in AES, since there is 4 operations inside every round then it is possible to make 4 stages?

Yes, with 4 stages per round, thus $4K$ stages per block ($K\in\{10,12,14\}$ depending on key size). That's useful in an iterative implementation (which goal is reduced silicon area at the expense of throughput). One stage still needs to perform 4 identical byte substitutions (since each 16 bytes of a block go through that at each round) in the SubBytes steps, thus a minimum-area implementation might further subdivide that, for a total of $16K$ steps per block.

but what about the last round?

Indeed the last round needs to be special-cased; in a pipeline that's different (simpler) function in the last round, in an iterative implementation that's an extra input to the logic to inhibit MixColumns, held to a different state during the last of the $K$ rounds.


Why do the game-hops in Kyber and related papers contain 2 steps at a time? In the Kyber paper in section 3 about the Kyber IND-CPA Encryption there is a proof by sequence of games containing three games. I understand that in the first game hop the M-LWE advantage is used to bound the advantage of distinguishing the games.
The second hop (from $G_1$ to $G_2$) exchanges two elements ($\boldsymbol{u}', v'$) in the protocol at the same time with essentially the same reasoning.

A similar proof based on R-LWE instead of M-LWE can be seen in the paper by Bos et al. in section 3.

Why is this done in one hop instead of two distinct ones and would it be valid to do it in two hops, i.e exchange one element first and the second one in a second hop?

I'm answering my own question here, because i finally found the answer and want to preserve it for future reference.

The Bos et al. paper states it more clearly.
The define the R-LWE problem as a problem on $m$ independent samples, either from the uniform distribution over the ring, or from the R-LWE Distribution where the secret $s$ is common to all the samples.
With this assumption, we can clearly do the game hop with two simultaneously exchanged parameters (here $m=2$).
I am assuming the definition for M-LWE is similar.

Regarding validity of splitting the game hop into two:
That may be possible, but is not obvious, i.e. I was not able to write down the reduction.


Randomized functions cannot increase statistical distance In these lecture notes instructor Chris Peikert states the following lemma without a proof

  Let $f$ be a (randomized) function on the domain of $X$, $Y$. We have

  $\triangle (f(X), f(Y)) \leq \triangle(X, Y )$

where triangle denotes statistical distance between two random variables.

First question: How can I prove this?

Second question:

Assume $X$ and $Y$ are independent uniformly distributed random variables. Define randomized algorithm $f$ like this:

$f(x) := \text{return 1 if $X = x$ and 0 otherwise}$

However, $\triangle (X, Y)=0$, but $\triangle (f(X), f(Y))$ is not zero? What I am missing here?

Second question:

$\Delta$ is defined on distributions so the distributions of $f(X)$ and $f(Y)$ are the same, since $X,Y$ are both uniform. The supremum definition makes this clearer.

First question:

Unless the map is one to one, hence a bijective,  when equality holds, the probability that $f(X)=f(Y)$ can only increase compared to the probability that $X=Y$. Prove this for binary distributions and then subpartition and use induction to conclude the general case by using conditional probabilities.


Shamir Secret Sharing data limitations per share? Do “Shamir Secret Sharing” schemes have a limitation for the amount of data that can be split up between each share, or a maximum number of data that can be shared within one secret?

I believe there is a relationship between the maximum data that can be shared the prime and the number of shares, or am I mistaken?

In principle, the secret is a single field element. Thus, this is exactly what you can store. However, there is a notion called "packed secret sharing" that enables you to store more than a single value. However, it cannot always be used, and it depends on the required thresholds. For example, assume that you wish that no less than $t$ parties will be able to learn anything about the secrets, but you can assume that $t+\ell$ parties will be able to come together to reconstruct. Then, in this case, you can share $\ell$ values using a single polynomial of degree $d=t+\ell-1$. In order to do this, you can define $p(-i)=s_i$ for $i=0,\ldots,\ell-1$ for secrets $s_0,\ldots,s_{\ell-1}$, and then use other points for the parties' shares (use $p(i)$ for party $i$'s share). Of course, in this case, you also need the field to be larger than $n+\ell$ where $n$ is the number of parties.


Is it possible to determine if data was encrypted by a specific public key? If the prover provides a block of data and a public key. The provided data is supposedly ciphertext that was encrypted using the provided public key. Is there a way to prove that the provided data has infact been encrypted using that specific public key?

The verifier does not have access in any way to the plaintext data or the private key. However, the prover does have access to the plaintext data and private key, and can provide additional information to assist in proving, as long as zero knowledge of the plaintext data and private key are exposed to the verifier.

Update:
Based on the current responses, it seems unlikely that the verifier would be able to prove or disprove the claim by the prover using only the provided data and public key. However, the question still remains if this could be accomplished using some form of additional proof data, possibly in conjuction with a zero knowledge based algorithm.

This depends on the scheme that is being used.

In the case of a scheme that behaves like a random oracle: We could assume that the scheme that is used behaves as a random oracle, and that we are to infer by the ciphertext that some specific key was used. This would imply that we could actually get some information about the key, by knowing only the ciphertext (and not the plaintext). Namely if a specific key was used to encrypt the plaintext. This would however violate the assumption that the scheme behaves like a random oracle. So in the case of a random oracle the answer would be no.


Why use an RSA public key exponent of form $2^n+1$ instead of $2^n-1$? The short exponents in RSA which are only a few bits in length,i.e. $e=3,\ 17$ and $2^{16} +1$

Why we are using exponents of the form ${}2^n+1$ not $2^n-1$?

The keys of form $2^n + 1$ only contain two bits set (the ones in your question are also short prime values, in case you didn't notice). The public exponents of form $2^n - 1$ on the other hand contain a lot of bits set when $n$ grows (the value 3 is obviously both 10 + 1 in binary as well as 100 - 1 in binary).

Modular exponentiation is usually deemed more efficient if only a few bits are set. At least it is easier to see how to implement it efficiently. The public exponent is usually a prime to make it easier to find a value of $p$ where the public exponent is relative prime to $p - 1$.

Note that $2^{16}+1= 1\ 0000\ 0000\ 0000\ 0001b$ and $2^{16}-1=1111\ 1111\ 1111\ 1111b$. So there is quite a difference in the number of bits set (2 against 16). As the value is 65535 in decimal, it is quite obviously not a prime either as it divides by 5. Then again, $2^{17} - 1 = 1\ 1111\ 1111\ 1111\ 1111b$ is prime and contains as many bits.

The primes with just 2 bits set (the first and last one) are called Fermat primes. There are currently five known Fermat primes:
$$F_0 = 2^{1} + 1 = 3$$
$$F_1 = 2^{2} + 1 = 5$$
$$F_2 = 2^{4} + 1 = 17$$
$$F_3 = 2^{8} + 1 = 257$$
$$F_4 = 2^{16} + 1 = 65537$$
if there are any others (this is an open math problem) they will most definitely not be small primes.

For comparison, try to calculate both $6\times999$ and $6\times1001$ in normal decimals. It is easy to see why this calculation is efficient.

[EDIT] I did do some performance measurements on Java 8 build 71 and I did not find a (consistent) difference between Fermat and Mersenne primes. This could be due to the information that Poncho provided:

  Note: $e=2^{16}+1$ can be computed with 16 squarings and 1 multiplication; $e=2^{16}−1$ can be computed with 15 squarings and 4 multiplications; calling the former 'much more efficient' appears to be a bit of an exaggeration...

But it could also be due to side channel protection in the Java runtime. In the end it will depend on the implementation as well. It does seem to show a common misconception that Fermat primes should always be (much) faster than other primes. I would not be surprised if Fermat primes are just more entrenched than other values.

The following are the known Mersenne primes (values that are both prime and of form $2^{n}-1$) up to $2^{31}-1$.

$$2^{3}-1 = 7$$
$$2^{5}-1 = 31$$
$$2^{7}-1 = 127$$
$$2^{13}-1 = 8191$$
$$2^{17}-1 = 131071$$
$$2^{19}-1 = 524287$$
$$2^{31}-1 = 2147483647$$

I'll be surprised if I see a use for these Mersenne primes as public exponent within RSA though.


PyCrypto and AES: can i use a longer key than the block size (16byte)? I see that in many scripts are used keys of 16 characters for a block of 16 byte, but can I use key of 40 (for example)? And then why in some scripts with aes module the block size is set to 32 byte if aes can handle a fixed size block of 128 bit? Is it correct?

I see that in many scripts are used keys of 16 characters for a block of 16 byte, but can I use key of 40 (for example)?

No, AES uses a key size of 128, 192 or 256 bits. That's 16, 24 or 32 bytes.

  And then why in some scripts with aes module the block size is set to 32 byte if aes can handle a fixed size block of 128 bit? Is it correct?

No, that's not correct. It could however be that the module implements Rijndael instead of AES. AES is a subset of Rijndael, and Rijndael can have the block sizes 128, 160, 192, 224 and indeed 256 bits. So in that case the block size can be 256 bits.

Notes:

not all implementations of Rijndael offer support for 160 and 224 bit block and key sizes (so many posts don't mention these block and key sizes);
bytes are not characters, although the name of a byte in C/C++ is traditionally called a char as for ASCII each character is represented by exactly one byte - no conversion necessary;
sometimes when characters are mentioned they actually contain hexadecimal digits; as you need two hexadecimal digits to represent one byte it may seem that 256 bits are used instead of the actual 128 bits.


Overview of relations between cryptographic primitives? Is there a web page that gives a graphical (or, alternatively, a textual) overview of known implications and separations between cryptographic primitives?

More specifically, I am looking for something like the following, but more comprehensive and with references to the respective works.
(The following graphic is taken from a set of slides by Danny Harnik and Moni Naor that I found on the Internet.)

You'll find it in any textbook on basics of cryptography, for example Foundations of Cryptography by Goldreich. I have added a figure which sums up the relationship between the primitives: arrow represent reductions (i.e. $A\rightarrow B$ means that primitive $B$ can be constructed in a black-box manner from primitive $A$) and dashed arrows represent separations (i.e. $A$--$> B$ means that primitive $B$ cannot be constructed in a black-box manner from primitive $A$). The asterisk denotes folklore results (but feel free to correct me if it is wrong).

(1. I'll add other primitives (FHE, iO...) and assumptions (Factoring, DLP...) in due course.

Please correct any mistakes in implicaitons/separations or references.)

Abbreviations

C: Commitments
CFP: claw-free permutation
CRHF: collision-resistant hash function
DLP: discrete-logarithm problem
DS: digital signature
OWF: one-way function
OWP: one-way permutation
TDP: trapdoor permutation
OWF: one-way function
OWP: one-way permutation
OT: oblivious transfer
PKE: public-key encryption
PRG: pseudo-random generator
PRF: pseudo-random function
PRP: pseudo-random permutation
SKE: symmetric-key encryption
UOWHF: universal one-way hash function
ZKP: zero-knowledge proofs for NP

References.

[D]: Damgård. Collision Free Hash Functions and Public Key Signature. Eurocrypt’87.

[GGM] Goldreich, Goldwasser and Micali. How to Construct Random Functions. JACM’86.

[BM] Blum and Micali. How to Generate Cryptographically Strong Sequence of Pseudorandom Bits. SIAM JoC’82.

[EGL] Even, Goldreich and Lempel. A Randomized Protocol for Signing Contracts. CACM’85.

[GMR]: Goldwasser, Micali and Rivest. A Digital Signature Scheme Secure Against Adaptive Chosen-Message Attacks. SIAM JoC’88.

[GMW1]: Goldreich, Micali and Wigderson. How to Play any Mental Game: A Completeness Theorem for Protocols with Honest Majority. STOC’87

[GMW2]: Goldreich, Micali and Wigderson. Proofs that Yield Nothing but their Validity or All Languages in NP Have Zero Knowledge Proof. FOCS’86

[H+]: Håstad, Impagliazzo, Levin and Luby. A Pseudorandom Generator from Any One-Way Function. SIAM JoC’99.

[IR] Impagliazzo and Rudich. Limits on the Provable Consequences of One-Way Permutations. STOC’89.

[LR] Luby and Rackoff. How to Construct Pseudorandom Permutations from Pseudorandom Functions. SIAM JoC’88.

[N] Naor. Bit Commitment using Pseudorandom Generator. JoC’91.

[NY] Naor and Yung. Universal One Way Hash Functions and their Cryptographic
Application. STOC’89.

[Rom] Rompel. One way Functions are Necessary and Sufficient for Secure Signatures. STOC’90.

[Rud] Rudich. PhD Thesis

[S] Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Eurocrypt’98

[Y] Yao. Theory and Applications of Trapdoor Functions . FOCS’82


Possible data leak when duplicating encryption? Say we have 3 keys $K_1$, $K_2$ and $K_3$, and a piece of data $D$.

If I were to encrypt $D$ with all three keys separately and store them together  then discard two of the keys, will it be possible to recover the other keys from it?

My understanding is because we have access to the plain-text via one of the keys, it should be possible for us to figure out the other keys based on all the information we have.

Is that assumption correct? is such a scenario leaking information?

Any good encryption algorithm is resistant to known-plaintext attacks, i.e. an adversary who knows the encryption of certain plaintexts has no advantage in finding the key or even in encrypting other plaintexts or decrypting other ciphertexts. This means, in particular, that the adversary can't find the key. Good encryption algorithms even have stronger properties — even if the adversary can choose the ciphertexts or the plaintexts, they can't reconstruct the key, or encrypt/decrypt other plaintexts/ciphertexts. (That latter property only works for authenticated encryption — with non-authenticated encryption, there are systemic chosen-ciphertext attacks, such as decrypting a prefix of a ciphertext whose decryption is known.)

Barring implementation bugs, having access to the plaintext via one of the keys is of absolutely no help to find the other keys.


Security of Diffie-Hellman when one party has a flawed RNG (compared to TOFU) Use case: We need to establish a long-lived key. In this phase, it is unlikely attacker will either sniff or the modify communication, but we want to cover even this case. So we use Diffie-Hellman or ECDH with some kind of authentication (in order to prevent MITM) for the initial key exchange. We can also assume that both parties don't reuse their DH keypairs. So far, pretty standard situation.

Now, let's assume that RNG of one peer is seriously flawed and attacker can guess (EC)DH private key of this peer. The other peer has unbreakable RNG. My intuition is this in not any worse than simple TOFU (Trust On First Use) key exchange where the party with a high-quality RNG generates the secret and transfers it in plain, hoping there is no attacker in the initial phase. (If we aren't confident about either party's RNG, we could xor random values provided by both parties.)

Note that a flawed RNG does not imply a complete failure. Consider a RNG that is OK for generating unique values (so nonces for encryption are good enough for some modes), but they can be predictable. For sake of simplicity, let's assume attacker can simply learn the key with 100% probability and full accuracy.

In other words, you can imagine a scenario: You have missed the initial (EC)DH key exchange, so you can neither read it nor influence it. You can capture and intercept any subsequent communication, which is encrypted and authenticated using the key exchanged in the handshake you have missed. You have an oracle that can give you the private key used by one party in the initial (EC)DH key exchange. Your task is to learn something about the key or the communication itself. Anything you can learn without knowledge of the oracle is not considered as a gain.

My reasoning about its security is pretty simple:

When the attacker has captured the initial phase, we are flawed in either case, so flawed DH is not worse than TOFU.
When the attacker does not have captured the initial phase, we are pretty secure in case of TOFU. In case of Diffie-Hellman, attacker might have the group, one party's private key (as one peer has a flawed RNG), but she doesn't have other party's public key, as it was present just in initial handshake. Without this, attacker should be unable to learn anything about the secret.

My intuition might be right, but it is far from a proof. Is there any proof of this?

Theoretically, if my intuition above is wrong, both parties can generate random nonces and xor both nonces with the secret. As at least one nonce is unknown for attacker that doesn't know the initial handshake, so the resulting secret is secure in the same way as with TOFU. This is something I can prove to be secure at least as TOFU even in case of flawed RNG on one peer, but it is also some non-standard (and probably unnecessary) addition to DH that requires collecting some additional entropy.

There are a few things missing from this question.

First of all, TOFU (trust-on-first-use) is not a scheme and cannot therefore be compared with DH. TOFU is more a property of a protocol than anything else.

Second, you say you would use "some kind of authentication". This is what TOFU "solves", establishing trust without which it is impossible to authenticate. You cannot just skip over that part of the protocol if you want to compare schemes.

Third, I don't see any  comparison between active attacks and passive attacks. If an attacker can create the private key then passive (eavesdropping) attacks would be possible. It is not clear if passive attacks are possible for TOFU as it is not a protocol or scheme in itself. That said, I think it is tricky to think of a scheme where a broken RNG isn't an issue in itself.

Finally, for your own scheme you say that you "generate random nonces" but it is unclear how these nonces are shared or what they would add if they would be shared publicly.


Are there any known values for common hashes known to have no preimage In a system which requires a user to have a password, as a quick workaround I wrote random junk as the bcrypt hash so that no one will be able to login to that user.
However theoretically there probably is a password which matches this randomly selected hash value.

I was wondering if it could be possible in such a scenario to specially craft a hash value (possibly using a different supported algorithm other then bcrypt) for which it would be guaranteed that there is no preimage.

For bcrypt I suspect this wouldn't be possible, since if my math is correct the expected number of hashes with no 75 char password preimage is (1/e)^(2^416) also known as 0.

But perhaps for another common password hashing algorithm these values would not only be expected but there will also be a way to find such a value.

This is mostly answered (in the negative) in Do well-known hash functions have any "impossible" output values?.  Cryptographic hashes typically don't have enough mathematical structure to talk about things like the number of pre-images a particular value has.  You can do much better analysis of some non-cryptographic hashes like CRC32, since they have so much mathematical structure. In general, uniformly covering the full domain is a design goal, so the property you are asking about would be seen as a weakness.

Of course, it's not hard to design a hash with the property you are looking for.  Given any hash function $h(x)$ you can define

function H(x) {
    var count = 0, result = 0;
    do {
        result = h(x . count);
        ++count;
    }
    while (result == 0);
    return result;
}

Essentially you are just re-hashing any time you would return the "reserved" value.

All that said, the typical way to solve this problem from an engineering standpoint is to use a value definitely outside the set of possible values, like NULL.  This has the advantage that it survives changing your hash functions.


Hash collisions in sha512 hash of secp256k1 public keys For a sha512 hash of a secp256k1 public key, how many other public keys could generate that hash? I would assume zero since the key size is equal to the hash length (secp256k1 public keys are 64 bytes, 512-bit), and there are only $2^{256}$ public keys as the private keys are 256-bit.

The output of the SHA512 is 512-bit, so there are at most $2^{512}$ different outputs.

For random inputs, the expected hash collision with 50% probability is $\sqrt(2^{512}) = 2^{256}$ by Birthday Paradox ($\sqrt(n)$).

The public keys of secp256k1 have 64-byte = 512-bit. To calculate SHA512  hash the input values are padded so that the input size is always multiple of 1024. After $2^{256}$ SHA512 hash of the public keys, we expect to find collisions with 50% probability.

SHA512: For finding a collision with birthday attack for SHA512 is almost impossible. You will need immense time, storage, and power for $2^{256}$ input values.
SHA256: For finding a collision with birthday attack for SHA256 is almost the same as breaking AES-128 by brute force, need for $2^{128}$ hash values. If we assume that the BitCoin miners top peak performance is $\approx 2^{91}$ hashes in a year, you will need $2^{37}$ years with the same computing platform and power consumption.


Why Nonces and timestamps are used in Public key authority? why the nonces(N1 and N2) and Timestamps(T1 and T2) are used in Public key Authority? which of them prevent replay attack?

To understand how nonces and timestamps are used to prevent a replay attack, you must understand generally what a replay attack is. A replay attack is a network attack in which a data transmission (that is valid) is repeated or delayed. An attack like this is usually done by an adversary who happens to intercept this data and re-transmits it.

If Alice (Initiator A) and Bob (Responder B) are conversing, Alice can send over a nonce with a MAC which can be checked by Bob to verify that it is Alice and not an adversary sending it.

Timestamping also is important because if Alice sends a message with one, Bob can choose to only accept messages with reasonable timestamps.

So for 'Certificate-Based Key exchanges', Alice provides nonce, or a timestamp along with her certificate. This will help preventing Replay Attacks!


What does Shor's algorithm tell us about the complexity class of RSA and the DLP? If quantum computers operate in BQP and (using Shor's algorithm) they are able to factor large integers and break the discrete log problem, what does that tell us about the complexity class of these problems?

I just read an article that claims that it is unlikely that RSA or ECC will ever be reduced to NP-complete problems, but given Shor's algorithm isn't that impossible?  Or what about the other way: if someone does find such a reduction, does that tell us anything about the relation of BQP and NP?

That tells us those problems are in BQP.
This answer
describes a way of reducing factoring to SAT.
More elaborate approaches will give reductions from  RSA or ECC  to SAT.
On the other hand, if there is a polynomial-time reduction

from an NP-hard problem to  RSA or ECC   then    BQP ∩ UP ∩ coUP  =  NP  .


Argon2i versus Argon2d? I am planning to use Argon2 in my Android app to encrypt some sensitive info that is only stored on the user's phone (in an SQLite DB) and not exported anywhere else. From documentation I see that Argon2d is more resistant to GPU based brute-force attacks compared to side-channel attack in 2i.

Would this mean that in my scenario, it'd be better to use the 2d implementation? Since, in "usual" scenarios it is apparently recommended to use 2i.

Finally, is Argon2 studied sufficiently enough, or should I choose the Android natively supported PBKDF2 with HMACSHA1. I can reasonably use 20,000 iterations in the latter.

Basically, I want to delay malpractice/protect user's data from being decrypted through brute-force methods. I do understand that it also depends on the user's password input.

TL;DR: You want to use Argon2d here.

Even though Argon2 was standardized only somewhat recently, it is the result of the Password-Hashing Competition (2013-2015) and was a late re-design of Argon which also picked up ideas from a few other finalists. Since then there have been attacks on it, which caused the scheme to be tweaked to counter them better, this is why we have Argon2 v1.3 as the most current version, you may want to note that most of these attacks mostly weakened Argon2i and not Argon2d.

Now during the competition results came up that your defense against time-memory trade-off attacks will suffer if you make sure that your scheme is immune to the various kinds of side-channel attacks that people have come up with (which also includes more "crazy" stuff like leaked intermediate state). Because of this, it was decided that there should be two versions: Argon2i and Argon2d. One offering the best possible protection while trying its best to be immune against side-channel attacks (by using data- and password-independent memory access patterns) and the other dropping these requirements and all-out optimizing against such attacks (by using data- and possibly password-dependent memory access patterns).

Enough with the history now. Argon2d offers better protection than Argon2i at the expense of being more vulnerable to side-channel attacks. Now you have to ask yourself: Do these apply? No, not really. You said that you are on Android, which is not exactly known for high platform security, so if you have an attacker in such a privileged position to execute something like cache-timing attacks or similar attacks that try to exploit memory access patterns, your user has already much bigger problems anyways.
It's a similar logic as with AES: There are cache-based side-channel attacks, but these have never been observed in the wild, probably because other options are much easier, more relieable and equally as effective.
So the conclusion is: You want to use Argon2d.

So for whom is Argon2i? People who need to run applications on shared hardware or where timing attacks are a real thread. For example if you run a webserver in a public cloud on shared hardware. Then you have to be worried about who else is on the same CPU. And with webservers it's also easier to measure the timing of reactions and trying to deduce information from that.

The final hint that Argon2d is the way to go here, is the fact that KeePass (one of the open-source password managers) also has decided for Argon2d.


Does $(u_1=r_1\cdot x,\ \ w_1=r_1\cdot z, \ \ u_2=r_2\cdot x,\ \ w_2=r_2\cdot z)$ Leak Information? Consider we have a fixed value $x$. We pick values $ r_1,r_2,z\leftarrow \mathbb{F}_p$, where $p$ is a large prime number, and it is public. So $r_1,r_2,z$ are uniformly random values.

We compute four values as below:

$u_1=r_1\cdot x,\ \ w_1=r_1\cdot z$
$u_2=r_2\cdot x,\ \ w_2=r_2\cdot z$

Question: Do $u_1,u_2,w_1,w_2$ leak information about values $x,r_1,z,r_2$?

In other words: can an adversary learn about the values $x,r_1,z,r_2$ when given $u_1,u_2,w_1,w_2$?

Edit: $u_i, w_i\neq 0$

Yes, this does leak some information.  In fact, just knowing $u_1$ and $w_1$ will allow the attacker to calculate $u_1^{-1} w_1 = x^{-1} z$.*  In particular, knowing this value will let the attacker calculate $x$ if they know $z$, or vice versa.

Similarly, knowing $u_1$ and $u_2$ will let the attacker calculate $u_1^{-1} u_2 = r_1^{-1} r_2$.  With $u_1$, $w_1$ and $u_2$, they can calculate both of these.  (Knowing $w_2$ will not actually add any further information, since it can be calculated from the other values as $u_2 u_1^{-1} w_1 = u_2 x^{-1} z = r_2 z = w_2$.)

Without additional information, however, you cannot work out the exact value of any single parameter.  In particular, given any (non-zero) $x$, we can choose $r_1$ and $r_2$ so that $u_1 = r_1x$ and $u_2 = r_2x$ take any values we like, and then further choose $z$ so that $w_1 = r_1z$ takes any value we like; $w_2 = r_2z$ will then equal $u_2 u_1^{-1} w_1$, as it always must.

*) I'm assuming here that all the values are non-zero, and therefore invertible, which they most likely are if they're chosen at random modulo a large prime.  You can work out the special cases where some of the values are zero as an exercise yourself, if you like.


Can MGF1 within OAEP and PSS be replaced by a XOF? Do we still need MGF1 as used in the PKCS#1 v2.x specifications for SHA-3 hash functions? MGF1 is currently used for OAEP and PSS as Mask Generation Function. Now that the SHA-3 specification contains SHAKE128 and SHAKE256 could MGF1 be replaced?

It seems to me that there is only one input to MGF1, called the seed. It seems that MGF1 is directly replaceable with a XOF which also has one input and one output. In that case we could call MGF2 = XOF, and the XOF (hash) function would simply be one of the SHAKE functions specified in the SHA-3 standard.

Will a extendable-output function directly cover the security requirements expected from a mask generation function?

It seems that the authors of Keccak sponge (the algorithm chosen to be SHA-3) do think their SHAKE functions can directly be used for simplifying OAEP and PSS:

  The introduction of extendable-output functions (or XOFs, pronounced zoff) is a particularly nice feature of the standard. A XOF like SHAKE128 or SHAKE256 can be seen as a generalization of hash functions where the output length is not fixed but is potentially infinite. Concretely, XOFs can be used instead of complex constructions involving hash functions and counters such as MGF1. With RSA, this is of immediate benefit to full domain hashing (edit: also known as FDH), to RSA OAEP (Optimal Asymmetric Encryption Padding) and to RSA PSS (Probabilistic Signature Scheme). Other use cases are key derivation functions and stream ciphers.


Is regular CTR mode vulnerable to any attacks? Regular plain CTR mode, is it vulnerable to any attack?

I plan to write a program to encrypt a drive with ctr mode. Would this be wise? Would AES be better?

When I look at this diagram, it looks pretty solid to me.

If the question is "too broad", allow me to rephrase:

Which is better, AES 256 or CTR mode like the picture above to encrypt a drive?

Summing up the discussion in the comments: What you are describing is the CTR Mode of operation of block ciphers, which requires an encryption function ("E" in your diagram) like AES. So, "should I use CTR or AES?" should instead be "should I use AES with CTR or with another mode?"

As @RickyDemers already mentioned, CTR mode (without any additional authentication step) is malleable, which means that it is possible to change the meaning of the ciphertext. For example: you want to encrypt the message $m=01010101$. Counter mode will use the counter and the encryption function to generate a keystream, for example $s=10010110$, and compute the ciphertext

$$c = m \oplus s = 01010101 \oplus 10010110 = 11000011$$

An attacker could now, for example, flip the second bit in the plaintext $m$ by changing $c$ to $c'$:

$$c' = c \oplus 01000000 = 10000011$$

The decryption would use CTR mode to derive the same key stream $s$ as before, but use it to decrypt $c'$, which would result in

$$m' = c' \oplus s = 10000011 \oplus 10010110 = 00010101$$

As you can see, the second bit (which used to be $1$) was changed to $0$ by this change, while leaving the remaining parts of the file data unchanged. This is called malleability.

You can prevent this by using a message authentication system like HMAC or, even better, an authenticated encryption mode like GCM, which functions like CTR mode but also authenticates the data and thereby makes it impossible to change the ciphertext without being detected. Many systems were broken because they did not use any authentication of the ciphertext, and more were broken because they did the authentication wrong.

So, my reply would be:

Use AES with a sensible mode: XTS or EME if you want to authenticate your data separately using HMAC or something similar, or GCM if you want to do it all at once (I'm not sure if GCM is suitable for full disk encryption though, and be careful when using it, there are some ways to shoot yourself in the foot)
Also, if this is to be more than an experiment on your part, seriously consider using an established disk encryption tool instead
Use a cryptographic library instead of writing the encryption code yourself. There are many non-obvious ways to shoot yourself in the foot, and any one of them may be fatal to the security of your system. Established cryptographic libraries have been vetted for these bugs and while they do crop up occasionally, they are much less likely than in any code a single person can write.
Read and understand this question and all answers in its entirety.
Your misconception about AES and CTR mode indicates that you are pretty new to the field of cryptography. That's fine, everyone was a novice at some point! But make sure to understand the field a little more before building anything serious, because bugs in cryptography are both hard to find and can be devastating if they occur in software used in practise.


RSA public key same across all clients or different? I understand that public key is a pair of $(e, N)$ where $N$ is product of two primes and $e$ is encryption key.

I understand that $N$ is usually unique for an entity. For example, Facebook, Google, etc. have $1028$ or $2048$ bit $N$ that they publish.

What about $e$? Is it also unique or do these entity give different $e$ to different clients/customers? Does it changes from one session to other for same client?

The full public key is usually published, not just $N$. The public key consists of $N$ and $e$ + meta data (ASN.1 encoding, object identifier for RSA, etc.). How the public key is encoded depends of course to the protocol.

If it is shared for e.g. transport security it is usually part of a certificate that also contains subject, issuer, validity period, key usuage etc. and of course the signature of the issuer over the certificate. This makes it possible not just to retrieve the public key but also to find out if the key should be trusted and how the key should be used.

Generally the public key uses the Fourth prime of Fermat (F4) as public exponent $e$. This makes public key operations somewhat faster and it allows for easy key pair generation. Some cryptographic libraries or runtimes restrict the size or value of $e$, so choosing a different value is not recommended. Still, most libraries will accept an $e$ that is, for instance, smaller than 4 bytes (i.e. $2^{32}$ for unsigned or $2^{31}$ for signed integers). Using F4 is generally not a requirement in protocols. That said, using anything different may cause compatibility issues.

Having a different $e$ doesn't affect the security of RSA, as long as it is relative prime to $φ(pq)$.

Notes:

Using 1024 bit RSA is not recommended anymore. Using a 2048 bit or higher key size is highly recommended.
$N$ directly depends on the two (or more) random primes used to generate the key pair so $N$ is always fully unique, making the public key fully unique - regardless of $e$. A hash over $N$ is generally used as key ID or fingerprint of the key pair. $N$ is part of both the public- and the private key.


Why do we need to compute message digest of a message first while signing it? Why is it more efficient to compute a message digest (message & signature) rather than sign the message directly?

One of the main reasons for hashing is that hashing destroys any algebraic structure that is hidden in the signatures. If you don't hash, then in most signature schemes the messages will satisfy some algebraic relation. A typical example is that

$$Sign(m_1m_2)=P(Sign(m_1),Sign(m_2))$$

meaning that the signature of a product/concatenation/whatever of two messages is a polynomial in the signatures of the individual messages. For RSA, we would have $P(x,y)=xy$. These dependencies can be more complicated and as long as they are efficiently computable, we have problems. What a hash function does, informally speaking, is that in terms of bit strings, $H(m_1),H(m_2)$ and $H(m_1m_2)$ become totally unrelated, therefore it removes any sort of efficiently computable dependency of $H(m_1m_2)$ on $H(m_1)$ and $H(m_2)$.

The point of removing these dependencies is that it prevents us from using previously seen message/signature pairs for forging signatures on new messages. This is what breaks EUF-CMA security. Therefore, hashing is not just an issue of efficiency, but also one of security.

Another issue is of course that the message to be signed needs to be of the proper form before a signature is issued. Since a signature scheme typically operates on elements in some group $G$, there needs to be a function that takes a message $M\in\mathcal{M}$ from the message space and maps it to a group element. Therefore, we need some function $H:\mathcal{M}\to G$ that allows us to transfer messages to a format that we can sign. For RSA we need to take an arbitrary bitstring and then turn it into an integer modulo $N$. The kind of a function that does this in a way you want is precisely a cryptographic hash function.

There is actually a theoretical issue here as well. It's very very hard to build a EUF-CMA secure signature scheme without relying on a hash function (meaning not proving security in the Random Oracle Model). There are some quite efficient structure-preserving signature schemes that are EUF-CMA secure and don't use a hash function, but they rely on the generic group model. To my knowledge, no practical construction is known to date, which only depends on a standard assumption.


How does hashing twice protect against birthday attacks? The bitcoin wiki says:

  Bitcoin is using two hash iterations (denoted SHA256^2 ie "SHA256 function squared") and the reason for this relates to a partial attack on the smaller but related SHA1 hash. SHA1's resistance to birthday attacks has been partially broken as of 2005 in O(2^64) vs the design O(2^80). While hashcash relies on pre-image resistance and so is not vulnerable to birthday attacks, a generic method of hardening SHA1 against the birthday collision attack is to iterate it twice. A comparable attack on SHA256 does not exist so far, however as the design of SHA256 is similar to SHA1 it is probably defensive for applications to use double SHA256. And this is what bitcoin does, it is not necessary given hashcash reliance on preimage security, but it is a defensive step against future cryptanalytic developments. The attack on SHA1 and in principle other hashes of similar design like SHA256, was also the motivation for the NIST SHA3 design competition which is still ongoing.

I don't understand how hashing twice would prevent a birthday attack considering that finding a collision after the first hash would trivially entail a collision after the second hash.

Is it because you have to compute the hash twice thus slowing the process down or is there a more significant reason?

A collision in any hash function gives a collision in a "squared" variant of the hash function. This is easy to see. If hash(x)==hash(y), then hashing the outputs will also be the same.

So the wiki entry is wrong. To see the real purpose of the double hash see this question and answers.


What is the difference between Shannon entropy and saying that tossing a 6-sided die 100 times has more than 256-bit entropy? I'm confused.

I thought that tossing a 6-sided die 100 times had a greater than 256-bit entropy because $6^{99} < 2^{256} < 6^{100}$. (A similar concept appeared in this XKCD comic, where choosing four random words from a dictionary of presumably 2048 words has a 44-bit entropy, presumably because $2048^4 = 2^{44}$.)

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits. (According to the comments by Sakamaki Izayoi to my other question.)

Are these two different concepts of "entropy" entirely? If so, what's the difference and if not, what am I missing?

I read this thread but I'm still confused.

On the other hand, the Shannon entropy of a 6-sided die tossed 100 times is $-6 × 1/6 × \log_2(1/6) = 2.5849625007$ bits.

That is wrong: $-6\cdot\frac16\cdot\log_2\frac16$ is the entropy of a single die roll. Assuming the $100$ die rolls are independent, you can simply sum the entropies of the individual rolls to obtain
$$ 100 \cdot\left(-6 \cdot\frac16\cdot\log_2\frac16\right) \approx 258.49625 \text, $$
which is precisely $\log_2(6^{100})$ as expected.


What are the characteristics of a quantum secure protocol? What are the characteristics of quantum secure protocol, and does it always need to be information theoretic to be called as quantum secure? Are the current techniques used in bitcoins quantum secure?

Quantum computers don't attack the protocol, they attack the cryptographic primitives used in the protocol. You need to avoid primitives that can be broken by quantum computers.

Quantum computers don't break all computationally secure cryptography, so you don't have to resort to information theoretic algorithms (one-time-pad).
Symmetric encryption is secure if the keys are big enough (256 bits). Hashes are secure if the output is big enough (256 bits might be enough). Popular asymmetric crypto including RSA, Diffie-Hellman and DSA (including elliptic curve equivalents) will become totally insecure, but there are replacements.

The biggest problem QCs pose for bitcoin is that it uses ECDSA to control ownership of coins. Since QCs can break DSA, everybody who learns your public-key can compute the corresponding private key and steal your coins. Keeping single-use public-keys secret until use can help somewhat, but it's still problematic.

Grover's algorithm might cause some additional issues, including faster mining, $2^{80}$ pre-image attacks against the 160-bit hashes used for bitcoin addresses and faster cracking of weak passphrases for password derived keys.


How many bits of entropy does an elliptic curve key of length n provide? A FAQ for an open source project makes the claim:

  Indeed, an elliptic curve key of length n provides $n/2$ bits of security.

I have two questions:

What is the practical difference between "bits of entropy" and "bits of security"?
How does one estimate the number of bits of security (or entropy) for an elliptic curve private key of length $n$?

Bits of entropy

The assumption for all cryptographic operations is that a random key of n bits has n bits of entropy.  If it doesn't (due to PRNG defect or implementation error) then the key will be weaker than expected but the underlying assumption of all cryptographic primitives is that an n bit key has n bits of entropy.  This is the same for all types of cryptographic systems.  It is also why in cases where the key is derived from a password while it may be impossible to brute force the key it is possible to brute force the significantly weaker password.

Bit strength

An ECC key has a bit strength equal to half the key length.  To understand why we need to take a step back and look at what makes ECC strong.  By strong we mean that it is computationally difficult to derive the private key from the public key.  Why is that difficult?  Well the short version is that to go from public key to private key would require solving a discrete logarithm and no efficient solution is known.  This is a mathematical assumption on which ECC is based.

So why is the bit strength equal to half the key length?  It is because all of the fastest solutions for solving a discrete logarithm problem are on the order of $O(2^{n/2})$.  So for a 256 bit key we are talking about $2^{128}$ operations which is the same as an exhaustive search on a 128 bit symmetric key thus it is 128 bit strength.

Key length does not equal bit strength

The ratio between key length and bit strength will vary by algorithm.  For unbroken symmetric algorithms there is no solution short of an exhaustive search of possible keys to find the proper key thus a 128 bit AES key has 128 bit strength.  However for asymmetric encryption there are faster solutions and as a result it takes a larger key to achieve a similar level of security but that ratio will depend on the algorithm used and the fastest known solution.

$$\begin{array} {r r r}
AES\ 128\ bit\ key & = 2^{128}\ operations &  = 128\ bit\ security   \\
ECC\ 256\ bit\ key & = 2^{128}\ operations &  = 128\ bit\ security   \\
RSA\ 2,048\ bit\ key & = 2^{128}\ operations &  = 128\ bit\ security   \\
\end{array}$$

$$\begin{array} {r r r}
AES\ 256\ bit\ key & = 2^{256}\ operations &  = 256\ bit\ security   \\
ECC\ 512\ bit\ key & = 2^{256}\ operations &  = 256\ bit\ security   \\
RSA\ 15,360\ bit\ key & = 2^{256}\ operations &  = 256\ bit\ security   \\
\end{array}$$

Now if tomorrow someone found a faster solution to solve the discrete logarithm problem, let say $O(2^{n/4})$ then a 512 bit ECC key would no longer be 256 bit security it would be 128 bit security.  I think that is unlikely but I use it as an example to illustrate why keys of different algorithms have different lengths for the same level of security.


Subtracting one pederssen commitment from another I am building a range proof to prove that a secret number x lies between a specific range a

prover commits to a values a<x<b

prover generates a pedersen commitment to a value a

prover generates a range proof to commitment that is commitment from 1 minus
  commitment from 2

prover sends range proof together with the opening of the commitment from 2

regarding step 3, how do I subtract one commitment from another? is there a better way?

Note: I am using the a javascript implementation to calculate the pederssen commitment
https://github.com/omershlo/simple-bulletproof-js

how do I subtract one commitment from another?

Actually, it's surprisingly simple; you subtract the two commitments (and, no, that's not a joke, that's really how you do it).

That is, if we have a commitment $C_1 = x_1G + r_1H$, which is a commitment to the value $x_1$ (you don't know what the values $x_1, r_1$ are, but the prover does.

And, you have a commitment $C_2 = x_2G + r_2H$, which is a commitment to the value $x_2$ (again, known to the prover).

Then, all you do is compute $C_1 - C_2$, that is subtracting these two elliptic curve points.

We have $C_1 - C_2 = (x_1 - x_2)G + (r_1 - r_2)H$; where the prover can compute $x_1 - x_2$ and $r_1 - r_2$, and so this is a valid commitment to the value $x_1 - x_2$ (which the prover can open, should he choose to), which is what you are asking for.

However, I am unfamiliar with the javascript package you're using; I am unable to point you to how you'd do that...


Small subgroup attack on Diffie-Hellman key exchange Alice and Bob are using DHKE in the group $\mathbb{Z}_p^ * $, where $p = 1031 = 2 \cdot 5 \cdot 103 + 1$. Their generator $g = 2$, which generates a multiplicative group of order $515$ in $\mathbb{Z}_{1031}^ * $. This group has a subgroup consisting of $5$ elements $\{ 1,518,264 = {518^2},660 = {518^3},619 = {518^4}\} $. Eve uses this subgroup to find out DH keys exchanged by Alice and Bob. In one exchange, Alice sends ${2^a} = 919$ to Bob. Eve intercepts the message, raises $919$ to the power $103$ and gets $619\,\bmod \,1031$. Eve sends $A = 619$ to Bob. Bob replies by sending ${2^b} = 270$. Eve intercepts it, raises $270$ to the power $103$, gets $660\,\bmod \,1031$, and sends $B = 660$ to Alice. Eve now finds the integer value of DH key ${B^a} = {A^b}$ computed by Alice and Bob without knowledge of $a$ and $b$, and actually without any more computations modulo $1031$. Explain how this is possible, and give the value of the resulting DH key.

My solution:

Eve was smart enough to come up with a subgroup $S < \mathbb{Z}_{1031}^ * $ such that $\left| S \right| = 5$ and $S = \left\langle {518} \right\rangle $. By Lagrange theorem we know that all elements of $S$ must have an order $1$ or $5$. Thus it follows that $\left| 1 \right| = 1{\text{ and }}\left| {518} \right| = \left| {264} \right| = \left| {660} \right| = \left| {619} \right| = 5$. Furthermore, we know that $S = \left\langle {264,518,619,660} \right\rangle $.

Alice sends to Bob ${2^a} = 919$, when Eve stops the message she computes ${({2^a})^{103}} = {(919)^{103}} = 619 = {518^4}$ and hence Bob receives $619 = {518^4}$. Bob sends to Alice ${2^b} = 270$, when Eve stops the message she computes ${({2^b})^{103}} = {(270)^{103}} = 660 = {518^3}$ and hence Alice receives $660 = {518^3}$.

The value of the key is $$K = {B^a} = {660^a} = {518^{3a}} = {518^{4b}} = {619^b} = {A^b}$$Clearly the usage of much smaller subgroup with the following properties allow Eve to forge the message and limit a search domain to $5$ values. However, i do not understand how Eve can find the integer value of the key without knowing $a$ or $b$ and without more computations modulo $1031$.

For different values of $a$ and $b$ the generator of $S$ - $518$ will produce one of five possible values that will satisfy the equality. The only way i see Eve finds the key is by trying all five possible values (e.g small exhaustive search). In this way Eve does not need to do more computations modulo $1031$ as she knows the elements of $S$.

However the problem asks to give the value of the key. Does it mean that i have to try all $5$ values from $S$ or the key can be indeed determined uniquely without performing exhaustive search on $S$?

Does it mean that i have to try all 5 values from S or the key can be
  indeed determined uniquely without performing exhaustive search on S?

In the general case, you cannot determine the key without performing exhaustive search on $S$.

Small subgroup attacks aim to make the key belong to a small subgroup to make the exhaustive search feasible in practice. So by definition, usual small subgroup attacks require exhaustive search.

I posted something about Small subgroup confinement attack on Diffie-Hellman to fully understand the functioning of the attack, maybe it can help you.


Importance of supersingularity of elliptic curves I'm struggling to understand the high-level idea of "Verifiable Delay Functions from Supersingular Isogenies and Pairings" (https://eprint.iacr.org/2019/166.pdf) by De Feo et al.
I will shortly outline the construction (p.12):
setup:

(choose appropriate parameters)
Select a supersingular elliptic curve $E/\mathbb{F}_p$.
Choose a direction on the horizontal l-isogeny graph and compute a cyclic isogeny $\phi : E \rightarrow E'$ of degree $l^T$ and its dual.
Choose a generator P of X1 = $v^{-1}$($\tilde{E}[N] \cap \tilde{E}(\mathbb{F}_p)$) and compute $\phi(P)$.

eval:

Compute $\hat{\phi}(Q).$

verify:

Verify the condition ($e_N(P, \hat{\phi}(Q)) = e_N(\phi(P), Q)$) for the pairing $e_N$.

For step 2, I wonder: Why does the curve need to be supersingular? I think that it has a certain implication on the structure of the isogeny graph from $E$, but that is only my guess.
For step 3: I assume that we do a random walk on the isogeny graph. I think that means: for any elliptic curve $E_0$, we construct an isogeny, compute it, jump to the new curve $E_1$ and repeat this process. I wonder: Isogenies project points between curves, but their result isn't really a new curve. So how can we compute an isogeny from $E_1$ without really knowing it? Why is it important that the isogeny graph is "horizontal"?
How can we prove that the isogeny actually takes T steps (.. which is necessary for the delay property of VDFs)? Or do we just publish all T intermediate isogenies? Why can we assume that all of them have order l?
The idea in step 5 and 6 looks clear to me: The condition (which is quick to evaluate) only holds for correctly computed isogenies, which can only be calculated with delay T.
Concerning P: $v : E \rightarrow \tilde{E}$ is defined as $(x,y) \rightarrow (u^2 x, u^3 y)$, $\tilde{E}$ is the quadratic twist of E. I understand that $E$ and $\tilde{E}$ are isomorphic, but I don't see why X1 is constructed in such a complicated way. Why can't we use the points on E as X1?
If my questions are too specific, I'd be more than happy for the explanation of supersingularity in this case! Would the construction also work for ordinary elliptic curves?

Your questions are a bit too rambly, so I'll just answer the title question. We use supersingular curves because ordinary curves don't have enough isogenies. Specifically, for supersingular curves, the graph of $\ell$-isogenies defined over $\mathbb{F}_{p^2}$ has good expansion properties. For ordinary curves, the graph of $\ell$-isogenies does not have good expansion properties. In most cases the latter graph is just a union of disjoint cycles. You can get graphs of ordinary isogenies with good expansion properties, but in order to do so you have to do something like take the union of $\ell$-isogeny graphs over various different $\ell$.


RSA encryption using euclidean alorithm when given p=5, q=19, e=5
solution:-
    n=5*19
     =95
    φ (n)=4*18
         =72

de=1 modφ (n)
d(5)=mod(72)
using euclidean algorithm

72=14(5)+2
5=2(2)+1

back substituition

1=5-2(2)
1=5-2[72-14(5)]
1=15(5)-2(72)

now what how to calculate the value of 'd'

You seem to have already calculated it. If you have
15(5) - 2*72 = 1 then  15(5) $\equiv 1$ (mod 72).  Can you see the solution now?


How long it takes for new cryptographic results to become generally accepted? Suppose there is a new scheme, for the sake of argument let's call it a CEPQSS - CryptoEnthusiast's Post-Quantum Signature Scheme. Now most practitioners aren't convinced that using this is a good idea let alone that it works. But the results are completely valid.
How long would it take until most practitioners evaluate and peer review it to the point where it would be generally accepted?

How long would it take until most practitioners evaluate and peer review it [...]?

Unfortunately peer review tends to be more of a "push" than a "pull" based process. Meaning that experts in that area tend not to crawl the internet for schemes to investigate and "declare good to use" but rather that the authors of such schemes work hard to get that attention. And even then, most schemes - even those with somewhat famous authors - have excellent chances at never being used seriously in practice. This is the case even if the relevant people have used much of their time to analyse such proposals and found no flaws.
The best example for this is actually the on-going NIST Post-Quantum Competition where chances are really slim for any candidate kicked out in the third round to see any real usage.
So even if a scheme is good - and it has to be reasonably secure and performant - and it is published in the right place at the right time with a large amount of serious, convincing self-analysis, there's a good chance that it never sees real usage outside of that the author implements themself.
This situation doesn't get better if the scheme in question has no properly formatted paper with lots of relevant, convincing cryptanalysis and security proofs, which hasn't even been submitted / accepted at the right venue / journal.
If one would really want to have such initial analysis it might be worth to try and hire a serious, professional cryptographer as a consultant and either have them analyse the scheme - which is unlikely to be very useful given that this kind of work takes a lot of time and thus money - or to collect (some) likely relevant initial background material to start working on the analysis in a way that is generally accepted. Additionally such professional help would likely also be able to review the analysis to give potential improvement suggestions to the analysis and its presentation to lessen the chance of an instant reject if and when it is tried to be submitted to a serious venue.


Partial proof of work: an hash function that validates parts of input, insensitive to the rest In typical proof of work, there is a one-way hash-function that takes binary inputs and generates an output $h(x,y)$ where $x,y\in\{0,1\}^M$ are binary inputs, so that finding $x$ for a certain $y$ such that $h(x,y)=0$ becomes a complex problem.
Is it possible to design $h(x,y)$, such that it is insensitive to parts of input, say it completely discards parts of input $x$, without revealing those positions? While we can just concatenate the "sensitive" bits, and apply any one-way function, the description of such a hash function would contain and reveal the bit positions. Is there way to achieve this partially sensitive hash, without revealing the sensitive/non-sensitive pattern?

If you give me enough information to evaluate $h$ on inputs of my choice, then I can easily check whether $h$ is sensitive to the $i$th bit of input --- just evaluate it on two strings that differ only in their $i$th bit and see if the outputs are the same. So it is not possible to hide this property in the description of a public function.


Client login without sending a password I would love to have a system where the password is never send in plaintext (even with TLS) to authenticate a user. I've come up with this protocol, but I'd rather use something proven.

Registration:

Client (javascript in a browser) generates a 2048 bit RSA keypair (using Forge js)
Client generates hash from the users password using pbkdf2 with 68000 rounds
Client encrypts the private key with the above hash as the passphrase using AES 128 in OpenSSH format
Client sends the encrypted private key, public key, pbkdf2 salt and the username to the server

Login:

Client requests the encrypted private key and the pbkdf2 salt using the login name
Client generates hash from the users password using pbkdf2 with 68000 rounds and salt from the server
Client decrypts the private key using the pbkdf2 hash
Client requests a challenge from the server
Server sends an challenge that is encrypted using the user's public key using OAEP-SHA1 (Using cryptography.io)
Client decrypts the challenge and sends the plaintext challenge to the server
Server sends an limited use token to the client to use the api with

TLDR: Is there a login protocol where the client can prove authenticity to a server without sending a password. The user can then use a token for API calls that expire after a set time/a few calls. This system cannot use oauth.

I can see some weaknesses in your protocol. For example, it allows any attacker to request the encrypted private key and thus mount an offline dictionary or brute force attack on the password. (An incorrect password doesn't give you a properly formatted OpenSSH key.)

Thus this is a good idea:

  I'd rather use something proven.

As mentioned in the comments SRP does exactly what you want. Here is description of the version 6(a) protocol.

To protect against compromised servers (like normal with password authentication), you'll want to incorporate your idea of using PBKDF2 (or another password hashing function). If you don't want the server to have to compute a slow password hash on each login attempt, you can use a normal hash as $H$ except when deriving $x$, which only the client needs to do. Or if you use an SRP library (as you should if possible) and it doesn't support this, you could calculate the $p$ you feed into SRP using PBKDF2 from the actual password.


Proving G(x)=x||[x^2 mod 2^N] is not a PRG This was a question from my exam yesterday.
We have that $G:\{0, 1\}^n\rightarrow \{0, 1\}^{2n}$ and
$$G(x)=x\mathbin\|[x^2 \bmod 2^n]$$ with $x$ is uniform and $|x|=n$, give an efficient distinguisher $D(w)$ that shows that $G(x)$ is not a PRG.
After writing a program that shows all values $[x^2 \bmod 2^n]$ can take for some fixed $n$, I found that there is a mirror pattern in these values, but I don't see how to mathematically prove this.

Given as input a $2n$-bit string $x||y$, the distinguisher $D(x||y)$ outputs 1 if $y = x^2 \bmod{2^n}$ and $0$ otherwise.
If $x||y$ is uniformly distributed over $\{0,1\}^{2n}$, the probability that $y=x^2 \bmod{2^n}$ is $2^{-n}$. If $x||y$ is distributed as $G(X)$ where $X$ is uniform over $\{0,1\}^n$, the probability that $y=x^2 \bmod{2^n}$ is 1. The distinguishing advantage of $D$ is $1-2^{-n}$, which is non-negligible.


If WhatsApp cannot read our message, how can the media forwarding happen in an instant? WhatsApp says even the photos shared on its platform are end-to-end encrypted. When WhatsApp says encrypted I assume the data is encrypted in my device and then sent across to the recipient.

When we are sending a photo for the first time we can see the actual upload happening (if you are in a slow network), but when we forward the same picture to someone else, the upload is not happening. It happens in an instant.

AFAIK the photo would have been again encrypted with the key pair for the second recipient and then again sent to the second recipient. Since the second upload is not happening is it that the encryption happens in the WhatsApp server? Is WhatsApp decrypting the media file and encrypting it with the new recipient's key when we forward it? Can it be called end-to-end encryption in that case?

Leaving aside the WhatsApp aspect fo the question: the effect described can be achieved with hybrid encryption, where the bulk of the data is encrypted under a random secret symmetric key, and the result uploaded once; revealing that data to a recipient is performed by encrypting that symmetric key towards the recipient (e.g. using his/her public key), and thus requires very little data transfer from the sender for each additional recipient.


Is entropy affected by time? I'm quite new to cryptographic systems, and today we discussed entropy at work. Since entropy is used to ensure the difficulty for an attacker to break in, I was wondering if the more time the high entropy value remains the same, the more the system becomes vulnerable.

Is the concept of entropy related with the time (like a logarithm function or else)?

No.  Entropy does not depend upon time.  Entropy is a purely mathematical, probability-based concept.

The entropy of a distribution is some particular function of the distribution.  The entropy of a random variable is the entropy of its distribution.  Formally speaking, it does not make sense to speak of the entropy of a particular value; but we can talk about the entropy of a random process.  For example: suppose I roll a fair 6-sided die, and get 3.  It doesn't make sense to talk about the entropy of the number 3, but I can ask what is the entropy of this random process (the process of rolling a fair 6-sided die to get a random number from 1 to 6) -- it has $\lg 6$ bits of entropy, in particular.  The entropy of a process is the entropy of the distribution on the possible outputs from that process.

Notice how nothing here changes with time.  If I roll a fair 6-sided die today, the entropy of the result is $\lg 6$ bits.  If I roll it tomorrow, the entropy of that will also be $\lg 6$ bits.  If I roll a fair 6-sided die today, write down the answer, and then a decade from now look at what I wrote down and ask about its entropy, the answer will still be $\lg 6$ bits.  The entropy of this random process remains $\lg 6$ bits no matter how long we wait, because its entropy depends upon the distribution of possible outputs from the random process, and that distribution is whatever it is -- it does not depend upon time.

Now in some cases it might be true that, if you use a random secret key, then the longer you use the same key, the greater the chances that an attacker can recover the key.  That might be true.  But it has nothing to do with entropy.  The entropy doesn't change or degrade with time; the entropy of that key is what it is.  All that changes is, the longer you use the key, the more chances the attacker has to try to break it.  For the same amount of entropy, the more times the attacker can try to break it, the better the attacker's odds will be.  So that's one sense in which the attacker's success probability (or the security of the system) might depend upon how long the system is used for -- even though the entropy of the crypto key does not depend upon that.


One-Time Pad Vulnerabilities Why is it that a one time pad is vulnerable is the key is shorter than the message?
I know that if a key is reused across multiple plaintexts, you can XOR two existing ciphertexts to get the pad, but I'm not entirely sure how this works in practice.

Any help/ explanation is appreciated. Thanks.

If the key bits are shorter then the message you need to reuse some part of the previous key bits. If this is known, and we can assume by Kerckhoff Principles,
then the enemy can crib-drag on the same message. A more dedicated enemy will always try this case and also the reuse case; the same key is used with another message, too.

As an example;

m = xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
k = KkkkkkkkkkkkkkkkkkkkkkkkKkkkkkkkkkkkkkkkkk

where $x$ represents the message bits, $k$ represents the key bits and $K$ represents the start of the key bits. Divide the message into parts;

m1 = xxxxxxxxxxxxxxxxxxxxxxxx
k  = Kkkkkkkkkkkkkkkkkkkkkkkk
m2 = xxxxxxxxxxxxxxxxxx
k  = Kkkkkkkkkkkkkkkkkk

now, execute crib-dragging.


Multi-argument Poly Notation In complexity theory, how do you interpret multi-argument poly notation, such as $poly(a,b)$ or $poly(a,b,c)$?

Does it mean $poly(x)$ for $x=\max(a,b,c)$?

That would be literally $P(a, b)$, for some multivariate polynomial $P(X,Y)$.

Of course, in that case, $P(a,b)\leq |P(a, b)|\leq Q(a, b)$ for some polynomial $Q$, where all coefficients of $Q$ are positive, and then $Q(a, b)\leq Q(\max(a,b), \max(a, b))=R(\max(a,b))$ for some univariate polynomial $R$, where $R(X)=Q(X,X)$.

Conversely, $R(\max(a,b))$ for some polynomial $R$ with nonnegative coefficients is bounded by $R(a+b)$, so this is $P(a,b)$ where $P(X,Y)=R(X+Y)$.


Use of symmetric keys rather than asymmetric keys for transport security Alice has an asymmetric key pair and it also has Bob. They want to encrypt traffic between each other. It would be simple to encrypt the traffic with their public keys, but instead they use key pairs to generate symmetric keys, which are then used to encrypt traffic.

Why would you not directly use the asymmetric keys?

The main reason is efficiency; asymmetric cryptography requires a large overhead with regards to CPU time and bandwidth, while symmetric encryption does not. The time to perform RSA decryption for instance is slower than AES:

  Doing 4096 bit private rsa's for 10s: 48 4096 bit private RSA's in 10.10s

That's clearly somewhere about 2,4K/s for a reasonable key size for RSA, and that's excluding overhead, so say about 2 KB/s.

  Doing aes-128 cbc for 3s on 64 size blocks: 6221203 aes-128 cbc's in 3.00s

So that's over 128 MB/s, just slightly faster.

You'd need both confidentiality and integrity / authenticity though. So to add a signature and MAC you should about half the speed for both.

Asymmetric encryption is not usable for bulk encryption.

There are more reason to use short term session keys. One is that you can achieve forward secrecy when you derive the session keys using ephemeral-ephemeral key agreement. If that is used the session remains secure even if the private keys become compromised. In such a scheme the asymmetric key pairs are only used for authentication. This will be the default for TLS 1.3.


Index in PRNG output sequence We have some simple PRNG, like a LCG or LFSR. Easiest is one that follows a output state, transform state cycle. Let's call that cycle an "iteration", and one of these outputs a "word".

Knowing the PRNG used, and all parameters including the starting state, we want to take a given word, and assuming it does appear in the output sequence, find the "index", that is, the number of iterations before that word appears for the first time.

Of course, this problem will vary between PRNGs, but what I want to know now is:

How hard is it in general? $O(2^n)$ for $N$ bit words, or much less?
Which PRNGs, if any, is it easy for? Looking for polynomial to $N$, or at least subexponential.
How to detect when the given word doesn't appear in the output sequence, when it's not obvious like with a LCG.
What to do with PRNGs which output only part of their state or put it through some mapping (not a crypto hash of course).

Plain LCG would be harder than discrete logarithm right? Discrete logarithm is doable in polynomial time for power of 2 modulus though. Not sure how much difficulty the addition adds.

I'd think enough nonlinearity would make this task intractable due to the complexity. So ones like xorshift and MT19937 should be doable.

Pick your favorite $b$-bit block cipher $E_k$, say AES-256.  Let $k$ be the seed and let the $i^\text{th}$ output be the $b$-bit string $x_i = E_k(i)$.  Then $i = E_k^{-1}(x_i)$.  Given $k$ and $x_i$, this is widely considered to be ‘easy’, for most block ciphers including AES-256.  Note that every possible $b$-bit string has an index.

$\newcommand{\Z}{\mathbb{Z}}$Pick your favorite 2048-bit safe prime $p$, say $2^{2048} - 1942289$, and your favorite nonzero generator $a$ of $(\Z/p\Z)^\times$, say $5$.  Let $x_0 \in (\Z/p\Z)^\times$ be the seed and let the $i^\text{th}$ output be $$x_i = a x_{i - 1} = a^i x_0.$$  Then $a^i = x_i x_0^{-1}$, so that $i = \log_a x_i x_0^{-1}$.  This is widely considered to be ‘hard’, for sufficiently large safe primes including $2^{2048} - 1942289$.  Note that every possible element of $(\Z/p\Z)^\times$ has an index.

Defining ‘easy’ and ‘hard’ is left as an easy exercise for the reader.  Deciding whether to encode $i$ as little-endian or big-endian for $E_k$ is left as a hard exercise for the reader.

This does not address any security of these PRNGs.  One of these is fit for use in cryptography; the other is emphatically not.  Since you didn't mention any security requirements in your question, I didn't mention any security properties in my answer.  Figuring out which one is which is also left as an exercise for the reader.  (I hope you're taking notes, because there'll be a quiz on Thursday next week about all these exercises!)


Isn't AES-NI useless because now the key length need to be longer? AES-NI speeds up both encryption and decryption. The encryption is as secure as the time needed to brute force the decryption. Doesn't it mean that the application developers will just need to increase key length until the time taken is almost the same as without AES-NI?

No, AES-NI provides a hardware implementation of AES. Before AES-NI, anyone could have purchased a specialized hardware encryption device that ran AES in hardware. So having AES-NI doesn't really change anything. When key sizes are chosen, they must take into account that specialized hardware could be developed. So, the key sizes we use already take this into account.


Attacking AES/CCM with random IV A cryptosystem is using AES-128 in CCM mode with random IV.

Suppose an attacker capable of:

asking the cryptosystem to encrypt a single plaintext as many times as he wants; and
asking the cryptosystem if any ciphertext is valid (ie, if it decrypts to some plaintext)

The attacker knows what is the single plaintext that he can encrypt, but he cannot chose a different one to be encrypted. That plaintext is short -- around 50 bytes.

Each time, the cryptosystem will chose a random IV and use it to encrypt the plaintext, giving the attacker a different ciphertext for that single plaintext.

In this threat model, can the attacker "easily" obtain the secret key?
Can the attacker somehow modify the ciphertext in order to change the plaintext it will decrypt to? (he would have to be able to generate a valid MAC, since the cryptosystem correctly checks the validity of the MAC)

What about the same questions, if the attacker is able to encrypt some different plaintexts? He wouldn't be able to chose them, but he would know them. Suppose he can do it for, like, 10's of different plaintexts.

No.  The attacker cannot easily recover the secret key.  The attacker cannot modify the ciphertext to something that decrypts to some other plaintext.  This remains true even if the attacker can encrypt an arbitrary number of chosen plaintexts.

This is known as "IND-CCA2 security" (security against adaptive chosen plaintext/ciphertext attack).  CCM satisfies that notion of security.  So too do other authenticated encryption schemes, like EAX, GCM, etc.


Suppose $A$ knows $a$ and $B$ knows $b$, is it possible to efficiently compute $g^{ab}$ without leaking $g^a$ and $g^b$ to each other? I know the garbled circuit solution, but is there any more efficient method?

It's not possible because if $B$ knows $b$ and $g^{ab}$, then she can compute $\left(g^{ab}\right)^{b^{-1} \bmod N} = g^a$ (where $N$ is the order of $g$, which is normally prime so that $b^{-1} \bmod N$ exists).

EDIT: As noted by poncho in the comments, this assumes we are in a typical discrete logarithm setting, where the order of the group is prime to avoid attacks on the discrete logarithm by Pohlig-Hellman. In other settings such as RSA it may not be feasible to compute $N$ in the first place, but on the other hand having a group of non-prime order makes the discrete logarithm easier to attack...


Why is HMAC-SHA1 still considered secure? This Q & A https://security.stackexchange.com/questions/33123/hotp-with-as-hmac-hashing-algoritme-a-hash-from-the-sha-2-family

says that the security of HMAC-SHA1 does not depend on resistance to collisions? Are they are saying specifically with respect to HOTP or for HMAC-SHA1 for any use?

If HMAC-SHA1 is used for verifying the integrity of a document and you can find a collision, you can make changes in the document, right?

http://tools.ietf.org/html/rfc2104#section-6

Even the RFC says that resistance to collisions is relevant

  The security of the message authentication mechanism presented here depends on cryptographic properties of the hash function H: the resistance to collision finding (limited to the case where the initial value is secret and random, and where the output of the function is not explicitly available to the attacker), and the message authentication property of the compression function of H when applied to single blocks

What am I missing here?

In the first section of this answer I'll assume that through better hardware or/and algorithmic improvements, it has become routinely feasible to exhibit a collision for SHA-1 by a method similar to that of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu's attack, or Marc Stevens's attack. This has been achieved publicly in early 2017, and had been clearly feasible (the effort represents mere hours of the hashing effort spent on bitcoin mining; but the hardware used for that can't be re-purposed for the attack on SHA-1).

Contrary to what is considered in the question, that would not allow an attacker not kowing the HMAC-SHA-1 key to make an undetected change in a document; that's including if the attacker is able to prepare the document s/he's willing to later alter.

One explanation is that the collision attacks on SHA-1 we are considering require knowledge of the state of the SHA-1 chaining variable, and the attacker of HMAC not knowing the key is deprived from that knowledge by the key entering on both extremities of the iteration of rounds in which the message stands in HMAC. A much deeper break of SHA-1's round function would be needed to break HMAC. Not coincidentally, M. Bellare's New Proofs for NMAC and HMAC: Security without Collision-Resistance shows that security of HMAC holds assuming only weaker properties on its round function than needed for collision resistance of the corresponding hash.

What would be possible is for an attacker knowing the HMAC key to prepare a document that s/he willing to later alter, that can be altered without changing the MAC. But since the attacker is holding the HMAC key, that's not considered a break of HMAC.

A comment asks when should SHA-1 not be used?

It is advisable to quickly phase out SHA-1 in applications requiring collision-resistance (as an image: quickly walk away, as you exit a building which fire alarm rings when there's no smoke). That includes hashing for integrity check or digital signature of documents prepared by others even in part (which is, most documents). If continuing to use SHA-1 has strong operational benefits, it can safely be made an exception by inserting something unpredictable by adversaries before any portion of the message that an adversary can influence. For example, by enforcing an unpredictable certificate serial number at time of request of a certificate, a certification authority could still safely issue certificates using SHA-1 for their internal signature.

As explained in the first section of this answer, as long as the key of HMAC-SHA-1 is assumed secret, there is no indication that HMAC-SHA-1 is insecure because it uses SHA-1. If the key is assumed public, or its leak is considered an operational possibility where it is still wanted collision-resistance for HMAC including for message prepared after disclosure of the key, then the precautions discussed in the previous paragraph apply.


How can 3DES encryption use decryption in the middle step? I have been reading about the 3DES algorithm and I cannot understand one part. In 3DES we do following operation: $$C=E[K_3,D[K_2,E[K_1,P]]].$$
Where $C$ is ciphertext, $P$ is plaintext, $E$ is DES encryption and $D$ is DES decryption.

In the second part we have the decryption with $K_2$. How can we decrypt a cipher with one key ($K_2$) which was encrypted with another one ($K_1$)?

I do not understand how can we decrypt a cypher which was encrypted with $K_1$, with $K_2$.

Triple DES essentially involves three encryptions on the plain text. First is using $K_1$, second using $K_2$, and third using $K_3$. Now one may argue that $K_2$ is not being used for encryption but decryption. Well, technically speaking, encryption and decryption are just the same, and are only the reverse of each other in all ciphers using the feistel cipher structure. So actually decryption with $K_2$ does nothing but jumble-up the message further more. We are not decrypting the cipher in the real sense. We are adding another layer of obscurity with a second key.


For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$ Alice uses an ElGamal signature in group $(Z/pZ)^{*}$ without using hash function. To sign the message $m \in (Z/pZ)^*$ calculates the signature $(r,s)$ as follows: choose random $k \in \{0, 1, \dots, q-1\}$ where $q/p-1$ is prime number and the order of the base $g$ and then calculates $r\equiv g^{k}\pmod p$  and $s\equiv k^{-1}(m+ar)\pmod q$ where $a$ is the private key of Alice.For $p=23$, $g=2$, $q=11$ you are given the signature $(18,3)$ in the message $m=2$. Construct a signature in the message $m'=3$ (without using the private key). The public key of Alice is $y=13$

Could someone give some hints on how to construct this signature in message $m'=3$?

Just read the original paper for ElGamal signatures. Especially one of the attacks in section IV. B should help you out. Alternatively, the Wikipedia article about ElGamals signatures also has a section about existential forgeries.

Since this is clearly homework, I'll leave the rest up to you. One last hint: Use q instead of p-1, since you're actually in a smaller multiplicative subgroup.


Using only pseudorandom function to drive many deterministic keys My question is related to:

Can Pseudorandom values be used as secure keys?

But here I'm only using pseudorandom function.

Assume we have a pseudorandom function, $PRF$. We have a truly random  master key: $mk$ for the PRF function.

I want to deterministically generate $n$ keys, so I do:

$\forall i, 1\leq i\leq n: k_i=PRF(mk,i)$.

Question: Is it secure to use each key $k_i$ to generate $m$ pseudorandom values? E.g. $\forall j, 1\leq j\leq m : k_{i,j}=PRF(k_i,j)$.

Is there any protocol using such scheme (if the scheme is secure) ?

Yes, what you suggest is essentially "KDF in Counter Mode" as defined in section 5.1 of SP 800-108 (pdf). That shows how to derive a long block of "derived key material" using a PRF in counter mode as you do. It includes some inputs for differentiating the context and length of the derived key for domain separation. You could use those, but if you only use this one key derivation procedure you can skip them.

Section 7.3 of the same document states that you can divide the derived material for keys as you like, as long as they do not overlap:

  In the absence of limitations that may be imposed by relying applications, any segment of the derived keying material having the required length can be specified for use as a key, subject to the
  following restriction: When multiple keys (or any other types of secret parameters, e.g. secret initialization vectors) are obtained from the derived keying material, they shall be selected from disjoint (i.e., non-overlapping) segments of the KDF output.

I cannot think of a protocol that does this off the top of my head. E.g. TLS uses a more complex key derivation function, until 1.3 which is supposed to use HKDF.

Speaking of, you might want to use HKDF just because it is more standard, but what you are doing is fine too.