Reuse of a DH / ECDH public key I was wondering whether it is safe to use the same DH or ECDH key pair in more than one key agreement, particularly if these public keys are in a public registry. These public keys could be used by your counterparts (who also have their public keys in the same registry) to agree on a secret used to send you a message, even when you're not online. A user's public (EC)DH key is changed each time s/he goes online.

Is that system safe? Does reusing the same public key makes it more easy to solve its DLP?

EDIT : When I meant to use a public key in more than one key exchange, I meant it will be used with different counterparts.

Using DH when both sides have static public keys (always send the same message when running the DH protocol) doesn't make DLP easier. It does increase the value of the secret key.

There are some things to worry about. If the DH shared secret or one of the secret keys is compromised, the compromise is complete. This is mitigated if the static public keys are replaced often.

In ordinary DH, the shared secret is a one-time secret. With static public keys, you have a multiple-use secret. You need to be very careful when using this key.

You should also be aware that DH where only one side has a static public key is essentially equivalent to ElGamal encryption...


Question about the definition of a secure PRF I'm taking a cryptography introduction course, and we're covering the definition of a secure PRF.

I understand the test goes as follows: A challenger picks a function $f$ such that

$f \leftarrow \left\{
     \begin{array}{lr}
       b=1: k\leftarrow K, f\leftarrow \left(k,\cdot \right ) \\
       b=0: Funs \left(X,Y \right )
     \end{array}
   \right.$

Where $Funs(X,Y)$ is the set of all possible PRFs, The entire experiment is defined as $EXP\left(b \right )$, such that the output is the adversary's guess as to whether or not the challenger chose a function at random. A secure PRF is then defined as the conditions where

$\left | Pr\left[EXP\left(0 \right ) =1\right ] - Pr\left[EXP\left(1 \right ) = 1\right ] \right |$ is negligible. Or in other words, when the probability that the attacker's result is zero minus the probability that the attacker's result is one is negligible.

However, what if the adversary's detection method always returns one? This would imply that the cipher is not secure, but that can't be true.

What am I missing here?

You have the math right, but you seem to have mis-interpreted the formulas.  So, let me try to walk you through it.

The "advantage" of an attack is the difference $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]|$.
The advantage is a measure of how effective the attack is.  If the advantage is large (significantly greater than 0), the attack is successful (and the function is not a secure PRF). If the advantage is negligible, the attack is ineffective.

You suggested we look at an attacker whose algorithm always returns one.  In this case it turns out that the advantage is 0: in particular, $\Pr[Exp(0)=1] = \Pr[Exp(1)=1] = 1$, so $|\Pr[Exp(0)=1] - \Pr[Exp(1)=1]| = 0$.  Since the advantage is 0, this attack strategy is ineffective -- exactly as you'd expect.


Blind quantum computing and fully homomorphic encryption I am somewhat familiar with current research on fully homomorphic enryption schemes and their possible application to Cloud computing.

I've just noticed (somewhat late) that a marketing-savvy group of Physicists working on quantum information is approaching the same possible application: they call their approach blind quantum computing.

Is this a serious contender with respect to the claimed application (the group's reputation in Physics is not in doubt) and are there any significant similarities between the two approaches on a fundamental level?

Well, since I'm one of the authors on the paper, let me try to answer your question.

First I should explain that the paper you link to is not the original paper proposing that approach, but rather the first implementation of it (in this case using quantum optics). The original paper which introduced the Universal Blind Quantum Computing (UBQC) protocol which the experiments demonstrate was written by myself along with Anne Broadbent and Elham Kashefi, and appeared at FOCS in 2009, so at least some people in the CS community took us seriously. I should also point out that of the three of us, only I am a physicist. Elham and Anne are both computer scientists. Indeed Anne's PhD supervisor was Gilles Brassard, one of the Bs in BB84, and one of the discovers of quantum key distribution.

One might ask why our original paper doesn't reference fully homomorphic encryption, but that is easy to answer. It simply didn't exist when we wrote the paper in 2008.

As David Cash mentions in the comments above, UBQC is a quantum protocol, and hence requires quantum information processing, meaning at least some quantum computational abilities. It is certainly not something you can expect to deploy tomorrow, and any large scale version of this kind of thing is likely decades off. We worked with one of the top experimental groups to implement it, and still only managed 4 qubits (essentially hiding a 12 bit description of the circuit).

Now, we're certainly not the only ones to have written about the concept of blind quantum computation. The term is taken from a 2003 paper by Arrighi and Salvail which introduced a non-universal blind computation protocol, although there was earlier work by Childs. A few months after us, and apparently independently, Aharonov, Ben-Or and Eban came up with a similar idea in the context of interactive proofs.

There are some important differences between blind quantum computing and homomorphic encryption. First, blind computation and homomorphic encryption are fundamentally different in what they seek to achieve. In blind computation the aim is to have a remote computer perform a computation for you in such a way that it remains "blind" to the computation (i.e. the input, output, and the actual computation performed), and should only learn upper bounds on the resource requirements. In homomorphic encryption the situation is somewhat different, since while the intention is indeed to hide the input and output, the computation itself is known to the remote computer and not necessarily to the user. This is a fundamental difference in the goals of the various protocols. Secondly, protocols such as ours and the Aharonov-Ben-Or-Eban approach, take measures to ensure that the remote computer cannot interfere with the protocol without being detected, which is in completely the opposite direction to homomorphic encryption. Thirdly, there is a fundamental difference in security. Many of the blind quantum computation protocols are information theoretically secure, meaning that they are secure independent of the computational power of their adversary. This is not true of current schemes for fully homomorphic encryption. And, last, but certainly not least, blind quantum computing allows you to essentially boost the computational power of the user, in computational complexity terms, expanding the class of decision problems they can solve from P to BQP, which contains certain problems believed to be NP-intermediate problems such as factoring, which is not something fully homomorphic encryption currently allows for.

Let me close by saying why I think people should be interested in blind quantum computation. As I have said, as a tool for cloud computing, practical technologies would be decades off, and I certainly don't want to be guessing the future that far in advance. Rather, I would suggest, the main reason people currently find such protocols interesting is because of their possible consequences for the study of complexity classes, and as a practical means for verifying that purported quantum computing technologies do indeed function correctly (which is a non-trivial task since BQP is believed not to be contained in NP, and hence there exist no efficient means to verify the outcome of certain quantum computations after the fact).

I hope this helps answer your question.


Current mathematics theory used in cryptography/coding theory What are the mainstream techniques borrowed from algebraic geometry (or some other branch of mathematics) which are currently used in cryptography/coding theory? I've only heard about a small subset of elliptic curves and hermitian curves. I've also heard about research of hyperelliptic curves but I don't know if some software has already implemented it.

Could you mention some other branches of mathematics being strongly used in cryptography/coding theory and its state? (mainstream/in research)

Finite fields - which is a branch of algebra - is a must. It is, in some way, used in almost all types of cryptographic algorithms.

Also, you need some sort of basic programming ability since you will need to calculate time and space complexity of cryptographic algorithms. An "Algorithms" course  taken from a CS  department would be very useful.

My advice is, you can read the  first 2-3 chapters of Rudolf Lidl' s Finite Fields book. You don't need to understand every little detail in the book, just read that part and get the general idea, and that would be enough for the beginning.

But the bible for the beginners in cryptography is definitely, "Introduction to Cryptography" by Washington and Trappe. It is the most basic book amongst all in addition to being very  comprehensive. It  has a solution manual and nice exercises that you will enjoy solving. I personally learned a lot from it. Trappe covers almost every basic thing that you need to know as a beginner.


If I know an element and it's inverse, can I learn the modulus? If I know an element $x$ in a group, and it's inverse $x^{-1}$, can I guess the modulo, or with a probability?

As said in the comments above, you have that $x \cdot x^{-1} = 1 \mod n $.
Another way to say that is $k \times n=(x \cdot x^{-1}) -1$

So no, you can't always find the exact value $n$ from $x$ and $x^{-1}$.

Take $x=12 \ $ and $x^{-1}=17$. You have $x \cdot x^{-1} = 204$.
So $n$ is a divisor of $204-1=203$, meaning, $ n \in \{29,203\}$ (other divisors are smaller than $\max(x,x^{-1})$ so they can't be $n$)

The only cases where you can find $n$ is when the only divisor of $kn$ greater than $x$ and $x^{-1}$ is $kn$ itself. In this case, $n=kn=(x \cdot x^{-1}) -1 $


Is the PCG PRNG a CSPRNG, or why not? Is the PCG family of PRNG algorithms cryptographically secure, and if not, what about them makes them inadequate for that?

I have a good enough understanding of the general problem space that if you mention something like "backtracking resistance" and give a sentence summary of what it means, I can connect the dots enough to understand why it matters for security.

I have a (likely incomplete) understanding of what it takes to make a cryptographically secure PRNG - for example I know that resistance to predictability or backtracking matters, ideally resistance that stays strong even as the attacker learns more outputs of the PRNG or learns bits of the PRNG's internal state.

But I lack the deep experience and knowledge needed to actually evaluate PRNGs myself to figure out if they meet any of these properties, or to be confident that I haven't missed something.

I do know that PCG was not designed to be suitable for cryptography - it seems to have been optimized for good statistical properties and efficiency of producing outputs.

I have also found people saying that PCG is not cryptographically secure.

But what I have not found is any actual analysis of PCG - any write-up explaining what properties it fails to fulfill, and so on.

I've looked a bit more into it and there is one PCG type with a 128 bit state, where the output is marginally decoupled from the internal state.
PCG is a suite of algorithms to generate pseudo-random numbers that have been created on top of existing lightweight random number generators so that they:

stay lightweight;
pass the various statistical randomness tests;
are possibly less predictable.

Now only the 3rd part is of interest with regards to cryptography. However, all but one of the algorithms seem to have a state of 64 bit or less (if I discount the one that has been deemed insecure by the author). That makes them directly unsuitable for cryptographic random number generation.
That leaves us with PCG-XSL-RR, the only one that makes any claim to be secure. This seems to have been accomplished by adding a XorShift on the state and a few very simple operations to derive the output of the state:
output = rotate64(uint64_t(state ^ (state >> 64)), state >> 122)

Although there are certainly very simple stream ciphers, it seems to me that we need analysis to see if many outputs cannot be used to derive the state bits. As long as that analysis is not performed, just stating that it might be secure, and that the prediction difficulty is "challenging" doesn't make a cryptographically secure algorithm.
Personally calling it "secure" is therefore unwarranted. Listing the prediction difficulty as "challenging" means using weasel words to indicate that no sufficient analysis is performed and that the security of the algorithm is unknown. If the state can be retrieved then the algorithm would be fully predictable after all. Without knowing the details of how much output is required for such an unknown attack, how can we have any trust in that statement?

Now that was putting it very black and white, and even accuses the author of incorrect statements. However, we have to consider all the statements made by the author of the algorithm to at least partially exonerate her:

I know that if I were trying to predict a random number generator, I'd want something easier than the PCG family. But if I wanted actual crypographic security for secure communication, I'd probably want to use something that has been around longer and seen more scrutiny.
Hopefully as time passes, the PCG generation scheme will receive scrutiny from people with far more expertise in crypographic security than me, and we will have a clearer picture about how easily it can be predicted. With that in mind, I hope to offer some crypographic secuity challenges in the future to encourage people to try to break it.

So please consider it insecure until analysis has shown otherwise, and maybe use a generator where the words "cryptographic" and "security" are spelled correctly, preferably with the word "analysis" attached to it...


Performance metrices of cryptographic algorithms I'm a beginner and working on cryptography performance metrics.

My question is that what are the important metrics to check the performance of Cryptography Algorithms.

Criteria for evaluation of Cryptography Algorithms:

Having public specification (the only secret is the key).
Patent status.
What it aims at: block cipher (DES, AES..), cipher, message digest, MAC, proof of origin, signature, key establishment, TRNG, PRNG.
Requirements for and limitations of the algorithm itself.

Randomness requirements;
Requirements to validate the input parameters (e.g. public key for ECDH).

Being symmetric (block ciphers, SHA) or asymmetric (RSA, ECDSA, ECDH).
Security under some threat model:

Resistance to key recovery (bounded at least by key size);
Block size (for block ciphers);
Resistance to pure cryptanalytic attacks;
Resistance to side-channel leakage (with many subdivisions);
Resistance to fault injection.

Complexity and familiarity / learning curve to use the algorithm.
Parameter sizes:

Output size (overhead / expansion ratio);
Encoded (public) key size;
Accepted input sizes;

Speed (often very platform-dependent):

Cycles/byte averages for large messages or multiple uses with the same key;
Time to setup a new key;
Time versus size.

Memory footprint:

Code;
RAM per running instance.

Availability of a version with suitable characteristics as above on a given platform.
Acceptance by security authorities.

Note: fell free to restructure / add to the list, this is a community wiki.


How to encrypt/decrypt data in an SPI BIOS FLASH I need some info/suggestions about the cryptographic algorithm that make me sure that the executed bios by the CPU is an authenticated bios. The check has to be performed by a FPGA.

I have SPI Flash that contains the bios code ( assembler code ), CPU and  FPGA between CPU and SPI Flash.

The first idea was to authenticate the bios performing a HMAC authentication of the data stream between CPU and flash, but I saw that the stream is always different so impossible to authenticate ( the bios/CPU waits the wake up of the peripheral so perform each time different operations ).

The second idea is to encrypt the whole SPI flash and decrypt on fly with FPGA when the CPU request the data. I actually don't know if FPGA is enough fast to do this, but I'm sure I can't use an AES 128 because the FPGA isn't so fast to fetch 128 bit to decrypt only 32 bit ( during the bios execution there are a lot of memory jump and usually the fetched data are 32 bit for each CPU operation ).

Encryption does not imply authentication. With most unauthenticated encryption algorithms an attacker can cause at least random changes to the plaintext by modifying the ciphertext. Some algorithms are malleable, which means the attacker can even cause (some) changes they want.

Therefore, even if you could find a secure encryption algorithm that works quickly enough, it would not be enough to authenticate the BIOS. For that you need something like HMAC, which you mention. If you don't know the order the data is used in, and cannot afford to calculate a MAC over the whole data in advance, you could use several MACs for parts of the data. In that case you would also need to make sure the location of the data is authenticated (i.e. included in the "message" of the MAC) so an attacker cannot reorder the authenticated data blocks

Note that with symmetric keys the same key is used to both generate and check the MAC. That means the FPGA needs to know the key and an attacker with access to it would be able to use that key to forge another BIOS. To prevent that you would need to use asymmetric signatures, so that even if the attacker got the public key used to verify it, they couldn't forge new signatures. (They could still be able to replace the public key with their own, of course, which would allow then to sign whatever.)


How can we build a ZKP simulator for “Were is waldo?”? The following link illustrates two possible methods for solving the "Where is Waldo?" puzzle in zero knowledge.
http://www.anagram.com/jcrap/Volume_0_1/crv0n1-3.pdf

Let's consider the first method:

How can a Simulator be built for any of the method described above?

I believe that the question above can answered only once the protocol view has been defined. And here is where I am stuck.

One option is to define the view as a video recording of the interactions between Alice and Bob. This video should also include the full cavity search performed by Bob on Alice as this is part of the interaction.
If this is the view used for the protocol, how can a simulator build this view without having knowledge of Waldo's position?
After the cavity search has been performed, Alice (or whoever impersonates Alice) must have knowledge of Waldo position in order to complete the protocol successfully.

If the cavity search is omitted by the recording, then a simulator can build a view without having knowledge of Waldo's position as the cut-out image of Waldo can be replaced with any image of Waldo.

However, I believe that the cavity search should be part of the recording as it is part of the interaction between Alice and Bob.

I think that it would be more suitable to model this as witness hiding, meaning that after the proof it should be still be "computationally hard" to find Waldo. The best place to learn about witness indistinguishability and hiding is either in Oded Goldreich's Foundations of Cryptography (volume 1), or in Uri Feige's PhD Thesis.

In general, witness indistinguishability is a property that just says that it's not possible to distinguish which witness the prover knows. It is not hard to show that zero-knowledge implies witness indistinguishability, but it gets more interesting. For example, parallel repetition of witness indistinguishable proofs preserves witness indistinguishability and reduces soundness. Thus, it is possible to construct 3-round witness indistinguishable proofs for any language in NP (something that is not possible for zero knowledge, at least not for black-box zero knowledge).

Feige also defines witness hiding, which means that if a language is hard and one cannot extract a witness, then even after the proof the verifier cannot extract a witness. For example, consider a randomly sampled tuple $(g,h,g^x,h^x)$. Then, a prover could prove that this tuple indeed is of this form (what we call a Diffie-Hellman tuple) using a zero-knowledge proof. Alternatively, in some cases it may be enough to just prove that it is of this form in a way that ensures that a cheating verifier cannot learn $x$ (or any other witness to this fact). As such, witness hiding is the "one-way function" analog of zero-knowledge; it is much weaker, but makes sense in some cases. Feige showed that any witness indistinguishable proof with two "computationally independent witnesses" (meaning that one cannot learn one witness without the other) is witness hiding.


Using master password to encrypt and decrypt user credentials I need a way to store third party credentials, and I want to avoid storing passwords in plain text. I can't use a hash because I will need to be able to get the raw password to log in to the third party service.

My idea is to use a master password that I enter on the startup of the service that will be used as a key to encrypt and decrypt the users third party information. The only flaw that I see with this method is that I (or anyone who can somehow get the master password) will have access to user data for the third party service.

Alternatively, the user can enter their third party login credentials when accessing my service, and my service can access the third party site. However, the service is supposed to run 24/7 and this method would require them to reenter their login credentials every 8 hours rather than only once.

Are there any significant flaws with either of these methods, or is there any better approach to solve the problem?

It's true that anyone who learns the master key has enormous leverage.  Key management best practices are worth investigating.  I highly recommend that you consider using a key management service (KMS) that is backed by a hardware security module (HSM).

There are affordable offerings in cloud-based services, such as Amazon's Key Management Service, that allow you to retrieve a key from their service and use it locally.  Alternatively you can use a cloud-based KMS to encrypt by transmitting plaintext data to the service, and receiving a reply consisting of ciphertext and a reference to a key (decryption consists of sending the ciphertext back to the same service along with the key reference).

Of course using a cloud-based service requires that you authenticate with the service, and that means transmitting credentials to it at some point.  You can make this process more secure by configuring the KMS to accept communication from a limited set of IP addresses.  Also, your KMS authentication credentials could be encrypted and stored at rest in the form of ciphertext.  The unencrypted KMS credentials could exist in RAM for a duration that you determine (your original post said every 8 hours, which seems adequate).  The method for decrypting the KMS credentials could be that you supply a password which gets converted to a key that could then perform the decryption.  Then let the KMS do the rest of the encryption work.


Is it reasonable to consider that an encryption scheme must be invertible? I am in a dispute regarding a test question in an exam.
The question is something like that:

What would happen if one were to use RSA with $n=100$ and $e=13$ to
encrypt a message $m$?
a) You would be able to encrypt the message but not decrypt it.
b) You would not be able to encrypt the message.
...

Both parties agree that the operation $c = m^e \bmod n$ (a transformation known as encryption when using proper RSA) is no longer bijective, as $n$ is not the product of two primes. For example, $m=10$ and $m=20$ would both result in "cryptogram" $c=0$.
I consider that an encryption function must be invertible, as the purpose of encryption is to hide information from non-authorized eyes while allowing authorized parties to retrieve it. The fact that this transformation (which I'd argue could not even be called RSA, as $n$ does not fulfill RSA's rules) is not bijective means that it is not invertible, so it cannot be considered encryption. I would say that, under this assumption, any discussion of encryption/decryption is pointless, and if one answer had to be marked, it should be B: we cannot call $c = m^e \bmod n$ "encryption".
On the other hand, the other party sustains that the only correct answer is A, and that "it is fallacious to believe that encryption must be invertible, as there are many non-invertible encryption schemes". They are not available for questioning, so I cannot seek further clarification about what they meant. I assume they meant cryptographic hashes, but I would not consider them encryption schemes, but cryptographic primitives.
My question is therefore two-fold:

Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption?
If I am correct: Could I be pointed out to some reputable bibliographic source to use to strengthen my case?
If I am incorrect: Is it because cryptographic hashes are considered encryption schemes or because there truly are non-invertible cryptographic schemes? If so, how do they meaningfully differ from hashes?

Am I correct in assuming that it is not wrong to impose the condition that a transformation must at least be invertible in order to be considered encryption?

Yes, strictly speaking: Encryption is the process of turning a plaintext message into a ciphertext (encryption) which then can later be turned back into the original plaintext (decryption).

If I am correct: Could I be pointed out to some reputable bibliographic source to use to strengthen my case?

Gary Kessler has published An Overview of Cryptography.
In chapter 3 "Types of cryptographic algorithms" you can see that there is a distinction drawn between encryption and hash functions.

If I am incorrect: Is it because cryptographic hashes are considered encryption schemes or because there truly are non-invertible cryptographic schemes? If so, how do they meaningfully differ from hashes?

Encryption, decryption and cryptographic hashes all belong together in the realm of cryptography but they can definitely not be used interchangable (see this earlier answer from a different question). Some differences include:
Reversability
Encryption schemes can usually be transformed back into their original form, i.e. a once encrypted plaintext message can usually be decrypted back into the original plaintext. Hashes, on the otherhand, are created in a manner that the input undergoes a loss of information, ultimately making it irreversible.
You can always create a hash from a given input but it's not possible to be sure what the original message once was if you're only given the hash (see pigeonhole principle).
Keys
Encryption schemes always use keys. Hashes do not require keys.
Length
A long plaintext message results in a long encrypted ciphertext & a short plaintext message results in a short encrypted ciphertext.
Hashes will always have a predefined length, no matter the input.


Are there Guaranteed Proof-of-work Systems? Proof-of-Work systems such as hashcash, it seems to me, do not actually prove that a certain amount of work has been performed. For example, in the case of hashcan, could not the first random hash choice just get lucky? Thus almost no actual "work" was performed?

My question is on the existence (and practicality) of methods that guarantee, within a probability, that a given minimum amount of "work" has been performed in each and every case, without compromising the average or maximum amounts.

On hashcash then, the probability of failing to prove work is the chance of "getting lucky". So, with a 20 bit zero hash target, that's around a few in a million (the first few random attempts out of a 2^20 space). Therefore a few in a million hashcans won't really be doing any work. But if i wanted to reduce this proof-of-work fail to a lower probability, simply increasing the zero bit space does not work, since it also drastically increases the average work.

To compare this to, say, the workload of compressing a file (eg zip). That's a much more controllable amount of work, roughly proportional to the input length.

Say we manufacture an unpredictable text generator, fed into zip, fed into a hash function. The proof of work is the generator seed and the final hash value. the generator output length controls the amount of work and saying you could "guess" the final hash is virtually impossible (compared to say 1:2^20).

But this example is not practical because it is symmetric, requiring the same work to be performed for verification.

so, are there any guaranteed (within probability) asymmetric proof-of-work systems?

You could use a challenge consisting of multiple subtasks.

For example, provide a unique random string of characters $R$ and ask for $n$ distinct strings that have $R$ as a prefix and whose SHA256 sum ends in $z$ zeros.

In a single hash calculation, the probability of a lucky guess is $2^{-4z}$, so the probability of multiple lucky guesses in one challenge is going to be very small if $z = 10$.

The number of SHA256 calculations needed to pass the challenge is of the order of $n \times 2^{4z}$, but only $n$ hash calculations are needed to check the results (plus a little extra to check that no two strings are the same).


Schnorr NIZK over Ed25519 I am trying to implement the following Schnorr non-interactive zero-knowledge protocol: https://tools.ietf.org/html/rfc8235#page-7

I'm using the libsodium 1.0.16 and GNU MP libraries.

I just can't seem to get it working. Here are some questions:

    In the setup of the scheme, Alice publishes her public key
    A = G x [a], where a is the private key chosen uniformly at random
    from [1, n-1].

    The protocol works in three passes:

   1.  Alice chooses a number v uniformly at random from [1, n-1] and
       computes V = G x [v].  She sends V to Bob.

   2.  Bob chooses a challenge c uniformly at random from [0, 2^t-1],
       where t is the bit length of the challenge (say, t = 80).  Bob
       sends c to Alice.

   3.  Alice computes r = v - a * c mod n and sends it to Bob.

   At the end of the protocol, Bob performs the following checks.  If
   any check fails, the verification is unsuccessful.

   1.  To verify A is a valid point on the curve and A x [h] is not the
       point at infinity;

   2.  To verify V = G x [r] + A x [c].

Regarding step (3) on the computation of r = v - a * c mod n it means that this step is using regular modular arithmetic?

Regarding step (2) on the verification V = G x [r] + A x [c], can you please explain how that would hold? Is the following equivalent: V = ed25519_scalarmult(r, ED25519-BASE) + ed25519_scalarmult(c, A) where ed25519_scalarmult(scalar, point i.e. publickey)? And most importantly that + is Ed25519 point addition?

Regarding step (3) on the computation of r = v - a * c mod n it
  means that this step is using regular modular arithmetic?

Yes.

  Is the following equivalent: V = ed25519_scalarmult(r, ED25519-BASE) +
  ed25519_scalarmult(c, A) [...]?

Yes, see also section 1.2 (near the end) where it says "P x [b]: multiplication of a point P with a scalar b over E(Fp)".

  And most importantly that + is Ed25519 point addition?

Yes, that is indeed the case, + represents the group operation here, which is modular-reduced multiplication for the finite field and point-addition for the EC case. This can be seen when looking at section 2.2.

  V = G x [r] + A x [c], can you please explain how that would hold?

I'll use a slightly more tense notation ($\xleftarrow{\$}$ means that the variable on the left is sampled uniformly at random from the set on the right).

Pick and publish your public key $A=[a]G$ with $a\xleftarrow{\$}\{1,...,n-1\}$
Pick $v\xleftarrow{\$}\{1,...,n-1\}$, send $V=[v]G$.
Pick $c\xleftarrow{\$}\{1,..,2^t-1\}$, for some security parameter $t$, send $c$
Compute $r=v-a\cdot c\bmod n$ and send $r$.

Now the question is why $V=[r]G+[c]A$ holds in an honest protocol execution. Well $$[c]A+[r]G=[c\cdot a]G+[v-a\cdot c]G=[c\cdot a+v-a\cdot c]G=[v]G=V$$


Implementing a zero-knowledge proof I'm trying to get my head around zero-knowledge proofs and my definition of a zero-knowledge proof is as follows.

  A zero-knowledge proof is a method by which one party can prove to
  another party that they know a secret value, without sharing any
  data about this secret value.

To implement a zero-knowledge proof some data will need to be exchanged.

With that in mind, is the following assertion correct?

To implement a zero-knowledge proof, data can be exchanged but this data should not contain any information about the secret value?

If the above holds true, could a digital signature be classified as a zero-knowledge proof?

Your initial definition is imprecise

A zero-knowledge proof is a method by which one party can prove to
another party that they know a secret value, without sharing any data
about this secret value.

This is not merely a zero-knowledge proof, but it is a zero-knowledge proof of knowledge. A zero-knowledge proof is more general, it can be proving a statement that may or may not relate to a secret.

Is the following assertion correct?
To implement a zero-knowledge proof, data can be exchanged but this
data should not contain any information about the secret value?

No this assertion is too loose. Not only the data must not contain any information about the secret value, but it must not contain any new information, or anything that could not have been generated without knowing the secret.
A digital signature is a piece of data that cannot be generated without knowledge of the secret. It is a proof of knowledge, but it is not zero-knowledge because it is leaking some information.
I can take that signature and use it on its own, to claim the following statement: "someone knows the secret". This was not possible before the exchange.
All of the data exchanged must be trivial to create on its own, the proof is only valid from the point of view of the verifier producing the challenges, in a statistical sense.


How to prove that the concatenation of two secure PRG is secure? Given $G:\{0,1\}^s \rightarrow \{0, 1\}^n$ a secure PRG, how can one prove that $G'(k_1, k_2) = G(k_1) \cdot G(k_2)$ is secure ($\cdot$ means concatenation)?

In other words, I'd like to show that if there is a distinguisher for $G'$ then this implies that there exists a distinguisher for $G$.

For example, could this distinguisher be as follows?

$A(x) = \text{round}(\frac{1}{2^n} \sum_{y \in \{0,1\}^n} A(y \cdot x))$

Since this looks like homework, I'm not going to answer the question directly (and I hope others won't either), but I'll just give some hints:

You're on a good direction.  If you want to prove that $G'$ is a secure PRG, then your general approach (trying to show that a distinguisher for $G'$ implies a distinguisher for $G$) is a good strategy.  Keep at it.
Your particular distinguisher $A$ is not an effective distinguisher against $G$.  Hint: What is the running time to compute $A(x)$?
You can probably fix up your distinguisher (to get the runtime down to something reasonable), but that's working harder than you need to.  Instead, you might want to read on....
Have you heard of the notion of a "hybrid argument"?  If yes, can you see any way that it might be relevant?  If no, go read up on "hybrid arguments"; they are a fundamental and important proof techniques for proving indistinguishability/distinguishability.


K-dimensional equidistribution - how big are periods of PCG? I'm trying to figure out what is period of PCG generator XSL-RR-RR:
https://www.pcg-random.org
https://en.wikipedia.org/wiki/Permuted_congruential_generator
If we use just random multiplier and increment in LCG in that PCG. M. O'Neill wrote:
"For the PCG family, arbitrary k-dimensional equidistribution (and the huge periods it implies) requires PCG's extended generation scheme."
It looks like their generators has big periods, XSL-RR-RR too. But I can't find accurate information about that. She proved somehow that they are k-dimensional equidistributed. But what is k exactly, what periods it implies and could it be the same with every parameter of LCG in XSL-RR-RR? She tested some specific multiplier and increments so maybe other ones have worse parameters and periods?
I don't understand exactly why she use just some specific miltipliers (two ones if I understand it well) and increments in XSL-RR-RR. What will happen if we will use other, random ones?

PCG is just LCG where the output is run through a transformation. The amount of internal state of the PCG - which is what controls the period - is all contained in the underlying LCG. So the period is $2^n$ where $n$ is the number of bits of state. The only thing to worry about is if the output transformation makes the period smaller, but since it's a permutation it does not.
When pcg-random.com talks about "arbitrary" period, they just mean that they have a way to make the internal state arbitrarily large. For a given state size, the period is the same as other algorithms of the same size.


Origin of values for "security margin"? It seems that the acceptable "security margin" for ciphers is set to be between 25% and 30% as a target by designers, where this number represents the number of rounds that remain "unbroken" for a certain worse-case attack.   It is all too eerily empirical from a field that dislikes that sort of thing considering that the security margin tends to decrease over time as attacks improve.

Is there a historical reason for picking this arbitrary number or is there just a consensus that better than 25% is good enough?

There is not much reason behind this particular number, but I think that the AES cipher stands as an example. By the time of its selection as AES, Rijndael-128 had 7 out of its 10 rounds broken, though for the 7-round attack it was not clear then if it is better than the exhaustive search. So the security margin was about 30% that time. Now, as the attacks have de-facto advanced by 1 round only (the biclique attacks have only a small constant advantage factor), it is understood that the security margin was well chosen and it made sense to have it 30%.


How to make the interactive Schnorr identification protocol become non-interactive I am reading about ZKP and I found this interesting question about changing this protocol from  interactive Schnorr identification protocol to non-interactive and I need help in solving it :

Peggy (prover) and Victor (verifier) have shared primes p,q such that q|p-1 and a generator $g$ such that $1<g<p$ and $g^q=1 \bmod p.$

Peggy has a private key $s$ and a public key $v=g^s$ ($v$ is known to Victor). Peggy wishes to convince Victor that she knows the secret exponent s without revealing what s is. She performs the following interactive protocol with Victor.

Peggy chooses a random $r$ from $[0,q-1]$, calculates $x =g^r \bmod p$, and sends $x$ to Victor.
Victor chooses a random challenge $e$ from $[1,\ldots,2t-1]$ where $t$ is a security parameter and sends $e$ to Peggy.
Peggy calculates $y = r-se \bmod q$ and sends it to Victor.
Victor checks that $x= g^yv^e \bmod p$. If so, then Victor “accepts”; otherwise, Victor “rejects”

The most common way to change an interactive Schnorr protocol into a non-interactive one is to rely on a random oracle. This is the so-called "Fiat-Shamir heuristic".

Notice that a transcript in your case would look like $(r, e, y)$, where $e$ is the challenge the verifier sends to the prover.
Now, you want to get rid of any interaction with the verifier to get that random challenge $e$, so what you need to do is to find a way to get rid of that interactive challenge. And there, you could have a random oracle giving you the challenge instead of the verifier.

In practice, this is done using a cryptographic hash function $H$ and so your transcript becomes $(r, H(r), y)$ or, as on Wikipedia: $(r, H(g,y,r), y)$. (It is important to include the public parameters in your Fiat-Shamir, to avoid problems such as weak Fiat-Shamir heuristics.)

Now, you can still verify that it works just like the interactive case, excepted we don't need to ask Victor, the verifier, to provide us with a random challenge anymore, since both the prover and the verifier can compute the challenge out of the rest of the data in a non-interactive way.


Is it safe to AES-CBC and AES-CMAC both using the same key? There is a very similar question (Using a derived key for CMAC) but it doesn't quite answer this one (at least for me it does not).

I have a situation where I need to transfer some data. My data has variable length (but padded to 16-byte blocks, of course) and I encrypt it using AES-128 in CBC mode. It is done like this:

I first prepend the data with last 16 bytes of previous ciphertext I sent out, append data if it needs to round to 16 byte block, and then finally encrypt it. Therefore my plaintext looks like this: [random_16_bytes_as_IV] [DATA] [PADDING]
Then I calculate AES-CMAC over the entire ciphertext (using the same key used for encryption) and append it to the ciphertext and finally transmit to the receiver. So my transmission looks like this: [CIPHERTEXT] [CMAC]
Receiver receives, verifies the AES-CMAC, decrypts and discards first 16 bytes of IV and whatever was appended for 16-byte block padding.

A while ago it was suggested to me to use AES in CBC mode along with CMAC for a pet-project I am working on (Is this an acceptable implementation of ARC4 encryption for my system?) and now I wanted to check if this is the right way to do it. Even though it is a pet-project I should at least give my best to do it correctly.

My concerns are bolded above. Also, please note that those 16 bytes that I prepend are actually the AES-CMAC of preious transmission, maybe I should not use those 16 bytes but use the last 16 bytes of actual ciphertext instead? - or it doesn't matter since they are both known from previous transmission...

The answer is simple.
The recommandations of all experts in this case is to dissociate Keys used for Encryption from Keys used for MAC-ing.
Then you have to use two different Keys.


How can one share information using the 'host-proof' paradigm? I am attempting to make a web-based secure password management and sharing utility, both as an academic exercise and to fully understand and feel safe about using it.

I really like the idea of a "host-proof" application, where encryption/decryption is done on the client side using javascript and only encrypted information ever leaves the browser, much like PassPack or Clipperz. What I cannot figure out is how Passpack manages to allow people to share passwords. I cannot see how it can be done without either plain text or an encryption key being transferred to the other user via the server, making that process inherently break the "host-proof" paradigm.

Can anyone point me towards a solution?

Getting data from user A to user B securely generally works via asymmetric encryption. Encrypt the data with B's public key and store the result on the server. B then retrieves the encrypted data and decrypts it using his private key.

This assumes the server does not store the private key, or at least stores it in a form that can only be decrypted by the owner.


persisting sensitive binary data encrypted (+integrity) [#not_a_crypto_expert]

rather than forming the question by the techniques I'll describe the use case:

I'm persisting blocks of sensitive binary data in a remote store, the communication is secure (lets assume), but the store may not be.

The data needs to be sent and stay encrypted on the remote store - it doesn't get decrypted immediately, just stays encrypted until some time when it's needed.
The data needs to have proof that it was not altered
The data needs to have proof that it came from the source
block i+1 should have proof that it is the following block of block i

Putting the last requirement aside for a sec, what I have in mind it the following:

Encrypt the data with the user's private key (for authenticity)
Encrypt the data with the server's public key (for encryption) with symmetric encryption
MAC the ciphertext for integrity
Send the encryption + MAC

Thoughts about the above:

While I think it has the desired security properties it's an awkward use of symmetric encryption - as the data is not immediately decrypted on the other side, but instead remains encrypted for a long time which will require saving the symmetric secret for a very long time - which I think is not the typical case.
If I just replace AES symmetric encryption above with encryption with the server's public key - I'm not sure this preserves the security properties of the MAC then encrypt.

Thanks,
Z

There are at least two ways to do this:

Using asymmetric encryption. This may be advantegeous if you want to use hardware-enforced keys or something like that. However, such keys tend to be "weak" for long-term storage (in a theoretical sense).
Using symmetric encryption. This may be advantegeous as you can easily use a password or a hardware-enforced AES key to do this. However such devices are much rarer than those supporting e.g. RSA.

Now classically you would do the following:

Encapsulate the data's symmetric key using asymmetric and / or symmetric encryption and / or key derivation methods.
Encrypt each block using said data key and an authenticated encryption mode (e.g. AES-CCM, AES-GCM or AES-EAX), using the index as the nonce.
If you use asymmetric encryption: Compute a signature over the complete ciphertext and store it for later verification (because an attacker could use the public key to just replace the data).

Now the data is immune to re-ordering attacks (because the authenticated nonces would miss-match).


ElGamal encryption of concatenated messages Suppose an encrypter separately produces three ElGamal ciphertexts $c_1 = E(m_1)$, $c_2 = E(m_2)$ and $c_3 = E(m_3)$, which encrypt the messages $m_1$, $m_2$ and $m_3$, respectively.
Is it possible for the encrypter to prove with a zero-knowledge proof that $m_1$ = $m_2 \mathbin\| m_3 = m_2 \times 2^{32} + m_3$, i.e., that $c_1$ encrypts  the concatenation of the messages $m_2$ and $m_3$?

(added by moderator to summarize exchanges with the OP)

It is used a variant of ElGamal encryption, where for plaintext $m$ the group element $g^m$ is what gets encrypted using standard ElGamal.
In the expression $m_2\mathbin\|m_3$, plaintext integers $m_2$ and $m_3$ are bitstrings of fixed size (32-bit).
One option for the encrypter/prover is to make use of the ephemeral secret exponents generated at encryption.

We'll consider the additively homomorphic variant of ElGamal encryption, in a finite group with generator $g$ of prime order¹ $n$.
The private key is a random secret integer $d$ drawn uniformly randomly in $[0,n)$. The public key is $q\gets g^d$.
Encryption for integer $m$ goes:

Draw a random secret integer $k$ uniformly randomly in $[0,n)$
Compute $r\gets g^k$ and $s\gets g^m\cdot q^k$
Output ciphertext $(r,s)=c$ as the result of encryption of $m$, noted $E(m)$.

Decryption of ciphertext $(r,s)=c$ goes

Check that $r$ and $s$ are in the group
Compute $a\gets r^{n-d}\cdot s$
Find integer $m\in [0,n)$ with $g^m=a$. This requires tractable work for small $m$, using e.g baby-step/giant-step. For large $m$, we assume some oracle solves that problem when we write $D(c)$.
Output $m$ as the result of decryption of $c$, noted $D(c)$.

Note: Encryption $E$ is not a function. $D$ is one.
When $c=(r,s)$ and $c'=(r',s')$, we'll note $c\cdot c'$ for $(r\cdot r',s\cdot s')$; and $c^u$ for $(r^u,s^u)$.
It's easy to show that

if $0\le m<n$, then $D(E(m))\,=\,m$ [whatever $k$ was drawn by $E$]
$D(E(m)\cdot E(m'))\,=\,(m+m')\bmod n$
For any integer $u$ it holds that $D(E(m)^u)\,=\,(m\times u)\bmod n$ [where $\times$ is integer multiplication].

In the following, we assume the $c_i$ have been independently computed as $E(m_i)$ for $i\in\{1,2,3\}$; $m_2$ and $m_3$ are in $[0,2^{32})$; definition of $m_2\mathbin\|m_3$ as $m_2\times2^{32}+m_3$; and $n>m_1$, $n\ge2^{64}$.

(Given the value of such $c_i$) is it possible for the encrypter to prove with a zero-knowledge proof that $m_1\,=\,m_2 \mathbin\| m_3$?

Yes, if the encrypter/prover holds the private key $d$: define $c\gets{c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3$, and present any skeptical with a Zero-Knowledge Proof that $D(c)=0$ [see next paragraph]. Argue $D(c)=0$ proves $-m_1+m_2\times2^{32}+m_3\bmod n\,=\,0$, thus $m_1\,=\,m_2\times2^{32}+m_3$. The computation of $c$ won't be too tedious, for computing ${c_2}^{(2^{32})}$ requires computing a mere $62$ squares in the group, while ${c_1}^{n-1}$ requires at most $2\left\lfloor\log_2n\right\rfloor$ squares and less multiplications, using a standard method of exponentiation.
There remains to make a Zero-Knowledge Proof (ZKP) that $D(c)=0$; that is, with $c=(r,s)$, that it holds $r^{n-d}\cdot s\,=\,g^0$; equivalently, that $r^d=s$. The prover is assumed to know $d$, an can check this directly. The ZKP aims to convince the verifier knowing group elements $g,q,r,s$ that the prover knows $d$ such that $g^d\,=\,q$ and $r^d\,=\,s$. This the Chaum-Pedersen proof of equivalent discrete logarithms, explained there and there.
That should convince a rational verifier well versed in math. Good luck with that line of argument facing a random citizen fearing there was fraud in an election.

If the encrypter/prover does not hold the private key, but controls or keeps the $k_i$, there ares ways too.
A simple way is that the encrypter/prover generates $k_1$ as $k_1\gets k_2\times2^{32}+k_3$, rather than randomly. This ensures $c_1\,=\,{c_2}^{(2^{32})}\cdot c_3$, which is trivial for anyone to verify. That relation itself allows to prove this choice of $k_1$ [on top of the assumed $m_1=m_2 \mathbin\| m_3$] does not weaken anything. Even simpler, $c_1$ can be computed directly as $c_1\gets{c_2}^{(2^{32})}\cdot c_3$.
Computing and revealing $k\gets k_2\times2^{32}+k_3-k_1$ also does the job: it allows to check $c_1\cdot(g^k,q^k)={c_2}^{(2^{32})}\cdot c_3$, which conclusively proves $D(c_1)\,=\,D(c_2)\mathbin\|D(c_3)$. But I pass at proving my intuition there's nothing useful revealed, and I would not say it's a true ZKP.
But that can be turned to a true ZKP thru the Chaum-Pedersen proof of equivalent discrete logarithms: with $c=(r,s)$ defined as ${c_1}^{n-1}\cdot{c_2}^{(2^{32})}\cdot c_3$, the ZKP aims to convince the verifier knowing group element $g,q,r,s$ that the prover knows $k$ such that $g^k\,=\,r$ and $q^k\,=\,s$.

¹ That is: the group has $n$ elements $g^m=\underbrace{g\cdot g\ldots
g}_{m\text{ terms}}$ for $m$ in $[1,n]$, with $g^n$ the group neutral $1$. For security, $n$ is usually a large prime. A simple example would be a Schnorr group.


Perfect secrecy and block ciphers Consider a block cipher that encrypts bit strings of length $n$, where the key-space of the block cipher is of size $2^{kn}$, $k \geq 1$.   My understanding of perfect secrecy is that a system is perfectly secret if (and only if?) the size of the key space is larger than the size of the message space.  But then, if the stated block cipher was used to encrypt messages, is it not true that such a block cipher could encrypt $k$ messages of length $n$ with perfect secrecy?  Would this be possible if, after each encrypted message, a nonce was used that changed the key in some way, so that every subsequent message had perfect secrecy?

It is helpful to first define what a perfectly secure block cipher is. In the ideal case there are n different keys where each key uniquitely indexes one of the permutations mapping {0,1}^k to {0,1}^k. In this case we have n=(2^k)! Possible permutations/keys.

Perfect security typically means that no information is revealed at all. Not even against an adversary that is computationally unbounded (ie brute force) .

Given such an ideal block cipher (random permutation), can you think of a situation where information is leaked after seeing more than one message. Keep in mind, brute force attacks are allowed here.

Hint, this is why we have block cipher modes.


Birthday-paradox for big numbers and more than one person: Computing the approximate probability of $k$ hash collisions for $n$ hashes Given a cryptographic hashing function, with say a $256$  bit-length, I want to calculate the probability that out of $n$ hashes we have at least $k$ hashes that collide in the first $32$-bit (assuming the $n$ hashes are uniformly distributed over all $2^{32}$ possible prefixes). Assume $k$ and $n$ are very high, something like $k=2^{32},n=2^{64}$. This reminds me of the birthday paradox but for more than $2$ people. I found this post, which suggest using an poisson approximation which from my understanding would result in the formula:

$$ P(\text{at least $k$ hashes in $n$ trials share the same prefix}) =$$
$$ 1 - \exp \left (-{n \choose k}/(2^{32})^{(k-1)} \right )$$

because if we would check every combination of $k$ hashes in the set $n$ hashes, we would on average have $\lambda = {n \choose k}/(2^{32})^{(k-1)}$ combinations that share the same $32$ bit prefix.

The problem with that that formula is that the calculations take too long. For example, calculating the number $(2^{32})^{2^{32}-1}$ is simply too complex. Is there any other way I can approximate this probability while remaining in the computationally feasible area?

For large $k$ growing with $n$ the binomial coefficient needs to be approximated.

Let $h(x)=-x\ln x-(1-x)\ln (1-x)$ be the binary entropy function in nats, then for $k\in [1,n-1]\cap \mathbb{Z}$ we have
$$
\sqrt{\frac{n}{8k(n-k)}}\exp\{nh(k/n)\} \leq \binom{n}{k} \leq \sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}
$$
where the upper bound approaches equality if $k$ and $n-k$ are both large. This is obtained from Stirling and then some other manipulation, and covers the whole range of $k$.

This result appears, e.g., in Bob Gallager's book Information Theory and Reliable Communications.

This will give a good approximation if you use the upper bound.

So, you have
$$
1-\exp\left[-\frac{\sqrt{\frac{n}{2\pi k(n-k)}}\exp\{nh(k/n)\}}{\exp\{(k-1)\ln 2^{32}\}}\right]
$$
and can further take differences of the exponential function arguments inside and simplify for $n=2^{64},k=2^{32},$ to
$$
1-\exp\left[-\sqrt{\frac{n}{2\pi k(n-k)}}\exp\left(nh(k/n)-(k-1)\ln 2^{32}\right)\right]\approx$$
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(nh(1/k)-(k-1)\ln 2^{32}\right)\right]
$$
or
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(nh(2^{-32})-2^{32}\ln 2^{32}\right)\right]
$$
and since for large $k$, $h(1/k)\approx \ln k,$
$$\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(n \ln 2^{32})-2^{32}\ln 2^{32}\right)\right]
$$
$$
\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left((2^{64}-2^{32}) \ln 2^{32}\right)\right]\approx
$$
$$
\approx 1-\exp\left[-\sqrt{\frac{k}{2\pi}}
\exp\left(2^{64} \times 32 \ln 2 \right)\right]
$$


Crypto algorithm identification (reverse engineering) I'm trying to identify a certain cryptographic algorithm used in a program. From examining the executable, it appears it

Has 16 rounds (plus 2 "rounds" for pre/post processing)
Pads the input plaintext to 256 bytes with the results of a linear congruence generator (with a fixed seed). This might be a preprocessing step and not part of the actual crypto algorithm
Each round operates on the entire plaintext (updates all 256 bytes of the output). At the end of each round a 256-byte array is subtracted from the output
Uses a (random) initialization vector, ie the same input produces different outputs

I suspect it's a variant of DES, but the block size listed for DES is only 64 bits. Is there a 2048-bit variant that is commonly used, or some kind of optimization that allows the next round for each block to be computed in parallel while still using an initialization vector? Alternatively, given a plaintext and the intermediate values produced each round is there an easy way to determine the type of cipher?

Is there a 2048-bit variant that is commonly used, or some kind of optimization that allows the next round for each block to be computed in parallel while still using an initialization vector?

Bit slicing is an optimization technique that consists in calculating $b$ instances of a function (e.g. $n$ block decryptions/encryptions) in parallel on a machine with $b$ bits. An apparent 2048-bit block size is consistent with a 64-bit cipher and a 32-bit bitslice. Bitslicing can only be done when the data for block operation $n+1$ doesn't depend on the output of block operation $n$, so it's useless for e.g. CBC mode but can be used for e.g. CTR mode.


Help with example RSA problem While learning about RSA, I found this example problem. The answer is supposed to be "a 4-digit number that is a pattern of digits." I have computed it to be 16657 twice.

OK, now to see if you understand the RSA decryption algorithm, suppose you are person A, and you have chosen as your two primes $p = 97$ and $q = 173$, and you have chosen $e = 5$. Thus you told B that $N = 16781$ (which is just $pq$) and you told him that $e = 5$.
He encodes a message (a number) for you and tells you that the encoding is 5347. Can you figure out the original message? Hint--well, not really a hint, but a check of your final answer: it is a four-digit number that is a pattern of digits.

I have failed to decode this to a 4-digit number. What am I doing wrong?
p = 97
q = 173
N = 16781
dp = 16512 = (p-1)(q-1)
e = 5
d = ?
C = 5347
M = ?

I computed d = 6605 since that seems to be the smallest value of d possible for:
ed = 1(mod (p-1)(q-1))
5d = 1(mod 96 * 172)
5d = 1(mod 16512)
# I need a multiplier for 16512 that when added to 1 yields a number that
# ends in a 5 or a 0 so it will evenly divide by e=5
# 1 + 2 times dp will yield a number that ends in a 5
d = 6605

Now I need to compute M = C^d(mod N):
M = C^d(mod 16781)

    5347^6605(mod 16781)

6605 = 4096 + 2048 + 256 + 128 + 64 + 8 + 4 + 1

5347^1   (mod 16781)    = 5347
5347^2   (mod 16781)    = 12366   (not included in final math)
5347^4   (mod 16781)    = 9484
5347^8   (mod 16781)    = 96
5347^64  (mod 16781)    = 389
5347^128 (mod 16781)    = 292
5347^256 (mod 16781)    = 1359
5347^1024(mod 16781)    = 3105
5347^2048(mod 16781)    = 8731
5347^4096(mod 16781)    = 11059

5347^6605(mod 16781)    = 16657

I've also computed the same result in Excel by reproducing the same table above one power at a time for 6605 rows.
Update: It turns out to have been a mistake. The original author corrected the problem, but not before the error was copied across the internet.

You don't appear to have done anything wrong; you can double check your result by computing:

  $16657^5 \bmod 16781$

and find that it is indeed 5347; that is, 16657 is the number that, when encoded with the public key, results in the value you were given.

I suspect that moral of this story is that random examples on the internet might be worth just as much as you pay for them.


Is this algorithm secure? I recently found this site, proposing a hashing algorithm for passwords.

They describe the following:

pad the password on both sides with SHA1(email) to 4 * length(password)
HMAC(padded password, global salt)
choose a random salt of 22 characters
bcrypt(hmac, salt)

Is this algorithm secure? I think it might be a security flaw to pad the password on both sides with the same text, and I see no point in using a global salt and a salt which is chosen randomly for every password.

Points 3 and 4 are a secure way of storing the input to bcrypt (with appropriate choice of parameters for bcrypt).

Points 1 and 2 aren't necessary but don't harm:

they would add a small amount of extra computation for an attacker is possession of the password database that wants to do a dictionary attack;
the attacker wouldn't be able to straight-out use a standard cracking tool as it is a custom scheme, they would need to modify existing tools or develop their own.


What are the differences between the elliptic curve equations? I think we're all aware of the "classical" Weierstrass (short?) elliptic curve equation: $y^2\equiv x^3 + ax +b \pmod p$. Well known examples of these curves include the NIST's and Brainpool ones.

Now there's also the "Montgomery" representation: $by^2\equiv x^3 + ax^2 + x \pmod p$ where the famous Curve25519 is an example for.

To get things even more complicated there are "Edwards" and "Twisted Edwards" curves (of which I don't even have the general equations). A well-known sample would be Ed25519 I think.

Now what are the equations of these curves ([twisted] edwards only)?
Can they be converted into each other?
What are the computational advantages over using a given curve equation over another?
Are there any security implications (including side-channels) in choosing a specific equation?

All of these are answered by the SafeCurves project:

For twisted Edwards curves, $ax^2 + y^2 \equiv 1 + dx^2y^2 \pmod p$. Edwards curves are the special case a = 1.
Edwards curves can be converted to Montgomery form.Montgomery curves can be converted to Weierstrass form.Some, but not all, Weierstrass curves can be converted to Montgomery form.
The Montgomery ladder (applicable only to Edwards and Montgomery curves) is faster than standard weierstrass point multiplication methods.
the Montgomery ladder is constant-time, while the standard Weierstrass point multiplication methods are not.The Brier-Joye ladder allows constant-time point multiplication on Weierstrass curves, but is much slower than the standard point multiplication methods. The EdDSA signature scheme is only supported by twisted Edwards curves.


Difference between "one-way function" and "cryptographic hash function" What's the difference between a one-way function and a cryptographic hash function?

It's all a matter of definitions.

Typically, a "cryptographic hash function" $H$ has three properties:

Preimage resistance: Given $H(x)$, it's hard to find $x$
Second preimage resistance: Given $m_1$, it's hard to find another $m_2$ such that $H(m_1) = H(m_2)$
Collision resistance: It's hard to find any two distinct messages $m_1$, $m_2$ such that $H(m_1) = H(m_2)$.

These aren't definitions that are set in stone. This sort of broad definition is not really very nuanced, but it is indeed a common one. Usually, it's not necessary to be any more specific than this.

For a less restricted definition, you might say a hash function $H$ only has two properties:

  a.  Easy to compute: Given $x$, it is easy to compute $H(x)$
  b.  Compresses: $H : \{0,1\}^{*} \to \{0,1\}^n$ (i.e., it maps any bit-length string to a fixed bit-length)

And then from there you can become more nuanced. Now you can say a "one-way" hash function is a hash function (using the less restricted definition) that possesses properties 1 and 2; that is, it is an easy-to-compute compression function that possesses preimage resistance and second-preimage resistance. In other words, the function can only be computed "one way".

Using this sort of definition is sometimes convenient for a detailed study of hash functions. You can also have collision-resistant hash functions, which possess property 3.

In fact, property 3 implies property 2 implies property 1. (In other words, there is a hierarchy of security properties, each one implying the one above it.) So a hash function that is collision-resistant is also second-preimage resistant and preimage resistant. Note that it does not go the other way: MD5 is an example of a hash function that is preimage resistant (very much so) but is very broken when it comes to collision resistance.

Ultimately, it just depends on whose definition you are using. In this case, I'm essentially summarizing the definitions given in the Handbook of Applied Cryptography.


Base point in Ed25519? The paper "High-speed high-security signatures" by Bernstein et al. introduces the Edwards curve Ed25519.

Concerning the base point $B$, it says that

$B$ is the unique point $(x, 4/5)\in E$ for which $x$ is positive, and
$B$ corresponds to the basepoint used on the birationally equivalent curve Curve25519.

The actual coordinates of $B$ are:
[15112221349535400772501151409588531511454012693041857206046113283949847762202, 46316835694926478169428394003475163141307993866256225615783033603165251855960]

I'm not sure I fully understand the choice of this point:

I can't really see that $B$ is unique and that '$x$ is positive'. (What does positive mean here?)
Does this point have any special security properties that other points do not have, or is it just a 'rigid' choice to convince us that no backdoor was built-in?

If you know anything about this point, please tell me! Many thanks!

1. The equation $-x^2+y^2=1-(121665/121666)x^2y^2$ defining the curve $E$ is quadratic in $x$, hence for any given $y\in\mathbb F_q$, there are at most two points on $E$ which have $y$ as their second coordinate. In this case, the two possible $x$-coordinates for a point on $E$ with $y$-coordinate
$4/5\in\mathbb F_q$ are the solutions to the equation
$$ -x^2+(4/5)^2=1-(121665/121666)x^2(4/5)^2 \text. $$
that is
$$ x^2=\frac{1-(4/5)^2}{-1+(121665/121666)\cdot(4/5)^2} \text. $$
Now by considering the symmetric representants (that is, from the set $\{-(q-1)/2,\dots,(q-1)/2\}$) for the elements of $\mathbb F_q$, we can interpret one of the roots of this equation as being positive and the other as negative, corresponding to the signedness of their symmetric representant. The unique "positive" solution to the equation above is precisely $15112221349535400772501151409588531511454012693041857206046113283949847762202$.

2. As far as I am aware, the base point is chosen pretty arbitrarily. As described in the Ed25519 paper, it arises from the choice $u=9$ in the original Curve25519 paper, but there seems to be no justification for that either. However, to the current state of knowledge, there are only very few bad choices for the base points, most importantly those whose order has no large prime divisor. (A nice overview of known weaknesses is SafeCurves.) Besides that, the choice of base point is not all that important, as the discrete logarithm problem has a property called random self-reducibility: An attacker who can efficiently compute logarithms with respect to a sufficiently large fraction of possible base points can in fact compute logarithms with respect to all base points.


Do I need to use HMAC in this crypto wallet backup application? I'm building an application for securely backing up cryptocurrency private keys or 12-word backup phrases that crypto wallets use as a seed to generate private keys. For the purpose of this question, if you're unfamiliar with cryptocurrency, you just need to know that whoever knows your private key can spend your money.

This is the backup process:

The user encrypts his plaintext with a password (I'm using scrypt and AES256)
The ciphertext is base64-encoded, and both the ciphertext and some header data are encoded as a single QR code -- this is the user's backup
The user prints several copies of the QR for storage
If the user's computer crashes and he needs to restore his backup, he can scan the QR code and provide the password to decrypt the message and retrieve his private key(s)

The QR code contains the scrypt parameters, salt, initialization vector, and the ciphertext.

My question is: Do I need to add an HMAC signature to the contents of the backup? If possible, I'd like to leave it out, since it significantly increases the complexity of the resulting QR code, and complex/large QR codes are more difficult for devices to scan.

I'm thinking I don't need an HMAC signature because, if the ciphertext is altered in any way by a malicious party, the resulting altered plaintext will be useless to the user - he won't be able to recover his cryptocurrency. Altering the ciphertext would produce the same results as simply destroying the user's backups (a signature can't protect against that). A length extension attack would also be pointless in this context.

The fact that an altered backup is useless seems like a built-in integrity check, making a signature redundant. Is this conclusion correct, or do I need to add a signature?

No, I don't think that a HMAC is necessary here. However, you may want to consider what happens if the QR code is indeed wrong. For instance, it was found that a system that used passive RFID tags was vulnerable against buffer overrun attacks: all the attacker had to do was to increase the size of the ID represented by the tag.

Ultimately you want simply to keep the private key value secret. The validation of the private key can be handled by performing an action on the wallet. If such an action is not possible on its own or if the verification of the private key solely rests on the decryption of that key then you may be in trouble: you need some way of verification that the decryption result is OK. Padding in that case cannot be trusted enough to be worth the cost (and if you can pad then you can also not pad and store a authentication tag (MAC value).

Having a MAC over the ciphertext makes it much easier to prove security. Note that you can derive the IV from the salt and the pass phrase using scrypt or scrypt and a KDF/PRF (such as, funny enough, HMAC), so you could replace that with an authentication tag. Using SIV mode is also possible, then the IV would double as authentication tag.

The scrypt parameters could be represented by a single protocol version byte representing hard coded parameters.


is it unsafe to AES encrypt using multiple modes? Example:
message = 'sup'

// encrypt
cipher = aesencrypt(aesencrypt(aesencrypt(message, 'CFB'), 'CTR'), 'OFB')

// decrypt
message = aesdecrypt(aesdecrypt(aesdecrypt(cipher, 'OFB'), 'CTR'), 'CFB')

if it's not a possible vulnerability, it'd just rather use all 3 than decide on one.

When combined with your comments, I can say this is unsafe in the sense that it is highly advised against "rolling your own encryption."
It looks to me like you are layering multiple encryption methods together without too great of a concern for understanding the attacks made against them.  Is this secure?  Maybe.  In theory, we designed these algorithms sufficiently well that your outermost layer provides you enough protection.  Of course, in that case, all your layering really isn't making you more secure.
In general, it is recommended that you use one algorithm, the way it is typically used.  Then, if you identify a particular attack vector you care about which isn't handled by that algorithm, you can look at a careful layering.  For example, you specifically want a slow algorithm for hashing the key.  You then may layer PBKDF2-256 onto your process in order to achieve that specific goal.
In theory, AES was well designed enough that you can get away with layering, and the strength of the encryption you have is at least as strong as the outer layer.  However, if you are layering encryption schemes without thinking through the threat model carefully, you could get unlucky and break a key feature of one layer with a feature of another.  Its not the layering that's the issue, but rather the mindset that layering makes it stronger that is the issue.  This is not always provably the case, and it puts you at risk for future decisions you might make, thinking you are making the product stronger.
A test you can give yourself: If I want to do X in cryptography, do I see any commercial or open source libraries doing X?  If not, that's a sign that what I'm doing is unorthodox and may not be as secure as I think it is.


What is the difference between static and dynamic tokens? First, what is the difference between hardware and software tokens?
Tokens are "what you have" for example a car key or a chipcard. This would be (I think) hardware tokens? But what are software tokens?

Also what is the difference between static and dynamic tokens?

Could you give me examples for better understanding?

Software tokens are software that generate tokens for you. For example the Google Authenticator App or Authy on your smartphone, while hardware tokens are actual hardware that are only made for generating those tokens without doing anything else, such as RSA SecurID.

A static token would be a token that is always the same, for example a password stored on a Yubikey that is entered each time you press a button on the token.
A dynamic token is a token that varies, like Google Authenticator two-factor tokens that change each 10 or whatever seconds.


Password-Managers: what is the IND-CDBA attack logic? In the work of Paolo Gasti and Kasper B. Rasmussen On The Security of Password Manager Database Formats, they describe two attack forms: IND-CDBA and MAL-CDBA.

While I understand the MAL-CDBA attack by modification of records in the DB, what is the attack logic of IND-CDBA?

Intuitively, IND-CDBA means an attacker cannot tell which of two databases contains a record he picked.

In other words even if you know the passwords in a database. And even if there are only two possible databases to pick from. An attacker still cannot figure out which one is the right one.

This is the formal definition from the paper:

Indistinguishability of databases game $\text{IND-CDBA}_{\text{Adv}_r, \mathcal{PM}}(\kappa)$:

  A challenger $\text{Ch}$ running $\mathcal{PM}$ interacts with
  $\text{Adv}_r$ as follows:

  $\text{Ch}$ runs $\text{mp} \leftarrow \text{Setup}(1^\kappa)$
  $\text{Adv}_r$ outputs two record-sets $\text{RS}_0, \text{RS}_1$
  $\text{Ch}$ selects a bit $b$ uniformly at random and returns the database $\text{DB}_b \leftarrow \text{Create}(mp, \text{RS}_b)$ to
  $\text{Adv}_r$
  $\text{Adv}_r$ eventually outputs bit $b'$ and wins if $b = b'$

This is similar to the familiar IND-CPA definition where you pick two messages and then you get an encryption of one of them and you have to guess which one it was.

Of course what this tells you in the end, is that you cannot learn any information about the passwords in a password file if this game is hard to win.


What will happen if I use RSA encryption for plaintext larger than RSA bit size? I have often read that using RSA for encrypting bigger size plaintext is not good solution.

What I understand is that using RSA encrytion is best for small plaintext and most effective if it is smaller than 'bit size' of RSA. For instance, if I use RSA with a 2048 bit size then the plaintext that I can encrypt must be smaller than 256 bytes.

Is this true? What happens if the plaintext is bigger than 256 bytes? Why is there a problem with larger plaintext when performing RSA encryption?

If you have an RSA public key $(e, N)$ (in the case of RSA2048 $N$ will be 2048 bits) and private key $d$ then you can only encrypt messages $m$ whose integer representation is less than $N$.

Recall that in RSA encryption is defined as $c = m^e \text{ mod } N$ where $c$ is the resulting ciphertext, and decryption is defined as $m = c^d \text{ mod } N$. The key insight is that decryption cannot produce an $m \ge N$ because of the modulo $N$ operation (the remainder of division by $N$ must be less than $N$). Thus if we encrypt an $m \ge N$ decryption will not produce the correct value.

To get around this it is possible to break $m$ up into chunks that are smaller than $N$, encrypt the chunks, and then recombine the chunks after decrypting to form $m$. For example ($||$ denotes concatenation):

$$m = m_1 || m_2$$ $$c1, c2 = Enc(m_1), Enc(m2)$$ $$m = Dec(c_1) || Dec(c_2)$$

More things to consider beyond this are space that padding will take (unpadded RSA is not secure), and whether you should be using a symmetric cipher like AES which is more suited for encrypting large amounts of data (RSA is much slower than symmetric ciphers and was not designed to encrypt large amounts of data).

Edit: If we do encrypt a message $m \ge N$ the ciphertext $c$ resulting from encrypting $m$ will not decrypt back to $m$. Example using some small parameters:

$$p =17, q = 19, N = p*q = 323, e = 5, d = 173$$
$$m = 400$$
$$Enc(m) = c = 400^5 \text{ mod } 323 = 229$$
$$Dec(c) = m' = 229^{173} \text{ mod } 323 = 77$$

Note that $m \ne m'$ and thus for values $m \ge N$ RSA does not decrypt properly. In fact, for any value $m \ge N$ encrypted via RSA the ensuing decryption will produce $m \text{ mod }N$ instead of $m$ (as is the case in the example: $77 = 400 \text{ mod } 323$).


Group signature's Scheme I'm looking to use group signature that is scalable in terms of the size of the signature is independent of the number of the group members.

Two question-

1- Is [1] considered an up to date, efficient and secure scheme?

2- In case of new joining member, does the signature needs to be changed? (to also to reflect the new member's membership).

[1] - https://link.springer.com/content/pdf/10.1007/BFb0052252.pdf

My answer to a multi-sig question may shed some more light if you're interested in more flexible groups.

I don't see the date of the paper you've linked, but it does not reference anything after 2k. The following is from 2001.

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

As far as I know there isn't anything that would compete directly without being a distinct protocol. If you want n-of-n, you may look at MuSig, which is a recent advancement in the n-of-n signing of a common message. If you want a subset, you can select the signers directly. This isn't anonymous between cosigners as in t-of-n; but it is directly traceable.

Joining a new member to the group does not change old signatures, but it does change the identity of the group. Evolving t-of-n produces opaque new identities; while n-of-n MuSig evolves transparently. In either case you'll need to have some method and protocol to manage which identities are valid and when. I.e. Git code signing could be relative to the state of the commit.

What properties are you interested in?

If you want t-of-n anonymous groups. AFAIK you'll need to do a re-key and establish a new identity for any group changes. This would certainly be annoying to maintain, especially if this is frequent.

If you want a traceable subset of a larger known, and trivially dynamic group; then you may prefer a direct n-of-n through identity-aggregation.


Replay attack prevention under strict conditions Say I have a request-response protocol and the task to make it immune to replay attacks. The requirements are as follows:

The defense mechanism cannot rely on the clocks of the parties.
The defense mechanism should work even when requests are not sequential.
No party can store more than 1KB of data at any given time for the purposes of replay attack prevention (per session - see below).
No requests must be sent for the purposes of replay attack prevention.

Given that:

Before the defense mechanism is used, another protocol is used to authenticate the first party and create a session. The session ID is included in every request of the above protocol.
During the authentication protocol, up to 1KB of data can be sent to the first party for the purpose of replay attack prevention on the above protocol.

In what way does HTTPS handle replay attack prevention? How can this (the first described) protocol be made immune to replay attacks?

Considered Idea #1:

A 256-bit secret is shared by the two parties during the authentication protocol.
When party 1 makes a request, they include this secret in their message.
Party 2 checks that this is the same value they have stored. If so, it is included in the response and this value is hashed and stored, replacing the previous value.
Should the response be valid and contain the value sent, party 1 hashes the value sent and stores it, replacing the previous value.
Steps 2-4 are repeated for every request and response.

The problem with this is that requests need to be sequential.

Considered Idea #2:

Every time party 1 makes a request, a nonce is included.
Party 2 checks if this nonce has been used before with this session id, if yes, it denies the request, if not, this value is stored. Party 2 includes this nonce in the response.
Party 1 checks if the sent nonce is included in the response.

The problem with this is the large storage space needed.

The standard solution would be to have the sender maintain a counter, and sending the value of that counter in each request (which is tied into the integrity check of the request).  The receiver would remember the largest counter value that he has received a valid request for, and a bitmap showing which of the N requests prior to that he has actually seen.  With 1kbyte of memory available on the receiver, you can have N=8000 or so, which means that we can do accurate replay detection, as long as we don't get a request that is older than 8000 requests previous to the most recent.  If we do get such a request, we'll reject it, even if it is a previously-unseen request.

See RFC6479 for details on one possible method of implementing this.

As for how HTTPS does replay detection, well, each TLS record has a sequence number associated with it.  Both sides maintain a copy of the counter, and it is included in the integrity check.  So, if someone were to replay an HTTPS record (adjusting the TCP sequence numbers, if they don't do that, the TCP stack will assume that it's a retransmission and ignore it), the TLS sequence number of the receiver won't be the same as the sequence number that the sender used, and so the integrity check will fail, and the record will be rejected (and the session will be shut down; TLS can't recover from these sorts of errors).


Using encryption as authentication I am building an app in which I would like to encrypt user data and support offline login.

From this answer about using passwords for encryption:

  Best practice is to use a PBKDF to generate a 'key encryption key' (KEK), then a full entropy random key is used to encrypt the data, and the KEK is used to encrypt that key.

Would it be reasonable to include in the data a known value such as "hello everybody" (or the username, if the variability per user would help?), and authenticate users by attempting to decrypt their data and checking that the decrypted value matches the known value?

With the numbering in your comment: 1 yes, 2 no.

If you just need to encrypt files, use age if you can.

I'm going to answer the rest of this in the context of using libsodium as your cryptographic library. You might have a different choice, like NaCl or , but any choice should support a high-level API like I'll describe. If your library doesn't, it's not safe and you should pick a better one.

For generating random numbers (nonces, salts, etc), use your library's secure random generation function(s). For libsodium, this is almost always going to be the randombytes_buf function.

For turning a password into a key, use your library's password hashing function. If that's libsodium, you want to hash it using the crypto_pwhash function. That takes in a random salt generated via randombytes_buf, some parameter limits, and a password, and outputs a key. You'll need to store the parameters and the salt with the encrypted data.

The reason to use the password-derived key as a KEK instead of using it directly is to allow the user to change their password without needing to re-encrypt all the data. You'd just need to re-encrypt the actual data key. The encryption method used should be your library's preferred authenticated encryption function. For libsodium, that's crypto_secretbox_easy (and decryption is crypto_secretbox_open_easy). If you don't actually need this functionality, don't include it, just use the output key of the PBKDF to encrypt the data.

You don't need to check that the data has been decrypted successfully. That's handled by the Authentication part of an AEAD (Authenticated Encryption with Associated Data) mode. If the authentication tag verifies, it decrypts correctly. If it doesn't verify, it discards the (potentially very dangerous) decrypted data without doing anything else to it.

Assuming you have to use libsodium or similar and are going with the KEK system, you'll need a random salt, a unique nonce for the AEAD encrypting/decrypting the data key with the password-derived KEK, and a second unique nonce for encrypting/decrypting the data.


Practical consequences of a honest-verifier zero-knowledge of the Schnorr protocol Schnorr protocol is known to be honest-verifier zero-knowledge and not perfectly zero-knowledge.

What are the practical consequences of this fact? Does it mean a dishonest verifier can do something to discover the secret exponent $x$?

Setup

$P$ chooses a large prime $p$ and a generator $g$ of the $q$ order subgroup of $\mathbb Z_p^*$.
$P$ chooses a secret $x \leftarrow_{uniform} \mathbb Z_q^*$, computes $y = g^x$ and gives $y$ to $V$.

Protocol

$P$ chooses $r \leftarrow_{uniform} \mathbb Z_q^*$, computes $t = g^r$ and sends $t$ to $V$
$V$ chooses $c \leftarrow_{uniform} \mathbb Z_q$ and sends it to $P$
$P$ computes $s = r + cx$ and sends $s$ to $V$
$V$ verifies that $g^s = ty^c$.

By definition, a dishonest verifier may be able to completely extract the witness from an honest-verifier ZK proof.

To prove this: take any zero-knowledge proof, and add an initial round where the verifier sends 1 to the prover. The prover then works as follows: if it receives 1 then it runs the original zero-knowledge proof; if it receives 0 then it sends the witness.

The above proof is clearly honest-verifier zero-knowledge, but a dishonest verifier can learn the witness by sending 0.

Typically, the point of an honest-verifier zero-knowledge proof is that it can be "compiled" into a (full) zero-knowledge proof without much difficulty.

Having said the above, some honest-verifier zero-knowledge proofs already have stronger properties like witness indistinguishability. This makes no sense for Schnorr itself since there is only one witness, but I believe that the standard Diffie-Hellman tuple sigma protocol is witness indistinguishable (I would want to write a proof to be 100% sure but I'm nearly sure).


Do Weak Elliptic Curves Exist? I'm running into very contradictory opinions when try to understand if weak elliptic curves exist. I'm not interested in the case when a curve's weakness is attributed to properties of an EC's prime, because those cases have been already explored, e.g. here: http://wstein.org/edu/2010/414/projects/novotney.pdf

I want to understand if there is a known proven weakness attributed to parameters a or b of a short Weierstrass equation.

Dan Brown introduced a hypothesis of "spectral weakness" here:

https://www.ietf.org/mail-archive/web/tls/current/msg10393.html
https://www.ietf.org/mail-archive/web/cfrg/current/msg03952.html

DJB went even further and dubbed curves with unclear parameter's generation method "manipulative" at http://safecurves.cr.yp.to/rigid.html

Both major and popular ECC standards such as NIST and Brainpool have a "verifiable random" requirement for the curve's parameters.

At the same time I've learned just yesterday that there is a strong opinion that "spectral weakness" (attributed to the parameters) doesn't exist (see comments to this blog: http://ogryb.blogspot.com/2014/11/why-i-dont-trust-nist-p-256.html)

If no weak curves have been discovered yet, how big the threat of "spectral weakness" is?

The following is more or less a copy-paste of a comment I made on the related ArsTechnica thread. Indeed, StackExchange is probably one of the better places to debate this.

A few reminders first:

there are approximately $p$ elliptic curves over the finite field of integers $\pmod{p}$;
of these curves, only those with (almost) prime order are of cryptographic interest (I will write only about prime order, for simplicity): there are approximately $p/\log p$ such curves;
among these prime curves, there are some known conditions which happen rarely and make the curve insecure;
the "Suite B" generation procedure is basically: pick some seed $\sigma$ (randomly or maliciously; assume that it is malicious), hash it with a cryptographic hash function (and more particularly, a preimage-resistant hash function), and derive curve parameters from this.

The largest class of "subtly weak" curves (with prime order) that we know is the set of supersingular curves, which has a size of about $\sqrt{p}$ and therefore a probability of occurrence of $1/\sqrt{p}$ (neglecting the logarithmic factor). So finding one via the Suite B generation procedure, even in the malicious case, should take about $\sqrt{p}$ tries - which, coincidentally, is exactly as long as solving ECDLP in the first place. (Besides, this class is easy to detect anyway, but that's not the point).

So any useable (by the NSA) class of weak curves would need to be much (= exponentially) larger than this; this is, much larger than all known classes of weak curves.

Then: if such a class exists, then how does the NSA exploit it? Because of hashing, (assuming SHA-1 to be preimage-resistant, which seems plausible), they cannot have inserted backdoor info in the curve: any trap that they use is computable from the curve itself without knowing the seed $\sigma$. This means that such a backdoor is available to any good mathematician (no need to steal NSA secrets!).

So the Suite B curves can be considered as dangerous only if you believe all three following conditions:

there exists a class of curves which is exponentially larger than all known classes of weak curves;
NSA knew about this class 20 years ago, but nobody else has been able to discover it since then;
they deliberately published, and use for themselves, a curve which they know to be weak to anybody else.
I personnally do not believe either (2) or (3), and tend not to believe (1) either. This is why I still believe P-256 to be safe.

Actually, even the DUAL_EC_DRBG scandal makes a strong case that both the P-256 curve (vs. ECDLP) and SHA-1 (vs. preimage computation) are probably safe: if the NSA had had, at the time of the DUAL_EC_DRGB parameter generation, a mean to either compute a SHA-1 preimage OR an elliptic curve discrete logarithm, then they would have been able to publish the seeds $\sigma_P, \sigma_Q$ for both points $P, Q$ while still knowing the discrete logarithm $\log(Q)/\log(P)$. They would have gained the same powers of prediction of the DRBG without leaving such a mess.

Of course, the preceding paragraph does not rule out that the whole DUAL_EC_DRBG scandal could have been deliberate misinformation from the NSA, and that Snowden could be a double agent. But this is leaving the crypto domain for the tinfoil-hat domain...

So why did NIST not use a verifiable method for generating the "Suite B" curves? Again, this is only borderline crypto, but my opinion on this is: nobody asked them to at the time, and it is only post-DUAL_EC_DRBG that we, the crypto community, have matured enough to require verifiability in all published parameters (which is a good thing, but does not mean by itself that P-256, or even worse, ECC in general, is broken!)


Authentication scheme using HMAC I have an authentication service, a client and an application service.

The client needs to use the application, but they have to be authenticated first. I'm trying to create a simple scheme to do this and what I've come up with is:

The client contacts the authentication service, sends its metadata (e.g. license number)
The authentication service validates the client (i.e. checks the license against a database) and returns a token containing: some new metadata needed by the application, a timestamp telling when the token was created and a HMAC-SHA256 for the mentioned data.
The client uses this token to contact the application service and perform its tasks
The application service checks a client's token by validating the HMAC-SHA256 (thus confirming that the token was generated by the authentication server) and also checks the timestamp, confirming that the token is still valid. If the operations succeed, it will use the metadata from the token to perform the task required by the client.

All communications between the authentication service and the client, as well as between the client and the application service are done over HTTPS. The secret key shared between the authentication service and the application service will be something large (e.g. at least 64 bytes)

My question is if anyone sees any flaw in this scheme.

PS: I know OAuth 1/2 exist, but to be honest I'm horrified to look into those. What I need is something really simple, like that "JWT stateless session" everyone recommends against. Oh, and I don't want to use JWT or Paseto because I've done a benchmark and a simple HMAC is faster (than Paseto at least)

All communications between the authentication service and the client, as well as between the client and the application service are done over HTTPS.

So at least the servers are authenticated to the client, and the communication channels are private.

This is not really an authentication problem. What you have is a capability-based access control while the license (and the token) serves as a capability list to authorise the user's operations. Your goal (I guess) is that only users who possess a valid license can access the application. The server's token is MAC protected so integrity should hold (assuming good a MAC scheme is used and good key management). The application server can be sure the token was generated by the authentication server, and not long ago (timestamp).

The first problem is whether the client needs to prove it possesses the license. Presenting the license number is not enough for this, because the number is a string which can be stolen or even simply enumerated. If you need a proof of possessing, need the license needs to be linked to some verifiable secret only known to the owner e.g. a secret key, a password. This is similar to when spending bitcoin you need a private key for the account. In bitcoin, the account number is equivalent to license number in your case, and a signature verifiable using the public key associated with the account number is the proof of possession. If you don't care and anyone who has the license number can use your service, then this is not a problem and you have the next problem.

The next problem is to prevent multiple users from sharing one license. This is similar to the double spending problem in e-cash, and in your case it can be solved easily since you have a centralised system. For example, when issuing a token, the authentication server can keep a record of the license number and the token expiration time. If a user comes with a license number that already has a token issued and the token hasn't expired, then the server can reject issuing a new token. The application server can also link tokens to sessions to ensure each token can initialise only one session. Of course, there are practical issues like the user may lose his token because the computer is shut down unexpectedly etc., and the full solution needs to cover those.


Bent Combining Functions Bent functions are boolean functions with maximum nonlinearity and are widely studied for their potential applications in cryptography. Lets say you wanted to use a simple two input AND gate as a nonlinear combiner for the outputs of two Linear Feedback Shift Registers . Because a two input AND gate is a bent function, is it technically correct to call the output sequence of this combination generator a bent sequence ( I need to know this for a paper I am writing).Thank you for commenting.

No.  As far as I can tell, this does not appear to produce a bent sequence.  (Or, if it does, that fact requires proof/justification.)

According to Wikipedia, a "bent sequence" is a sequence of the form $(-1)^{f(x_0)}, \dots, (-1)^{f(x_{2^n-1})}$ where $x_0,\dots,x_{2^n-1}$ is the sequence of $n$-bit values in lexicographic order and $f$ is some bent function.  That's different from what you are mentioning.  If what you're mentioning happens to fit this definition, that fact is far from obvious.

I don't know if this is the same definition of "bent sequence" you are using.  If it isn't, I suggest editing your question to include the definition you are using.


Why does NaCl's crypto_auth have twice the security level of crypto_onetimeauth? The crypto_auth function produces a 256-bit HMAC, with a 512-bit version also available. But the crypto_onetimeauth function (and the Box and SecretBox constructions that use it) only produces a 128-bit authenticator. Is there any particular reason NaCl doesn't include a 128-bit HMAC function?

There are two things to consider.

First is that the security models differ: crypto_onetimeauth only has to be secure for one message, while crypto_auth needs to be secure for any (practical) number of messages. The reason crypto_secretbox gets away with using the Poly1305 authenticator internally is that it generates message-specific authentication keys based on the nonce.

Second is the size of the authenticator. There is no very secure 128-bit hash function – using MD5 would be iffy even if it is not known to be broken in HMAC. You could still truncate HMAC-SHA256 and get a 128-bit authentication tag, but that would require assuming more than just the security of SHA-256.