Multiplication in elliptical curve cryptography I'm practising for a cryptography test and came across this question:

  Let us assume that for a specific elliptic curve the formulas for the computation of $(x_3, y_3)=R+S$ are given by:

  $X_3=\sigma^2-x_1-x_2\ (\textrm{mod}\ p)$

  $Y_3=\sigma(x_1-x_3)-y_1 \ (\textrm{mod}\ p)$

  $\sigma = \frac{y_2-y_1}{x_2-x_1}\qquad \textrm{if R}\neq\textrm{S}$

  $\sigma = \frac{3x_1^2+5}{2y_1}\qquad \textrm{if R = S}$

  The following holds: $p=17$, $P=(3, 5)$, $a=3$, $k=2$, $M=(2, 7)$. Compute Q.

I understand the provided solution up until step 5.

  1.$\ Q=a\cdot P = 3\cdot P$

  2.$\ P= (3, 5) \Rightarrow 3\cdot P=2\cdot P+P$

  3.$\ 2\cdot P\Rightarrow(3,5)+(3,5)$

  4.$\ \sigma=\frac{3x_1^2+5}{2y_1}\qquad\ \ \ (R=S)$

  5.$\ \sigma =\frac{3\cdot 3^2+5}{2\cdot 5}=\frac{32}{10}=\frac{16}{5}=\frac{16\cdot7}{5\cdot 7}\textrm{ mod } 17=112\textrm{ mod }17=10\qquad\ \ \  (5^{-1}=7\textrm{ mod } 17)$

I understand that $16\cdot 7\textrm{ mod }17=10$, but where does the $7$ come from? Also, why is $5^{-1}=7\textrm{ mod } 17$ shouldn't that equal zero..?

I understand that $16\cdot 7\equiv 10 \bmod 17$, but where does the $7$ come from? Also, why is $5^{−1}\equiv 7 \bmod 17$ shouldn't that equal zero..?

When working with modular arithmetic, $a^{-1}$ (if it exists) is a number $b$ such that $a\cdot b\equiv 1$. So, because $5\cdot7\equiv 1\bmod{17}$, we say that $5^{-1}\equiv 7\bmod{17}$. Not sure where $0$ came from in your mind as $0$ times anything is $0$.

In step 5, where you are multiplying by $\frac{7}{7}$, the reason they are doing this is to cancel out the bottom since $5\cdot 7\equiv 1$. This step is not necessary, but it does make things simpler, I guess. You can play around with this modular arithmetic calculator to verify that $\frac{16}{5} = 16\cdot 7\equiv 10\bmod{17}$.


Do perfect squares count as valid moduli for an RSA semi-prime? The question is pretty self-explanatory but basically I just want to ask if, when choosing the p and q primes that, when multiplied, become the modulus for an RSA public key, is there a risk that attackers can exploit if p and q are equal to each other?
The only requirement that I've seen up until now is that both p and q need to be primes but I never read anywhere about what happens if they are the same number. Basically, p = q and, as such, the square root of the N modulus is p. Is there an efficient algorithm that can detect this efficiently and, as such, factor the numbers and compute the private key? And, if such an algorithm exists, doesn't this mean that this can compromise existing RSA keys with such setups?
Is this even a realistic risk at all or is it just too unlikely to happen in practice?

There is a simple way to detect if a number is square because there is an efficient way to compute square roots.
This should not be a realistic threat as the chance of picking two $b$-bit primes uniformly at random and getting a match will be about $b(\log 2)/2^b$. Given that a broken random number generator that always returns the same value would cause this to happen, it should not be discounted as a threat. However many standards specify a minimum difference between $p$ and $q$ to block Fermat's difference of squares attack (e.g. ANSI X9.31) which should stop such moduli being generated. Moreover, if such moduli were generated, they would not function properly as RSA moduli as the decryption process would not work.


how to validate cert when signed cert has authority key id but signing cert doesn't? Say I have the following signing cert:

-----BEGIN CERTIFICATE-----
MIIB4zCCAUygAwIBAgIUSyCTib61O8k8TM5JA5n3zDYDFs8wDQYJKoZIhvcNAQEF
BQAwHDEaMBgGA1UECgwRcGhwc2VjbGliIGRlbW8gQ0EwIBcNMTcxMjEwMTYxMDIw
WhgPOTk5OTEyMzEyMzU5NTlaMBwxGjAYBgNVBAoMEXBocHNlY2xpYiBkZW1vIENB
MIGfMA0GCSqGSIb3DQEBAQUAA4GNADCBiQKBgQCn5XdGJUd9PY9zpksbJ2kD57PL
nQ3ISK+qbeSe2H+Uj0AEDnm611tvXlr9a7zBPNwZ2ali9bczirQkxtu/sftSHCGv
LL6sz1vdYP0Un792o5h+PkbQLnDe1lf/W8Q87GY9cRxUQVVfA7QUfgsl4iWgi7tv
qz3dRmxzBpjpgWvp/QIDAQABoyAwHjALBgNVHQ8EBAMCAQYwDwYDVR0TAQH/BAUw
AwEB/zANBgkqhkiG9w0BAQUFAAOBgQBQJpF/uakVjNIOz4Ve+duZYeeghpVxVNVK
t4OFi8DQzAsdFBpDDg/ZdAoXYOI/VHwNR+jKS2bPLmvNR2dP+OuZVdSTYu4/dZtI
Tp9ju17bym9oyWjX8CApa32+4N4WtcYLaVHOgyGA9f1VRHBtLTc8xcuHnJg6v3m9
TYVkR8c3IQ==
-----END CERTIFICATE-----

Here's the output of openssl x509 -in mycert.pem -text -noout on that cert:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            4b:20:93:89:be:b5:3b:c9:3c:4c:ce:49:03:99:f7:cc:36:03:16:cf
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: O=phpseclib demo CA
        Validity
            Not Before: Dec 10 16:10:20 2017 GMT
            Not After : Dec 31 23:59:59 9999 GMT
        Subject: O=phpseclib demo CA
        Subject Public Key Info:
....
        X509v3 extensions:
            X509v3 Key Usage:
                Certificate Sign, CRL Sign
            X509v3 Basic Constraints: critical
                CA:TRUE
    Signature Algorithm: sha1WithRSAEncryption
....

And the following signed cert:

-----BEGIN CERTIFICATE-----
MIIB5TCCAU6gAwIBAgIUVCrbYZRButS1ka5fyUe2iOzFAmwwDQYJKoZIhvcNAQEF
BQAwHDEaMBgGA1UECgwRcGhwc2VjbGliIGRlbW8gQ0EwIBcNMTcxMjEwMTYxMDIw
WhgPOTk5OTEyMzEyMzU5NTlaMB4xHDAaBgNVBAoME3BocHNlY2xpYiBkZW1vIGNl
cnQwgZ8wDQYJKoZIhvcNAQEBBQADgY0AMIGJAoGBANkmWIAsKkL1Bv3PiFA65IRQ
EOSc65rui70M5tvrDpka1jl6QgvGY/jI/6D6h8sZBxyYyncgWaCA4dVv9dmdZm8Z
JPXACUfHTJuk7ApPq2oYjyheyQkSLp8kYP47cidbNfWk3RkTRqwleh3ByG4e1Qxh
sfdf5owA1yuW5JSygppvAgMBAAGjIDAeMA4GA1UdIwQHMAWAA3p6ejAMBgNVHQ4E
BQQDenp6MA0GCSqGSIb3DQEBBQUAA4GBACMLNye3bEzTnHJAroAiV8Rw9rL6QG+x
wrFDBq173MXTAnKar/TujUxfmOzNZCxjPHh6oKRosOWZuI5v8/0wG9I6irYwLXOw
kXMvXT91/m5Vk7rLCqQ+zsFncxg12leHRgglWh1wsJOhPI/B0mYgCA04RNHsm+iC
/XjRBlAt1kMb
-----END CERTIFICATE-----

Here's the output of openssl x509 -in mycert.pem -text -noout on this cert:

Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            54:2a:db:61:94:41:ba:d4:b5:91:ae:5f:c9:47:b6:88:ec:c5:02:6c
    Signature Algorithm: sha1WithRSAEncryption
        Issuer: O=phpseclib demo CA
        Validity
            Not Before: Dec 10 16:10:20 2017 GMT
            Not After : Dec 31 23:59:59 9999 GMT
        Subject: O=phpseclib demo cert
        Subject Public Key Info:
...
        X509v3 extensions:
            X509v3 Authority Key Identifier:
                keyid:7A:7A:7A

            X509v3 Subject Key Identifier:
                7A:7A:7A
    Signature Algorithm: sha1WithRSAEncryption
....

For brevity I've stripped out the "Subject Public Key Info" and "Signature Algorithm" sections from both.

Anyway, note how in the signed cert both the "X509v3 Subject Key Identifier" and the "X509v3 Authority Key Identifier" extensions are present. In the signing cert neither are present.

It seems to me that since the signing cert doesn't have a "X509v3 Subject Key Identifier" while the signed cert does have a "X509v3 Authority Key Identifier" that the cert ought not validate. And yet in OpenSSL it does:

openssl verify -verbose -CAfile signer.pem signed.pem

So who's correct? Is my interpretation correct or is OpenSSL's? Is there any RFC that discusses what the behavior ought to be in this scenario?

The subject key identifier is not used for validation, it is merely used to help in path building.

Please see RFC 5280 section 4.2.1.2 for more details.

Edit: Use of key identifiers in certificate path building is detailed in RFC 4158 section 3.5.12


Lenght of the ElGamal cipher Ok, it's kind of stupid question, but I want to make sure.

What is the length of the ElGamal cipher? It's equal to the size of 2 elements of the cyclic group, right? But lengths of elements are NOT always the same, right?

Toy example:

We pick p = 23, q = 11 (p = 2q+1), our generator is 18, so
G = {18,2,13,4,3,8,6,16,12,9,1}. Sekret key x is 6 (a random form {1,q-1}), h = g^x mod p = 8.

Now is the fun part:

1) Encryption of m = 18 with  r = 8 is (16,3)

2) Encryption of m = 18 with  r = 7 is (6,9)

Am I getting different length ciphers because it's the toy example or what? Padding? All group elements have identical length? I haven't noticed any length difference in the real ElGamal implementation.

One common possibility is that your non-toy ElGamal cipher express integers as fixed-width octet strings, of width large enough for any element in the base field; that could be with I2OSP of PKCS#1v2.2 or equivalent, but there are a number of other (less common) ways.

Another possibility is that you did not try hard enough to find shorter ciphertext for your non-toy ElGamal cipher. When ASN.1 representation of integers is used, the digit size is an octet, and for some parameters an integer might be under the maximum size with low probability, like down to about 1/256 ≈ 0.4%. Even with two integers, quite a few hundred attempts might be necessary to observe a ciphertext below the usual size. There are other conventions where observing shorter ciphertexts would require billions attempts.


ElGamal digital signature. why mod p-1 in delta? Im trying to figure out why $\delta$ in the signature part of ElGamal has mod $p-1$ when $\gamma$ has mod $p$?

$\gamma = \alpha^k \mod p$

$\delta = (x-a\gamma)k^{-1} \mod p-1$

Basically because of Fermat's little theorem: if $a$ is not divisible by $p$ then $a^{p-1} = 1$ $mod$ $p$. A part of the expression for $\delta$ appears as a power of $a$ in the ElGamal signature verification equation, which "happens" to work because it is reduced modulo $p-1$ so Fermat's little theorem applies.


Advantage of AES(Rijndael) over Twofish and Serpent I'm trying to figure out a suitable encryption technique and after reading a bit, I figured the current AES 128-bit encryption is suitable for what I'm trying to do. However, this is more due to the wide-range use of AES than any other factor. So I need to know how the AES compares to the other finalists Twofish, Serpent of NIST's AES competition in terms of speed, security in software systems.

During the final round of the AES contest, NIST issued a summary of the 5 finalists on the topics of security, speed, implementation, and such. That sounds like what you're looking for, see sections 3 and 5 of the paper.

General ideas from the paper:

Rijndael had a potentially lower security margin than Twofish and Serpent.
Rijndael had better performance than Twofish and Serpent.
The Rijndael construction was arguably simpler than Twofish and Serpent.

However, this was published in 2000, 12 whole years ago, so it won't have the latest security updates on the algorithms. Rijndael certainly has more attacks against it due to the focus on it. But presumably a lot less has been put into Twofish and Serpent, so we don't know how strong those algorithms would look if they had the same attention that Rijndael had.


Linear combination IOP for SNARK registers The STARK paper says

  Our ZK-STARK uses a separate Reed-Solomon codeword for each register, leading to w many codewords, each of lower degree n · c. At first glance this tradeoff may seem wasteful, because we now have to solve an RPT problem for each of these w codewords. However, the interaction and use of randomness allowed by the IOP model once again come to our aid: it suffices to solve a single RPT problem, applied to a random linear combination of all w codewords.

My understanding is that

The prover sends an oracle containing a trace of each register, purportedly encoded as a codeword.
The verifier picks a random coefficient for each register.
The prover sends an oracle which purportedly contains the linear combination of these register traces, using the coefficients from #2.
The verifier somehow tests for consistency between the two oracles.

And then there's an IOPP to convince the verifier that the linear combination is close to a codeword. If so, then each register's trace is close to a codeword with high probability.

My question is, how does the consistency test (#4) work? If the verifier was already convinced that each register trace was a codeword, then the verifier would know that either the linear combination was correct, or it was incorrect at many indices. So they could test for consistency at a small number of indices, and if those were correct, the entire linear combination must be correct with high probability.

But in this context, it seems like the above technique wouldn't help, since the verifier is not yet convinced that each register trace is close to a codeword. So how does the verifier test that the purported linear combination is correct?

The prover does not send another oracle as you suggest in #3. Rather, both parties invoke the FRI protocol for the function that is the random linear combination (random coefficients selected in #2). Now, every query to the function you refer to in #3 is answered by querying all oracles #1 and computing the linear combination #2 (which is something the verifier does). Thus, the soundness error for this function is 0 and there's perfect consistency, by construction.


Is there a cryptography algorithm that will remain safe if P=NP? From what I heard, many encryption algorithms are based on the assumption that some problems are computationally hard, i.e, NP-complete. In the unlikely event that someone proves that P=NP, these codes will break.

Is there a practical encryption algorithm that will remain safe even if P=NP?
I.e, an algorithm that depends on problems that are more difficult than just NP-complete?

My guess is that the answer is no: to be practical, a code must be verified in polynomial time, i.e, the problem must be in NP. Is this correct?

Whether P = NP is a question about the asymptotic growth of computational costs of algorithms as functions of input sizes.  It may provide hints about concrete computational cost estimates of algorithms for specific input sizes, but doesn't provide answers.

In the eyes of the asymptotic setting, an $O(n^{10000})$ cost is ‘smaller’ than an $O(1.0001^n)$ cost because for sufficiently large values of $n$, past some boundary $n_0$, all values of $1.0001^n$ exceed the corresponding values of $n^{10000}$.

Does that mean an instance of a cryptosystem that costs $128\;\text J$ energy to compute and costs $128^{10000}\;\text J \approx 10^{20000}\;\text J$ to break is less secure than a cryptosystem that costs $128\;\text J$ to compute and costs $1.0001^{128}\;\text J \approx 1.01\;\text J$ to break?  Certainly not!

For example, finding $k \in \{0,1\}^{128}$ given $\operatorname{AES}_k(0)$ takes $O(1)$ time because the input size $n$ is a constant, but that fact implies nothing about its feasibility in practice.  The asymptotic growth of the NFS and ECM costs guide us toward parameter growth curves for, e.g., RSA, but they require concrete analysis to attain confidence in concrete choice of parameters.

For a particularly goofy example of this, see

  Daniel J. Bernstein, Nadia Heninger, Paul Lou, and Luke Valenta, ‘Post-quantum RSA’, PQCrypto 2017, Springer LNCS 10346, 2017, pp. 311–329,

which shows how to take advantage of a merely quadratic difference between a user's asymptotic costs and an attacker's asymptotic costs to make a cryptosystem, with a recommendation for specific input sizes guided by concrete use and attack cost estimates, that is just barely usable by rich users but likely out of reach of attackers even if they had access to a large quantum computer.

So would it matter if there turned out to be an asymptotically polynomial-time algorithm to solve every NP-complete problem in $O(f(n)^{10000})$ time when testing a solution takes $O(f(n))$ time for polynomial $f$?  No, not really.

Could it matter, if there were a really amazing trick to use a low-degree polynomial that is, in concrete terms, cheap to compute?  Maybe, but at this point that seems implausible—and cryptography might survive nevertheless by high-degree polynomial asymptotic gaps and exorbitant concrete gaps between user and attacker costs even if they're not exponential.


Question about Damgård–Jurik crypto system I am reading the paper about Damgård–Jurik cryptosystem.

In the proof, I found this equation

  $c^d = (g^mr^{n^s})^d = (\boxed{(1+n)^{j m}x^m}r^{n^s})^d =  \boxed{(1+n)^{j md\pmod{n^s}}}(\boxed{x^m}r^{n^s})^{d\pmod{\lambda}}$,

where $g=(1+n)^{j x}\pmod{n^{s+1}}$, $n=pq$ is an RSA module number, $\lambda$ is the least common multiple of $(p − 1)$ and $(q − 1)$, and $\lambda|d$.

I don't know why $((1+n)^{j m}x^mr^{n^s})^d = {(1+n)^{j md\pmod{n^s}}}({x^m}r^{n^s})^{d\pmod{\lambda}}$ holds, can anyone tell me?  Thank you!

The simple answer is that the element $(n+1)$ is of order $n^s$, i.e. $(n+1)^{n^s} \equiv 1 \bmod n^{s+1}$. Thus the first part can be written as $(1+n)^{jmd \bmod n^s}$.

For the other part it is $(x^mr^{n^s})^d$, it is written in that way so that it is easier to see the setting that $d \equiv 0 \bmod \lambda$ ensures this part $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$. To see why, note that $x^\lambda \equiv 1 \bmod n^{s+1}$ and also $(r^{n^s})^\lambda \equiv 1 \bmod n^{s+1}$. The explaination is as the following:

We know that $x\in H$ where $H=\{g^{n^s} \bmod n^{s+1}|g\in Z_{n^{s+1}}^*\}$ is a subgroup of $Z_{n^{s+1}}^*$, we know $r \in Z_{n}^*$ and $Z_{n}^*$ is a subgroup of $Z_{n^{s+1}}^*$ (thus $r$ is also in $Z_{n^{s+1}}^*$).
We know the exponent (the least common multiple of the orders of all elements of the group) of $Z_{n^{s+1}}^*$ is $n^s\lambda$ (see here, $\lambda$ in the paper is a shorthand for $\lambda(n)$). In other words, $a^{n^s\lambda}\equiv 1 \bmod n^{s+1}$ holds for any element $a$ in $Z_{n^{s+1}}^*$
Therefore, $x^\lambda=g^{n^s\lambda}\equiv 1 \bmod n^{s+1}$, and $r^{n^s\lambda}\equiv 1 \bmod n^{s+1}$

It thus follows that if $d\equiv 0 \bmod \lambda$ (i.e. $d = k\lambda $ for some k), then $(x^mr^{n^s})^d \equiv 1 \bmod n^{s+1}$.


Difference between semi-honest and malicious adversary using Ideal Real Model Paradigm Would you please explain to me why in the security definition of ideal/real model paradigm which is described in the efficient secure two-party protocol book(Hazay, Lindell), the simulator tries to simulate inputs and outputs of a party(in the semi-honest model), but the simulator just tries to simulate outputs and not inputs in the malicious model?

Would you please explain the difference between the security definition of idea/real model in the semi-honest and malicious model which is described in that book(page 21 and 25)?

Malicious Adversary

Semi-Honest Model

Would you please explain to me why in the security definition of ideal/real model paradigm which is described in the efficient secure two-party protocol book(Hazay, Lindell), the simulator tries to simulate inputs and outputs of a party(in the semi-honest model), but the simulator just tries to simulate outputs and not inputs in the malicious model?

As mentioned in the above comments, the inputs do not need to be simulated because they are given to both the simulator (i.e., the adversary in the ideal world) and the adversary (in the real world).

  Would you please explain the difference between the security definition of idea/real model in the semi-honest and malicious model which is described in that book(page 21 and 25)?

In the semi-honest setting, the parties have to follow the exact prespecified protocol in the real world, which implies that they cannot change their inputs or outputs. Therefore, the simulators only need to generate an indistinguishable view for each party, given the semi-honest party's input and output.

In the malicious setting, each corrupted party can deviate from the protocol, e.g., changing the inputs and outputs, aborting the protocol, etc. To define its security, intuitively we also want to simulate the adversary's view, but such a view cannot be defined in the same way as in the semi-honest setting anymore. In particular, the view depends on the real-world adversary which can change the given inputs and generate whatever outputs. Therefore, the secure two-party computation is defined as the indistinguishability between the outputs (which could be anything, like the adversary's view) of the simulator and the adversary.

FYI, I think Lindell's tutorial is very helpful.


Choice between appending or prepending nonces to ciphertexts I understand that when using CTR mode it is usually secure to append or prepend the nonce to the resulting ciphertext, whether the nonce is before or after the ciphertext being unimportant.

However, I am making another home-brew protocol (the bad thing that always happens from time to time), which led to the following scenario:

I chose XChaCha20Poly1305, the best AEAD primitive I could get my hands on, as the encryption primitive. I must give up the actual user control of the encryption key, and the nonce cannot be reliably stored persistently, so I chose to generate the nonce randomly. The resulting ciphertext will then be fed into another deterministic encrypter, say AES-CBC with a constant key (burnt into the chip and cannot be changed in the device's lifetime) and zero IV, over which I have completely no control. The final result will then be sent over the wire.

Does the sequence in which the ciphertext is formatted matter? I have no idea whether the device's RNG is broken or not, nor can I choose where to place the authentication tag in relation to the ciphertext.

If it is
$$ nonce || Enc(key, plaintext) || tag $$
then in case of a RNG failure, the security is undermined; and if the extra encrypter is broken, the system fails completely. But if it is
$$ Enc(key, plaintext) || tag || nonce $$
then the extra encrypter might provide a bit of security or even make most security claims hold, even in case of a RNG failure.

Many limitations are involved here, and this might be complicated question, but I hope someone can shed some light on this question for me.

The order of the tag, the nonce and the ciphertext doesn't matter at all. Any encoding would perfectly fine, since what gets authenticated is the data itself and not the way it is encoded for transport.

Now, if you can't use counters, and you don't trust the PRG, you may end up reusing nonces, no matter how they are encoded.

You should either use a nonce-misuse resistant scheme such as AES-GCM-SIV, or use a KDF to create the nonce from the ciphertext, some output from the PRG, and a secondary key.


Design for file transfers to a new party I'm pondering a problem of how to enable transfers of files from clients to people that does not yet have an application/account/keys yet.

Here's my current thought for Alice wanting to send Bob FancyPants.png through my tool:

Generate random UUID
Generate encryption keys from that UUID
Encrypt FancyPants with the key
Upload to server
Ask Alice for Bobs e-mail and send "You have a file waiting, click here to download client and retrieve file securely"
Alice sends Bob the UUID out-of-band, somehow.
Bob clicks the link, enters the UUID on a page and receives a client prepared to start downloading FancyPants.png from the server.

However this method has a couple of problems, step 1, 6 and step 7.

Point 1 since I figure some form of user input would be good, otherwise it's basically just a random key and doesn't require any previous knowledge so anyone can generate it.

Point 6 since it's an out-of-bounds method which likely means they'll likely e-mail or sms in cleartext potentially defeating the whole encryption.

Point 7 since at that point my server will know the unencrypted file, which I'd like to avoid.

Are there any ways around these? I'm looking into if something might be usable like private set intersection or oblivious transfer but people here seem really knowledgeable and might know a better way.

This might be too vague but let me know and I'll edit it. I also don't know how this should be tagged, suggestions highly welcome.

Point 1 since I figure some form of user input would be good, otherwise it's basically just a random key and doesn't require any previous knowledge so anyone can generate it.

Nothing wrong with that. A long random value is the best kind of key there is, much better than anything dependent on user input.

However, as mentioned in the comments, the key material must be from a secure RNG. If you generate the UUID as e.g. a 128 or 256-bit random number using OS randomness, you should be fine.

  Point 6 since it's an out-of-bounds method which likely means they'll likely e-mail or sms in cleartext potentially defeating the whole encryption.

You cannot avoid this. The recipient must know everything needed to request the file, so anyone who finds out what they know will also be able to do the same. By making download links work only once you can at least prevent silent compromise.

(Some sort of email confirmation could also require a compromise of the email specifically, rather than just any random out-of-band channel used. Coupled with warning "do not use email for sending UUID" you have a light 2FA-like system.)

  Point 7 since at that point my server will know the unencrypted file, which I'd like to avoid.

The server does not necessarily need to know it, only the client program. I.e. you can make the user download a generic client that asks for the UUID and identify the file using some derived information. E.g. derive encryption key from the UUID $u$ using $H(u, \text{e})$ and file identifier using $H(u, \text{i})$, then send the latter to the server with the encrypted file. The server will be unable to find $u$ or the encryption key.

Of course, you can always offer a malicious client program anyway, so the server must be trusted.


Argon2 output length and parameter storage? I just started using the libsodium port for .net today and the output length parameter kind of confused me (I'm using the argon2i implementation).

With my limited exposure to hashing, whatever hash algorithm I've used have always returned a constant bit length (for example MD5 & 128). By default it returns 128 just like MD5 which suprised me. I always equated length with strength (though I realize there isn't a 1 to 1 correlation in every case).

Then comes the question with a variable length output what should I choose :). With argon2 are increased bit lengths really going to be that much more secure? I arbitrarily chose 512 bits but I don't know if that's good or not.

A second, but a little unrelated question, do you think you should store the parameters (that can change the hash) in the database along with the password & salt. Examples would be opsLimit, memLimit, outputLenght, etc...

You need to consider the weakest link property: a security system is never stronger than its weakest link.  Since Argon2 is a password-based function, the weak link here is going to be the strength of your users' passwords.  Choosing a longer output length doesn't help if the passwords' entropy is lower than that.

Think of it this way: if the hash function is secure, the attacker has two ways to attack the passwords:

Use dumb brute force to try and find a preimage of one user's passwords.
Use knowledge about user habits to guess more likely passwords ahead of less likely ones.

Longer output may make #1 harder, but once you make #1 hard enough then #2 becomes the easy path and attacker will just try that.  So Argon2's authors' recommendation of 128-bit hashes sounds fine, because the only circumstance in which the 128 bit output would be the limiting factor is if your users' passwords were crazy entropic, like:

ASCII printable uniformly random passwords of length 20 or more (6.6 bits/character);
PINs of 40-digit length or more, chosen uniformly at random (3.3 bits/digit);
11-word or longer Diceware passphrases (12.9 bits/word);
12-word or longer XKCD "correct battery horse staple" passwords (2,048 word dictionary, words chosen uniformly at random).

If your users could be counted on to choose passwords that strong, you wouldn't need a specialized password hash function in the first place!

  A second, but a little unrelated question, do you think you should store the parameters (that can change the hash) in the database along with the password & salt. Examples would be opsLimit, memLimit, outputLenght, ect...

Yes, you should store them.  Note for example that the Argon2 command line utility (which is available from the Argon2 repo) produces verification tags that integrate it (the "Encoded" field from this example from the link):

$ echo -n "password" | ./argon2 somesalt -t 2 -m 16 -p 4 -l 24
Type:           Argon2i
Iterations:     2
Memory:         65536 KiB
Parallelism:    4
Hash:           45d7ac72e76f242b20b77b9bf9bf9d5915894e669a24e6c6
Encoded:        $argon2i$v=19$m=65536,t=2,p=4$c29tZXNhbHQ$RdescudvJCsgt3ub+b+dWRWJTmaaJObG
0.188 seconds
Verification ok

Thinking about this some more, I think I understand why I'd be confused if I was in your position.  If the default 128-bit length is fine, and making it longer doesn't really offer more security, why does the function allow me to choose a longer output length?

Well, the reason is that Argon2 has two distinct uses:

Password verification
Key derivation

Long outputs are of no use in password verification, as I explained above, but of great use in the key derivation case.  An example situation where you want something like that is password-based encryption where you're doing something like encrypting a file with AES-256 but, instead of making the user manage raw AES keys, you try to be friendlier and let them use passwords instead.  This is, for example, how GnuPG's symmetric encryption mode works (albeit it doesn't use Argon2).

In this case, since your cipher needs 256-bit keys then you need the ability to generate 256-bit keys from your users' passwords.  So the selectable output length allows you to match the requirement.

Note that the weakest link property still applies here, so in that scenario even though you'd be using 256-bit encryption, the password would still be the weakest link.  What the longer output length allows you to do is to match a technical requirement imposed by the 256-bit cipher, and offers your users the option of choosing passphrases that are effective up to that security level—which very few will do (e.g., a 40 character random ASCII password!).


In the RSA DES challenges, how did the contestants know they had found the right key considering they weren't given any plaintext? If the contestants were given both the plaintext and ciphertext, it's straightforward. Just bruteforce all 56-bit keys until you find one that maps the given plaintext to the given ciphertext.

But from what I understand, the contestants were given only the ciphertext and the initialization vector. I'm confused as to how they cracked the challenge without any plaintext.

What I imagine they did was:

Ok, we know the plaintext is less than or equal to the size of the ciphertext.
Calculate all possible plaintext from 1 bit up to the bit size of the ciphertext.
Calculate all possible 56-bit keys.
Run each plaintext through all 56-bit keys until they found a mapping.

But this doesn't make sense given the sheer size of the possibilities.

So since they weren't given any plaintext, how did they know they'd found the right plaintext/key combination?

One can still access the challenge rules from the archive.org

  Each contest is based on a specified cipher. A brief piece of printable ASCII text (containing byte values in hexadecimal notation from 0x20 to 0x7e) will be appended to the fixed 24-character string "The unknown message is:". The result will be padded and then encrypted with the associated cipher under a randomly-generated key.

The message is also padded by PKCS#5 padding. Thus, the attacker has three options to test their results;

Check the beginning of the message; it must start with "The unknown message is:"
A valid PKCS#5 padding at he the end.
And, one general rule when only ciphertexts are given; one can check the result is valid (English) language. For this, one block may not be enough, since there are many valid words in the 64-bit block. One block will result in many keys. To narrow the keys, additional ciphertexts are required. This approach can be work even 1. and 2. cases are not known. For this specific challenge the range of the characters given between 0x20 and 0x7e, i.e. between  and ~

distributed.net  found this message in DES Challenge II-1;

The secret message is: Many hands make light work.

Note : It is interesting that the Wikipedia says; The secret message is: where the source is lists.distributed.net, however, the RSA archives says The unknown message is:.


Can a attacker compute a hash from another hash of the same plaintext (both using different salt)? Imagine two PBKDF2-SHA-512 hashes of the same password are generated. Each has individual salt. If an attacker had one hash and the salt of both hashes, would he be able to compute the missing hash or would he gain a significant advantage guessing it?

My situation:
A user inputs a password that should be used for AES encryption. The password is hashed once to get a AES Key. Then a second hash of the password the user entered is generated with a different salt than the first one and is sent to the server together with the salts of both hashes. Can a attacker who hijacked the server, calculate the hash that is used as AES key?

Imagine two PBKDF2-SHA-512 hashes of the same password are generated. Each has individual salt. If an attacker had one hash and the salt of both hashes, would he be able to compute the missing hash or would he gain a significant advantage guessing it?

No. The idea of a hash is that it is impossible to reverse a hash. You can of course guess the hash then both outputs can be calculated, but having two different salts will not give any advantage to an attacker.

Note however that by performing PBKDF2 twice you are giving some advantage to an attacker, who only need to perform PBKDF2 once to verify correctness of a guess. Basically your advantage compared to the attacker is reduced by a single bit.

This is why you could also use PBKDF2 once and then create two values using a KBKDF such as HKDF(-expand) twice with two different labels. KBKDF's such as HKDF do not perform key strengthening so the work factor implied by PBKDF2 doesn't need to be performed twice on the server.


Does larger key size mean larger data size in asymmetric encryption? I'm new to cryptography. I know the larger the key size (like 128-bit vs 1024-bit) the harder the ciphertext is to crack, generally. But assuming everything else being equal, does a larger key size increase the data size compared to the original data in asymmetric encryption? I know AES doesn't increase the data size, but what about RSA?

I've been Googling my question, but I haven't found a straight answer. I just hope the answer is not "it depends", thus I added "assuming everything else being equal".

In addition to kelalaka's answer, keep in mind that the amount of data that can be encrypted with RSA is relatively small (keysize+padding/8), so most schemes use hybrid encryption to use RSA to encrypt a symmetric key and some other critical information and most data is encrypted using the symmetric key.


GoofyCoin question -- why pk, why not sk? At 45:43 in this video (from the Princeton Coursera Bitcoin and CryptoCurrency Course), they talk about GoofyCoin and show the image below.

My question is, why does it say "signed by pk"... isn't the actual signing done using the "sk", and the verification done using the "pk"?

Update: I think I figured out what's going on here, and am leaving this here for future reference. signed by pk(goofy) means "signed by the identity of goofy" because as mentioned in an earlier video, pk = identity

My question is, why does it say "signed by pk"... isn't the actual
  signing done using the "sk", and the verification done using the "pk"?

Yes. The actual signing is done by the "sk".

However, the signature is usually bundled with the public key which can be used to verify it. Thus it makes sense to more strongly associated the public key with the signature. Additionally it makes it trivial from a formal standpoint which public key to use for verification.

Furthermore, the mapping of public-key to private-key is 1:1 most of the time, making the choice of which key to use for indication here a matter of preference.


Solving a quadratic equation for a variant of Rabin My understanding of Rabin
We have $p$ and $q$ which are distinct primes congruent to $3 \pmod 4$.  Then we have $n = pq$.
Encryption is done as $e(m) = m^2 \pmod n$, where $m$ is our message.
Decryption is done by evaluating $d(c) = \sqrt{m} \pmod n$, where $c$ is our ciphertext.  This can be accomplished by determining $m_p = c^{(p+1)/4} \pmod p$ and $m_q = c^{(q+1)/4} \pmod q$ and their negative counterparts.   Then, $m$ is congruent to both $m_p \pmod p$ and $m_q \pmod q$.  Chinese remainder theorem can be used to calculate the four possible values of  $m$.
The variant of Rabin which I'm having trouble with
I'm having trouble with a variant of Rabin which uses the encryption function $e(m) = m^2 + Bm$ where B is an arbitrary value. We then have $c = m^2 + Bm$ which leads us to $0 = m^2 + Bm - c$.  I'm confused as to how to proceed from this point.
My guess is that I must solve the quadratic formula, yet solve the $\sqrt{b^2 - 4ac}$ portion as you solve the square root in regular Rabin.  However, my attempts at this have failed. Is this the correct approach?

The tricky point is that modulo a Blum integer (the product $n = pq$ of two primes $p$ and $q$ that are equal to 3 modulo 4), in general, a quadratic residue (a value that is a square of something) has four square roots, not two.

Consider the "normal" Rabin algorithm. Message $m$ is encrypted into $c=m^2\bmod n$. To decrypt, you work modulo $p$ and modulo $q$. Modulo $p$, you first compute $c_p = c \bmod p$, then $d_p=c_p^{(p+1)/4} \bmod p$
. The value $d_p$ is a square root of $c_p$ modulo $p$; however that is not the only square root. The other one is $d'_p=p-d_p$ .

Similarly, working modulo $q$, you get two square roots of $c$ called $d_q$ and $d'_q$. By combining these square roots with the CRT, you end up with four candidates for $m$. This is the usual problem with Rabin encryption: you have to include some redundancy of format in the message (e.g. deterministic padding computed through a hash function) to determine which of the four candidates is the right one.

With the variant, things are similar: you must still work modulo $p$ and modulo $q$, and get two candidates modulo each prime, hence four combinations. With encryption $c=m^2+Bm \bmod n$ , you solve modulo $p$ the equation:

$$c_p \equiv  d_p^2+Bd_p \pmod p$$

which is equivalent to:
$$d_p^2+Bd_p-c_p \equiv 0 \pmod p$$

you solve it by computing $D_p=B^2-4c_p$, then extracting one square root $S_p=D_p^{(p+1)/4} \bmod p$. The two candidates are then:

     $d_p=(-B+S_p)/2 \bmod p$

     $d'_p=(-B-S_p)/2 \bmod p$

You also get two candidates $d_q$ and $d'_q$ modulo $q$, and the CRT gives you the four candidates for the decryption result.

Note that whenever you extract a square root with the $(p+1)/4$ exponent, you should verify that you indeed get a square root (by squaring it and checking that you indeed get the source value). Modulo $n$, only about one value in four is a quadratic residue. If the encrypted message is correct, then all square root extractions shall succeed, and you get four candidates; if it is not, then you get wrong values, and you should report an error.


Generalizing the conversion of Diffie-Hellman to El Gamal How can we generalize the conversion of Diffie-Hellman to El Gamal public-key encryption scheme? The goals is to be eventually able to show that any 2-round key-exchange protocol can be converted into a public encryption scheme that is CPA-secure.

The 2-round key-exchange protocol mentioned should satisfy the requirement that: given a key K, it will not be able to determine whether it was given the "correct" key corresponding to the given execution of the protocol, or whether K is completely random key independent of the execution.

The conversion of Diffie-Hellmen into Elgamal is assisted by a few factors that are not inherent to key exchange/agreement protocols in general, but a general conversion may be possible.

The DH $\rightarrow$ Elgamal case. In Diffie-Hellman, Alice generates $a$ and sends a representation of it: $g^a$. Bob generates $b$ and sends $g^b$. Both parties can compute $g^{ab}$. To convert to Elgamal, Alice starts the protocol generating $a$ and posts $g^a$ so anyone can complete Diffie-Hellman with her. If Bob wants to complete the protocol, he generates $b$ and sends $g^b$. To make it encryption, he generates the shared secret $g^{ab}$ and multiplies in his message $mg^{ab}$ and sends that as well.

Why is this CPA-secure? Under DDH-assumption $g^{ab}$ is indistinguishable from a random group element so it works as a sort of one-time pad. Since the sender contributes $b$ to the random mask, each encryption of the same message results in a different ciphertext.

What is needed for a general conversion? (These is just "brainstorming" and not meant to be comprehensive).

It is important to have a DDH-type assumption that shows the shared secret is indistinguishable from random.
The shared secret must be an element of a group so there is a permissible operation that can be used to combine it with the message with closure.
The conversion is also assisted by being from an unauthenticated key exchange. Most other common key exchange protocols are authenticated (or mutually authenticated). This doesn't necessary prevent a conversion, just adds unnecessary weight to the encryption scheme (and if you strip off the authentication, you may find yourself back at basic Diffie-Hellman).
As per @Paulo's comment, Alice's first move must be securely repeatable.
While in DH, this does not occur, there is not problem with Bob using Alice's output from the first move to generate his share. So two-round protocols are fine when only one party is needed in the second round.

It would be interesting if you could provide some examples of other key exchange protocols that are eligible for conversion. I think you'll find the majority are either based on adding properties to Diffie-Helman that assists in making it a better key exchange but doesn't assist you in a conversion, or they don't lend themselves to conversion (too many rounds, they already use public key encryption, etc.)


Is it okay to include relative time for true random number generation? Similar questions have been asked regarding use of time in true random number generation, but I'd like to consider using time as just one source of entropy, complementing others.

True random number generation relies on the mensuration of some physical stochastic process.  Electrons avalanche across depletion boundaries in essentially one dimension.  Polarised photons move in two dimensions, whilst rolled dice move in three.  All are potential sources of entropy whose measure in up to three dimensions is used to generate random numbers.

However space is four dimensional.  Rolling a 6 might be random, but isn't it even more precise to say it was a 6 at 7.49 am?  Some people say that as time is known it is unsafe to use as a source of entropy.  On my machine, Java can measure relative time to a precision of 350ns from boot time.  Allowing for a realistic boot duration variation of 10s, that allows for 7.5 decades of resolution.  Who can tell when my machine was booted? It might have been on for a year, so 7.5 decades of resolution is a conservative estimate.  And what if the numbers aren't consumed immediately, but cached somewhere ageing them? Bytes resulting from such a generator obviously have no associated time stamp.  This then adds at least another 7.5 zeros to the number of combinations of entropy, and consequently increases security.

When measuring a physical property, isn't it just as important to record when a voltage was measured as is the number of volts? The voltage is measured relative to a reference voltage, and surely it can be measured relative to boot time? After all, /dev/random uses timings for it's cryptographically secure output.

Supplemental:

After some testing, I found that the simple Java function

System.nanoTime() & 0xff

can generate entropy at a rate of 1.4mb/s surprisingly.  It varies in as still uncertain ways correlated with the system load.

Also, there seems to be a great effect when such entropy (call it Relativity) is mixed with another source.  So again based on experiments, the following was found (but I think requires further study - seems to exhibit behaviour reminiscent of superposition)...

H(weak source) = 0.039%

H(Relativity) = 2.2%

H(weak source XOR Relativity) = 32%

If Relativity is therefore combined with physical measurements, this seems to be low lying fruit, especially in an entropy deficient environment.

Who can tell when my machine was booted?

Anyone who observed it go on, at least. That could include someone sniffing your wlan traffic. However, if the computer in question is a shared server, anyone with access can probably call uptime.

  After all, /dev/random uses timings for it's cryptographically secure output.

In setups where timing information is included (in a way that counts entropy), the thing being timed is supposed to be unknowable. For example, the least significant bits of when a physically present user presses a key.

In theory, even that isn't necessarily unknown (e.g. wireless keyboard), but since there is additional variation in how long it takes until the kernel knows about it and the entropy estimate is quite pessimistic, it is assumed to be.

However, in my opinion the most important thing to keep in mind is that you only need the TRNG to produce something like 256 bits on output. Use that to seed a CSPRNG and you can produce more output than you could ever use.

So if you have a truly random process, measuring the non-time values should be enough to quickly collect the required amount of entropy. You can throw time values into the entropy extractor if you like, but you don't need to credit them with entropy if you get enough anyway.


Can CBC-encrypted files be modified in-place? When changing a (small) part of the plaintext of a CBC-encrypted file, how much of the file will have to be rewritten?

My suspicion is that everything after the modified block will have to be decrypted and reencrypted as well, due to the changes of the ciphertext blocks cascading through the rest of the file.

If you could use the same IV, then yes, you would need to rewrite everything after the modified block.

But you shouldn't do that; every time the contents change, you should generate a new IV, which would require the whole file to be rewritten. Otherwise an attacker can learn more information than it should about how the file changed (precisely by checking which blocks of the file have changed).


What algorithm does .NET use to generate primes for RSA and how can I verify it? There is an implementation of RSA in C# .net, but how can people know that this implementation is considering all the secury stuff conserning to RSA?

For example I want to know what is the algorithm that they use to generate prime $p$ and $q$, and how the verify that that primes are good primes and they don't need to look for another pair.
Also, what value of $e$ they are choosen?

Is there some documentation with this kind of information aviable online?

Best regards,

There is an implementation of RSA in C# .net,

That depends on what you mean by "implementation".

In .NET Framework there are two built-in classes which provide RSA functionality:

System.Security.Cryptography.RSACryptoServiceProvider (mscorlib.dll)
System.Security.Cryptography.RSACng (System.Core.dll)

In .NET Core there are 3.5 classes:

System.Security.Cryptography.RSACryptoServiceProvider (System.Security.Cryptography.Csp.dll, some functionality Windows-only)
System.Security.Cryptography.RSACng (System.Security.Cryptography.Cng.dll, Windows-only)
System.Security.Cryptography.RSAOpenSsl (System.Security.Cryptography.OpenSsl.dll, non-Windows-only, requires OpenSsl 1.0.x on the system)
The opaque type returned by System.Security.Cryptography.RSA.Create() (System.Security.Cryptography.Algorithms.dll)

None of those actually "implement" RSA, in that none of them really understand modulus, exponent, or CRT.

  What value of $e$ they are choosen?

All of the inbox providers use F4 / 65537 / 0x010001 as the value for the public exponent with their default options.

  I want to know what is the algorithm that they use to generate prime $p$ and $q$

That's up to the underlying library.  In some cases, that's up to an underlying library for the underlying library.

RSACryptoServiceProvider (.NET Framework, .NET Core on Windows)

The key is created with CryptGenKey.

Unless configured differently with a CspParameters value in the constructor(s) which accept(s) one the type uses PROV_RSA_AES with the default provider for that ProvType (MS_ENH_RSA_AES_PROV / "Microsoft AES Cryptographic Provider") and a key in the AT_EXCHANGE slot.

RSACryptoServiceProvider (.NET Core on non-Windows)

Skip ahead to RSA.Create(), this is just a compatibility type on non-Windows systems.

RSACng (.NET Framework, .NET Core on Windows)

The key is created with NCryptCreatePersistedKey using a null name (making it an ephemeral key) and the Microsoft Software Key Storage Provider provider.

To create keys using other providers someone can call a CngKey.Create overload and pass the pre-created key to new RSACng(CngKey).

RSAOpenSsl (.NET Core, non-Windows)

Keys are created using RSA_generate_key_ex with a fixed $e$ = $65537$, and an RSA* created with RSA_new (the default engine).

RSA.Create() (.NET Core)

On .NET Core an opaque type is used for platform-independent RSA functionality.  On Windows it's functionally equivalent to using RSACng.  On Linux (and any other *NIX other than macOS (or including macOS for the 1.0 or 1.1 releases)) it's functionally equivalent to using RSAOpenSsl.

Starting with .NET Core 2.0 the macOS version is powered by a non-public type which creates the key using SecKeyGeneratePair.

Completing the matrix

RSAOpenSsl doesn't exist at all on .NET Framework, and throws PlatformNotSupportedException on .NET Core for Windows.  RSACng throws PlatformNotSupportedException on .NET Core for systems-other-than-Windows.

On .NET Framework RSA.Create() emits an instance of RSACryptoServiceProvider, unless configured differently via CryptoConfig.

Other types

RSA is an open type, so anyone is free to write an RSA provider for .NET.  This post contains all of the types that ship as part of .NET (Framework or Core) and provide RSA functionality... for any other types you'd need to track down their owners.

So, I know that doesn't really answer your question; but it does give you places you can go to further hunt things down if you want to know the answers.

The proof of these statements for .NET Core can be found at https://github.com/dotnet/corefx/.  RSACng on .NET Framework at http://referencesource.microsoft.com/, and for RSACryptoServiceProvider on .NET Framework a combination of referencesource and a debugger (the actual call to CryptGenKey lives within clr.dll, which is not published on referencesource).

Oh, and Mono and Xamarin are probably doing something completely different.


How to compare one time pad security and efficiency with AES? It seems that the minimal size of Pseudorandom permutation (PRP) output is $128$ bits. In general, I'd like to see if there's any minimal size of the output of pseudorandom function (PRF) as well? for instance can we set the output size of PRF to 32 or 40 bits.

Below, I'm trying to explain the question with an example.

Let $k_i$ be secure random key. I've a message $m$ of 32-bit. I want to encrypt it in two different ways:

Using output of a pseudorandom function (PRF) as a one time pad: I do the following:

a) $PRF_{k_1}(0)=a$,

b) $c_1=a \cdot m$.
Using a Pseudorandom permutation (PRP):

a) $c_2=PRP_{k_2}(m)$

Question 1: What is the minimal size of $c_1$? Can we set the output size of PRF to 32 bits, so the size of $c_1$ would be the same?

Question 2: what is the minimal size of $c_2$? Am I right it is at least 128 bits?

Question 3: If the answer to both questions is positive, then how can we compare the security and efficiency of the above two schemes with each other?

Please kindly let me know if my question is not clear, etc instead of down voting it; and I'll address your comments.

Answer 1:  If you are going to use a "one time pad", then $c1$ must be exactly the same size as $m$, so $c1$ must be 32 bits.  (Note:  Using a PRF and evaluating with the input of 0 is not a one-time pad.  It might be equivalent if you change $k_i$ every time, but then why bother with the PRF when you could use $k_i$ directly?)

Answer 2:  Since you specific it as a PRP (pseudorandom permutation), $c2$ must be 32-bits.  With a permutation, the size of the input matches the size of the output.  A PRP pseudorandomly maps each element of the possible input set to a single item in the output set.  So as with the first, $m$ and $c$ must be exactly the same size.

Answer 3: There isn't sufficient information about the rest of the system or usage to really comment on their security with the exception to say:  trying to make a "one-time pad" from other function almost always fails and anything that has only a 32-bit input can probably be trivially brute forced.


Hash which can be used to verify one of multiple inputs? Is there a hash function H1 which, when given inputs a, b, etc., produces output Z, and an H2 which can verify any one of a, b, etc. when given Z like this:

H1(a, b) => Z
H2(Z, a) => true
H2(Z, b) => true
H2(Z, c) => false

And where Z is (currently thought to be) cryptographically secure (i.e., modifying Z in any knowable way makes H2 return false for any of the provided inputs)?

Edit: An additional condition which I forgot to articulate originally. a cannot be derived from b and Z, and b from a and Z. Without this condition, we can just use Shamir's Secret Sharing, with a k value of 1, a randomly generated secret Z and a, b, etc are our n values.

What you are looking for reminds me of one-way accumulator functions [1]. Basically, a one-way accumulator permits to prove the membership of an element $x$ to a set $S$ without revealing the actual members of the set. See for example this definition from [2]:

  The most common form of one-way accumulator is defined by starting
  with a “seed” value $y_0$, which signifies the empty set, and then
  defining the accumulation value incrementally from $y_0$ for a set of
  elements $S = \{x_1,···,x_n\}$, so that $y_i = f(y_{i−1},x_i)$, where $f$ is a
  one-way function whose final value does not depend on the order of the
  $x_i$'s. [...] Because of the commutative nature of $f$ ,
  a source can digitally sign the value of $y_n$ so as to enable a third party to produce a short proof for any element $x_i$ belonging to $S$ [...].
  A well-known example of a one-way accumulator function $f$ is the
  exponential accumulator  $exp(y,x) = y^x \mod N$, for suitably-chosen
  values of the seed $y_0$ and modulus $N$. In particular, choosing $N = pq$ for two strong
  primes $p$ and $q$ makes the accumulator function $exp$ as difficult to break as RSA cryptography [1].

Update: Let's see an example using the $exp$ function defined above. Suppose $a$, $b$, and $c$ are inputs, and that $y_0$ and $N$ are chosen properly. Then the accumulator algorithm $H_1$ will do the following:

Compute $s = a \cdot b \cdot c$ and $y = exp(y,s) = y_0^s = y_0^{abc}$
For each element $i$ in the input, compute $y_i = exp(y,1/i) = y^{1/i}$. For example, $y_a = y_0^{bc}$.
Output $z = (y,y_a,y_b,y_c)$.

Now, if you want to check if some element $x$ belongs to the original collection, you just have to check if for any of the partial results $y_i$, the equation $y = exp(y_i,x)$ holds. For example, if you try with $a$, then equation $y = exp(y_a,a)$ holds, since $exp(y_a,a) = (y_a)^a = (y_0^{bc})^a = y_0^{abc} = y$. On the contraty, if you try with $d$ different to $a$, $b$ and $c$, then none of the equations hold.

The problem with this solution is that output $z$ grows linearly with the size of the set of members.

References:

[1] Benaloh, J., & De Mare, M. (1994, January). One-way accumulators: A decentralized alternative to digital signatures. In Advances in Cryptology—EUROCRYPT’93 (pp. 274-285)

[2] Goodrich, M. T., Tamassia, R., & Hasić, J. (2002). An Efficient Dynamic and Distributed Cryptographic Accumulator*. In Information Security (pp. 372-388).


Can we reverse a hash when we know part of the input? While I read that hashes are not meant to be reversible, but assuming we have part/half of the message/input of a hash? Is there any method that we can use to recover the remaining message via this part of the message that we have?

Thanks in advance

It depends of course on the hash function you're dealing with. Assuming it is a cryptographically secure hash function, you're still looking at brute forcing the output: in other words, trying every possible input, computing the hash and then comparing with the output. Finding two inputs with the same output is a hash collision. Consider the MD5 hash function, which is no longer considered secure, the known collision attacks end up flipping more bits across the whole input, so depending on exactly which parts of the input you know, you might be closer to a collision.

However, most hash functions besides MD5 have only theoretical collision attacks, with no known working examples. If you aren't extremely lucky, then you will have to search for exactly as long as for what you know is different from the real input.

Knowing part of the input does reduce the search space of your brute force attempts, especially if you know the total size of the input. Most hash cryptographic functions can be used a checksums, which means they can function on inputs of arbitrary length. So in other words, if you don't know the total size of the input, then you may be searching literally forever.

If you know the input class to the hash function is fairly straightforward (for example, it's an English dictionary word, or a series of words), then you can potentially employ a rainbow table. If the input is sufficiently noisy, the rainbow table becomes prohibitively large, which is why salt is an effective countermeasure.


converting to rank one constraint system I was reading Vitalik Buterin's post on ZK-snarks and I need some clarification
on some points . since there aren't that many posts and articles regarding the subject , I had no choice other than turning to stackexchange .
here is the post :
https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649

first I need to know what does he mean by saying " There is a standard way of converting a logic gate into a (a, b, c) triple depending on what the operation is " ?   is he pointing to a specific topic in math ? why triple ? googled R1CS . not that many results came up.

secondly , why use the variable "one" . why assign the variables in a particluar order which is : "one" "x" "out" ... etc .  why 3 vectors ? and HOW does that exactly work ? ESPECIALLY assigning the variables at the 3rd gate is a bit not clear .

I know these are too many questions and even though I really appreciate any help that I can get , yet I don't expect you to answer every single question.however , if you could point me to the topics,keywords,etc... which describe the methods used therein ,perhaps I could work my way to the end of this article .
i wish someone would have wrote a complementary post on this article instead
of repeating the sudoku example over and over again . all you can find is either
really heavy math papers or waldo analogy . nothing in between .

p.s : i have read posts on zcash blog. still not clear on R1CS and QAP . and scientific papers are too math heavy ...!
thanks in advance

what does he mean by saying " There is a standard way of converting a logic gate into a (a, b, c) triple depending on what the operation is " ?

He means that every "+" operation will follow the same pattern.  (As will every "-" operation, "*" operation, and "/" operation)
Example using '+' operation:
Statement:
x + y = z

Witness vector
Let's assume our witness vector corresponds to the following variables:

[ ~one, x, y, z (or ~out) ]

The order of these variables is arbitrary, it just has to be kept consistent through out the process
Convert the statement into the A * B - C = 0 format:
(x+y) * 1 - z = 0

This means the following is also true:
A = x + y
B = 1
C = z

Determine the "factors" for each variable in our witness vector
A = (0 * ~one) + (1 * x) + (1 * y) + (0 * z) = x + y
B = (1 * ~one) + (0 * x) + (0 * y) + (0 * z) = ~one
C = (0 * ~one) + (0 * x) + (0 * y) + (1 * z) = z

Our vectors then directly correspond to the factors for each variable in the witness vector
A = [0, 1, 1, 0]
B = [1, 0, 0, 0]
C = [0, 0, 0, 1]

Note that this "pattern" of vector will be used for ANY addition gate where two variables are being added to create a third variable.

A:

1 for each value corresponding to the variables being added
0 for everything else

B:

1 for the value corresponding to ~one
0 for everything else

C:

1 for the value corresponding to the output variable
0 for everything else

I hope this also demonstrates why the ~one variable is necessary.

EDIT:

why 3 vectors ? and HOW does that exactly work ?

The formula A.s * B.s - C.s = 0 allows you to perform any addition/subtraction/multiplication/division operations between values and variables.
The dot product (A.s) allows for scaling and addition of values, and the A*B part allows for multiplication and division of values.
The C vector simply represents the result as a value or variable


Consequences of AES without any one of its operations Suppose AES-$128$. There are $4$ operations in AES's encryption, they are SubByte, Shift Row, MixColumns and AddRoundKey.

Question: If I remove one of the following opearations, what will happen to the AES?
SubByte, Shift Row, MixColumns

If Shift Row is removed, then attacker can treat input block ($128$ bits) as $4$ independent $32$ bits block. Hence, attacker can attack these $4$ blocks one by one to recover key.

If MixColumn is removed, then attacker can treat input block ($128$ bits) as $16$ independent $8$ bits block. Hence, attacker can attack these $16$ blocks separately.

If SubByte is removed, then the non-linearity of AES is gone. But I don't know how an attacker can attack the AES?

Can anyone give some hint?

As poncho notes in the comments above, viewing the input block as a 128-element vector over ${\rm GF}(2)$, the AES ShiftRows and MixColumns operations are both linear transformations, and AddRoundKey is just vector addition.

Both linear transformations and addition of a constant are kinds of affine transformations, and since the composition of any two affine transformations is itself an affine transformation, it follows that, if the non-affine SubBytes step is removed from AES, the whole cipher becomes affine.

In particular, every affine transformation can be represented in the form $c = Ap + k$, where $p$ is the plaintext input (a vector of 128 bits), $c$ is the corresponding ciphertext output, $k$ is a constant vector and $A$ is a 128 × 128 bit matrix.  Furthermore, the inverse of this transformation is then simply $p = A^{-1}(c - k)$, where $A^{-1}$ is the matrix inverse of $A$, and (for vectors over ${\rm GF}(2)$) both vector addition "$+$" and subtraction "$-$" simply mean bitwise XOR.

The constant $k$ obviously depends on the key, but the matrix $A$ actually does not — it is fully determined by the ShiftRows and MixColumns steps, neither of which are key-dependent.  Thus, you can precalculate it e.g. by implementing this affine AES variant yourself, leaving out the AddRoundKey step as well to make it linear, and using this to encrypt (or decrypt) all the 128 blocks with a single bit set to one and all other bits zero, which will directly give you the columns of $A$ (or of its inverse $A^{-1}$).

Once you've precalculated $A$, even just a single known plaintext/ciphertext block pair $(p,c)$ encrypted using the actual affine cipher will let you determine the key-dependent the additive constant $k = c - Ap$.  Knowing $A$ and $k$ will then let you encrypt (or decrypt, using $A^{-1}$) any arbitrary plaintext (or ciphertext) block.


Trying to finalize my understanding about password storing am sorry, an a beginner, so please forgive me if i make mistakes, so here is what I understood:

PBKDF2: uses HMAC, so, the message is the password, and the key that crypts the message is the salt? or is it the inverse? and this is done the number of the rounds $n$ times.

So I guess the second one, because the user will write the password, and then the program will consider this as a key to decrypt the salt?

BCrypt: used to avoid custom hardware cracking, altering the table where the hashes are stored to make the result unpredictable so to force the program to wait and to block? and using only 4KiB in CPU cache to block the program (GPU will become slow since they dont have cache? )?
BCrypt encrypts the password using a key derived from the same password using Blowfish $2^n$ times?

SCrypt: kind of BCrypt but...uses lot of memory to block the process on a huge amount of memory, to block the calculations and force the program to wait?

So, BCrypt uses a small amount of CPU Cache, while SCrypt uses a large amount of RAM?

Each of these algorithms has a similar process:

$K_{i+1} = R(K_i)$

Where $K_0$ is set to some concatenation of the plaintext password and optionally a salt value, and $R$ is the algorithm specific "round function". The number of iterations is also adjustable by the application.

As you said, the input of the next round comes from the output of the previous round, which forces the work to be done in serial. A program that uses this need not block, it could be done in a separate thread.

The algorithms differ in their choice for $R$. It seems that BCrypt uses a function based on Blowfish, while SCrypt $R$ relies on a large lookup table. They all have the same purpose, to make checking a large number of hashes as resource hungry as possible, while trying to minimize user inconvenience caused by a small delay in checking a single password.


discrete logarithm problem of ecc I have read a lot about the discrete logarithm problem of ecc, but I still do not understand the problem as follows:

We have domain parameters: (p, E, P, n, h), where n is the order group of P.

The process of creating privatekey - publickey is as follows:

Select a random number k under [1, n - 1]
Calculate Q = kP
Return Q is publickey, k is privatekey.

As far as I know, domain paramters and Q will be public. But, suppose I was the eavesdropper, I know P produces 1000 points (as the parameter n), because Q = kP so Q will be a point in point set generated by P, so I can generate order group P and see the position of Q for privatekey k (since k is in [1, n-1]).

For example: P generate 0P, P, 2P, 3P, ... 1000P. I choose k under [1,999] is 120 -> Q = 120P -> position of Q in the order group P is 120 -> k = 120.

So if I know P and Q, then I know privatekey then ??? So where is it safe?

I suppose so because NIST gives you some recommended domain parameters and I think the order group has to be pre-calculated to save on computational cost.

Thank you for everyone's help!

The poblem of computing the private key $d$ from the public key $Q$ is indeed referred to as $ECDLP$. It is crucial that you choose the domain parameters so that the $ECDLP$ is intractable. Concerning your choice of $d$ ... it is too small and can thus be computed efficiently. Imagine $d$ not having 7 Bits like in your example but 192-, 384- or even 512 Bits. You wouldn't get very far using your method (or any other currently known and implementable algorithm).

In order for the $ECDLP$ to be intractable, $d$ must be adequately chosen so that you cannot just brute-force all values for $d$ until you find a $d$ so that $dP = Q$. This is why curves that are considered as secure today use large values for $n$ and $p$ and create a random value $d$ in the range $[1\dots n-1]$.


ECDSA private key format Here's a sample ECDSA private key (I don't use it for anything):

-----BEGIN EC PRIVATE KEY-----
MHQCAQEEIFL3sLnioGcDvHWM/BPlNw96BOx1KKco2qsq4UwhQUosoAcGBSuBBAAK
oUQDQgAEXs1Fmq4QdPAbn3NycdEU+HOjc3kW9efbso2kI/vdDTWcSCMk310s53G3
tRClDBPPuuJAsKghbPfaTaUpmXFCNA==
-----END EC PRIVATE KEY-----

Here's what OpenSSL's asn1parse says about it:

    0:d=0  hl=2 l= 116 cons: SEQUENCE
    2:d=1  hl=2 l=   1 prim:  INTEGER           :01
    5:d=1  hl=2 l=  32 prim:  OCTET STRING
   39:d=1  hl=2 l=   7 cons:  cont [ 0 ]
   41:d=2  hl=2 l=   5 prim:   OBJECT            :1.3.132.0.10
   48:d=1  hl=2 l=  68 cons:  cont [ 1 ]
   50:d=2  hl=2 l=  66 prim:   BIT STRING

My question: where is this format defined?

You can find the definition in RFC 5915.

It defines an ECPrivateKey object:

ECPrivateKey ::= SEQUENCE {
 version        INTEGER { ecPrivkeyVer1(1) } (ecPrivkeyVer1),
 privateKey     OCTET STRING,
 parameters [0] ECParameters {{ NamedCurve }} OPTIONAL,
 publicKey  [1] BIT STRING OPTIONAL
}

From Section 3:

  The fields of type ECPrivateKey have the following meanings:

  version specifies the syntax version number of the elliptic curve
    private key structure.  For this version of the document, it SHALL
    be set to ecPrivkeyVer1, which is of type INTEGER and whose value
    is one (1).
  privateKey is the private key.  It is an octet string of length
    ceiling $(\log_2(n)/8)$ (where $n$ is the order of the curve) obtained
    from the unsigned integer via the Integer-to-Octet-String-
    Primitive (I2OSP) defined in RFC3447.
  parameters specifies the elliptic curve domain parameters
    associated to the private key.  The type ECParameters is discussed
    in RFC5480.  As specified in RFC5480, only the namedCurve
    CHOICE is permitted.  namedCurve is an object identifier that
    fully identifies the required values for a particular set of
    elliptic curve domain parameters.  Though the ASN.1 indicates that
    the parameters field is OPTIONAL, implementations that conform to
    this document MUST always include the parameters field.
  publicKey contains the elliptic curve public key associated with
    the private key in question.  The format of the public key is
    specified in Section 2.2 of RFC5480.  Though the ASN.1 indicates
    publicKey is OPTIONAL, implementations that conform to this
    document SHOULD always include the publicKey field.  The publicKey
    field can be omitted when the public key has been distributed via
    another mechanism, which is beyond the scope of this document.
    Given the private key and the parameters, the public key can
    always be recomputed; this field exists as a convenience to the
    consumer.

As pointed out in the comments, OpenSSL actually uses a slightly different format, namely the SEC1 format found in SECG's SEC 1: Elliptic Curve Cryptography. From the description of the openssl ec command:

  -inform DER|PEM

  This specifies the input format. The DER option with a private key uses an ASN.1 DER encoded SEC1 private key.

However, as was also noted, the differences are small even if they are worth noting. From RFC 5915's Appendix B:

  This appendix lists the differences between this document and
    SECG1:

  This document uses the I2OSP routine defined in RFC3447 while
     SECG1 defines its own routine.  The two routines result in the
     same output.
  SECG1 constrains its parameters (i.e., the curves) to
     SECGCurveNames.  This document constrains the parameters to
     NamedCurve from RFC5480.
  This document requires parameters be present while SECG1 does
     not.
  This document specifies requirements for encoding rules while
     SECG1 did not.


Why is breaking the Blum Blum Shub PRNG not an undecidable problem? The Blum Blum Schub (BBS) pseudo random number generator (PRNG) is defined inductively by
$$
x_{i+1} = x_i^2 \mod N
$$
to generate the bit sequence $b_0b_1b_2...$ where the bits are taken to be the parity of the integers $x_i$, and $N$ and $x_0$ must satisfy particular properties (see this post for example).
The BBS generator is a cryptographically secure PRNG, modulo the Quadratic Residuosity problem; given the integer $N$; the authors reduced finding the prior bit stream to the problem of finding the two prime factors of $N$.
What I am unclear on is why the authors assumed the adversary has access to the integer $N$ and or $x_i$.  By the definition of a cryptographically secure PRNG on Wikipedia, given part or all of the internal state, an adversary should not be able to reconstruct the prior stream of random numbers.  Under this definition, would it not be sufficient to claim that the "internal state" is not the integers $x_i, N$, but rather the stream of bits $b_0b_1...$?
After all, if I am not mistaken, if an adversary obtained access to part of the pseudo random bit stream, then uniquely determining $x_0$ and $N$ from just that information should be very difficult or undecidable, so I am not sure why the authors reduced the challenge of reconstructing the prior bit stream to solving the quadratic residuosity problem.
In particular, how exactly is the "internal state" of a PRNG defined, if not off the random bit stream?  Is the internal state defined as being the random seed? A few iterations after the random seed?  If so, and the PRNG "seed" is reliant on a set of secret parameters $a_1, a_2,...a_m$, then how many of those parameters should be revealed to constitute an "internal state"?

By the definition of a cryptographically secure PRNG on Wikipedia, given part or all of the internal state, an adversary should not be able to reconstruct the prior stream of random numbers.

That's an engineering specification of what requirements a practical CSPRNG should be evaluated against. The definitions used for pseudorandom generator (PRG) in cryptographic theory are weaker than that. For example in Katz & Lindell's textbook (2nd edition), Definition 3.14 (p. 62):

DEFINITION 3.14. Let $\ell$ be a polynomial and let $G$ be a deterministic polynomial-time algorithms such that for any $n$ and any input $ \in \{0,1\}^n$, the result $G(s)$ is a string of length $\ell(n)$. We say that $G$ is a pseudorandom generator if the following conditions hold:

(Expansion:) For every $n$ it holds that $\ell(n) > n$.
(Pseudorandomness:) For any PPT algorithm $D$, there is a negligible function $\mathsf{negl}$ such that $$\bigg|\mathrm{Pr}\big[D(G(s)) = 1\big] - \mathrm{Pr}\big[D(r) = 1\big]\bigg| ≤ \mathsf{negl}(n)$$ where the first probability is taken over uniform choice of $s \in \{0,1\}^n$ and the randomness of $D$, and the second probability is taken over uniform choice of $r \in \{0,1\}^{\ell(n)}$ and the randomness of $D$.

This is the sort of definition that Blum Blum Schub would be evaluated against, and it doesn't even assume that PRGs have an incrementally updated state.

The engineering requirements (I wouldn't call it a definition) that you're reading are, of course, contemplating a range of practical attacks that the theoretical work abstracts away from. But you'll find that practical cryptographic random generator designs routinely embed something like the theoretical definition as a module. For example, with Fortuna the recommendation for what it calls its "generator" submodule is to use a block cipher in CTR mode, whose state is a key/counter pair that allows trivially to reconstruct earlier states (just decrement the counter). But that state is scoped to individual calls to the larger Fortuna construction:

The key is also changed after every data request (however small), so that a future key compromise doesn't endanger previous generator outputs. This property is sometimes described as "Fast Key Erasure" or Forward Secrecy.

So a generator that doesn't have forward secrecy (a name for the property you ask about) is used as a building block to construct one that does.


What is proper use of a True Random Number Generator? Let's say I have a true random number generator TRNG. Random numbers are generated on demand from a HW-entropy source, resulting in a 32-bit random value each time it is called.

I have to fill an array of 10 Bytes (=10*8 bits= 80 bits) with random numbers. Can I make a first call to TRNG, take the fist byte, the second, the third and the fourth to fill my array, and then call again...

Or should I call a new random number for each byte and throw away the non used bytes?

I would say the first approach is correct, but there is a slight issue with random number quality in my project and I want to be sure - maybe I'm completely wrong...

I assume your TRNG has a uniform distribution and can generate all possible 32bit numbers (ie. isn't limited to a specific smaller number range, just to [0,2^32-1]).

In this case, it doesn't really matter, because the TRNG output is also a stream of truly random single bits, as well as a stream of truly random 2bit pairs (numbers 0-3), etc.
If this were not true, ie. your 32bit numbers are uniformly random but the single bits are not, it wouldn't be possible: Take the first 32bit number, then see what bits it has, and you already have information about some bits of the next numbers, meaning the full number isn't ranodm either.

So, if you take just a part of one 32bit dataset, it doesn't mean that the rest is less random anymore. Just use the rest too.


Proving that an encryption scheme is susceptible to certain attacks I'm currently trying to prove the following:

Where p is a prime number of cryptographic size, prove that:

e(m) = am + b (mod p) where a and b are private is open to a known plaintext attack
e(m) = am + b (mod p) where a, b, and p are private is open to a known plaintext attack
e(m1,m2) = $
\left[
  \begin{array}{ c c }
     m1 & m2
  \end{array} \right]
$ $\left[
  \begin{array}{ c c }
     a & b \\
     c & d
  \end{array} \right]
$ +
$
\left[
  \begin{array}{ c c }
     e & f
  \end{array} \right]
$ mod p

where a,b,c,d,e,f are private and m1 and m2 are two parts of a message is open to a chosen plaintext attack.

I think I've figured out the answer for the first one (it's an affine cipher with variable values for the modulus instead of 26, if the adversary Eve has 2 samples of plaintext-ciphertext pairs then it's not too hard to prove that she can find the decryption function which allows her to decode the entire message).

I'm having trouble with the last two however. With the 2nd one, how will having a few samples of plaintext-ciphertext pairs help Eve find out p? With the 3rd one, I'm not seeing how her ability to choose particular plaintext and finding out their corresponding ciphertext helps her find out how to decrypt the message.

Any guidance would be highly appreciated.

how will having a few samples of plaintext-ciphertext pairs help Eve find out p [in the second scheme]?

Well, suppose we have four plaintext/ciphertext pairs, and lets look at what is available to the attacker.  We make the plaintexts $m_1$, $m_2$, $m_3$, $m_4$, and the corresponding ciphertexts:

$$e_1 = a m_1 + b + k_1 p$$
$$e_2 = a m_2 + b + k_2 p$$
$$e_3 = a m_3 + b + k_3 p$$
$$e_4 = a m_4 + b + k_4 p$$

for unknown values $a$, $b$, $p$, and $k_1, k_2, k_3, k_4$.

First step: can we combine these ciphertexts in a way to form three values that do not involve the unknown $b$ values?  Hint: consider $e_1 - e_2$.

Second step: can we combine the values from step 1 in a way to form two values that are both multiplies of $p$?

Third step: given two values which are multiples of $p$, what's an efficient way to recover $p$?

  With the 3rd one, I'm not seeing how her ability to choose particular plaintext and finding out their corresponding ciphertext helps her find out how to decrypt the message.

Suppose you ask for the encryptions of the values $(x,w), (y,w), (z,w)$; how could we use the previous observation to recover $p$?  (Hint: you might find it a bit easier if you assume a few more chosen texts).


Length Regular and Length Preserving What does it mean to say a function is length regular and Length preserving? Does any one of them implies the other? Example if any could be useful

Length-regular: if $x$ and $y$ have the same length, then $f(x)$ and $f(y)$ have the same length.
Length-preserving: $x$ and $f(x)$ have the same length.
Examples:

$f(x) = \overline{x}$ (flip every bit in $x$): length-preserving.
$f(x) = x \|x$ (concatenate $x$ with itself): length-regular but not length-preserving.


Pseudorandom function or not? I've read Intro to Modern Cryptography PRF section (and example 3.26) and on stackexchange(1, 2), but I still don't fully know how to prove it (with probabilities)

To prove it's a PRF, I know you have to prove that no adversary can distinguish $F'_k(x)$ from a random function or I show a possible attack. So the question is (similar to 3.10 from book):

  Let F be a length-preserving pseudorandom function. Prove $F'_k(x): \{0, 1\}^{n} → \{0,1\}^{2n}$ such that $F'_k(x) = F_k(0^{n})||F_k(x) $ is a $F'_k(x)$ keyed pseudorandom function or not. Where || denotes concatenation.

What I've done so far: No. Consider an adversary A that input $r \in \{0, 1\}^{n}$, it returns 1 if its first n bits are 0...0. On a truly random string it returns 1 with prob $2^{-n}$. On a pseduorandom string it returns 1 with probability 1. Then adversary has advantage $1 - 2^{-n}$ which violates the definition of psuedorandomness (as it's no longer < negligible?).
1. I believe this is correct, or what have I not understood correctly?
2. If it is the case, I am having trouble applying this to $F'_k(x) = F_k(x)||F_k(\bar x) $ on a paper I found here, example 3.7.2. It says No, but I'm having trouble connecting it with the method I learnt in class, but it looks random to me. I would say it returns 1 if its last bits?? I'm not entirely sure.

There are actually two different ways to do this, I will give hints for both, with additional hints in the spoilers:

First approach: Think about the definition of the security game again, and how many queries can a distinguisher make to the oracle?

   You can query the function on two values. If you compare those two results, are there similarities? And how would a truly random function behave?

Second approach: As others have stated in the comments, what happens if you query $F_k'(0^n)$?

   Since $F_k(0^n)$ is a PRF, you can just assume that this one is actually a truly random function. What happens if you query a truly random function twice? Is that visible in some way in $F_k'(0^n)$?

From your last comment, I guess this isn't clear yet: The distinguisher can query the function for any kind of $x$, as often as he wants - with the limitation of being a polynomial time algorithm. And he has to find out whether the results he gets back are from a truly random function or from $F_k'(.)$, with just $k$ being drawn randomly. So the distinguisher can only do one thing: Choose $x$ in a clever way, so that some structure appears within one result or over several results, if it is $F_k'$ - and the random function does not have that.


NTRU homomorphic rerandomization I am currently implementing NTRU, keeping its homomorphic properties. I want to implement rerandomization like this:

Encryption: $e = pr * h + m \pmod q$
Rerandomization: $e = e + pr \pmod q$ (using a new random $r$)
Decryption is as described in the original NTRU paper.

The first few rerandomizations work just fine, but after some iterations I am not able to decrypt it anymore. What am I missing in my formula?

The decryption error occurs for the following reason.

In a classical NTRU decryption you compute

$c = e * f \pmod q \pmod p \\
\ \  = p r*h*f + m*f \pmod q \pmod p\\
\ \  = p r*g + m*f \pmod q \pmod p$

By construction $f = 1 \bmod p$. Therefore, if the all the coefficients of $(p r*g + m*f)$ are within the interval of $0$ and $q-1$, (or $-q/2$ and $q/2$, depending on how you define mod operation. Then you will have $c = m \bmod p$. On the other hand
if any coefficient is not within the interval, $\bmod q$   will cause a wraparound since in this case:

$p r*g + m*f \pmod q \pmod p \neq p r*g + m*f \pmod p
$

The current parameters for NTRU ensures that this wraparound does not happen
except for negligible probability, say $2^{-128}$, etc.

Now back to your re-randomization process, suppose

$e_1 = pr_1*h+m$ and $e_2 = e_1+pr_2$

When decrypting $e_2$, you will have

$c = e_2 * f \pmod q \pmod p \\
\ \ = p (r_1 +r_2)*h*f + m*f \pmod q \pmod p \\
\ \ =  p (r_1+r_2)*g + m*f \pmod q \pmod p
$

As you can see, you have grown the $r$ term and therefore you increase the
decryption error probability. You probably will be fine with a few re-randomizations since adding only a few of $r_i$ doesn't increase the $r$ term much. But eventually you will see a decryption error by repeatedly re-randomization.


Why use randomness in digital signature algorithms? I understand why randomness has to be employed in encryption, because deterministic ciphers are not IND-CPA. I don't understand why digital signature schemes that employ randomness, like RSA-PSS, are any better than purely deterministic ones like RSA-FDH. Isn't it still likely that RSA-FDH is EUF-CMA?

Acronyms:

IND-CPA: indistinguishable under chosen plaintext attack
RSA-FDH: Hash the message, then apply textbook RSA
RSA-PSS: Another RSA variant
EUF-CMA: Existentially unforgeable under (adaptive) chosen message attack

The main benefit of adding randomness in RSA signature padding is that it simplifies and strengthens security arguments. At least that's claimed by PKCS#1v2, paragraph above 8.1.1 (emphasis mine)

  RSASSA-PSS is different from other RSA-based signature schemes in that it is probabilistic rather than deterministic, incorporating a randomly generated salt value. The salt value enhances the security of the scheme by affording a “tighter” security proof than deterministic alternatives such as Full Domain Hashing (FDH); see [Mihir Bellare and Phillip Rogaway: The Exact Security of Digital Signatures-How to Sign with RSA and Rabin (in proceedings of Eurocrypt 1996)] for discussion. However, the randomness is not critical to security. In situations where random generation is not possible, a fixed value or a sequence number could be employed instead, with the resulting provable security similar to that of FDH [Jean-Sébastien Coron: On the Exact Security of Full Domain Hashing (in proceedings of Crypto 2000)].

De-randomization can be used to turn a randomized signature scheme (such as RSASSA-PSS of PKCS#1v2 parameterized with significant random salt) into a deterministic one: we use some CSPRNG seeded with the (hash of the) message to be signed instead of true randomness, essentially transforming the scheme into a deterministic one (similar to deterministic RSA-FDH), with a security proof. The weakness in that simple argument is that an adversary that hypothetically could get benefit of some characteristic the random portion may have, can now try messages until finding one with the corresponding pseudo-randomness having that characteristic, then obtain a signature; so quantitative security bounds on the number of signature queries (rather than any kind of oracle queries) necessary to make a forgery is not as good as with the original randomized scheme.

Update following comment: in the above I'm considering a truly secure CSPRNG, but one that is known to the attacker, which can thus run it without querying the signature-producing device/oracle. That conceivably could matter: a real-life attacker might have a low and hard limit on the number of signatures for chosen message she can obtain from a remote server, but can run the CSPRNG (and whatever other computation involving the public key) at high speed with her own CPUs.

Note: My answer above is at the hand-waving level, with no proof, rather than a precise comparison of the security of RSA-PSS and RSA-FDH for stated security criteria and hypothesis on RSA; which is complex.

While some fault-based attack (like Dan Boneh, Richard A. DeMillo, Richard J. Lipton's On the Importance of Checking Cryptographic Protocols for Faults, in proceedings of EuroCrypt 1997) indeed are blocked by a randomized message, this is an a posteriori rationalization; such attacks should be blocked by independently checking any signature produced against the public key before it is output.

Randomized rather than deterministic padding has an influence for side-channel attacks, but it is debatable that randomizing improves security; when doing some DPA attacks, a known random input is often the ideal setup (note that the padded message gets known to the adversary in any RSA signature scheme).


RSA public key recovery from signatures Is it possible (how) to recover public (512 bit long) RSA key from multiple signatures having corresponding plain texts. Padding is not randomized.
I need it to verify any future message comming from the same source.

Suppose you have two message-signature pairs, $(m_1, s_1), (m_2, s_2)$, where $s_i = m_i^d \bmod n$. Suppose we also know the public exponent $e$—it is usually $65537$, $3$, $5$, $17$, or some similar small integer. Then we know that $m_i = s_i^e \bmod n$, or in other words $s_i^e = k_in + m_i$ and it follows that $\gcd(s_1^e - m_1, s_2^e - m_2) = \gcd(k_1, k_2)n$, where $\gcd(k_1, k_2)$ is expected to be small.


Key collision in scrypt and hkdf I am developing a mostly-offline authorization system that authorizes a user using an deterministically generated AuthKey derived from a MasterKey derived from a high-entropy chunk of data (128 bits) and a low entropy data (for example, an email address).
The total length of the concatenated data will never be more than dkLen (256, either by hashing the low entropy data using md5 or using padding), and AuthKey will be used in order to generate a ECC asymmetric pair.

MasterKey = KDF ( HighEntropy, LowEntropy )
AuthKey = KDF ( MasterKey, keynumber )

For this purpose, and in order to avoid bruteforce I am considering using hkdf or scrypt.
My primary concerns are:

Are there considerable chances of key collision?

I know that just with the 128 bits of entropy there are 3.4028237e+38 combinations, even more with the low entropy data.
Still, provided that no one used the same LowEntropy value, and considering:

dkLen=LowEntropy.length+HighEntropy.length

Is It possible for two different AuthKeys to collide?
¿After applying a KDF to the 256 bits of data, and getting 256 bits of data, will the chance of collision be reduced or increased?

Is there any reason, given the previously exposed model, to choose HKDF over scrypt?

As far as I have read scrypt requires more resources and therefore is more costly to bruteforce, a recent question suggests that

Don't ask the user for memory/cpu factors, you don't need them if the input is high entropy. You don't need a salt either.

The thing is I want HighEntropy and LowEntropy to be a headache to bruteforce, if possible, even in a long-term post-quantum cryptography futuristic enviroment.

Also, is there any reason for the either the highentropy or the lowentropy data to be used specifically as key or hash?

No, you don't have to worry about collisions.

As long as no pair of users have the same LowEntropy input, they will receive different MasterKeys.  If the MasterKey is different, then the AuthKey will be different.  Even if you use the same MasterKey to generate multiple AuthKeys, you don't need to worry about collisions: as long as the keynumber values are different, the derived AuthKeys will be different, too.

You don't need to use scrypt if you are using a 128-bit crypto key (assuming the crypto key is kept secret and not revealed to others).

I don't understand what you are asking when you talk about using multiple times the same ECC key.  I think you should post about that separately, as it sounds like a separate question.  (On this site, we want you to post one question per question; if you have multiple different questions, please post them separately.
  Don't forget to read the FAQ.)


Is it possible to recover the seed value from a Mersenne Twister PRNG state? So I know that you can recover the state of a mersenne twister generator by observing a sequence which is long enough.

I was wondering if you could be able to recover the actual seed value used or if an attempt would yield an equivalent at best?

Also, closely related, let's say we use a 32-bit seed value. Does this mean that a mersenne twister generator could yield $2^{32}$ different sequences for each unique seed value or are there seeds which produce the same sequence?

I was wondering if you could be able to recover the actual seed value used or if an attempt would yield an equivalent at best?

Yes (and it turns out to be not that expensive computationally).

The Mersenne twister state is an invertible linear function of the seed, hence recovering the unique seed is possible.

  Also, closely related, let's say we use a 32-bit seed value. Does this mean that a mersenne twister generator could yield $2^{32}$ different sequences for each unique seed value or are there seeds which produce the same sequence?

Every seed will generate a unique sequence.  This is a stronger statement than what I just previously made (it would be conceivable that two different states would generate the same sequence - however, that doesn't happen with Mersenne).


How to analyze the off-by-one error's impact on the entropy of the result? I'm reading Jean-Philippe Aumasson's book Serious Cryptography to learn more about cryptography. On page 37, the author gives an example of Cryptocat's off-by-one error in its PRNG implementation in 2013, as shown below:

Cryptocat.random = function() {
    var x, o = '';
    while (o.length < 16) {
        x = state.getBytes(1);
        if (x[0] <= 250) {
            o += x[0] % 10;
        }
    } return parseFloat('0.' + o)
}

The off-by-one error is found in the IF condition clause which uses <= rather than <. The author states that the values generated had an entropy of 45 instead of approximately 53 bits.

I'm wondering how the entropy of 45 bits is calculated.

In fact, if the code uses <, then everything is all right: the probability of a decimal digit is equally 1/10. Thus the entropy of 16 decimal digits would be 16*10*1/10*log(10, 2) = 53.1508.

However, in the case of the above-flawed code, the probability of decimal 0 is 26/251, and the probability of each other value is 25/251. Thus, the entropy of 16 decimal digits would be 16*(26/251*log(251/26, 2) + 9*25/251*log(251/25, 2)) = 53.149.

I don't any clues on how to get the 45 bits entropy. Can anyone help me, please?

References:

https://tobtu.com/decryptocat.php
https://nakedsecurity.sophos.com/2013/07/09/anatomy-of-a-pseudorandom-number-generator-visualising-cryptocats-buggy-prng/

First of all the first Entropy calculation is not correct. Recall the definition of (Shannon) entropy:

$$H(X) = -\sum_{i=1}^n {\mathrm{P}(x_i) \log_{\,b} \mathrm{P}(x_i)}$$

If uniformly chosen a digits entropy is

$$H(X) = -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 3.3219280...$$

Case $<250$ with 16 digits;

\begin{align}
H_1(X) &= 16 \cdot - \sum_{i=1}^{10}{\frac{1}{10} \log_2\left(\frac{1}{10}\right)}\\
H_1(X) &= 16 \cdot 10 \cdot -\frac{1}{10} \log_2\left(\frac{1}{10}\right) = 53.15084951...\\
\end{align}

See the calculation at Wolfram Alpha
Case $\leq250$ with 16 digits;

$$H_2(X) = 16 \cdot - \left( \frac{26}{251} \cdot \log_2\left(\frac{26}{251}\right)+9 \cdot \frac{25}{251} \cdot
\log_2\left(\frac{25}{251}\right) \right) = 53.14921795...$$

See the calculation at Wolfram Alpha

It seems this is a mistake in the book. The current errata doesn't include this.

The difference is tiny but can make a difference since 0 will occur more and that is distinguishable. For example, take a 1.000.000 sample occurrence of 0 is around  103,500 – approximately 10.36%.

For the visualization of the difference read this nice blog Anatomy of a pseudorandom number generator – visualizing Cryptocat’s buggy PRNG


Where can I find NTRU test vectors? In some research work in 2001, it is stated that test vectors were not publicly available at the time. Then in this ESSS1v2 standard under IEEE1363 here , the appendix B mentions that the test vectors will be added in future versions. I haven't found any. Where could I get the test vectors for NTRU?

The most recent version of the paper indeed seems to be:

Efficient Embedded Security Standards (EESS)
EESS #1: Implementation Aspects of NTRUEncrypt and NTRUSign
Consortium for Efficient Embedded Security
June 20 th , 2003
Version 2.0

(PDF download)

Yet, as you stated, that doesn’t contain any test vectors; just like the previous (v1) paper:

  Appendix B - Test Vectors

  [To be added in future versions]

But you can find test vectors when checking implementations. For example, by looking at the files contained in the directory https://github.com/Yawning/ntru/blob/master/testvectors/

Alternatively, you could take a look at the files contained in the NTRUOpenSourceProject directory https://github.com/NTRUOpenSourceProject/ntru-crypto/tree/master/reference-code/Java/Encrypt/com/securityinnovation/testvectors/ (see NtruEncryptTestVector.java file)