Zero knowledge proof for sign of message value I am using ElGamal encryption to encrypt an integer message $m$ as,

$E[m]$ = ($g^x$, $g^m.h^x$)

Can I write a zero-knowledge proof to prove to a verifier that $m > 0$ ?

I can create the bit representation of $m$ and encrypt each bit to prove this, but I have a lot of integers and am trying to avoid this approach.

What you are looking for is called a range proof. There has been a vast body of research on the topic recently - so vast, in fact, that it can be quite hard to know what is the state of the art, and what solution is the most appropriate in a given situation. Therefore, to let you evaluate by yourself what might best suit your exact situation, I'll attempt at providing a quick survey of the existing methods and their constraints.

The most natural method is the naive method that you mentioned: commit to the bits $(m_i)_{i\leq \log q/2}$ of the plaintext $m$, prove that $\sum m_i 2^i = m$ and that $m_i(1-m_i)=0$ for every $i$ (id est, each $m_i$ is a bit). Unfortunately, this takes $O(\log q)$ group elements, hence it is very costly. An improvement to this naive method has been suggested in this article. The idea is the following: rather than decomposing $m$ in base 2, decompose it in base $B$. You now simply need to commit to the $\log_B(q/2)$ elements $m_i$ of the decomposition in base $B$. To prove efficiently (in constant time) that $m_i \in \{0, \cdots, B-1\}$, the idea is to let the verifier add signatures of the integers $0, \cdots, B-1$ to the public key, and to use known methods to let the prover show that he can produce a signature for the committed value. As he cannot forge a signature for any value outside $\{0, \cdots, B-1\}$, it is sufficient to complete the proof. This gives you a proof which communicates $O(\log q / \log \log q)$ group elements, but it has a downside: it requires to use an elliptic curve with an appropriate pairing operation, as such a pairing is required for the signature part. The constant in this $O()$ has been improved in this article.

Now, you might also be fine with a proof that does not hold for arbitrary provers, but only for computationally bounded provers - it won't make much difference in practice. This is called a zero-knowledge argument, and there are more efficient methods in this case. The one I will describe is not explicitely mentioned in an article, but is a natural consequence of a serie of works by Groth and Bayer (and can therefore be seen as folklore). The core idea is that one can commit to many numbers at once using a scheme called "generalized Pedersen commitment scheme": the public key contains $n+1$ random group elements, and to commit to $n$ values $(a_1, \cdots, a_n)$ with random coin $r$, compute $c = h^r\cdot \prod_i g_i^{a_i}$. This is perfectly hiding, and computationally binding under the discrete logarithm assumption.

To prove that $m$ is in $[0,q/2]$, decompose $m$ in base 2: $m = \sum_i m_i2^i$. Group these bits by packs of $\sqrt{\log q}$ consecutive bits (you'll have $O(\sqrt{\log q})$ such packs). Commit to each pack, with a single group element per pack, using the generalized Pedersen scheme. Now, perform a batch product proof to show that all the committed values are bits (ie, they satisfy $m_i^2-m_i = 0$). This kind of batch proofs are non-trivial, but have been studied in detail in e.g. this article. Essentially, they are all constructed by carefully and repeatedly applying the Schwartz-Zippel Lemma, which is used to say (informally) that if someone knowns a random linear combination of some values, he must know all the values. Applying this lemma allows to shrink the dimensions of the problem.

The prover must also prove that $m = \sum_i m_i 2^i$; the previously mentioned article also shows how such proofs can be constructed. The techniques developed essentially allow to perform an efficient (batched) proof for any statement over committed values that can be expressed with linear algebra, see this article. Overall, this gives you a range proofs with a communication of $O(\sqrt{\log q})$ group elements. It involves many rounds (I'd say 7 to 9), but can be made non-interactive if you are fine with using the Fiat-Shamir transform, which is secure in the random oracle model (hence only "heuristically secure").

If you want an even shorter proof, then you can consider again using an elliptic curve with a pairing, to use the improved version of the above method: this article does essentially what I described above, but gains additional efficiency by using a pairing, which allows (informally) to commit to commitments, hence to get one more level of "packing". It gives a protocol which communicates $O(\log^{1/3}q)$ group elements.

And finally... You can have a proof of constant size. But then, you must rely on a completely different method: first, commit to $m$ in a group of unknown order, and prove that you've committed the same value in two different groups, using for example this article. To have such a group, the usual method is to have an RSA modulus $N = pq$, product of two safe primes, and to take a generator of the group of squares, whose order $\phi(N)/2$ is unknown unless one can factor $N$. Note that this means that the constant will be large: factorization-based methods need very large groups (say, $|N| = 2048$). This is therefore suitable for range proofs on large intervals. The trick is the following: by a theorem from Lagrange, an integer is positive if and only if it can be decomposed as a sum of four squares. Therefore, one simply commits to the elements of this decomposition (which can be efficiently computed) and prove that the sum of their squares is $m$. The group of unknown order is required to ensure that we indeed work over the integers: the prover cannot perform modulo reductions if he does not know the modulus. This method was described in this article, and improved several time. To my knowledge, the most efficient constructions of constant size range proofs are given in this article, which is one of my recent works. In particular, we review the existing optimized range proofs and give new constructions, while weakening the necessary security assumptions.

To choose an appropriate scheme is now up to you, depending on the following:

Are you willing to use an elliptic curve with pairings?
Are you Ok with using the random oracle model to get less interactive arguments?
Would you be fine with using additional assumptions, and a group of unknown order, which might require an additional setup phase?
How many range proofs will you have to perform? Range proofs can be batched: using a combination of this article and my article allows to perform $M$ range proofs simultaneously, incurring only a $\sqrt{M}$ overhead. As you seem to have many such range proof to perform, it would probably be better to perform a global batched range proofs.
What is the exact size of the intervals you will have? (having $q$ of size 256 bit, if using elliptic curves, or, say, 1024 bits if using subgroups of prime order fields, can change the appropriate method)

I do not provide detailed explanations of the methods in my answer, it would be too long; you can either refer to the articles I've included, or ask for precisions on a particular method if one of them seems to suit your requirements.


Why do we encrypt-then mac but sign-then-encrypt? This question was asked in comments on my answer to should we sign then encrypt or encrypt then sign. I think posing the question as a separate entity is best, so:

The general advice for applying MACs seems to be that we should encrypt first, then MAC. However, the general advice for signatures appears to be diammetrically opposed.

Why is this the case? Aren't these the same ideas? If so why are they so opposite.

I have answered this myself but feel free to improve upon this answer.

Okay. So first up, let's eliminate encrypt-then-sign. Why is this a problem? The idea behind a signature is to prove that a message came from me even in the presence of malicious actors. If a malicious actor changes the ciphertext under the signature, clearly this invalidates the signature as per expectations, however, that is only one possible attack scenario. The other is that the attacker could claim ownership of a message simply by stripping off the existing signature and adding their own - this is trivial, since the ciphertext (not the plaintext) is signed.
So relying on the signature to identify the recipient in this case could be fatal. D.W. gives an example of this in his/her answer.
The alternative approach to this is sign then encrypt. Clearly a malicious adversary cannot modify this in flight, but again the purpose of the signatures is to indisputedly identify the sender. A malicious recipient could forward the signed plaintext encrypted and it would appear to come from the original sender, defeating the goal of signatures.
D.W. gives one approach for resolving the issue. Others are sign-encrypt-sign, encrypt-sign-encrypt etc.
In the MAC case, our goal is different. We want to know whether or not the ciphertext has been modified on the wire or not, and whether or not we should decrypt it (to prevent the creation of an oracle, for example) or reject it as corrupted. We are not attempting to identify who the plaintext came from, simply that it has not been modified in flight.
So you might ask, okay, what happens if an attacker strip off a MAC block from a ciphertext and replace it with their own? Since we have exchanged MAC keys and we assume these keys are still secure, the recipient will identify an invalid ciphertext and reject it.
It is also worth reviewing Thomas' answer for some additional items. Specifically, not all cryptographers agree that encrypt-then-mac is the most ideal approach.
Secondly, Thomas highlights that MACs provide automatic protection against chosen ciphertext attacks. D.W. has recommended in his/her answer that an IND-CCA2 cipher should be used - that is, one provably secure under adaptive chosen ciphertext attacks.
Although it is not entirely accurate, I would say that the requirement for MACs and IND-CCA2 to defeat chosen ciphertext attacks is a closer parallel than comparing MACs and Signatures, although at first glance it looks like MACs and signatures are doing the same thing.


Securely "forwarding" a Large message in a hybrid encryption system without sending the actual message Alice has symmetrically encrypted the large (100Mb) MessageA with a random key K1, and then asymmetrically encrypted K1 with Bobs public key. She then stores the encrypted large message in a central and public repository and sends Bob's key to him.

Can Bob then decrypt the key K1 with his private key and then encrypt the key K1 again with Charles' public key, and send the resulting key to Charles - Giving Charles the ability to decrypt MessageA in the central repository?

I'm looking for a cryptographic approach to giving multiple users access to the same data without having to massage the actual data. (A gives to B, B gives to C and E, etc). Are there mechanisms for revocation?

One common way is securely sending the encryption key for each user with their public key and store the encrypted data on somewhere where each user can access.

You can do this with RSA-KEM with using RSAES-OAEP padding and any Authenticated Encryption like AES-GCM;

The Distributer;

First generate a random encrption key $k$ for AES-128,192,or 256
Encrypt the message with AES-GCM genenerate an $IV$ and $$(IV,ciphertext,tag) = \operatorname{AES-GCM-Enc}(IV,message, k)$$
Upload $(IV,ciphertext,tag)$
For each user send a message with $\operatorname{RSAES-OAEP}(pk_{user},k)$ using their public key.

The receivers;

To get $k$, They are using their private key ,$$k = \operatorname{RSAES-OAEP}(priv_{user},k)$$
Decrypts the message with AES-GCM $$message = \operatorname{AES-GCM-Dec}(IV,ciphertext,tag, k)$$

This Key Encapsulation Mechanism (KEM) together with Data Encapsulation Mechanism (DEM) provides the standard of IND-CCA2/NM-CCA2 — ciphertext indistinguishability and non-malleability under adaptive chosen-ciphertext attack.

Note 1: The above described modified the RSA-KEM since the original RSA-KEM for multiple users will fall into Håstad's broadcast attack. Instead, using RSAES-OAEP makes it safe for multiple recipients with the same $k$ encrypted for different recipients as PGP/GPG.


Is there a cryptographic solution for this “dating protocol”? The article Cryptographic Protocols with Everyday Objects by James Heather, Steve Schneider, and Vanessa Teague describes the following dating protocol (due to Bert den Boer):

  Alice and Bob wish to determine
  whether they both want to go on a date; but they want to avoid the embarrassing
  situation in which one of them does not want to go on a date, but knows that the
  other would have liked to do so. Essentially they need a two-player veto protocol:
  they want to compute whether at least one has vetoed the date, without revealing
  any further information.

Q: Bennett’s solution uses playing cards. Does this problem admits cryptographic solution?

Of course it can be reduced to Yao's Millionaires' Problem. But probably this problem has a simpler solution.

You can use a protocol solving the Socialist millionaires problem for this. Socialist millionaires compares two integers for equality. There are relatively simple implementations of this protocol, similar to Diffie-Hellman, which are used to implement PAKE (password authenticated key-exchange).

Agree a fixed integer to denote true. A party chooses that value if they want to signal true and a random other value (say 256-bits) if they want to signal false. This clearly works for the case where at least one party chooses true. If both parties choose false it will almost certainly produce a not-equal result from SM, since the chance of two random values being equal is negligible.

Thus you can securely implement the AND function using a Socialist millionaires protocol.


In theory, are there algorithms where everybody can read a message but only one person can write it? I know that there are a lot of asymmetric algorithms out there that use the public key to encrypt and the private key to decrypt. I was thinking about having exactly the opposite.

I do also know that the current way of doing it is sending it in plaintext and adding a signature to verify that its coming from the correct sender. But for me it sounds like it is just some sort of "overhead" with an additional signature to check and transmit.

In my mind it would be cool to say: If you can decrypt it, it is the right sender and if you can't, someone must have altered it / is not trustworthy.

If there isn't such thing, why is that exactly?
Because the signature "method" is the way to go?

If you can decrypt it, it is the right sender and if you can't, someone must have altered it / is not trustworthy.

Then by definition what you're looking for is called a signature. You're asking for something which is a signature, but is not called a signature. Sorry, there's no such thing. A signature is called a signature. And verifying a signature is called verification, not decryption.

It's not that “the signature method is the way to go”. It's that the properties you want are that of a signature. Therefore, anything that does what you want is a signature.


Trustless, Two-Party Random Number Generation I've been having trouble with coming up with a random number generator that produces a random number between two parties. My current scheme is this:

User 1 gives user 2 the hash of their randomly generated seed, user 2 responds with their unhashed seed. User 1 generates the random number by feeding his own unhashed seed and user 2's seed into a seeded RNG. User 1 discloses the resulting random number and discloses his own seed. User 2 accepts the outcome if the seed matches the hash and seeded RNG produces the same.

I'm not too good with the cryptography behind this but is this safe? Is it okay to just make the RNG seed by just appending one seed to the other? Is there any specific RNG I should use?

Why should user 1 disclose the resulting random number in addition to disclosing his own seed,

when user 2 can compute the resulting random number from the two seeds?

That might be safe enough, but it's far from secure.

For one thing, each user obtains user obtains proof that the "random number" is only pseudorandom.

For another thing, one would need to hope that the RNG still works well when one half of its

seed is chosen  in a way that adversarially depends on the hash of the other half of its seed.

A simple, somewhat good way is the following:
User 1 gives user 2 a commitment to a random string whose length is equal to the RNG's seed length.

User 2 gives user 1 a random string whose length is equal to the RNG's seed length.

User 1 sends User 2 the opening of the commitment, and both users

feed the xor of the two allegedly random strings into the RNG.

A secure way is the following:
User 1 gives user 2 a commitment to a random string whose length is equal to the output length,

and a zero-knowledge argument of knowledge of how to open the commitment.

User 2 gives user 1 a random string whose length is equal to the output length.

User 1 gives user 2 the value that was committed to (but not the opening information!),

and a zero-knowledge argument of knowledge of how to open the commitment to that value.

Both users output the xor of the two allegedly random strings.


How is digital signature different from a message authentication code (MAC)? I know the definitions of both but can't specifically tell how they are different and if one is better than the other.
Please help.

The main functional difference is that anyone able to verify a Message Authentication Code is also able to forge one, because the same key is used for both tasks; whereas someone with the public key can verify a digital signature, but can't forge one.

Contrary to a MAC, digital signature is thus usable in contexts where the verifier is not trusted, which is of tremendous practical value. There's a price to pay for that: a digital signature is significantly larger, and slower to generate and/or verify, than a MAC is.


Is using a rolling code as a constantly-changing shared secret effective for signing? I am your average developer looking for some crypto-related guidance.

I am trying to have assurance that a received message is from a particular sender, but have no need for the message content to be encrypted. The sender and receiver are allowed a one-time secure channel to establish a shared secret. I don't want to use a full-on crypto library for message signing because my target audience for the receivers includes websites running on low-end shared hosting where access to such libraries won't always be available. I'm wondering if only needing message signing and allowing a pre-shared secret sufficiently simplifies the problem to where it can be pulled off safely in my own code.

A method I've seen to do this is to simply append the shared secret to the message, apply a hash function to the message+secret, and send the hash function's output along with the message as its signature. That's fine I think except that it would be subject to replay attacks, which is problematic for my application.

If instead of using a static shared secret I used the one-time secure channel to seed a PRNG on both ends, appended the PRNG's current output to each message as input to the hash function, and advanced the PRNG on both ends following each verified communication, would this potentially be effective? I understand there's also a need to make intelligent choices about the hash function and PRNG used, but first of all does this high-level approach have any fatal flaws I can't appreciate as an average-joe developer?

Edit

Since there's been an enthusiastic continued response, let me share a bit more. First, I don't need to be convinced of the benefits of an asymmetric key solution, the problem as I've tried to convey is short of implementing one myself in a scripting language, I simply will not have access to OpenSSL/OpenSSH/GNUPG or anything else capable of using public/private keys on 100% of the systems where this needs to run. I am guaranteed to have SHA-256 and other hashing algorithms and HMAC on 100% of the systems where this needs to run.

The application is as a messaging system between websites running Drupal and another similar content management system and the CMS organization's servers, in order to give the organization a means to push official security updates to sites. Full details: https://github.com/mbaynton/cms-autoupdate-design. FWIW, I do plan to ship the security code changes themselves with an OpenSSL signature, but it will only benefit the sites where the administrators have made OpenSSL available to php. The MAC is basically the fallback so sites without OpenSSL still have some assurance of authenticity of the update package. This in and of itself would substantially diminish the value of the shared secret database were it to be compromised...you'd potentially be able to impact such a minority of sites that you'd almost be wasting your time trying.

Solutions that require a pre-shared key are pretty commonplace for this kind of inter-server web service application, I'll cite http://docs.aws.amazon.com/general/latest/gr/signing_aws_api_requests.html. Doing exactly this might be an even better idea...

I'm confused at your suggestion that your clients would not have access to a public key signature facility, given that you assume that they have crypto hashes and can run code of your authorship.  More generally, the fact that you're trying to roll your own crypto doesn't bode well.

Also, I'd suggest that you have a hard look at the challenges implied by your idea of using a "one-time secure channel" to establish shared keys with your users.  What happens, for example, when one of your users tells you that their key has been compromised?  Invalidating your own copy of that key is easy, but now you need the (supposedly "one-time") secure channel once more to establish a new one.  What's the cost and inconvenience of that?

Or even worse, imagine the case where your database of pre-shared secret keys gets compromised.  You then have to establish a new shared key with every single one of your users, all at once.  Ouch.

Compare this to, say, the way GitHub uses public-key cryptography to manage access to users' repositories:

Users generate private/public key pairs on their own computer.
Users log in to the website using conventional user authentication mechanisms (e.g., passwords, security tokens, SMS, etc.)
Users can then upload public keys, or delete earlier ones that they'd uploaded.

Notice what you gain in this case:

"Self-service": users can add and delete keys at their leisure.  Now when your users' keys are compromised they just log in to your site, delete the compromised ones and upload new ones.
No secret keys are ever transmitted over the wire.  Which implies that you're never storing any secret keys on your side, so if your public key database is disclosed it's not a big deal.
You do need a user authentication system, but:

That can be outsourced (think of all those websites that allow you to log in with your Google or Facebook credentials);
Even if you built one in house, with strong user passwords and proper password storage then a compromise of your password database is would likely be much less damaging than a database of shared secret keys.

But to address your narrower questions, I'd make two observations.  First, your hash(message + secret) scheme is insecure.  Read up on HMAC, which is a standard and secure way of using a hash function as a message authentication code.

Second, you can avoid replay attacks by incorporating a counter into the message that you compute a MAC over.  No need for the random numbers; each client just keeps track of the most recent message number they received from the other party, and rejects messages numbered earlier than the most recent one.

A good MAC will be secure against forgeries.  An attacker who sees the messages and tags (but not the key) for...

tag[1] = HMAC(key, rand[1] + message[1])
       .
       .
       .
tag[n] = HMAC(key, rand[n] + message[n])

...will not be able to forge a valid

fake_tag = HMAC(key, rand[n+1] + fake_messsage)

even if they can predict rand[n+1].  The unpredictability of the RNG's output gains you nothing.  All you need is a way to spot replays—which a counter will do just fine.


How is a sponge construction better than cycling the output of a hash back to the input? Wikipedia has this diagram of a sponge construction.

Why is this better than just cycling the output to the input? Like this, assuming $p$ is a list of blocks that are equal to the size of $f()$, and $z$ is the corresponding output.

$$c_{-1} = 0\\
c_{n} = f(c_{n-1} \oplus p_{n})\\
z_{n} = f(z_{n-1})$$

Or in other words, why not have $r$ be the whole block?

why not have $r$ be the whole block?

Because you'd essentially have no security.

In the absorbing phase, the attacker could set the intermediate state to whatever he wants.  For example, if the current state is $c_{n-1}$ and the attacker wants the next state to be $t$, he computes $p_n = c_{n-1} \oplus f^{-1}(t)$; this allows a trivial preimage attack.  And, even if $f$ wasn't invertible, this would still allow a trivial second preimage attack.
In the squeezing phase, if the attacker knows the value $z_0$, he could trivially compute the rest of the hash $z_1, z_2, ...$


Do hash functions for digital signatures need to be preimage resistant? I understand that hash functions used for hashing a document or some data before signing it, needs to be collision resistant and 2nd pre-image resistance. Otherwise an adversary could "look" for two random documents with the same hash or for a second document, having the same hash as a given document, and just replace the "original document" with the "fake document", because then the signatures of the two documents are also the same.
However, I see no reason, why a hash function for signing documents needs to be preimage resistant, or is it indeed a superfluous property?

A hash function which isn't preimage resistent is also not collision resistance.
If I hash a large random message and apply the preimage algorithm I'm extremely unlikely to get the same message I started with, thus finding a collision.
Collision resistance is critical for a hash used in a signature. As you can create forged signatures. Even though you need a bit more in order to forge meaningful messages, such as exploiting internal state collision to make extensions collide and utilize formats like pdf or postscript.


Did Merkle invent cryptographic hashing? Chapter II of Merkle's 1979 PhD thesis is titled "One Way Hash Functions." The chapter appears to be the first reference to cryptographic hashing. The chapter has no references. Is there an earlier reference that I am not aware of?

I think the first paragraph of this document show be helpful.

The Rabin reference at the bottom of the text is from 1978, and the impression I get from p3 of this document is that he came up with a linear iterated hash function in that 1978 paper. So maybe Rabin invented it.

I think we can be pretty sure it was either Merkle, Rabin or Yuval (if you must choose one), but that sounds like an answer correct for a good deal of history questions in this field.

Alt link


Breaking Truncated Linear Congruential Generator with known parameters There is an elaborate discussion on the breaking of TLCG on the link below, where they show how to break the generator with known parameters given the most significant bits.
Problem with LLL reduction on truncated LCG schemes

I tried to apply the same principles when given the least significant bits but with no success. On the paper by Frieze et al they discuss it briefly and mention substituting *x = 2s0*x(1) + x(2)*  that helps a little bit but I cant figure out what the value of s0 is supposed  to be. Is the anyone who can help.?

According to the paper Freize et al, for the most significant bit case which is discussed at length in the link,the modulus M must be odd, the addend I assume can be any number between 1 and the modulus, and the increment must be zero. So given:
a*x(i) + b ~ mod M
M is odd
0 > a < M
b = 0

Because both a and $M$ are known n we obtain high order bits y(i). Then $x = y + z$
where $y$ is the high order bits $n$, $z$ is the lower order bits.
Lx ~ 0 mod M
Taking B the reduced basis of yields.
Bx ~ 0 mod M
Substituting x = y + z gives
B x + By ~ 0 mod M which yields the equation
Bx + By = km for an unknown vector k of integers.

From this point, its easy to find the lower order bits $z$. (see the link above)
In the case where we are give the lower significant bits $z$ instead of the higher bits $y$, the paper suggests substituting $x = 2(s0)* y + z$. And they talk about finding the inverse of $2(s0) \pmod M$ which is guaranteed to exist since M is odd.
But that's where I get completely lost.


Why are only lattice problems used in cryptography? There are thousands of NP-hard problems out there. Why have only lattice problems been applied to cryptography?

What makes a problem suitable for cryptography is slightly different than what makes a problem NP-hard.

What is required for cryptography is average-case hardness --- i.e., a randomly selected instance of a problem should be "hard" for an adversary to solve. However, random instances of some NP-hard problems (3SAT, e.g.) turn out to be easy with high probability.

Lattices are interesting as some of its average-case hard problems (ex. Shortest Integer Solution, SIS) allow a reduction to worst-case hard problems (ex. Shortest Independent Vector Problem, SIVP) --- i.e. solving a random instance of one problem is as hard as solving worst-case instance of another. No efficient quantum algorithms are known against these problems either.

Moreover, lattices have enough underlying algebraic structure which allows building cryptographic primitives (OWFs, Trapdoors, FHEs...) based on these hard problems --- see the survey by Peikert.


Can One-time-password be used as nonce in HMAC to prevent replay? Note: In the following post OTP = one-time-password

I am working on a project wherein I need send one way messages between two end points. There is already a shared secret via a side channel between the two end points. No user is not involved at either of the end points. Due to some constraints I don't have control whether or not encryption will be used when the message is actually send, so I have to assume the message is going over plain text. The reader can assume the messages as some sort of "action".

The packet carrying the message also contains HMAC of the message calculated using the shared key. I need to prevent replay attack. From wikipedia, I see the options being: OTP, nonce and time stamp.

I can only assume that the clocks between two end points are roughly synchronized (both end points have some reliable time source). I'm thinking of adding some kind of nonce when computing the HMAC. I want to ask whether the option I selected below would be correct for nonce. I want to use some standard technique. I do understand that nonce cannot be repeated.

My first question is that whether certain OTP values can be considered as nonce (the wikipedia categories make them appear distinct).

I found the TOTP algorithm which can calculate a one time password using a shared key and timestamp. I want to ask whether TOTP can be used as nonce.

TC = floor((unixtime(now) − unixtime(T0)) / TS),
TOTP = HOTP(SecretKey, TC),
TOTP-Value = TOTP mod 10d, where d is the desired number of digits of the one-time password.

TC will be stored in an unsigned 64 bit variable. Since HOTP is a hash function (assume SHA-256), TOTP won't repeat (until the unsigned 64 bit TC reaches its max value and wraps around). My second question is whether TOTP can be used as nonce when calculating HMAC ?

(Note: I think, In general OTP is usually understood as One-Time Pad. Here it means One-Time Password.)

Using an OTP as a nonce does not seem possible in general. An OTP doesn't necessarily always have to be distinct. Since there is some kind of synchronization between the communicating parties the OTP might repeat.

Specifically, say your OTP consists of randomish 64 bits. Then whenever you need a password it is fine if both parties derive 64 random bits independently of previous values.

If you need a nonce, however this gives you a decent collision probability after about a billion repetitions. (Due to the birthday bound.)

However, practically, most hash functions have good PRF properties and can be used to generate nonces.


Salted password with AES encryption I am encrypting a text file using AES 256 encryption. Does it add much to the security of the file’s contents to also add a salted password to the file? (I don’t believe it would add much) Can a salted password be added as part of the encryption process to make the encryption itself more secure? ( I don’t believe so - my understanding is that salting only makes the password more difficult to determine, not the encryption )

Passwords are not keys. Keys consist of a specific number of randomized bits. So to encrypt a file using a password (password based encryption or PBE) you first need to create a key from a password.

Password hashes or Password Based Key Derivation Functions are the schemes that consume a password, a salt, a work factor (or iteration count) and possibly other parameters (parallelism, memory usage) and then produce a key. Known PBKDFs are PBKDF2, bcrypt, scrypt and Argon2.

The salt is mainly used for two reasons: making sure that duplicate passwords do not derive the same key and avoiding rainbow table attacks. Producing the same key is not a big issue during encryption; you can use an IV to create a different ciphertext. Rainbow table attacks are more problematic: you can create a table with keys derived from passwords and try and decrypt: this would allow an attacker to test keys without minding the work factor.

As you can also derive an IV with a PBKDF you might as well use a salt. This would make PBE indeed more secure for the reasons stated above. So yes, you should use an up to date PBKDF such as Argon2, a strong password, a large work factor and - indeed - a salt during encryption.


How to correctly encrypt data with proper authentication using AES-256-CBC in php? I have been using the openssl function for encrypting data with AES-256-CBC in php. I have been able to encrypt it using an unique IV (by generating with openssl_random_pseudo_bytes)for each new encryption.

But I am struggling with the idea of authenticated encryption with aes cbc. How do I basically authenticate when I am about to decrypt the data?

Do I need to use something like PBKDF2, blowfish or hash_hmac()?

Do I need to hash the key somehow?

Any help is extremely appreciated.

Basically you would be constructing an AEAD scheme. You will need to perform HMAC over the IV, the ciphertext and possibly over additional associated data (AAD). If you just need to authenticate the ciphertext then you may simply leave out (or leave empty) the AAD - but not the IV during the HMAC function.

Fortunately somebody already thought about standardizing this, so you may simply copy this draft RFC called " Authenticated Encryption with AES-CBC and HMAC-SHA". Obviously having a draft RFC is less optimal than a full RFC with a lot of research, but at least it has undergone some evaluation. It basically formalizes something that already existed in the first place.

Notes:

The RFC seems to have been written with TLS 1.3 in mind, but as TLS 1.3 deliberately leaves old style algorithms behind, it seems to have been mostly ignored;
This scheme uses encrypt-then-MAC, it doesn't hurt to understand the differences with MAC-then-encrypt and encrypt-and-MAC.


GCM and decrypting with Krack I'm trying to understand how Krack works on GCM. I thought that looking at GCM would be easier since it's a full break and the video shows a tool that is able to decrypt everything.

I see that the IV is resent, but how does that carry forward? Each packet is sent with an IV that is used to encrypt/decrypt that packet, correct? Am I wrong in thinking the IV is generated from the Anonce, Snonce, MACs and PMK?

If a key is known to be all zeros, that should make it easy to decrypt once the IV is known, but if the IV isn't sent with packet and is in fact generated, then how are so many packets decrypted?

Krack doesn't disclose the PMK so generating the IV on your own is out. Shouldn't you be limited to the number of packets that were sent between the nonce reuse? As in, if 5 packets were sent before the nonce was reused then you would only have enough information to try to decrypt the five packets sent after the first use of the nonce and the five packets sent after it was reused.

From 2.4 of the paper available at https://www.krackattacks.com (emphasis added):

  The GCMP protocol is based on AES-GCM, meaning it uses
  counter mode for encryption, with the resulting ciphertext being
  authenticated using the GHASH function [28]. Similar to CCMP, it
  is an AEAD cipher, and secure as long as no IV is repeated under a
  particular key. In GCMP, the IV is the concatenation of the sender
  MAC address and a 48-bit nonce. The nonce is also used as a replay
  counter by the receiver, incremented by one before sending each
  frame, and initialized to 0 when installing the TK [1, §12.5.5.4.4].
  This normally assures each IV is only used once. As with CCMP,
  the TK is used directly as the key for both communication directions.
  If a nonce is ever repeated, it is possible to reconstruct the
  authentication key used by the GHASH function [43].

[28] is NIST SP800-37D  (the standard for GCM)
[1] is IEEE 802.11-2016  (the standard for, well, guess)
[43] is 2006 comments by Joux to NIST


Practical disadvantages of GCM mode encryption It seems that GCM mode encryption has a clear advantage over CBC + HMAC in the sense that it only requires a single key. But it seems that there are some experts here that do not trust it enough to recommend it. This question is a call to those experts to clearly define those concerns.

Are there any properties of GCM mode encryption that make it less secure in practical operations than CBC + HMAC using two separate keys?

Answers could focus for instance on properties of the algorithm that make it more vulnerable to side channel attacks than other algorithms.

In comparison to CBC mode and HMAC, GCM mode is quite a commonly better alternative. But, I'll go to detail where it necessarily is not. Just like Richie Frame, I also do not agree that CBC + HMAC is always the best comparison target. I've added a few other details. Hope you find them useful.

Against CBC and HMAC

I'll discuss downsides first.

The authentication part of GCM (GHASH) is weaker than HMAC, GHASH provides a maximum 128-bit authentication tag, whereas HMAC allows lot longer tags (HMAC-SHA-256 would allow 256-bit authentication tag). In addition, forgery of GHASH tags in some cases is easier than HMAC:

  As with any tag-based authentication mechanism, if the adversary chooses a $t$-bit tag at random, it is expected to be correct for given data with probability $1/2^t$. With GCM, however, an adversary can choose tags that increase this probability, proportional to the total length of the ciphertext and AAD. (Borrowed from NIST SP 800-38D.)

Implementations using GCM mode often use short IV (96-bits), in fact, e.g. NIST SP 800-38D recommends using the 96-bit IVs. (Longer IVs are defined but they'll require the extra invocation of GHASH function.)
The 96-bit IVs (GCM) can be too short uses where 128-bit IV (CBC) would be sufficient. Consider e.g. collision probability of random IVs.

Benefits of GCM: Properly implemented GCM is almost always faster, and it is easier to use GCM than operate AES + HMAC combination correctly. CBC mode requires padding input to the block size, thus GCM mode produces smaller output if the input is not multiple of the block size.

Against CTR + HMAC

Because the AES parallelization benefits are available via CTR mode as well, CTR + HMAC is fairly similar to GCM and can perform pretty well. It can be better, in case authentication tag requirements exceed what GCM can provide.

Against CCM

The CCM mode is largely similar to GCM mode. It's the largest benefit is that implementation requires less code (SW) or gates (HW), but CCM implementations generally are slower than GCM.

Overall, some IEEE 802 standards tend to pick CCM over GCM due to the HW implementation gate count.

SIV-AES and AES-KW

It is possible to wrap other keys using AES-GCM (key wrapping).

For authenticated encryption where the target is key wrapping (encryption of key with another key), SIV-AES and AES-KW algorithms are commonly better than AES-GCM. Better in the sense that they can be used without reliance on random
number generation (or a deterministic IV generator) and that their output can be smaller because there is no need IV in addition to encrypted output and authentication tag. (These are commonly considered to be benefits of deterministic authenticated encryption.)

Key, IV pair reuse

I've already mentioned IV, key pair reuse.

GCM mode does not resist the reuse of Key IV combination. To prevent this, some parties like NIST put more requirements on the proper use of GCM mode than the other modes. This is a good idea from the security point of view, but it may reduce the allowed uses of the mode.

Generally, GCM is most convenient for uses where new keys are agreed or transported as a part of the protocol (TLS or IPsec). If there is use where a persistently stored key is needed, then it can be cumbersome to ensure IV uniqueness.

NIST is aware of this pitfall. NIST's CMVP (Cryptographic Module Validation Program aka FIPS 140-2 validation program) has a requirement for the careful use of GCM (FIPS 140-2 IG A.5). FIPS-approved implementations of GCM mode need to be very careful in their use of keys because, in GCM mode reuse of key, IV pair is not allowed to happen.

CBC-ESSIV

AES-CBC mode can be used for disk encryption (especially with ESSIV, see Wikipedia disk-encryption theory). The fact that GCM often uses small IV length and is not IV collision-resistant makes it hard to apply for contexts where it is needed to encrypt a large number of blocks and encryption does not happen in-order (deterministic IV increasing would be ok). For this reason, AES-GCM is not that much used for encryption of stored data, but rather data at transit.

Summary

GCM is a very good mode of operation, and it often is more convenient than legacy algorithms combinations like CBC + HMAC. However, it is not a universal solution (none of the modes is), but rather it is most convenient only for a large number of data at transit.


Do Chosen-Chiphertext attacks only apply to public-key cryptosystems? Do Chosen-Chiphertext attacks (CCA-1/2) only apply to public-key Cryptosystem?

No, there are also CCA games for private key encryption schemes. There you have additional encryption oracles that you can use, to obtain encryptions for messages of your choice (in a private key encryption scheme you can not encrypt yourself, because this requires the secret key).
See here for a concise explanation and comparison:
http://crypto.cs.uiuc.edu/wiki/index.php/IND-CCA


Simple math ECDSA example I'm trying to setup an ECDSA math example using just integer math and multiply (no EC).  The purpose is just to help people understand why this works with out the added complication of understanding EC.  However, it looks like I either don't understand something or I'm making a simple math mistake.

Can someone help me fix this?

Here is what I'm doing:

Signer workflow:

private da = 7

G          = 2

pubkey     = da * G = 14

message z  = 10

n          = 17

k          = 13

k^-1       = 4

x1         = 26

r          = 26 mod 17 = 9

s          = 4(10 - 9 * 7) mod 17 = 8

Verify workflow:

w  = s^-1 = 15

u1 = z * w mod n = 14

u2 = r * w mod n = 16

x2 = u1*G + u2*pubkey = 252

r2 = x2 mod n = 14 <=== failed...??

s = 4(10 - 9 * 7) mod 17 = 8

That should be:

s = 4(10 + 9 * 7) mod 17 = 3

If you modify the rest of the example to account for this, the example works.


Decrypting ciphertext produced by the Trivium stream cipher Given a message that is encrypted using a Trivium and the key that was used to encrypt it, how does the receiver decrypt the message?

Trivium is a synchronous stream cipher. For synchronous stream ciphers the key stream is independent of the plaintext and ciphertext.

The key stream (which is not the key itself, but the output of the cipher construction) is then combined in a reversible way with the plaintext to for the ciphertext (commonly byte-by-byte). The reverse operation with the same key stream and the ciphertext brings back the plaintext.

Usually XOR is used, which allows you to use the exact same construction for both encryption and decryption (as $PT \oplus KS = CT$ and therefore $CT \oplus KS = PT$).


How digital signatures work I understand how public/private key cryptography works, and I understand how one-way hashing algorithms work.

I have read through this explanation of how digital signatures work, but something still isn't clear to me. Can someone please help me understand how the receiver of a message that has been digitally signed can be sure that the message has come from the claimed sender, unaltered.

Here's my own breakdown of the explanation in the linked article, which assumes the receiver is using some sort of program ("the program") to receive the message, and verify the signature.

The SENDER of the message sends to the RECEIVER:

A PLAINTEXT copy of the original message
A digital signature which consists of an ENCRYPTED hash of the original document, encrypted using the signer's private key
A PLAINTEXT copy of the signer's public key

The RECEIVER receives the message, and verifies that it is unaltered and from the claimed sender by:

Using the PLAINTEXT public key received in the message, the receiver decrypts the hash. The receiver then re-hashes the original document, and ensures that both hashes match
The program also validates that the public key used in the signature belongs to the signer

What's going on in step 2, above? How does the receiver perform this verification step? I can follow everything up to this point, but based on what's been explained up to that point, it would very easy for someone to intercept the message being sent, rip out the signature, create a new hash, attach a new public key, and send it on its way. So at step 2 above, how can the RECEIVER be sure that the message they are looking at is both unaltered and from the intended sender? How do they "verify" it at that point in the process?

Thanks in advance.

The article is oversimplifying matters. In a real-world scenario, either…

The recipient already has a copy of the public key, or can retrieve a copy from a trusted source. Either way, they can confirm the key is correct by comparing it with the "known good" copy they already have. (This is roughly how PGP works.) Or…
The key has a signature attached to it, signed by a trusted central authority. (This is roughly how SSL/TLS works.)

Either way, your analysis is entirely correct -- attaching a signature and public key to a message doesn't confirm anything on its own.


Cipher Block Chaining - How do you change the plaintext of all blocks? I've just read about CBC encryption and decryption and was wondering how you can change every plaintext block?

Let's say you have an initialization vector, 3 ciphertext blocks, know each block-cipher-decryption and you know each plaintext block too. Then you have some string that you want to change these given plaintexts to. Edit: Assume there is a padding oracle available as well.

If I understood correctly, it will be quite easy to change the very first plaintext block: You take each byte of the initialization vector XORed with each byte of the first plaintext block XORed with the character of the string you want to change these plaintexts to. Putting all these new bytes together, this is now the new initialization vector and XORing this new initialization vector with the first ciphertext block, we will get another plaintext; that one we wanted.

The change of the iv has no effect on the plaintext of the next ciphertext block. But now in order to change the next, namely the second plaintext, we would have to do changes on the first ciphertext block which will sadly destroy the first plaintext block... And the same will happen if we move to the next ciphertext block and try to change its plaintext. So, in the end, there will just be junk plaintext or nothing at all, bad format. But I don't see any other way where you could change all plaintext blocks correctly? : /

I've mainly oriented myself on this nice diagram here from Wikipedia:

If this is all you have, then I think you can't.
You can easily get 1st and 3rd block.
Change the 2nd ciphertext to get the desired result of 3rd block and change IV to get the desired result for first.
But changing a cipher text block means you no longer have the results of the block cipher decryption.

If you have however limited access to a decryption oracle then you will just need to make trial decryption of two blocks. The ciphertext of block 2 which makes the 3rd block what you want. And then given it,  you choose the ciphertext for block 1 which you send to decryption in order to calculate required IV.


How does RSA padding work exactly? I've read everywhere online and people say plain text RSA is very unsafe. To make it safe you pad it but no examples are shown anywhere on how to do it. It's explained that random data is added to the encryption process to change up the final encryption so it can't be guessed at random by comparison to similar looking encryptions.

So far what I understand is you have a plain text, you turn that into a hash and pad it with extra bytes then you encrypt it and send it over and then it is decrypted into a hash with bytes and turned to plain text. Where does the padding go? Do you add random 'trash' bytes to the plain text to fill it up and then hash it and encrypt? Or do you do some extra math in the encryption process? What is this process? What about figuring out what is a padding byte and what isn't?

Apart from that how do you turn it back to text from a hash? What if I turn it into SHA-512 hash with a salt? How will the person be able to decrypt the data once they decrypt the RSA to find the hash? Is my understanding wrong of the process? Does turning the plain text into hex help with anything?

There exist many standards which describe a lot of padding modes and security protocols. If you're new in that field, I strongly recommend you to study the family of PKCS standards which are the reference in the domain. There also exist other distinct standards depending of very specific application fields (Banking, mobile, Cloud, Embedding ... or Global Platforms).

Briefly, as you've certainly observed the RSA primitive is based on modular exponentiation and this operation is homomorphic in the sense that if someone knows two ciphertexts $c_1=m_1^d$ and $c_2=m_2^d$, then he can immediately deduce : $(m_1.m_2)^d= c_1.c_2=c$.
This is the essential reason to break this "homomorphism", by adding inside the plaintext some hash or other techniques.

Other security protocols allow an attacker to interact with an oracle to prove the security of the scheme. Then randomization can be included in some cases to prevent the attacker from deducing any bit of information about the plaintext when she is given the ciphertext. The subject is very vast.


Why do key exchange protocols need secure clock synchronization? I'm studying Kerberos and other Key Exchange Protocols.

They always (or very often) require that the clocks are synchronized. To this purpose they periodically probe a time-server. This is said to be a critical operation because new kind of attacks arise. But which attacks?

Kerberos requires synchronised clocks mainly to ensure the messages are fresh and to thwart replay attacks. The messages include timestamps so that those with outdated timestamps (e.g. more than 5 minutes) will be thrown away (although there is still a time window in which replay is possible).

Many key exchange protocols don't use timestamps because clock synchronisation is often problematic and difficult. Nonce based based challenge response is used instead to prevent replay attacks.


Share two secrets between two parties Alice has a secret A, Bob has a secret B. They have a secure channel and a MAC. They each want to know the other's secret, but don't particularly want to give up their own. However, neither will not lie about the secret, but if possible, will stop communications once [s]he learns the other's secret.

How can such a protocol work, that if Alice or Bob doesn't correctly follow all steps in the protocol, neither person can gain any information about the other's secret.

You may not use a third party.

M.O.Rabin answered the question in 1981, named it oblivious transfer.


How to choose the appropriate public (i, m) and private (j, m) keys? I studied some encryption and decryption and I have found some very interesting problem to solve on the internet. I hope I am writing to right site - there are so many in StackExchange otherwise I hope some moderator will move it.

So, how to choose the appropriate public lets say (i, m) and private (j, m) keys which could be subsequently used to (de)encrypt in RSA when there are primes lets say p = 17 and q = 5?

I tried something like:

17*5=85

(17-1)*(5-1)=64

64 should be magic number but still do not know what to do next, can anyone help me here?
 I would really appreciate how to choose and in which way these keys ...

I assume that $m = pq$ (85) is the modulus, and the number you computed (64) is $\phi(m)$. Now we must choose the exponents ($i$ for public, $j$ for secret? , weird notation) in such a way that $ij = 1$ modulo $\phi(m)$. In fact we can work modulo 16 if we like, because that is the least common multiple of $p-1$ and $q-1$. So if we choose $i = 3$, we choose $j=11$, as $33 \equiv 1 \mod 16$. Or $i=11$, $j=3$, this is symmetrical. Or we could choose $i = 5$ and then $j=13$ works, or vice versa again.

Then encryption of a number smaller than $m$ is exponentiation to the power $i$, modulo $m$ and decryption is exponentiation to the power $j$, modulo $m$.

Of course these numbers are way too small to provide any security, but that's the general idea.


Are there any public-key encryption schemes based on DLog? There are public-key encryption schemes based on many different mathematical hardness assumptions, like the hardness of Decisional Diffie-Hellman problem, the hardness of the Factoring problem, the hardness of the RSA problem, etc.
But my question is, are there any public-key encryption schemes based on the hardness of the Discrete Log problem?  Does the hardness of the Discrete Log problem even imply the existence of secure public-key encryption?

It is a major open research question whether such a scheme exists, and how to construct one (see, for example, Open Problem 9.10). Of course, we do have schemes like (hashed) ElGamal, which are based on the conjectured hardness of the (computational or decisional) Diffie-Hellman problem. But it is unknown whether either of these problems is equivalent to the discrete logarithm problem (except, of course, in groups where discrete log is easy).


Public Key encryption /Assymetric encryption For a start, I 've got a question regarding the Public key encryption.
I know the public key encryption overcomes the Key distribution issue with the symmetric encryption and that in the case of communication between 2 parties, there is a total of 4 keys (each party has a public and a private key )

But here's what's been confusing me.
If Bob wants to send a message to Alice, then he will encrypt the message using Alice's public key. For Alice to understand that message, she would decrypt the message using her private key.  The problem is, isn't it like they both have the same keys? Because if Alice were to decrypt the message using her private key and no one else knows what that key is but her, won't she get a different message than the one sent by Bob?

The part you're missing here is that Public Key encryption is asymmetric - that is, data can only be encrypted with the public key, and can only be decrypted with the private key. Public key encryption systems are created in such a way that the encryption is (mostly) irreversible, but there is a mathematical 'trapdoor' that allows the private key to be used decrypt the data.

Compare this with a symmetric encryption scheme, where there is only one secret key (so both Alice and Bob would have to share the key to use such a scheme).

i.e. once the data is encrypted by Bob using Alice's public key, noone holding Alice's public key can decrypt it. Only Alice, using the private key and the different decryption algorithm can decrypt it.

The answers to How does asymmetric encryption work? give more detail as to how this works.


Why is a bit biased when generated from random $v \in Z_q$ for odd q? I am not understanding the following from "Lattice Cryptography for the Internet" by C. Peikert (pages 10, 11):

  When $q$ is odd, while it is possible to use the above methods to
  agree on a bit derived by rounding a uniform $v \in \mathbb{Z}_q$, the
  bit will be biased, and hence not wholly suitable as key material.

I don't understand the biased part and how it is related to $q$ being odd or even. Any help would be appreciated.

What Peikert is saying here is that you can generate a random bit $b$ by first picking a uniformly random number $v \in \mathbb{Z}_q$, and then setting $b = 0$ if $v \leq q/2$ and $b = 1$ if $v > q/2$.

However, when $q$ is odd there is one more number in $\mathbb{Z}_q$ that is smaller than $q/2$ than there numbers that are larger than $q/2$. I.e., the bit will be slightly biased towards zero.

Put in other words, the probability of $b=1$ will be $\frac{\lfloor q/2 \rfloor}{q}$ and the probability of $b=0$ will be $\frac{\lceil q/2 \rceil}{q} = \frac{\lfloor q/2 \rfloor + 1}{q}$.

Note: Actually, Peikert seems to be using a slightly different "rounding" method. But the same argument applies. You would have more numbers mapping $b$ to $0$ than $1$ (or the other way around).


What is the relationship between p (prime), n (order) and h (cofactor) of an elliptic curve? I am reading up on ECC and having trouble understanding how these are related.

In a finite field, all point operations are taken modulo $p$.

$n$ is the order of the generator $G$ — which apparently is the number of different points on the curve which can be generated by multiplying a scalar with $G$. This is clear. But —

How is this $n$ chosen? Is $G$ chosen so that $n$ is a certain number?
Does $n$ effect the security of the curve?
Do all the points of the crypto operations with a given $G$ fall in the set of $n$ points for that $G$?

$h$ is the cofactor which is the $\#E(\mathbb F_p)/n$.

What is the significance of this?
$\#E(\mathbb F_p)$ is the number of points of the curve apparently. Why is dividing that with $n$ interesting?

The prime $p$ is chosen to make arithmetic in a choice of field $k$ efficient.  Typically $k = \mathbb F_p$ or $k = \mathbb F_{p^2}$.  Popular choices of $p$ are near powers of two, e.g. the Mersenne primes $2^{127} - 1$ used by FourQ and $2^{521} - 1$ used by E-521 and NIST P-521, or $2^{255} - 19$ used by Curve25519.  Other popular choices differ from a power of two by a small linear combination of of powers of two, e.g. $2^{224} - 2^{96} - 1$ used by NIST P-224 or $2^{448} - 2^{224} - 1$ used by Curve448.

The field $k$, the curve shape, and the parameters of the curve shape determine an elliptic curve $E/k$.  Every elliptic curve over a field of characteristic ${>}3$ has a representation in short Weierstrass form $y^2 = x^3 - a x + b$ for parameters $a, b \in k$.  Some curves also have representations in Montgomery form $B y^2 = x^3 + A x^2 + x$ or twisted Edwards form $a x^2 + y^2 = 1 + d x^2 y^2$.

The choice of curve shape affects performance and security properties of the curve, e.g. Montgomery curves have fast $x$-restricted scalar multiplication by the Montgomery ladder whereas the best single-coordinate ladder on curves that have no Montgomery form is the much slower Brier-Joye ladder.  The curve parameters often also affect performance, because, e.g., the Montgomery parameter $A$ figures into the Montgomery ladder as a multiplier, so smaller values of $A$ make the Montgomery ladder faster.

A field $k$ and curve $E/k$ determines a group of $k$-rational points $E(k)$.  These are loosely the points in $k$ satisfying the curve equation, and $\mathcal O$, an identity element.  (In more algebraic-geometric jargon, these are the points fixed by the coordinatewise action of the automorphism group of $\overline k$ that fixes $k$; that definition also works with projective coordinates, which are all-around much nicer to think about than affine coordinates.)  This is the group in which we do arithmetic, and define scalar multiplication of a point $P \in E(k)$ by $[u]P = P + \cdots + P$, the $u$-fold sum of $P$ with itself, with $[0]P = \mathcal{O}$.

The number of $k$-rational points $\#E(k)$ is an upper bound on the number of possible values we can get by scalar multiplication, and thus the maximum defense against ECDLP attacks: it is the maximum possible order of any element $P \in E(k)$.  So scalars are equivalent modulo $\#E(k)$: $[a]P = [b]P$ if $a \equiv b \pmod{\#E(k)}$.  The order of the field $k$ puts bounds on possible values of $\#E(k)$ by Hasse's theorem: $$|\#E(k) - (\#k + 1)| \leq 2\sqrt{\#k}.$$  So in order for $\#E(k)$ to be large enough to resist Pollard's rho, $\#k$ must be large too; for $k = \mathbb F_{p^e}$, $\#k = p^e$, and since $e$ is usually 1 or 2, $p$ must be large as well.  This is also why the high-order digits of the primes in the NIST curves may naively appear suspiciously the same as the high-order digits of the orders of the NIST curves.

We don't pick $\#E(k)$ in advance; rather, we pick $p$, a field, a curve shape, and curve parameters, and then compute $\#E(k)$ by Schoof's algorithm.  In order to resist small-subgroup attacks, we want $\#E(k)$ to be prime or nearly prime, so that $E(k)$ has at worst only negligibly small subgroups.  So we either randomly search the parameters to the curve, or find the smallest/fastest values, that make $\#E(k)$ the product of a large prime $n$ with a small cofactor $h = \#E(k)/n$.  Some curves are chosen with $h = 1$ so that $\#E(k) = n$ is itself prime; others are not, e.g. because every Montgomery curve has a cofactor $h > 1$.

Finally, we pick a base point or generator $G$ of prime order $n$.  This can also be done randomly or deterministically, e.g. picking the smallest nonnegative integer $x$ that is the $x$ coordinate of a point $G$ of order $n$, which we test by multiplying $[n]P$ and seeing if we get back $\mathcal O$.  The choice of which base point in an order-$n$ subgroup is immaterial, so there's no reason to even be tempted to choose this at random.

The attacker's job, which we hope to make hard, is to find a secret scalar $u$ given a multiple $[u]P$ of some point $P$ known to the attacker.  The legitimate user normally reveals $[u]G$ as their public key, so the subgroup generated by $G$ needs to have large order to resist Pollard's rho offline, and prime order to resist Pohlig–Hellman offline.

For ECDH, the legitimate user will also reveal $[u]P$ for an attacker-chosen $P$, which exposes them to Lim–Lee active small-subgroup attacks in which the attacker feeds in points $P$ in small subgroups where the ECDLP is easy.  If $\#E(k)$ is prime, then $n = \#E(k)$ and there are no nontrivial subgroups.  If $\#E(k) = h n$ is near prime, with, say, $h = 8$, then there are nontrivial subgroups, but the amount of information revealed by $[u]P$ is at most $\lceil\log_2 h\rceil$ bits—and sensible ECDH systems such as X25519 pick secret scalars $u \equiv 0 \pmod h$ so that $[u]P = \mathcal O$ for any point $P$ of low order, and the active attack reveals nothing.  (For more about choosing secret scalars for X25519 or Ed25519 or more exotic applications, see this answer.)

There is a host of other considerations you need to worry about, and they depend on what cryptosystem you're using: e.g., ECDH/EdDSA and pairing-based cryptography have completely different constraints.  You can find a reasonably comprehensive listing of criteria for curves safe for ECDH and EdDSA at SafeCurves, which also addresses twist security, completeness of addition laws, rigidity of selection process, and various other criteria for choosing curves.

Note that novel uses of curves sometimes require further criteria beyond SafeCurves, or careful handling beyond the standard DH or signature schemes.  For example, the cryptocurrency Monero was badly surprised by distinct but equivalent signatures enabled by the small subgroups implied by a cofactor $h > 1$.

For further references, and for some more detail about X25519 in particular, see an earlier answer I wrote.


Tiny Encryption Algorithm (TEA) weakness The Wikipedia states that different multiples of a magic constant are used to prevent simple attacks based on the symmetry of the rounds. The magic constant, 2654435769 or 0x9E3779B9 is chosen to be ⌊$2^{32}$/ϕ⌋, where ϕ is the golden ratio.

And according to the code which wiki provides.

void encrypt (uint32_t* v, uint32_t* k) {
    uint32_t v0=v[0], v1=v[1], sum=0, i;           /* set up */
    uint32_t delta=0x9e3779b9;                     /* a key schedule constant */
    uint32_t k0=k[0], k1=k[1], k2=k[2], k3=k[3];   /* cache key */
    for (i=0; i < 32; i++) {                       /* basic cycle start */
        sum += delta;
        v0 += ((v1<<4) + k0) ^ (v1 + sum) ^ ((v1>>5) + k1);
        v1 += ((v0<<4) + k2) ^ (v0 + sum) ^ ((v0>>5) + k3);
    }                                              /* end cycle */
    v[0]=v0; v[1]=v1;
}

Since the constant is known, how could this constant prevent attacks?
I was stuck in the description.


Post-quantum authenticated encryption It is well-known that the Grover's algorithm reduces cryptographic strength of symmetric ciphers to a square-root - e.g. AES-256 becomes only 2128 strong.

However, these statements are always made about the raw block ciphers. How about GCM-AES256, CCM-AES256 and the like? The MAC tag in GCM is at most 128 bits. Does this mean GCM is not post-quantum secure, even if I use AES-256? What mode of operation that gives me authenticated encryption also gives me post-quantum security?

UPDATE

So I have found some interesting papers, namely:

Secure Signatures and Chosen Ciphertext Security
in a Quantum Computing World
Quantum-Secure Message Authentication Codes

GCM uses Carter-Wegman MAC, and per the second paper (p. 18): This MAC is not, in general, secure in the quantum setting. But the authors (Dan Boneh and Mark Zhandry) do give an example of a modified CW-MAC that is secure in quantum settings. So I guess that rules out the GCM mode, but what about CCM and others?

I am not sure whether the construction of MAC is the only issue in authenticated crypto, or the MAC tag space as well.

This [Carter-Wegman] MAC is not, in general, secure in the quantum setting

This is true; however we need to ask "what is this setting, and is it a realistic one?"

This setting is one where the adversary can ask queries that are composed of a superposition of quantum states, and the oracle returns the superposition of the answers.  In other words, the oracle (that is, the device with the MAC key that computes the MAC) must compute the answer without any decoherence in the quantum state, and the messages to and from the adversary must also not have any decoherence.  As far as we know, any significant amount of computation without decoherence must be done using Quantum Error Correction (to adjust for the decoherence that just occurs naturally), this effectively means that the device with the MAC key must be a part of the quantum computer (but, for some reason, the attacker doesn't look inside the device and just extract the MAC key).

I would argue that this is not an attack model that we need to worry about, if we're just creating devices that exchange messages, and are worried about someone building a Quantum Computer.

We do need to worry about Grover's algorithm, which given a function $F(x)$ with an unknown $n$-bit input, find an $x$ where $F(x)$ is a specific value in $O(2^{n/2})$ time.  However, the attacker can't take advantage to try to compute a 128-bit MAC tag; because, in addition to the tag that the attacker is searching for, the algorithm also has the key as the input, and the attacker doesn't know that.  Grover's algorithm could be used to attack the key itself; we can prevent that from being a possibility by using a 256 bit key.


Would the rotors in Enigma machines always advance by one position? Or was there a way to set this? Before encrypting a letter the first rotor advances by one, right? So there could be a way, once the first rotor turns 26 times, make the second rotor advance two positions instead of one. Or three. Did the Enigma take advantage of it?

No, there was no way on the Enigma machine to change the behavior of the rotor rotation.

Rotation on the Enigma was a fixed mechanical property of the rotors like the gears in a clock. However, other cryptographers noted this vulnerability in the Enigma and improved it in follow on rotor machines particularly the British Typex and the American SIGABA aka ECM Mark II aka M-134.

The Typex had five non-reflecting rotors (watch this video for why reflecting rotors were a flaw in the Enigma), but the first two were stationary. They could be set and acted like the Enigma's plugboard but did not have the flaw of being reciprocal, a key means of defeating the Enigma's plugboard (watch this video for why).

Typex type 22 or 23 with two plugboards

The other three rotated, but Typex rotors came in two pieces. An wiring insert which scrambled the letter, and a sleeve which determined when it rotated. Each sleeve had different numbers of notches in different locations making it difficult to work out when the rotors would rotate. They could even be reversed giving yet more variation.

SIGABA also had varying rotation but electric signals rather than mechanical notches.  The original used a paper tape with holes in it to allow or block an electrical signal. Each keypress read and advanced the tape which could contain many holes. Each keypress could turn any and all (or none) of the rotors.

SIGABA rotor unit

The next version did away with the paper tape and instead used yet more rotors (control and index rotors) to generate a 5 bit signal, each bit indicated which scrambling rotor (code wheels in the illustration below) to turn.  This eliminated the paper tape and instead rotation was determined by setting the rotation rotors according to daily code.

This provided SIGABA with very good pseudo-random behavior for the time and it is not known to have been defeated during its service lifetime.


What's the safest way to encrypt a messenger application? How can I safely encrypt a messenger application that sends data over the Internet via TCP?

I've already taken a look at Salsa20, but I don't know if that's a good algorithm to use for this.

What algorithms can I use for this and how secure are they?

Writing a secure messenger application is difficult, and vulnerabilities have been found, and keep being found in all of them.

This requires far more than just a stream cipher such as Salsa20. An entire protocol has to be designed for user registration, key exchange, group invites and more.

The MLS working group is currently designing a reference protocol to do group messaging.

Meanwhile, Signal has opensourced their core library (https://github.com/signalapp/libsignal-protocol-c), and this is something you may want to look at.

Wire, another popular application with fairly decent security, has also opensourced most of its components: https://github.com/wireapp

But I wouldn't recommend starting from scratch, especially if you are new to cryptography.


Is IV needed in ECIES? Is IV needed in ECIES (Elliptic Curve Integrated Encryption Scheme) used with AES-CTR?

The ephemeral key pair is generated randomly therefore the encryption key derived from the public key must be random, too. As I know, IV is required only if the symmetric encryption key is used more than once, but in ECIES, every time an ephemeral key is generated, new encryption key is derived from that.

Am I right or IV is still recommended in ECIS w?

Pedantically, you always have an IV with AES-CTR; you need to start counting somewhere.  So, your question really is "do I need an explicit IV, or can I use an implicit all-0 IV"?

With AES-CTR, the important requirement for IVs is that you never reuse the same IV for the same key.  With ECIES, you'd reuse a key only if the sender used the same random number $r$ twice (and used that common $r$ to encrypt to the same public key).  Assuming that you never do that, that is, you always pick a fresh $r$ whenever you do a public key encryption, then you are correct, using an implicit fixed IV is just fine.


Parallelizing MACs by subdividing the message and then aggregating results Most MACs other than GMAC (and Poly1305?) are not parallelizable. Examples include CMAC and HMAC.

Could these be securely parallelized by computing multiple MACs in parallel and then combining the result? This is sort of academic, just curious though.

Let's say you have a message being that you split into four parts such that M==M1|M2|M3|M4. You then compute CMAC on each of these and then a final CMAC on the results.

T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))

The advantage is that this could be implemented in a way that exploits instruction-level parallelism. Instead of splitting the message into four chunks you could implement this by computing four CMACs in parallel with a stride of 4*B where B is the block size of the cipher (e.g. 128-bit for AES). The final CMAC could also be done sort of in parallel with the last block of each component CMAC.

You could also potentially use those crazy 4X parallel AES instructions on CPUs that support AVX-512 to do four CMACs in true parallel.

Obviously, the result would be different from CMAC(M), but would the security be equivalent? This is basically a hash list so I'm thinking yes, but the MAC use case is different from ordinary hash use cases.

Edit: an even bolder thing would be to just compute four CMACs and XOR them, but since XOR is commutative that makes me think it would be vulnerable to chosen-plaintext attacks.

Edit #2: it appears the XOR case may be secure if each MAC is independently keyed, but I'd want to look into it more.

Edit #3: alternatively it seems like CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4)) should be secure if the above is secure. This can be done in parallel by computing CMAC on all four parts (or stripes) of the message and then doing three more blocks of the first CMAC to incorporate the siblings.

Edit #4: thinking about this more, I think the fastest algorithm would be to do N parallel HMACs/CMACs with different keys and then XOR them together. This is secure as long as the MACs are secure. You can't swap anything because the keys are different and so e.g. CMAC[k1](M1) XOR CMAC[k2](M2) != CMAC[k1](M2) XOR CMAC[k2](M1). On an AVX2 enabled machine you could use _mm512_aesenc_epi128 to do four CMACs at once with different keys in true parallel. Even without that instruction level parallelism would kick in if the CPU does it.

So you would have something like (pseudocode, using CMAC-AES with 16-byte blocks):

K1 = KDF(K,1)
K2 = KDF(K,2)
K3 = KDF(K,3)
K4 = KDF(K,4)

while (remaining >= 64) {
  CMAC_BLOCK(K1,input)
  CMAC_BLOCK(K2,input + 16)
  CMAC_BLOCK(K3,input + 32)
  CMAC_BLOCK(K4,input + 48)
  remaining -= 64
  input += 64
}

// ... do final blocks with padding ...

MAC = CMAC_FINAL(K1) XOR CMAC_FINAL(K2) XOR ...

A highly optimized implementation would interpolate the instructions for each AES round to allow ILP to work or use SIMD AES like _mm512_aesenc_epi128 if available.

There are two general approaches to parallelizing MACs:

Use a universal hash like GHASH or Poly1305 whose algebraic structure admits essentially arbitrary levels of parallelism.

For GHASH and Poly1305, the hash is polynomial evaluation:

\begin{equation}
      H_r(m_1 \mathbin\| m_2 \mathbin\| \dotsb \mathbin\| m_n)
        := m_1 r^n + m_2 r^{n-1} + \dotsb + m_n r.
   \end{equation}

The naive way to compute this is with Horner's rule:

\begin{align}
     h_0 &:= m_1, \\
     h_1 &:= h_0 r + m_2, \\
     h_2 &:= h_1 r + m_3, \\
         &\vdots \\
     h_n &:= h_{n-1} r.
   \end{align}

If you can compute two multiplications simultaneously, then by precomputing $r^2$ you can process the message two chunks at a time (handling an odd number of message blocks left as exercise for reader):

\begin{align}
     h_0 &:= m_1, \\
     h_2 &:= h_0 r^2 + m_2 r + m_3, \\
     h_4 &:= h_2 r^2 + m_4 r + m_5, \\
         &\vdots \\
     h_{n-2}
         &:= h_{n-4} r^2 + m_{n-2} r + m_{n-1}, \\
     h_n &:= h_{n-2} r^2 + m_n r.
   \end{align}

The same idea extends to an arbitrary degree of parallelism in an implementation without changing the semantics of the MAC you compute.  Other universal hashing MACs often have similarly parallelizable algebraic structure, e.g. UMAC which uses a combination of inner products and polynomial evaluation.
Use a PRF like BLAKE2 on a tree-structured encoding of a message—Merkle trees.

If $H$ is a uniform random (secret) function, then so is $$(x, y) \mapsto H(2 \mathbin\| H(0 \mathbin\| x) \mathbin\| H(1 \mathbin\| y))$$ on the appropriate domain, or at least nearly so—this construction is indifferentiable from a random oracle.  Then if you instantiate $H = F_k$ for uniform random $k$ where $F$ is a pseudorandom function family, the PRF-security of the construction $$(x, y) \mapsto F_k(2 \mathbin\| F_k(0 \mathbin\| x) \mathbin\| F_k(1 \mathbin\| y))$$ isn't much different from the PRF-security of the primitive $F_k$.  And of course a uniform random function makes a good MAC, so the PRF $(x, y) \mapsto F_k(2, F_k(0, x), F_k(1, y))$ makes a good MAC—for fixed-length messages.  Here $F_k$ might be, e.g., AES-CMAC or HMAC-SHA256.

You must take care to encode the message uniquely.  If you exposed oracles for $H$ (on short messages only) and $(x, y) \mapsto H(H(x) \mathbin\| H(y))$ (on long messages only), then an adversary could forge the authenticator for $(x, y)$ by querying the $H$ oracle for $x$, for $y$, and for $H(x) \mathbin\| H(y)$.  This mistake is not immediately obvious, and appears in real-world protocols like BitTorrent and certificate transparency logs, which is why proposed standards like BLAKE2 tree-hashing and Sakura exist.

Usually this technique is applied when we want to incrementally verify or modify part of the tree, but you could expand the radix to whatever fanout you want to maximize parallelism.  The BLAKE2bp and BLAKE2sp parallel-hashing modes do essentially this with the BLAKE2 compression function as a PRF, but if for some reason you had to use AES-CMAC or HMAC-SHA256, you could use those as PRFs instead in this structure (at considerable cost to performance), provided you uniquely encode all the parameters that figure natively into BLAKE2.

Merkle trees can attain an essentially arbitrary degree of parallelism, but you must agree in advance to change what MAC you use.  Maybe right now you like the idea of four parallel AES-CMACs; maybe tomorrow you would rather have chosen eight; maybe on Tuesday a customer with a small ARM system that can only do one sequential AES-CMAC is sad.

What about the constructions you suggested?

  T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))

If this is a fixed-depth Merkle tree, then it may make a secure MAC, but the devil is in the details of what oracles you expose for CMAC under your key and how you encode the message into a tree structure.  Of course, CMAC doesn't have built-in space for encoding parameters like tree position the way the BLAKE2 compression function does, so you'll have to find another way to do that.

  CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4))

Similar to above, but now you are even more likely to accidentally expose an oracle for plain CMAC under your key.

  Edit #2: it appears the XOR case may be secure if each MAC is independently keyed, but I'd want to look into it more.

That post discusses $H_1(m) \oplus H_2(m) \oplus \dotsb \oplus H_n(m)$, where the $H_i$ are independently chosen MACs applied to the whole message $m$, but you have taken this to mean $H_1(m_1) \oplus H_2(m_2) \oplus \dotsb \oplus H_n(m_n)$ applied separately to the separate blocks $m_1 \mathbin\| m_2 \mathbin\| \dotsb \mathbin\| m_n$ of $m$.  The conclusion you inferred does not follow.  (You also have to spend additional time deriving subkeys, of course!)


Security of chameleon hash functions With the knowledge of the trapdoor, we are able to compute the same digest for differents messages.

I've read that given two messages $m$, $m'$ and two numbers $r$, $r'$ such that
$Ch(m,r)=Ch(m',r')$, computed by the owner of the trapdoor, we are able to find other collisions and sometimes we are able to find this trapdoor information (for log based chameleon hash, in a work from Tal Rabin and Hugo Krawczyk, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.50.3262 ).

I don't really understand the purpose of chameleon hash functions, since computing colluding messages lead to attacks. What are the subtleties ?

Thank you.

I think you have some misunderstanding here. Finding collisions when knowing the trapdoor is a required feature, but leaking the trapoor when knowing collisions is an undesirable "feature" (which some constructions suffer from).

A chameleon hash function (aka trapdoor commitment) allows you given the trapdoor to find pairs $(m,r)$ and $(m',r')$ with $m\neq m'$ such that $Ch(m,r)=Ch(m',r')$. This means that given the trapdoor you can produce such pairs and it should be computationally infeasible otherwise. There are many theoretical and practical applications of chameleon hash functions. One nice practical application are sanitizable signatures, where the knowledge of the trapdoor allows a sanitizer to sanitize an already signed message without invalidating the signature.

However, there are some constructions of chameleon hash functions (trapdoor commitments), that leak the trapdoor if one such pair has been computed and is publicly known. Note that the chameleon hash functon in the linked paper (Section 2.2.) is essentially a Pedersen commitment and the trapdoor is the discrete log between the two group elements. When knowing $Ch(m,r)=Ch(m',r')$ for two pairs $(m,r)$ and $(m',r')$ with $m\neq m'$ this allows to extract the trapdoor (just take a look at the binding proof for Pedersen commitments to see how this works - or just look at the equation under figure 3 in your linked paper and solve for $x$).

Chameleon hash functions which suffer from this "undersirable feature" are known to suffer from key exposure (which clearly often is a very undesirable feature). You should take a look at this paper for constructions that do not suffer from this limitation and there are also some other constructions which do not suffer from key exposure as well.


Is it possible that two distinct RSA moduli share both of their prime factors? I am using an algorithm (can be found here1) that can compute efficiently the GCD of multiple RSA keys. It intended for RSA keys that were generated with low entropy and may have one of their primes in common.

In the documentation it is stated that:

  if a modulus shares both of its prime factors with two other distinct moduli, then the GCD will be the modulus itself rather than one of itsprime factors

Here's the scenario that this caveat in the documentation worries about:

Suppose you had three modulii:

$M_1 = p \times q$

$M_2 = p \times r$

$M_3 = q \times s$

Then, when the program outputs the GCD of $M_1$, it'll output $p \times q = M_1$. It'd do this even though the above has enough information to factor $M_1$ efficiently.

It does this because it actually outputs $GCD( M_1, M_2M_3)$; because both factors of $M_1$ appear in $M_2M_3$, both factors appear in the output.

This is certainly possible; as for how likely it is, well, that rather depends on the details within exact RSA generation algorithm.  I personally would be surprised, though; most RSA generation algorithms pick one prime, and then pick the other (and run into problems because entropy was lousy when they picked the first prime, and then got better when it picked the second).  The primes it picks depends on the internal state (and the entropy).  For the first primes to match, we need to assume that the initial entropy was lousy (however, it got better when picking the second prime); this is plausible.  However, in order to share the second prime, then two runs must have distinct states when picking the first prime, and then somehow fall into exactly the same state when picking the second. That seems rather implausible (although not impossible) to me.


Finding an elliptic curve of specific order I wish to use elliptic curves for cryptographic operations like commitments etc. I see that most standard elliptic curves like $\operatorname{secp256k1, sect571r1}$ have a certain specific and fixed order of the corresponding bit-length.
However, I require groups of non-standard order like say $q = (2^k)n +1$ for a certain $k,n$ for $k =128, 300$ etc.
Is there a way I can generate/form an elliptic curve group of any given order? Of course, I require solving discrete-log to be hard in the group.

There are many academic works on finding a curve for a given order.

1994 - Georg-Johann LayHorst G. Zimmer - Constructing elliptic curves with given group order over large finite fields

A procedure is developed for constructing elliptic curves with given group order over large finite fields. The generality of the construction allows an arbitrary choice of the parameters involved. For instance, it is possible to specify the finite field, the group order or the class number of the endomorphism ring of the elliptic curve. This is important for various applications in computational number theory and cryptography.

The task solved in this paper are;

Given an integer $m > 3$, find a prime $p$ and an elliptic curve E over the finite
field Fp of order $\#E(\mathbb F_p) = m$.
Given two integers $n$ and $c_{max}$, find an elliptic curve $E$ over the finite field $\mathbb F_{2^n}$ with $\#E(\mathbb F_{2^n}) = c \cdot q$ with $q$ a prime and $c \leq c_{max}$. ( Note that binary curves are off)
Given an integer $n > 1$, decide whether or not there is a prime $p > 3$ and an
elliptic curve $E$ over $\mathbb F_p$ with structure $E(\mathbb F_p) \sim (\mathbb Z/n \mathbb Z) \times (\mathbb Z/n \mathbb Z)$.
Given a prime $p > 3$ and an integer $m$ with $|p+ 1 - m  < 2 \sqrt p$ , build an
elliptic curve over $\mathbb F_p$ whose group order is m and whose endomorphism ring
has small class number.

2001 : Erkay Savaş, Thomas A. Schmidt, and Çetin K. Koç Generating Elliptic Curves of Prime Order

A variation of the Complex Multiplication (CM) method for generating elliptic curves of known order over finite fields is proposed. We give heuristics and timing statistics in the mildly restricted setting of prime curve order. These may be seen to corroborate earlier work of Koblitz in the class number one setting

The citers of the first one should help if there is a specific work directly your case.

2007 : Reinier Broker, Peter Stevenhagen Constructing elliptic curves of prime order

We present a very efficient algorithm to construct an elliptic curve E and a finite field F such that the order of the point group $E(F)$ is a given prime number N. Heuristically, this algorithm only takes polynomial time $\mathcal{\tilde{O}}((\log N)^3)$, and it is so fast that it may profitably be used to tackle the related problem of finding elliptic curves with point groups of prime order of prescribed size. We also discuss the impact of the use of high-level modular functions to reduce the run time by large constant factors and show that recent gonality bounds for modular curves imply limits on the time reduction that can be obtained.


Why do we focus on polynomial time, rather than other kinds of time? Polynomial time seems to be mentioned quite frequently on this site. It often forms a threshold between two possible outcomes like being secure or an attack's validity.  I know what $\mathcal{O}(n^c)$ means mathematically, but why do cryptographers not use other kinds of time for so many thresholds?

I don't think that I'm asking quite the same thing as What does "running in polynomial time" really mean?

The focus on polynomial time comes from cryptography's historical origin as a branch of computational complexity.

It makes sense for a theoretical field to develop technology-independent ways of measuring efficiency. Actual clock time or number of clock cycles are technology-dependent. Talking about running time in an asymptotic sense is convenient because it makes specific technology irrelevant. No matter how fast machine A is compared to machine B, if machine A runs a $\Theta(n \log n)$ algorithm and machine B runs a $\Theta(n)$ algorithm, then eventually (for large enough $n$) machine B will be faster in terms of actual time.
Algorithms that run in time $\Theta(n)$ are objectively fast/scalable/"efficient".
Suppose an "efficient" algorithm makes calls to a subroutine (we don't count the cost of the subroutine against this algorithm), and the subroutine can also be realized by an "efficient" algorithm. Then, intuitively, the overall system (accounting for both the calling program & subroutine) should be "efficient" too. This is a basic composition property, and without it you have a very messy theory. Polynomial-time is the minimal way to define "efficient" that contains running time $\Theta(n)$ and enjoys this composition property.

It is for these reasons that "polynomial time" is synonymous with "efficient" in computational complexity. Its minimal nature makes it a natural and well-motivated definition.

However, just because it's well-motivated and natural doesn't mean it's sacred. Mihir Bellare points out asymptotic complexity as one of the arbitrary aspects of cryptographic research, to be critically examined.

As others have said here, there is plenty of work that follows a concrete (rather than asymptotic) style. There is nothing wrong with working in this style. The main differences are: (1) things are a little messier; you can't hide all the mess inside an unspecified polynomial; (2) you forfeit the (very convenient) composability property.


19 out of 24 words of BIP39 passphrase (brute-force last 5?) I have managed to lose 5 words of my 24 word Ledger Nano S recovery phrase. I have words 1-19 but I am missing words 20-24.
I have significant holdings on the wallet so would very much like to recover it if possible.
The passphrase is a BIP39 mnemonic (see https://github.com/bitcoin/bips/blob/master/bip-0039.mediawiki).
I have the bitcoin and ethereum public addresses for this mnemonic. I am wondering if it's feasible to brute force the passphrase.

Each word is 11 bits (2^11 = 2048 possible words).
The last (24th) word of the passphrase is of the following form [3 random bits][8 bit checksum].
Therefore I only have to check 2^(55 - 8) = 2^47 = 1.4x10^14 combinations.
I would have to compute SHA-512-HMAC with an iteration count of 2048.
As far as I understand, that means I'd have to compute 1.4*10^14 * 2048 = 2.87*10^17 hashes in total.

Is there any hardware out there designed for this? I am aware of ASICs that compute sha-256 hashes but not sha-512 hashes.
Perhaps I could tweak one to work with sha-512 since they are very similar.

Assuming a fairly typical ASIC hashrate of 1TH/s (10^12 hashes per second), I could exhaust the search space in 2.87*10^5 = 287000 seconds = 3.3 days. I'd probably get there sooner, of course (expected 1.65 days). Time is not something I am worried about. Even if I have to wait months, I don't mind - so if I can get 10GH/s at a reasonable price, that would be great.

I would really appreciate any help/information you could provide to help me out and make sure I haven't missed anything.
I could also use GPUs for this (I calculate I can run them at roughly \$1 / 10TH - so it would cost me \$28.7k to exhaust the search space, which I will do if there are no cheaper options).

Many thanks,
James

When you say that you have lost the last 5 words, are they completely gone or just difficult to read or invalid?

If you use a 48 vCPU Linode VPN, you can use BTCRecover can be used to recover 3 completely missing words in 6 hours, 4 missing words in about a 1.5 years. 24th word is actually just a checksum, so it isn't really missing...

I have a YouTube video on how to use BTCRecover and will be releasing one in the future that looks at the limits for 3-4 missing words, etc.

BTCRecover doesn't currently support using a GPU, but if that were implemented, that could easily speed things up by a factor of 10 and bring a 4 word recovery into a manageable time frame.

Either way moore's law in on your side, so you may just have an enforced 10 year HODL. Don't throw out the 24 word seed and keep the public addresses and their derivation paths that you know about. (keeping an xpub for a known account is even better)


enhanced hash password in bcrypt for nuGet library Why do we use EnhancedHashPassword in nuGet library and chose a SHA algorithm like this?

BCrypt.Net.BCrypt.EnhancedHashPassword(password,hashType:HashType.SHA512)

and when do we use the SHA algorithm after blowfish or before?

Why do we use EnhancedHashPassword in nuGet library and chose an SHA algorithm like this?

The Bcrypt uses a 448-bit key that makes a 56-byte password limit. Some libraries can drop parts longer than 56-byte of the passwords or don't accept it. This is not good, therefore before bcrypt a hash is applied to the password. This is the  EnhancedHashPassword method in the library and this may increase the entropy.

The nuGet library by default uses SHA-384 which has known resistance to length extension attacks. SHA-512 doesn't have.

  when do we use the SHA algorithm after blowfish or before?

We use the hash algorithm before. The aim is using all of the password information in the blowfish. This is achieved by hashing which can hash arbitrary length input into a fixed size.

Modern password hashing algorithm Argon2 doesn't have the small password weakness. It can accept a password up to  $2^{32}\hbox{-}1$ bytes. On the other hand, PBKDF2 has no theoretical limit except the standard limits of the utilized hash functions 1,2.


What is the forward cipher function of AES-XTS? We're using OpenSSLs EVP_aes_265_xts encryption on data (with unique, random, IVs for every new message encrypted) - which is working well.

But, I've been asked; what is the forward cipher function of this algorithm? I was going to say it's AES256, but am having doubts as to whether that's what the actual forward cipher function is defined as and/or encompasses!

Can someone give a little more of a precise answer as to what the forward cipher function is defined as for AES (256 bit) XTS?

Thanks!

With OpenSSL the forward cipher for EVP_aes_265_xts is AES 256. The key being 512 bits, internally split into two 256 bit keys for each of the AES 256 ciphers used within the XTS mode of operation.


Padding oracle attack, encrypting your own message My understanding of the encryption attack on a padding oracle is that the attacker has a set of $P_i$'s and $\operatorname{Dec}(C_i)$'s

I understand that by back calculating the attacker can find out $C_{i-1}$'s because we have

$$P_i = \operatorname{Dec}(C_i) \oplus C_{i-1}$$

This way the attacker can find all the $C_{i-1}$'s, but what happens with the very last $C_i$? Since you're starting from the end and going backwards, it looks like the very last $C_i$ wont get calculated, in which case the attacker isn't able to encrypt all of the message...?

EDIT:

So i've run the decryption attack and obtained all the $Dec(C_i)$' for an intercepted ciphertext (so a bunch of blocks of $C_i$'s). and then using that i have calculated a sample $P_i$. I want to generate my own $P_i$ now and encrypt it. So what i've done is i take each block of my sample $P_i$ and XOR that with $Dec(C_{i-1})$ to get a C_i, however, the issue is that the response doesn't seem to be valid. So doesn't $Dec(C_i)$ directly depend on what $C_i$ is being passed into it? The conclusion i've made is that the $Dec(C_i)$ Value changes based on each block of ciphertext that's being fed into it, so the $C_i$'s that i generated using the previous $Dec(C_i)$'s won't be decrypted correctly, because the actual program computes a new set of $Dec(C_i)$'s and based on those my ciphertext isn't correct ... does that make sense? or am i misunderstanding the whole thing.

I'm assuming you mean CBC mode, and let's say PKCS7 padding. I haven't heard of this attack before, and can't really find any sources (please link if you have one! How would an attacker end up with the $\operatorname{Dec}(C_i)$'s?), but here's one way to generate a valid ciphertext.

If the attacker is okay with 15 garbage bytes at the end of his message, he could do the following:

Send $IV = C_{i-1}$ and a random ciphertext block $C_r$ to the oracle a bunch of times. For a little more than 1 in 256 times, $C_r$ will end up having valid padding (e.g. 0x01 for PKCS7). The attacker can simply add such a block $C_r$ to the end of his ciphertext ($C_1, \dotsc, C_{i-1}$) to get a valid encrypted message, albeit with (usually) 15 garbage bytes at the end of the decrypted, de-padded message.