Difference between Pseudo Mersenne primes and Generalized Mersenne primes

In the context of the papers you reference, Generalized Mersenne prime numbers and Pseudo-Mersenne prime numbers are indeed two different things.

A Pseudo-Mersenne prime number has the form $2^{\alpha}-\gamma$ for a small integer $\gamma \gt 0$.

The term Generalized Mersenne prime number is defined by example in the referenced paper, and the examples given are the primes used for the NIST prime curves for elliptic curve cryptography. For instance, the P-256 prime can be expressed as $2^{256}–2^{224}+2^{192}+2^{96}–1$. Consequently, a Generalized Mersenne prime number could be defined as a sum $2^{c_n}+(\sum_{i=1}^{n-1}{{-1}^{b_i}2^{c_i}})-1$ for two integer sequences $(b_i)_{i=1}^n$ and $(c_i)_{i=1}^n$ such that $b_i\in \{0,1\}$ and $c_1 \gt 0$ and $c_{i-1} < c_i$ and $c_n \gt n$.

The two definitions, as given here, overlap for (proper) Mersenne numbers $2^{\alpha}-1$, but any Pseudo-Mersenne number might also be expressed as a Generalized Mersenne number. The reverse is not true, unless you apply a very liberal definition of "small" as in small integer $\gamma \gt 0$. Typically, though, the $c_i$ exponents in a Generalized Mersenne number would be chosen as multiples of the word bit size, and $\gamma \gt 0$ would be selected as small possible.


Curve25519 was supposed to be mainly used for Diffie-Hellman key-exchange and it provides ~128bit security and should fulfill all standard security assumptions on elliptic curves (and even some more).

Now to answer the question is: yes.
ElGamal can be used securely with Curve25519, as ElGamal is simply a Diffie-Hellman key-exchange ($\delta= m*g^{\alpha k}$) using some message-specific private key $k$ which is transmitted via $\gamma = g^k$.This means one either has to break the Diffie-Hellman problem (which is hard on Curve25519) or break the discrete-logarithm problem on Curve25519, which is equally hard (as it would enable you to break the Diffie-Hellman problem)

However I'd strongly recommend against using plain (or even padded) ElGamal in production use. If you intend to use elliptic curves for message encryption and signature I strongly recommend you to either use EdDSA or ECIES.


The de-facto answer to any question about increasing the AES rounds is that as yet there doesn't appear to be any need, and any time you do so involves implementing at least some of it in custom code, which is inherently risky.

As far as running AES twice goes, have a look at Meet in the Middle (MITM) attacks. I don't know how relevant these will be to your target scenario given the space requirements, but in general they mean that running two encryptions is only twice as good as running one.

Throughout this post I'll refer to AES-128 as simply AES.

You certainly wouldn't be able to use the scheme you describe with the same key as this would not lead to 20 rounds of AES, because the key schedule would be incorrect for the second half of the rounds. Moreover, since the last round of AES is not the same as the intermediate rounds, you would end up with

[pre-whitening + 9 rounds + 1 last round ] + [ pre-whitening + 9 rounds + 1 last round]

If you were to extract the final values from the key schedule, you could use these to generate the next iteration of the key schedule. Using these two sets of data and your own implementation of AddRoundKey, you could remove the final round key, complete the final round into a full intermediary round and invert the pre-whitening that was about to occur (since pre-whitening just involves xoring in the next round of the keyschedule).  However, by the point you've done this you've basically ended up implementing most of the internals of AES yourself, and in a very messy way. Worse still, any home-brew AES implementation is likely to have significant side-channel weaknesses, so should be avoided.

The following question (suggested by SE to the right) might help with understanding the key schedule side:
how can i add more rounds to aes


How to customize a standard encryption algorithm?

The comments on the question are very good. That said, I'll try to address the question(s).

  What factors should I consider so that it does not become weaker?

This is a very important concern that I am glad you have. One of the big strengths that standard ciphers have is that lots of really smart people have looked at them and have not been able to break them. See Schneier's Law -- "Anyone, from the most clueless amateur to the best cryptographer, can create an algorithm that he himself can't break."

So normally the answer to this question would be to publish the details of the modification so that other cryptographers can analyze them and determine whether or not security has been weakened due to your modifications. Based on your comments, however, it sounds like that might violate other design constraints (BTW, I agree with the other commenters that keeping your algorithm secret is a poor choice). So, instead, I'd recommend hiring a group of experts to review the design and point out any fatal flaws. Actually, what I'd really recommend is that you use standard ciphers and just keep the key secret.

  What skill sets would be required to undertake this task?

Years of experience breaking ciphers. There are lots of ways to gain this expertise, but no shortcuts. It will take years of experience. That said, what modifications you make will have a great impact on what experience you need. For example, could the changes possibly create side-channel attacks? If so, you need that experience. The less you change the better and the easier it will be to do the analysis, but at the same time, the less you change, the more I have to wonder why you are changing anything at all. Make sense?

  How complicated can it get?

Depends on what you do. It could get very, very complicated. To the point that you are really not changing things and really creating a new cipher.

For a recent example of an "updated" cipher, I suggest you look at the Spritz cipher. It is an "update" to RC4. Maintains similar structure to the RC4 cipher but has very significant modifications. Also, take a look at this paper which claims statistical weaknesses in Spritz. See, even seasoned pros can potentially get things wrong when updating/modifying a standard cipher. This also is a good example of why publishing your cipher is a good thing.


Are My Answers to This Hash Question Correct?

What needs to be memorized in applied science (physics, crypto) is not a set of formulas. It's, for a few of the simplest formulas studied: what the formula yields, for what inputs, the units for inputs and output, and how to derive the formula when it does not boil down to multiplying or dividing the inputs in a way that can be found from the units. When one can't derive a formula or don't know its units, it's risky to apply it in real life¹.

We have an illustration: the question originally came with all the right formulas, but what the inputs should be was lost, or in the wrong unit (number of hashes versus hash length in bits), as quickly hinted by the terser answer. And for the now added formula-as-a-picture $q(n)=1-\left(\frac{365-1}{365}\right)^n$ it is lost what the formula yields, which has next to no relation with a birthday attack, contrary to the formula's heading.

That formula gives the probability that among $n$ persons, at least one was born on the 4th of July² of some unspecified year, assuming even repartition of birth days of humans on each of 365 days in a year³, and random selection of the $n$ humans⁴.

How do we derive a formula for that probability $q(n)$ ? Picture a room. Let $n$ be the number of persons in the room, $k=365$ the number of days in a year. If the room is empty, no one in the room was born on the 4th of July. Thus $q(0)=0$. Now, picture persons entering the room one by one (nobody leaves) until there are $n>0$. Someone in the room was born on the 4th of July if and only if at least one of two events hold:

Before the last person who entered the room did so, there was already one person born on the 4th of July. The probability of that event is $q(n-1)$, by the definition we give to $q$.
The last person who entered the room was born on the 4th of July. The probability of that event is $1/k$ and independent of $n$ and of the previous event (under hypothesis above following "assuming").

There's a formula for the probability that one of multiple independent events hold. Do yourself a favor and forget about it. Instead: if the probability of an event does not come evident, try the complementary event. Here that complementary event is: nobody in the room was born on the 4th of July. It should be clear that in our (non-empty) room there's nobody born on the 4th of July if and only if that held before the last person entered the room, and that person was not born on the 4th of July, which is the complementary event of (2.) above.

Now it's time to apply three indispensable rules in probability:

The probability that independent events all hold is the product of their probabilities.
The probability of the complementary event is 1 minus the probability of the event.
Independence of events is maintained when going to the complementary event.

And we get: $\forall n>0$, it holds $1-q(n)=(1-q(n-1))\times(1-1/k)$.

By induction, or directly by applying the first rule to all persons in the room, it comes $1-q(n)=(1-1/k)^n$, which we can rewrite as
$$q(n)=1-\left(\frac{k-1}k\right)^n$$
and obtain the question's formula for $k=365$.

How does that apply to the question then? Well, in (a) we want the probability that $n$ hashes of $b=8$ bit length have the same value as a the hash of a particular message. Picture a hash as an 8-bit value like $\tt 01100101$. Under the standard assumption that the hash function (the thing producing hashes from messages) behaves as a random function, the hashes behave as random values among $2^b=2^8=256$. That parallels the birth days of people in the room, which behaves as random values among $k=365$. We can thus adapt our existing formula, replacing $k$ with $2^b=2^8=256$, and get $q(n)=1-\left(\frac{2^b-1}{2^b}\right)^n$ or the equivalent $q(n)=1-\left(1-2^{-b}\right)^n$.

Here, we can directly apply that formula since $b=8$ is small. But take note that in cryptography, our hashes often use much larger values of $b$, e.g. $b=224$ would be considered a bare minimum nowadays in some applications. That formula still holds, but we can get into issues with its numerical stability. Using an ounce of math around that is not hard.

I really suggest that a student derives the formula for question (b), and only uses the ones in my Birthday problem for cryptographic hashing, 101 to verify the outcome, or after trying hard.

¹ Wrongly applying formulas can kill or cause huge losses, in engineering, chemistry, medicine, and business. In higher ed, well-thought notation at such exams should IMHO penalize incorrect answers, much more than no answer vs correct answer.

² That also works for my birthday, or any particular day in the year except February 29th.

³ An approximate model, mostly because reproductive activity is seasonal in most species, including humans to some degree.

⁴ That hypothesis could be seriously wrong at an exam for the driver's license.


RSA key pair generation using PRNG with same seed

To begin with, we have to assume your deterministic random bit generator is adequate for generating practically indefinite bit sequences given a single seed, and that your prime generation algorithm is such that it will always output a prime eventually, given any such indefinite pseudo random bit sequence.

Obviously, a 2048 bit two-prime RSA modulus can't have any factors in common with a 1024 bit two-prime RSA modulus, so, yes, changing the parameters might entail different output. Given my initial assumptions you will get an output in both cases, and they can't be the same for purely arithmetic reasons.

The same goes for implementation details: E.g. using a sieve or generating every candidate at random will also (likely) lead to different output, even if the DRBG sequence is the same.

Consequently, if you are asking e.g. because you want a way to store RSA private keys in a compressed format, your compressed format must contain an unambiguous indication of the number of primes to be generated, the bit sizes of these primes, the algorithm to be used for generating them, as well as any other parameter of the algorithm that might influence the output.

OTOH, if the problem is rather that you are looking for ways to tell if a given implementation suffers from RNG failures and has historically generated predictable RSA private keys, I am afraid this answer doesn't necessarily help much. In such case the conclusion would be that, no, you can't infer that your RNG is safe, just because your RSA private key generation procedure hasn't historically generated any prime number collisions.


Can I use the Sequence Number as the (implicit) IV in AES-GCM IPsec?

If I am correct, and you can just the ESN has the implicit IV, is doing so compliant with the standards?

No, it would not be compliant with the RFC. The RFC clearly states that there must be 8 bytes of IV payload immediately in front of the ciphertext (see section 3). Omitting those 8 bytes would not allow interoperability with standard implementations of ESP-GCM (and a large part of the reason the IETF does RFC's is to allow different implementations to interoperate).

Yes can, of course, copy the ESP sequence number into the 8 byte IV; that meets the requirement for uniqueness; however that obviously doesn't do the bandwidth saving you're looking for.

Alternatively, if you feel strongly enough about it, you could design a vendor-specific encryption method that does GCM (and derives the sequence number in the ESP header as payload); IKE does provide ways to do that.  However, you can't claim compliance to RFC4106...


Why is the number of qubits used in Shor's factoring algorithm so high?

There is a superposition of states initially, and there must be enough qubits in the circuit so that after the iterations the correct period of the function $f(x)=a^x\bmod N$ where $a$ is random and $N=pq$ can be found, i.e., the convergence should take place without wraparound effects, since we are working in a cyclic group and wraparound can introduce false alarms via accumulation.

Quoting Wikipedia:

  Shor's algorithm consists of two parts:

  A reduction, which can be done on a classical computer, of the factoring problem to the problem of order-finding.
  A quantum algorithm to solve the order-finding problem.

  […]

  The quantum circuits used for this algorithm are custom designed for each choice of $N$ and each choice of the random $a$ used in $f(x) = a^x \bmod N.$ Given $N,$ find $Q = 2q$ such that $$N^{2}\leq Q<2N^{2},$$ which implies $Q/r>N.$ The input and output qubit registers need to hold superpositions of values from $0$ to $Q − 1$ and so have $q$ qubits each. Using what might appear to be twice as many qubits as necessary guarantees that there are at least $N$ different $x$ which produce the same $f(x),$ even as the period $r$ approaches $N/2.$


As far as we know, no: from a mathematical standpoint, exposure of the raw RSA private key operation does not leak the private key, or anything allowing to perform the raw RSA private key operation (such as another private key, or a factorization of the public modulus). We have no proof; but this has been well studied, and any advance in that direction would make the headlines.

Things can be very different in practice, where you have to consider side channel and fault injection attacks. There are so many such attacks around, and they depend so much on the implementation (hardware, CRT or full modulus, Montgomery or straight arithmetic, blinding(s), randomized exponent scanning, other countermeasures..) that I pass on that part of the question.


Should we trust the NIST-recommended ECC parameters?

Edit: I have made some tests and I found something weird. See at the end.

Initial answer:

At least the Koblitz curves (K-163, K-233... in NIST terminology) cannot have been specially "cooked", since the whole process is quite transparent:

Begin with a binary field $GF(2^m)$. For every m there is only one such field (you can have several representations, but they are all isomorphic).
Restrict yourself to prime values of m to avoid possible weaknesses by plunging into sub-fields.
Consider curves $Y^2+XY=X^3+aX^2+b$ where $b \ne 0$; this is the normal form of non-supersingular curves in binary fields.
You only want curves where $a = a^2$ and $b = b^2$, so that you can speed up computations with the Frobenius endomorphism (basically, you replace point doublings with simply squaring both coordinates, which is very fast).
When $a = 0$, the curve order is necessarily a multiple of 4; when $a = 1$, necessarily a multiple of 2.

Then you want a curve order which is "as prime as possible", i.e. equal to $2p$ or $4p$ for a prime $p$ (depending on whether $a = 1$ or $0$). For $m$ ranging in the "interesting range" (say 160 to 768), you will not find a lot of suitable curves (I don't remember the exact count, but it is something like 6 or 7 curves). NIST simply took the 5 of them corresponding to the $m$ values which were closest to (but not lower then) their "security levels" (80, 112, 128, 192 and 256-bit "equivalent strength"). There is no room for "cooking" here.

So I would say that at least Koblitz curves are demonstrably free from all these "cooking" rumours. Of course, some other people argue that Koblitz curves have some special structure which might be leveraged for faster attacks; and that's true in two ways:

Faster computations mean faster attacks, mechanically;
One can solve discrete logarithm "modulo the Frobenius endomorphism" which means that K-233 is about as strong as a 225-bit curve (because 233 is an 8-bit number).

I still consider such curves to be reasonable candidates for serious cryptographic work. They have been "in the wild" for more at least 15 years and are still unscathed, which is not bad, as these things go.

Edit: I have made a few tests, enumerating all Koblitz curves in $GF(2^m)$ for $m$ ranging from 3 to 1200. For each $m$, there are two curves to test, for $a = 0$ and $a = 1$. We consider the curve "appropriate" if its order is equal to $4p$ (for $a = 0$) or $2p$ (for $a = 1$) with $p$ prime (this is the "best possible" since the curve is always an extension of the same curve in $GF(2)$, so the curve order is necessarily a multiple of the curve in $GF(2)$, and that's 4 or 2, depending on $a$). For the "interesting range" of $m$ between 160 and 768, there are fourteen appropriate curves:

$m = 163$, $a = 1$
$m = 233$, $a = 0$
$m = 239$, $a = 0$
$m = 277$, $a = 0$
$m = 283$, $a = 0$
$m = 283$, $a = 1$
$m = 311$, $a = 1$
$m = 331$, $a = 1$
$m = 347$, $a = 1$
$m = 349$, $a = 0$
$m = 359$, $a = 1$
$m = 409$, $a = 0$
$m = 571$, $a = 0$
$m = 701$, $a = 1$

NIST's target was their five "security levels" of 80, 112, 128, 192 and 256 bits, and a curve would match that level only if its size is at least twice the level. So the standard curve for each level ought to be the smallest curve which is large enough for that level. This should yield Koblitz curves in fields of size 163, 233, 277, 409 and 571 bits, respectively.

Strangely enough, this matches NIST's choices except for the "128-bit" level, in which they chose $m = 283$ instead of $m = 277$. I don't know the reason for this. For both field sizes, the smallest possible reduction polynomial is a pentanomial ($X^{277}+X^{12}+X^{6}+X^{3}+1$ for $m = 277$, $X^{283}+X^{12}+X^{7}+X^{5}+1$ for $m = 283$), so neither field is at a computational advantage on the other is using polynomial bases (well, the 277-bit field is a bit shorter, so a bit faster). With normal bases, the 277-bit field is actually more efficient, because it accepts a "type 4" Gaussian normal basis, while the 283-bit field is a "type 6" (smaller types are better for performance). The list of all suitable Koblitz curves is easy to rebuild and, indeed, NIST / NSA did it (e.g. see this article from NSA-employed J. A. Solinas -- search for "277").

Why they chose the 283-bit field is mysterious to me. I still deem it very improbable that this constitutes "cooking"; this is a backdoor only if NIST (or NSA) knows how to break Koblitz curves in a 283-bit field and not in a 277-bit field, which not only requires an assumption of "unpublished big cryptanalytic advance", but also requires that supposed novel breaking technique to be quite weird.


You could use message specific keys, which encrypt the messages themselves. Once a secret key has been established you can encrypt the message specific keys with it and send them over in a new message (with meta-data) to user B. You should of course have some method of storing the encrypted messages somewhere for this to work.


This question is similar to asking whether combining multiple symmetric encryption algorithms is a good idea. Of course it is less likely to get a collision for MD5 and SHA-1 simultaneously compared to just getting a collision for SHA-1. Surprisingly, it is, however, not much more expensive to find a collision to both MD5 and SHA-1 than to find one only for SHA-1, as explained here. Also using two hashes decreases the efficiency because you have to hash everything twice and it becomes more difficult to implement it correctly. Moreover, if you care not only about collision resistance, but also other properties, concatenating two hash functions could even be less secure than using just one of them, as explained here. Overall, it seems to be a better idea to just use one good hash function.


Why should the input value on a DPA attack be non-constant?

The Pearson product-moment correlation coefficient is what you evaluate, in general, when you perform DPA (CPA would be a better name for this, but DPA is used also in this context).

It is defined as:
$\rho(X,Y) = \frac{cov(X,Y)}{\sigma_X\sigma_Y}$

Where $X,Y$ are your vectors, $cov$ is the covariance and $\sigma_X$ is the standard deviation of X.

In your case, one of the vectors should be a vector of power values at the same time instant for all traces and the other vector should be the hamming weight of your hypothesis.

In your case the second vector is made by the same value. Therefore its standard deviation is 0 and then the correlation is not defined (denominator is zero).

Note that DPA is much better than SPA because by using multiple traces it somehow average out other factors (i.e. noise), but for this you also need different input values (I would say the more the better).


Using RSA signature as a secret material

Yes, the idea of using RSA signature as KDF can work. The KDF's key will be the RSA private key, and the other input of the KDF will be the message to sign. Other requirements:

Either:

The signature is post-processed by a cryptographically secure PRF, e.g. a hash (which will make the output of the KDF indistinguishable from random, and the KDF uninvertible).
Perhaps: It is kept only suitably little low-order bits of the raw output of the integer constituting the RSA signature. Without proof, I conjecture that for $n$-bit RSA, and secure deterministic signature padding, the low-order $n/3$ bits are indistinguishable from random, and the KDF uninvertible (including with the public key).
It maters neither that the "secret material" output of the KDF is distinguishable from random, nor that the input of the KDF is reconstructible form its output (e.g. by one holding the public key, or because some bits are distinguishable from random).

It is used a secure deterministic RSA signature scheme, including RSASSA-PKCS1-v1_5 of PKCS#1, and ISO/IEC 9796-2 scheme 1 and 3.
The signing procedure does not force something variable in the signed message, nor in the part of the signature actually used.

Requirement 1 insures that the output of the KDF has the desired properties. With 1.1 or perhaps 1.2 (an unproven shortcut to save a hash), the output of the KDF is indistinguishable from random, and the KDF is not invertible. With 1.3 the signature itself can be the output (no matter how it is formatted, including e.g. base64), and that could be usable for a KDF generating, from public material, some output that only needs to be unpredictable and not colliding, but can be long and distinguishable from random.

Requirements 2/3 are there to insure that the KDF is worth the name function, that is the same input always yields the same output. Requirement 2 excludes randomized RSA signatures, including  RSASSA-PSS of PKCS#1v2, and ISO/IEC 9796-2 scheme 2. Requirement 3 excludes, for example, a Smart Card that would increment an internal counter at each signature, and force that in the message being signed, or (combined with 1.1 or 1.3) as a suffix to the signature.

Unfortunately, I know no reference.


Basic Encryption and Decryption related question

For a block cipher

A block cipher is a PRP, a Pseudo Random Permutation. That is: given a key it generates a permutation of all possible plaintext blocks to all possible ciphertext blocks. So there is a bijection between each plaintext block and each ciphertext block, i.e. each possible plaintext block is assigned its own ciphertext block. So there is a 1:1 relation between the plaintext block and the ciphertext block given a specific key.

This doesn't of course happen in practice, this is just a mathematical description. Instead each plaintext block that is inserted into the block cipher gets transformed into a single ciphertext given a specific key. Without the key you cannot reverse this process (unless the cipher is broken). It is of course also impossible to retrieve the key from the plaintext and ciphertext. Decryption performs the reverse operation.

Now what happens if we change a bit in one of the ciphertexts? Well, you get another ciphertext, which in turn maps to a different plaintext. This plaintext can be any of the remaining $2^{128}$ plaintext. As all possible 128 bit plaintext are possible you get one block of random garbage. The cipher just reverses the mapping without checking that you get the wrong plaintext block!

Now this explains what happens with a block cipher. How the change is otherwise handled depends on the mode of operation that the block cipher is used for (ECB, CBC, CFB, CTR etc). If you introduce errors in the ciphertext you would have to look at the error propagation property of the mode of operation.

If the block cipher is CBC and padding is applied then an attacker may have enough information to perform a padding oracle attack. This means that the attacker can use the unpadding performed by the receiver to quickly and completely find all the plaintext from the message without breaking the block cipher. So in this case introducing a modification of the ciphertext may give the attacker enough power to find out all information about the message - full loss of confidentiality!

For stream ciphers

For stream ciphers (that generate a key stream) the situation is significantly easier. With a stream cipher (or OTP) changing a single bit in the ciphertext simply changes the bit at the same location in the plaintext.

Preventing modifications

Modification by an attacker can of course not be prevented by any algorithm. What is possible though is to add an authentication tag to the ciphertext. An authentication tag is usually computed using a Message Authentication Code or MAC. By verifying the MAC against the plaintext or ciphertext the receiver can detect if the integrity of the message is still intact.

Many new protocols, including TLS 1.3, use so called authenticated ciphers. Authenticated ciphers always create an authentication tag internally. So it should always be possible to verify that the ciphertext is not changed in transit.


"Jitterentropy" vs CPU RDRAND in VeraCrypt 1.24

I too am perturbed ~~~.  A few relevant points that cause my own knees to wobble:-

A TRNG is a special cryptographic case in that it has information theoretic security.  And proving this requires accurate entropy estimation which is very difficult and pretty much still an open question for general sources. Killmann and Schindler,  Schürmann and Grassberger, Herrero-Collantes, Garcia-Escartin and I have shown this measurement to be intractable.  Even NIST acknowledges it.     Jitterentropy injects raw entropy into pools via a primitive LFSR (§3.1.3), and then Shannon entropy is measured via the school boy  log formula.  That’s not possible for raw general sources and it’s done on a flawed IID assumption.    $  \frac{d^2t}{di} $  is not a de-correlator (it's a low pass filter), and there was no permutation testing undertaken to prove the counter.

Stephan Müller is  indeed long.  I don’t like that.  The source of entropy should be plainly obvious to even the stupid and be there right up in your face.  Period. It should not take hundreds of lines of explanation and countless graphics. The entropy either comes from God, or doesn’t.    This is too complicated for me to inspire confidence that it’s not just a non OTP capable CSPRNG akin to /dev/urandom or a Modular Entropy Multiplication TRNG do-da :-

There are no obvious safety factors for entropy measurement.  I use a conservative 2 or 3 in my designs, but  Jitterentropy has none.  Lifting apparatus had a safety factor of 6, so it would seem prudent to have some factor if your life depends on it.  Even /dev/random has accommodation for one (although it's unwritten).

An (insurmountable?) fundamental problem with instrumentation of any OS kernel is the Observer Effect.  If you're hunting single bits of OS entropy, the signal to noise ratio is ~1:1.  A 0dB entropy signal is even worse than some of those really poor supposedly quantum TRNGs you find lurking in ePrint.

Finally, VeraCrypt’s random number generator documentation does not mention Jitterentropy as the source of it’s secrets.  They talk of:-

• Mouse movements
• Keystrokes
• Mac OS X and Linux: Values generated by the built-in RNG (both /dev/random and/dev/urandom)
• MS Windows only: MS Windows CryptoAPI (collected regularly at 500-ms interval)
• MS Windows only: Network interface statistics (NETAPI32)
• MS Windows only: Various Win32 handles, time variables, and counters (collected regularly at 500-ms interval)

All the chatter in the VeraCrypt forums seems to concur.  We know unequivocally that         reading Java's System.nanoTime on a modern CPU generates true entropy, and that forms the basis of real time operating systems (RTOS).  Nullifying propagation delay by going to an expectation of $ x\delta $ mean execution times  in an RTOS does not necessarily allow you to quantify it in multi-tasking desktops.    But it’s very difficult to measure decisively. And the entropy rate is unstable, or at best meta stable. Especially within domain of all dedicated CPUs, IP CPU blocks and wacko software environments.

In management if you can't measure it, you can't manage it (Peter Drucker). There are other issues that perturb me as well, but this is getting waay too long.  I’m convinced that it’s a good CSPRNG, but remain unconvinced that it’s a TRNG, suffering the same basic mensuration problem that haveged and RDRAND/RDSEED do.


The discrete logarithm problem is usually only considered in prime groups. And there $p-1$ has to have at least one large prime factor.

Composite moduli are usually used for RSA problem (related to factorization), quadratic residuosity or composite residuosity. The hardness of these assumptions depends on the fact that the order of the multiplicative groups are not known (the factorization can be calculated from this order directly).

In general, the discrete logarithm problem could be considered in composite groups, and there you would require the totient $\phi(n)$ to have at least one large prime factor. The reason for this is, that the order of the multiplicative group mod n is $\phi(n)$. In prime order groups this happens to be $p-1$.

The reason for this assumption are algorithms like Pohlig-Hellman and Index Calculus. If the multiplicative group order has only small factors, then the problem becomes much easier.


In Theory
In theory, either method works and has its advantages and disadvantages. Sending the entire chain up to the root means the other party (e.g., web browser) has everything they need to do the validation. A disadvantage is that more bandwidth is used.

Sending only the one certificate could yield better bandwidth usage (the verifying party still has to request other certs in the chain, but these could be cached). But, the certificates then must embed information on how to retrieve the next link in the chain. This creates problems because if that information ever changes. In the case of SSL, then, the server would have to constantly be checking if the location was still valid and accessible. This could lead to DOS attacks on any server in the certification chain causing the server to be inaccessible.

In Practice
I'm not exactly sure how existing protocols do this. It seems that SSL requires you to install the entire chain on the server (e.g., instructions for apache).


A trapdoor one-way injection is a trapdoor one-way function such that two different elements

of a single domain are never mapped to the same element of the corresponding codomain.

By Goldreich-Levin, if there exists an trapdoor one-way injection

then semantically secure public key encryption exists.


Secure communication between multiple peers on a public channel

Generate a symmetric key
Encrypt symmetric key using public keys of all recipients, and broadcast (or provide on request from a client)
Transmit all user messages encrypted under the symmetric key

This means you only have one copy of the message (but you do have lots of copies of the encrypted symmetric key).

Of course you need to solve the key distribution problem first, to ensure you're only encrypting the symmetric key using authenticated public keys.


What does it mean for a number to be “in the order of” a prime number?

You are (slightly) misreading the statements. I've checked through all 13 occurrences of the word "order" in that paper, and see only "typical" statements, such as:

  Let $\mathbb{G}$ be a group of prime order $q$

"Order" means one of two things in group theory:

The order of a group is just the number of elements in it. So a group of prime order $q$ is just a group $\mathbb{G}$ where $|\mathbb{G}| = q$.
The order of an element of a group $g\in\mathbb{G}$ is how many times you have to repeat the group operation of $g$ to get to the identity. For a group written additively, it's the smallest $n$ such that $ng = 0$. For a group written multiplicatively, its the smallest $n$ such that $g^n = 1$.

These are (sort of) connected by a result in group theory that says that $\forall g\in\mathbb{G}, g^{|\mathbb{G}|} = 1$. As a consequence, the order of an element always divides the order of the group.
This is a generalization of both Fermat's little theorem and Euler's theorem.

The paper you're reading only seems to use order to mean the first of these two things. Note that groups of prime order are special in that they're always cyclic groups.
The most basic example of a cyclic group is $\mathbb{Z}/p\mathbb{Z}$, and in fact every cyclic group is isomorphic to a group of this form. Note that this isomorphism is generally not efficiently computable, which is good because the discrete logarithm problem is easy in $\mathbb{Z}/p\mathbb{Z}$.


A method to receive payments at obscured addresses

Your algorithm should be secure since it's basicly the same as the "one-time-address"-algorithm in the CryptoNote protocol, which is described as following:

Alice generates two secret keys $a$ and $b$ and publishes $A = aG$ and $B=bG$.
Bob, who wants to send a coin to Alice generates a random $r$ and publishes $R = rG$ and $P = H(rA)G+B$.
Alice (or any party knowing $a$) can check weather a payment belongs to Alice by checking whether $H(aR)G+B = P$. Note that this does not require $b$, so Alice can let any other party check for payment by sharing $a$ without risking them to spend her coins.
When Alice want's to spend the coin, she calculates $x = H(rA)+b$, which is the private key for $P$ since $P = xG = (H(rA)+b)G=H(rA)G+bG=H(rA)G+B$.

Your scheme is a variation of this algorithm with $a = b$ so that $A = B$. This leads to Bob calculation $P = H(rA)G + A$, a check can be performed with $H(aR)G+A = P$ and the secret key being $x = H(aR)+a$, so you can assume it being as secure as the CryptoNote's algorithm (which is pretty secure AFAIK), however you lose the ability to share a view key to let others search for transaction for Alice.


RSA Protocol behind Yaksha Security System

Can Alice obtain the session key due to the multiplicative properties of the modulus function and the basis of which RSA is built on?

Essentially, yes.  One way of looking why RSA works (that is, why the encryption and decryption are inverses of each other) is because of two mathematical identities:

$$(M^a \bmod N)^b \bmod N = M^{a \cdot b} \bmod N$$

$$\text{If}\  a \cdot b \equiv 1 \pmod{\phi(N)}\  \text{then}\  M^{a\cdot b} \equiv M \pmod{N}$$

(Note: in the second one, you can replace $\pmod{\phi(N)}$ with $lcm(p-1,q-1)$, which gives you a stronger identity; however what I have written is good enough for now).

For normal RSA, this is sufficient; however it is easy to extend these identities to three exponents:

$$((M^a \bmod N)^b \bmod N)^c \bmod N = M^{a \cdot b \cdot c} \bmod N$$

$$\text{If}\  a \cdot b \cdot c \equiv 1 \pmod{\phi(N)}\  \text{then}\  M^{a\cdot b \cdot c} \equiv M \pmod{N}$$

This is what Yaksha is relying on; the have $a$ = the public exponent (eAlice), $b$ = the private key known to the server (dAliceY), and $c$ = Alice's private key (dAliceA).

We can see that the relationship between eAlice, dAliceY and dAliceA holds, based on the fact that:

  $dAliceA \cdot dAliceY \equiv dAlice \pmod{ \phi(mod nAlice)} $

If we multiply both sides by eAlice (and rely on the fact that $dAlice \cdot eAlice \equiv 1 \pmod{ \phi(modnAlice)}$, we get:

$$dAliceA \cdot dAliceY \cdot eAlice \equiv 1 \pmod{ \phi(mod nAlice)} $$

which is precisely the relationship we needed to assume.


What is the hash of this cipher: TLS_RSA_WITH_AES_128_CCM

In draft 14, which is not the latest draft at the time of writing there are two places where a hash is used: the one for signature generation / verification using the private key / public key pair of the leaf certificate and the one used as configuration parameter for HKDF (session key derivation)

For signature generation / verification

TLS_RSA_WITH_AES_128_CCM doesn't exist, only  TLS_DHE_RSA_WITH_AES_128_CCM exists which is similar but uses a different key agreement protocol. RSA for key agreement was explicitly deprecated for TLS 1.3. In the RFC the ciphersuite can be represented by TLS_AES_128_CCM_SHA256; beware that the DH key agreement scheme - if that is used instead of ECDH - differs ever so slightly though (disclosure: sorry, I did that).

RSA uses the supported_signature_algorithms extension to select the hash configuration parameter within the signature generation function. This is specified clearly in section 4.2.2.  Signature Algorithms.

For key derivation

The hash is after the (EC)DHE key agreement operation to derive the session keys. This will always use HKDF, as specified in appendix A.4:

  Cipher suite names that lack a "HASH" value that are defined for use
  with TLS 1.2 or later use the SHA-256 hash algorithm by default.


Recover from compromised shares with Shamir Secret Sharing

The point is that the dealer generating the update needn't know what the shared secret is.

If we had a dealer that remembered what the shared secret was (or we asked enough people to contribute their shares so that the dealer could reconstruct it), then yes, the dealer could generate new shares.

However, this would require is a dealer that did know the secret. In contrast, anyone can generate a random polynomial with an constant term $0$; all they would need is the degree of the polynomial (that is, the threshold of the secret sharing scheme), the field the polynomial is in, and the $x$ coordinates of the uncompromised parties; all this can be made public without compromising the security of the system.

Remember, the whole point of the shared secret scheme was that no one knows what the secret is (until it's officially time to reconstruct it).


Is it possible to verify a clearsigned message with a short public key (fingerprints)?

No, it isn't possible to use a fingerprint as a key to verify signatures.

The PGP fingerprint is a hash of the public key material, see RFC 4880 section 12.2; it doesn't actually contain the public key, and as such it is not correct to speak of a fingerprint as a “short public key” as you did in your question—it is more like a unique key identifier.

A hash function maps an arbitrary-length input to a fixed-length output. One of the requirements for a cryptographic hash function is preimage resistance, i.e. given an output hash, it is difficult to find the input value to the hash. In this case, the input value to the hash would be the public key that was put into the hash. More to the point, the hash function that is used to generate the fingerprint effectively “loses” the public key information that you need to verify signatures.

Considering the size of the public key data, just trying potential public keys by brute force until you re-create a fingerprint to re-discover the public key information at runtime will also not work because it is too computationally expensive.


Why use an OTP if you already have a secure channel

First, let's re-iterate that there is no true one-time pad in modern cryptography or any other information system - it's only a hypothetical thinking reference.

The reason to use OTP in this case, would be to maximize the utility of the rare window where there would be a secure channel.

Let's imagine a world without internet and public-key cryptography cannot be carried out efficiently by any instrument available to the people and the enemy, the secure channel is a scarce resource, so a huge OTP stream is exchanged here so that it may be used later over the radio, possibly chunked according to the size of messages.

This way, the time to exchange the actual (encrypted) message can be freely chosen.


Why this malicious behavior of corrupted sender isn't considered in malicious-secure OT?

In MPC we judge security by comparing to the "ideal world" where a trusted third party does the entire computation. In the ideal world, an adversary can send anything it wants as input to the trusted third party. In the ideal world, when it comes to malicious adversaries, there really is no valid sense of a "correct/incorrect input" for the adversary. (For semi-honest adversaries, their input is supplied by the external environment and they are bound to use it in the ideal world.) Since "using whatever input you like" is possible on the ideal world, it is not considered an attack against the protocol.


Decode message $m = p * q$, where $p ^ 5 \bmod N$, $q ^ 5 \bmod N$ and $N$ are known

I don't have a full answer yet but here is what I have so far.  Since you know what $p^5 \bmod N$ is and what $q^5 \bmod N$ is then you know what $m^5 \bmod N$ is. Since we also know what $N$ is then we should be able to find out how many times we need multiply $m^5 \bmod N$ by $m^5 \bmod N$ till we get a full cycle (you can calculate it through $\phi(N)$ or you can multiply by m till you get back to your original number).  From that cycle, go back 4 terms and that should be what $m \bmod N$ is.
Update: Finding $\phi(N)$ can be difficult for sufficiently large $N$ but multiplication with mods is a fairly easy cheap.  First make sure that N and 5 are relatively prime, and then (for practicality purposes) repeatedly iterate $F: x\mapsto x^5\bmod N$, starting with the known $x_0=m^5\bmod N$ until $x_{j+1}=x_0$, thus making $x_{j}$ a possible $m$


Why don't table lookups run in constant time?

It mostly has to do with the real world influence of memory caches.

A cache is a small amount of fast memory; when you read from memory, the contents are placed in this fast memory (possibly along with adjacent locations); if you read from the location again, you read it from the fast memory (which, of course, proceeds much faster).

Hence, if you read a location that you've read before, it goes much faster than if you read a location which you haven't; hence, you're not constant time.

Modern CPUs can process data much faster than memory can respond (perhaps by a factor of 100), hence caches are pretty much ubiquitous.  Some lower end microcontrollers might not have them; but they're an exception...


Shamir secret sharing: calculate rest of shares when you know secret and one share

My question is whether one can start with both a secret and a string - representing ultimately a share in the end state - and work his way into finding the rest of the shares?

With $t-1$ shares and the secret, you can uniquely reconstruct the polynomial (and with that, generate all the rest of the shares, assuming you know their $x$ coordinates).  With fewer shares than that, we can't reconstruct the polynomial (even with the secret), as there'll be at least $p^k$ (where $GF(p^k)$ is the field you're working in) possible polynomials.

In essence, the secret is just another share (with $x$ coordinate 0).

However...

  Splitting the secret in shares and sending them encrypted will still leave them vulnerable to brute force attack due to the inherent structure of the secret

Nope.  You appear to be speculating that an attacker with $t-1$ shares might guess the secret, and reconstruct the other shares based on that guess.  They can certainly do that; however they have no way of determining whether that guess is correct (because all possible guesses will yield plausible looking shares).

In turns out that Shamir Secret Sharing is Informationally Secure; that is, with $t-1$ shares, you get no information about the shared secret, even if you have unbounded computation at your disposal.  This statement assumes that the polynomial was generated truly randomly; however it makes no other assumptions.


How unique and secure are verification codes created from different hashes?

There should not be any need to use several different hashes. One such as SHA3 will provide what you need. A Hash, Salt, and Stretch configuration as provided by for example bcrypt or scrypt will add extra protection if you want it.

As for shortening the code, yes this will decrease security but the same length of a NIST recommended password should suffice: 8 characters


Can we solve the Hidden Number Problem in $GF(2^n)$?

Yes, it appears that it can be solved in practical time in $GF(2^n)$, if the attacker gets $n+\epsilon$ random $a_i$ values, even if he gets a single bit of the $a_i \times k$ values.

The chief observation is that the mapping from $a_i$ to bit $j$ of $a_i \times k$ (which I'll refer to as $bit_j(a_i \times k)$) is bitwise linear (for constant $j$, $k$).

So, assuming that we have $a_i$ and the corresponding $bit_m(a_i \times k)$ values (for some known $m$), our first step is to find $n$ linear independent $a_i$ values (which, given $n+\epsilon$ random $a_i$ values, we'll have with good probability); we view this as a set of $n$ linear equations, and solve them in $O(n^3)$ time, giving us the mapping between any value $a$ and $bit_m(a \times k)$

Now, for polynomial representations of $GF(2^n)$, for every $i, j$ pair, there is a constant $c_{i,j}$ where $bit_i(a) = bit_j(a \times c_{i,j})$ for all $a$.

This observation allows us to find the linear mapping of $bit_n(a \times k)$ for any $n$, as $bit_n(a \times k) = bit_m(a \times k \times c_{n,m}) = bit_m( (a \times c_{n,m} ) \times k )$; in other words, to perform this mapping, we multiply the vector by the constant $c_{n,m}$, and then apply the mapping we already know (both of which are linear operations).

The result of this are $n$ linear maps giving us all $n$ bits of the product.  Then, we can solve these $n$ linear maps for the input that gives a 1 bit for the lsbit map, and 0 for the rest; the solution for this is $k^{-1}$, which immediately gives us the value for $k$.

I suspect that there are signficantly more efficient ways to solve this; however this algorithm should be enough to answer the question.


Estimating random number entropy for input into 256 bit hash

It is a little unclear, how you transformed all your numbers... e.g. how did you interpret your decimal numbers "as binary" and "create a bitmap"? Then you look at the binary representation and guess what.... and they are just the numbers 0-9 in binary and added on an static number (no idea where that came from).

Things to consider:

Of course the numbers 0-9 do not have an integer sized entropy, this range is not of the form $2^{x}$. Actually it is $3.3219...$
If your numbers are uniform distributed over 0-9, then evaluation of fixed bits will result in a loss of entropy or a loss of uniformity (or both).
What is your actual goal? In the beginning you mention "in a computer program" and then later on "use that as a key". Random numbers serve a lot of purposes, and different tasks require different properties (and thus different PRNGs).

How to solve your problem?

Let's assume  you want 256 bit of entropy and your RNG is good enough to create cryptographic keys (if you don't know the difference, read up on this).
If you do not want to "throw away" entropy, you can just calculate a large random number in the decimal system and use your RNG (let's call this $\Re$) for each digit. This way it is uniform distributed. You can do this e.g. by this formula: $r = \sum_{k=0}^{t}10^k\cdot\Re $. You have to choose $t$ large enough, that is covers at least the range from $0$ to $2^{256}-1$, which means $t \ge 77$. But now you $r$ is still uniform distributed in the "wrong range", because it can be greater than $2^{256}$.
Now you can decide if you want to start over if the result is higher than that, this will result in a uniform distribution in the "correct range" since you don't change the distribution by favoring some values over others... you just start fresh for the wrong results.
Or you can increase $t$ even more, and then calculate $r' = r \text{ mod }2^{256}$. This does not result in a perfect uniform distribution, but if the range for $r$ is a lot larger than $r'$, it is really close to uniform.
Otherwise, you can also do the rejection sampling at the bit level (That's throwing away some results, so that others are still uniform to each other): Draw a number from 0 to 9 and if it is 8 or 9, ignore it and draw again. Now you can use the binary representation of the numbers 0-7 as 3 bit for the long binary result. Repeat this and concatenate the 3-bit blocks.

You can even combine these techniques to optimize the number of rejected results, but that's probably going too far, these simple solutions should work.

PS: Concerning your first conclusion

  That must be why you shouldn't just use raw integers as random numbers in a computer program.

That statement is just not true. RNGs usually run on integers, and there are different RNGs for different tasks. What else should you use as random numbers? Floating point numbers are much worse to handle than integers, and even harder to actually proof statistical properties Therefore, RNGs use integers, because they are better than anything else, but the properties depend on the actual RNG. For example linear congruential generators and similar constructions are REALLY fast and have a long period, but their randomness has poor quality due to a large correlation of sequential elements. Linear feedback shift registers offer randomness of higher quality, but it is also possible to predict the stream from a short sequence of outputs. For statistical purposes the Mersenne Twister offers probably the best performance and high quality randomness.

But for cryptography, you need other properties (check the first link in this post). For actual computer programs: You should use the implementations in the standard libraries for secure PRNGs, e.g. SecureRandom in java.

Anyway, hashing is usually done to have the one-way property, s.t. you can not compute back to the original message/object/input/... E.g. if you have hashed values, you can compare if two items are the same, but nothing else. If you have to guess this item, you can't.


Lattice-based cryptography prone to side channel attack?

my understanding is that Supersingular isogeny Diffie-Hellman (SIDH) is fully protected against timing and cache attacks as all operations on secret data run in constant time. That was my own experience.


What is double-length derivation key ?

My reading is that is the Base Derivation Key (BDK), used to derive (produce) an Initial PIN Entry device Key (IPEK). Both BDK and IPEK are 16-byte keys for 3DES; otherwise said for TDEA keying option 2 per the (obsolete) FIPS SP-800-67-Rev1 section 3.2, item 2.

The 16-byte BDK or IPEK is split into two 8-byte halves $K_1$ and $K_2$, and 8-byte $P$ is enciphered into $C=E_{K_1}(D_{K_2}(E_{K_1}(P)))$. That's the usual Encrypt-Decrypt-Encrypt of 3DES/TDEA, as explained in step 3.

Step 5 complements the high-order two bits of the four left/high order bytes of each of the 8-byte halves of BDK, to form a different BDK'. The same 8-byte value obtained in the first half of step 3 is enciphered per 3DES/TDEA using BDK (resp. BDK') to form the left/high order (resp. right/low order) half of IPEK.


Negotiate a secure connection without certificates?

If you have a side channel where you can verify a string is identical you can simply do a Diffi Hellman key exchange and then verify both sides have the same resulting key.
If the side channnel is secure from evesdroppers you can directly compare the key. But you would probably prefer to compare a hash of the key. This also allows comparing something much shorter then the actual key.
For example I have seen systems for voice communication which after setting up the key the parties are expected to read out a verification number, but this simply assumes the mitm can not take the place of both parties and read out a different number to each. With nothing pre shared preventing man in the middle is tricky.
If you have a mitm resistant side channel which is public and very low bandwidth the above solution works. If it is high ebough bandwidth simply do DH key exchange over it.

Edit: to ensure the user can compare a short hash we should add a large random nounce before hashing the key. So a mitm won't be able to make keys which will collide with a truncated hash.


What can I do, if my SRP password verifier was stolen?

In SRP, if the server-side password verifier leaks, that does not immediately allow login to the server. That "only" exposes the password to brute force search in a dictionary (each password test essentially does what the normal client and server do at login, only at high speed and with speedups because the server's challenge can be fixed). The attack's difficulty depends mostly on the password quality; and on if the password first goes (on the client side) thru some entropy-stretching (PBKDF2 or modern alternative), which unfortunately is not part of SRP (no mention of a slow pre-hash of the password with some standard-defined salt).

Thus if the server database with SRP password verifiers leaks, the passwords are at least as exposed to brute force search as with standard password hashing methods, and typically much more. Short of changing all the passwords, nothing can be done to that.

Said leak however does not compromise confidentiality of sessions encrypted earlier using SRP-negotiated session keys.

Update: I now understand that the question uses SRP password authentication to protect the client from a bogus server when the password verifier is secret. I was told and accept this works.

The adversary with the password verifiers can act exactly as the server (assuming the clients does not otherwise authenticate the server). I do not see a remedy that re-establish server authentication after password verifier loss, short of changing all the passwords, or authenticating the server by a method other than SRP, or changing SRP in a way that requires storage on the client.

SRP is not without virtue; in particular, if it was enforced on the client side (which is rare), and if it came with slow password hash (which is not standard), it would be safer than current practice (establishing a TLS tunnel with server authenticated using a certificate, then sending password in that tunnel); in particular making it impossible that impersonating the server at a single login attempt (by way of a forged certificate or an inattentive user not using https) directly leaks the password to an attacker.


How does a client verify a server certificate?

Was I right?

Pretty much. I want to add something to help clarify though: The Verisign public key in his store is of the Verisign CA (It is also stored in the form of a certificate). Also I think this process would qualify at decryption, no?

  Verisign creates the digital signature over my certificate data. Which data?

I'm not really sure what you mean here, but I'm guessing you are referred to the public keys store.

Basically the browser/OS have to trust a Certificate Authority (in this case Verisign). This trust is implemented by putting Verisign certificate including a public key inside the software. The corresponding private key will then be used to digitally sign certificates of websites that buy Verisign services. Because the browser have the public key, it can verify anything that Verisign signed using the corresponding key, hence the strength of this model.

A question might pop: Whose private key is then used to sign the certificate that is stored in the browser? It is usually self-signed (Use the very corresponding private key) or sign by a public key that is eventually self-signed. There is no way to verify self-signed certificate, hence the trust must be made in advance (by putting certificates in store).

  The digital signature was created by what operation(?) over my certificate data? (Is this hashing?)

What Verisign (and other CA) do is generated a private/public key pair (this process is called key ceremony). They then sign certificates of websites using the private key (Which is only done once per website), this process create a certificate that is signed by Verisign, which is then passed to the browser. If you're asking about the algorithms, basically they hash the certificate content and then encrypt the hash with the private key, so typically there's usually 2 algorithms used, one for hashing (MD5, SHA, etc.) and one for encryption (RSA, DSA, etc.)

Edit: Read comments to find out more, but I think basically this explanation is correct.


Deciphering a key from XOR encrypted cypher using boolean logic

If $K$ is random and you only know $A$ or $B$ (but not both) then, no, there is no way to infer anything about the key - this is the (in)famous one-time-pad.

If you know $A$ and $B$, then you can recover $K$ very easily. Exclusive-or has those properties:

$\forall n$, $~~~~ n \oplus n = 0$
$\forall n$, $~~~~ n \oplus 0 = n$ (identity element)
$\forall a, b$, $~~~~ a \oplus b = b \oplus a$ (commutativity)
$\forall a, b, c$, $~~~~ a \oplus b \oplus c = (a \oplus b) \oplus c = a \oplus (b \oplus c)$ (associativity)

So we can do the following:

$B = A \oplus K ~~~ \Rightarrow ~~~ A \oplus B = A \oplus (A \oplus K) = (A \oplus A) \oplus K = 0 \oplus K = K$

So $A \oplus B = K$

Viewed differently, the exclusive-or operator is invertible:

$\begin{array}{|c|c|c|}
\hline
\oplus &0 &1 \\ \hline
0 &0 &1 \\
1 &1 &0 \\
\hline
\end{array}$

$\begin{array}{|c|c|c|}
\hline
A &B &\oplus \\ \hline
0 &0 &0 \\
0 &1 &1 \\
1 &0 &1 \\
1 &1 &0 \\
\hline
\end{array}$

And since the truth table is symmetric, the exclusive-or operation just happens to be its own inverse, i.e. $x \oplus^{-1} y = x \oplus y$. So if we take our original equation:

$A \oplus K = B$

We can represent it as follows:

$K \oplus A = B$

And we can then undo (invert) the exclusive-or by A:

$K \oplus A \oplus^{-1} A = B \oplus^{-1} A ~~~ \Rightarrow ~~~ K = B \oplus^{-1} A$

And as we found above, this is identical to:

$K = B \oplus A = A \oplus B$

As found at the beginning.

However, this is assuming A, B and K are all the same length. If K is smaller than A and B, then it means that K will be used multiple times (repeated over the length of the plaintext, presumably). This repetition can be exploited to successfully recover K from only B provided there is enough repetition and there is enough ciphertext to work with - see Vigenere cipher.


It can still be done, because some letters of the English alphabet are used more often. Analyzing a ciphertext based on the frequency of appearance of some characters is fittingly called Frequency analysis.

This method of cryptanalysis gets better, the more ciphertext you have. If the plaintext is in English, then you would know, that the most frequently used letter would be "e".

Because the Vigenère cipher is quite an old method of encoding something it can be (and has been) broken relatively easy by hand. The security relies on the keylength and the "randomness" of the key. 10-20 random letters is actually pretty good, but with a very long ciphertext you can ultimately still break the Vigenère method.


Why does curve25519 use a cofactor of 8?

Curve25519 was chosen to have the Montgomery shape $y^2 = x^3 + A x^2 + x$ to support the fast single-coordinate Montgomery ladder for Diffie–Hellman: given $x(P)$ and $a$, it is cheap to compute $x([a]P)$, so there is no need to pass the $y$ coordinate and implementors are not tempted to use secret-dependent conditionals to compute scalar multiplication with the naive double-and-add algorithm—that is, the shape of Curve25519 was chosen to encourage implementors of the X25519 DH function to avoid timing side channels without sacrificing performance.

Every Montgomery curve has a point of order 2 (if the equation holds for $P = (x, y)$ then it holds for $(x, -y) = -P$ so $P + (-P) = \mathcal O$), so the cofactor is always greater than 1—and when the coordinate field is $\mathbb Z/p\mathbb Z$ for $p \equiv 1 \pmod 4$ as is the case for $2^{255} - 19$, the orders of the curve and its twist are 4 and 8 or vice versa.

Curve25519 was chosen to minimize the cofactors, and when taking all the other criteria into account, the best choice had cofactor 8 for the curve and cofactor 4 for the twist.  RFC 7748 gives a deterministic algorithm to search according to these criteria in Appendix A.  For comparison, the Curve448 coordinate field is modulo $p = 2^{448} - 2^{224} - 1$ with $p \equiv 3 \pmod 4$, so both the curve and its twist have cofactor 4.


What does it mean when two encrypted files, encrypted with the same method but with different keys, when xor'd together, produce a repeating pattern?

The two plaintexts are almost certainly identical.  At the very least, any difference between them must be representable in 32 bytes, since that's as much information as the XOR of the encrypted files contains.

Assuming that the plaintexts are indeed identical, we can also see that changing the encryption key has a very simple and predictable effect on the ciphertext: every 32nd byte is affected the same way.  Clearly, this cannot be a semantically secure encryption scheme.

Indeed, the most likely explanation of the phenomenon you observe is that:

the two plaintext files are identical, and
the encryption simply consists of taking a 32-byte key (or possibly the 32-byte hash of a key) and XORing it with each 32-byte block of the plaintext.

If true, this is a very weak cipher, and it should not be hard to break.  A couple of methods to try would be:

If you can guess some part of the plaintext, you can immediately get the corresponding part of the key by XORing the guessed plaintext with the ciphertext.  For example, if the plaintext is XML, there's a good chance it'll begin with something like:

<?xml version="1.0" encoding="utf-8" standalone="no"?>

With a bit of luck, this can reveal the entire key!  Similarly, I believe Lua bytecode files should have a more or less fixed header that should also reveal at least part of the key.
Even if you can't directly guess the plaintext, you can make use of the fact that the key repeats, essentially making the cipher a many-time pad.

One way to attack such a many-time pad is to use crib dragging.  Basically, you guess an $n$-byte string that's likely to occur somewhere in the plaintext (such as, say, function in Lua code) and XOR it with each $n$-byte substring of the ciphertext.  Each XOR will yield a candidate $n$-byte substring of the key, which you then XOR with the corresponding parts of the ciphertext.  If the guess was wrong, you'll mostly get garbage, but if and when you guess right, the decrypted plaintext suddenly starts making sense.

Another way to attack such a cipher is to split the ciphertext into 32-byte blocks, take one of the blocks and XOR all the other with it (which cancels out the key, leaving you with an XOR of the plaintext blocks), print out the XORed blocks as a hex+ASCII dump (as with xxd -c 32) and examine the columns.  With the help of an ASCII table, you can infer a lot about the plaintext block you chose to XOR with the others (and thereby about the key).

Alternatively, if you're feeling lazy, you can just download xortool and feed one of the ciphertexts to it.  With a bit of luck (and the right options), it'll spit out the key and the plaintext (or at least something close enough for you to finish the job by hand) for you.


Vulnerabilities in specifying the hash algorithm used for signature verification on a per-message basis

To forge a message using a hash collision, you need to generate a signature (using that hash function to sign a "good" message); then that signature is also a valid signature for the "bad" message.

So, to prevent this from being a concern, you just never sign a message using MD5 as your hash function.  Yes, the attacker can generate a "good" and a "bad" message with the same MD5 hash, but unless he can convince you to sign the "good" message using MD5, that doesn't help him.  If you always use SHA-512 when you sign messages, that means that the attacker must find a collision in the SHA-512 hash function; we believe that's infeasible.


How many queries can you do (concretely, not asymptotically) for a balanced Feistel network with 7 rounds?

The linked paper is missing a lot of proof details. In any case, it seems impossible to say anything concrete for finite $n$ due to the existence of terms in $O(\cdot)$ notation in the bounds. You simply do not know how large those implied constants are.


Does a concatenation of hashes of differently prefixed variations of any chosen message contain all possible finite bitstrings?

Can we assume that for any chosen A, its corresponding B is unique and contains all possible finite bitstrings

No. Due to your requirement $H$ is compressing. This means that collisions must exist. Depending on your hash function construction, a collision might lead exactly the same output sequence. As a constructed example assume a hash function that processes input blocks from right to left and feeds them to SHA3. Any SHA3 collision would then work. Indeed, you cannot argue that your assumption above holds just with standard properties of a hash function.

However, finding such messages is extremely hard. Already finding two messages that lead one identical block of B is hard by the collision resistance of the hash function.

  can we use such technique as a cryptographically secure pseudo-random number generator that has no theoretical period?

No. There are also several arguments against building a PRG this way. For example with common hash functions like SHA3 this construction would be extremely expensive as you cannot reuse previous results in computing B.


Export ciphers date back to the time when cryptography export was regulated by governments, most notably the US government (see this answer for a good overview of the history of export restrictions). Back then, exporting cryptography with more than 56 bit strength was forbidden. For the Diffie-Hellman Key Agreement scheme, 56 bit of security meant that they could only use 512 bit parameters (I'm going to assume that you know how Diffie-Hellman works. If not, see for example here).

All of the remaining details of the protocol are, as far as I am aware, identical to regular Diffie-Hellman. They are a relic from past times that continually crop up and cause trouble (like in the case of logjam, which is explained well in this answer and this article). There is absolutely no good reason to support them in this day and age, and if you find a server that still allows it, you should contact their admins and tell them to disable it.

(This is also a very good reason why we should not go back to intentionally weakening cryptography, as some people have proposed lately - we tried that once and it's still hurting us, over 20 years later.)


if using cbc+hmac dealing with small size of data(less than 128bit) , will it cause any problem?

If the MAC'ing is done right (after the encryption) and if you pad the CBC data correctly there's no security risk. Howver changing to CTR or even better to GCM would be better, as both don't operate on whole blocks and GCM even provides authentication.


Don't confuse h which is commonly adopted for the cofactor in EC (Cf p13 of the doc). The class number $\mathcal{H}(K)$ for any number field K is the cardinal of the class group Cl(K).
Take a look to any course in algebraic number theory and specially H. COHEN and his famous book " A course in computational Alg. Numb Th ..."
The ring theory is very vast, and the link with EC lies in the structure of its endomorphism Ring which can be viewed as an Order in a quadratic field.
In H. COHEN you can understand that computing the class number for an random EC is not so easy, this is the reason why this value can't be chosen too small.


Is this symmetric key MAC-then-encrypt auth token methodology secure?

Is it secure, in this case, to employ a sign-then-encrypt method? I've read several opinions on this and walked away more confused than when I started.

First of all, given that your sample code is using HMAC, not digital signatures, I assume you mean MAC-then-encrypt.

The generally safe way to combine a MAC and encryption is encrypt-then-MAC: first encrypt the message, then compute a MAC on the ciphertext (including the IV and any associated data you may have!).  When decrypting, first verify the MAC, and only then try to decrypt the message.

Encrypt-then-MAC is safe because it guarantees that the MAC and the cipher each only need to do their own job: when encrypting, the MAC only receives input that has already been encrypted, so it cannot accidentally leak information about the plaintext; when decrypting, the cipher only receives input that has already been authenticated by the MAC, so it doesn't need to worry about securely handling forged or modified messages.

However, MAC-then-encrypt (or even MAC-and-encrypt) can be safe if the MAC and the cipher are chosen appropriately.  In particular, a sufficient condition for the security of MAC-then-encrypt is that the cipher mode must be length-preserving — that is, the ciphertext (not counting the IV) must be exactly as long as the input plaintext.

The CFB, OFB and CTR modes are all length-preserving, but CBC is not (unless combined with a modification known as "ciphertext stealing").  In particular, because normal CBC mode requires messages to be padded to an integer number of cipher blocks, it is often vulnerable to padding oracle attacks unless protected with a MAC applied after encryption (and thus verified before decryption).  Thus, you should not use CBC mode with MAC-then-encrypt.

  I've read that cbc-mode should be used when employing a sign-then-encrypt method. Is this the default mode for CryptoJS.AES.encrypt()?

That's hard to say, and may depend on which version of CryptoJS you're using.  This page says the default is OFB mode.  This page (for CryptoJS v3) says it's CFB.  Both of those appear to be unofficial third-party sources, but I haven't been able to find any comprehensive official documentation for this library.  Apparently it's "still a bit sparse." :(

In any case, as noted above, you should not use CBC mode with MAC-then-encrypt.  If you want to use CBC, apply the MAC after encryption.

  CryptoJS.AES seems pretty generic. Is this defaulting to AES256? Or is that something that I need to explicitly declare in my code?

See previous answer.  According to the linked Google Groups post (which may or may not be reliable, of course), the library can handle AES-128, AES-192 or AES-256, presumably depending on the size of the key you pass in.  If you pass in just a password, I have no idea which AES variant it'll choose.

(I'd also like to take this opportunity to reiterate my dislike of poorly documented crypto libraries.  It doesn't matter how well your library is coded, if nobody can tell what it's supposed to be doing and how to use it correctly and safely.)

  When passing a string to CryptoJS.AES.encrypt() I've read that it automagically generates a key and and iv 'behind the scenes'. Would it be more secure to generate my own key and iv, or should I just let CryptoJS handle that?

It looks like if you pass the encrypt() method a plain string as the key, it assumes that this string is a user-supplied password, and applies a password-based key derivation function like PBKDF2 on it.  Such functions are deliberately designed to be slow, in order to resist brute-force password cracking.  Thus, whenever possible, it's more efficient to call the key derivation function only once yourself, and to store the raw AES and/or HMAC key that it outputs.

You almost certainly don't have any reason to supply your own IV; any decent crypto library should be able to generate perfectly good random IVs for you.

  Is there more security to be had by employing a sign-encrypt-sign method, or is that just adding complexity to my app logic?

In general, there's no point in doing MAC-encrypt-MAC instead of plain encrypt-then-MAC.  That said, it shouldn't hurt either (beyond wasting a few CPU cycles, and increasing your ciphertext length a little), and it might protect you against some implementation mistakes (like forgetting to include the IV in the outer MAC input).

However, what you really should do, if at all possible, is use an integrated authenticated encryption mode like SIV (my current personal favorite) or GCM (or even the new GCM-SIV mode that combines them).  Those encryption modes come with message authentication built in, and take care of combining the encryption and the authentication safely and correctly.

(For actual digital signatures, sign-encrypt-sign might sometimes be useful, since the double signing protects against some attacks where e.g. the attacker takes a valid encrypt-then-signed message, strips off the signature and substitutes their own, or where a malicious recipient decrypts a signed-then-encrypted message and resends it to someone else, keeping the original signature.  In most cases, however, there are more effective ways to avoid such attacks.  See e.g. this earlier question for more details.)


Getting the Encryption Function From the Decryption Function + Decryption Key + Encrypted Item

Every encryption is reversible, that's why most security relies on hashing in place of encryption.


Does a partial preimage attack imply a preimage attack?

It depend on what notion of preimage resistance you mean, and on whether the preimage attack applies to only a tiny class of images or whether it works uniformly on all of them.

Fix a random hash family $H\colon \{0,1\}^{4b} \to \{0,1\}^{2b}$.  Define

\begin{equation*}
  H'(x) = \begin{cases}
    0^b \mathbin\Vert H_b(x), & \text{if $x$ starts with $1^{2b}$;} \\
    H(x), & \text{otherwise.}
  \end{cases}
\end{equation*}

Here $H_b(x)$ is some $b$-bit truncation of $H(x)$.  How does the obvious cheap preimage attack on $H'_b$ translate to the cost of a preimage attack on $H'$?

The everywhere preimage resistance (ePre) of $H'$ is at most half the bits of that of $H$, because there exists an image $y$—namely, any string starting with $0^{b}$—such that there is a known random algorithm $A_y(H')$ making $q$ queries that can find a preimage with probability $O(2^{-b} q)$ much higher than the generic $O(2^{-2b} q)$.

That is, we have an extremely cheap preimage attack on $H'_b$ for the image $0^b$ which translates to a cheaper-than-generic everywhere preimage attack on $H'$ because there exist images, namely those starting with $0^b$, for which we can find preimages at substantially lower cost than generic.
But this has negligible impact on the always preimage resistance (aPre), or just unqualified preimage resistance (Pre).  There are random algorithms $A_{H'}(y)$, for always preimage-resistance, or $A(H', y)$, for (unqualified) preimage-resistance, with conditional probability $O(2^{-b} q)$ of finding preimages given that $y$ lies in a certain class of image—but the probability of being challenged with such an image $y$ is about $2^{-b}$.

That is, although we have an extremely cheap preimage attack on $H'_b$ for the image $0^b$, it doesn't help us to find a preimage for a uniform random challenge image because the probability of being challenged with an image that starts with $0^b$ is negligible.


How to encrypt/decrypt data in an SPI BIOS FLASH

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 do we know a single differential/linear trail dominates the others?

The short answer is that we don't. There are several block ciphers (most famously PRESENT) where multiple linear trails combine to form a stronger distinguisher. The collection of trails is called a linear hull. The concept has been extended to differential-linear cryptanalysis, but I don't have any reference for a "difference hull". These multiple trail effects seem to be more pronounced in lightweight designs.
The analytic approach seems to be to assume that hulls don't contribute significantly unless they can be demonstrated to do so. If the term "resistant" is used rather than "immune", then this assumption does not feel too unreasonable.


Paillier Cryptosystem - Practical applications?

Yes, for example CryptDB uses the Paillier cryptosystem to implement homomorphic encryption for columns that require it. See CryptDB: Protecting Confidentiality with
Encrypted Query Processing (pdf) for a description.

Whether you consider that use "effective" is another matter. Earlier this month there was a back and forth between the CryptDB developers and some Microsoft researchers who claimed to have several attacks on CryptDB. However, as far as I can tell they were on the other forms of encryption CryptDB uses.


Is it possible to perform CPA(Correlation Power Analysis) when attacker has only specific round's waveform?

Yes, in general you can perform a key-recovery DPA attack on certain inner rounds of AES. Most of the attacks in public literature target leakage from first or last rounds (the outer rounds) after a highly non-linear operation (such as SubBytes) just for convenience. This attack is very easy to implement. Exploiting leakage from inner rounds becomes a bit trickier and slightly more cumbersome to implement, but it's certainly possible for the second round of AES (or second to last) and further in DES.

Let's recap a bit. One main ingredient of DPA attacks is divide and conquer. Say we are targeting AES-128. We essentially chop one intractable problem (performing key recovery on 128 bits) into 16 much smaller and attainable problems (16x 8-bit DPAs that recover each byte of the first or last round subkey). The DPA attack itself is basically comparing predictions for leakage when handling an intermediate $V$ against actual measurements. A vanilla DPA targets leakage from an intermediate $V_i=F(X_i, K_i)$ that is a function of:

data $X_i$ that the DPA practitioner knows (such as a portion of the plaintext or ciphertext), and
a portion $K_i$ of the (unknown) subkey. The main condition on $K_i$ is that the DPA practitioner can efficiently go over every possible value of $K_i$. This ensures the running time of the DPA attack stays manageable and the whole attack is practical.

Now we can see the reason we find DPA attacks on outer rounds easier: there are plenty of intermediates $V$ that satisfy these two conditions. In your example, the output of SubBytes makes an excellent choice: the practitioner needs to enumerate just $2^8$ subkeys. (There are other additional, unrelated reasons that make this a good choice; namely, it's the output of a highly non-linear operation, which helps in the process of weeding out wrong subkey hypothesis, but this is not important now.)

Note if we chose an intermediate $V$ that depends on too many key bits (in a way that the condition on $K_i$ above does not hold), then the DPA attack would just take too much time and not be practical, or even pose an advantage over plain cryptanalysis (including brute force).

Back to the original question, you can find intermediates in the second round in AES that satisfy these two properties. For example, a very, very naive attack could target the SubBytes output of the second round. The attack needs to enumerate $2^{40}$ keys. This is certainly a much heavier computation than $2^8$, but not the end of the world.

This hassle can be circumvented if the practitioner can deactivate portions of input texts by fixing them to a constant value. Say we're targeting an intermediate $V$ that is the xor of four S-box outputs: $V=S(P_1 + K_1) + S(P_2 + K_2) + S(P_3 + K_3) + S(P_4 + K_4)$. Naively, this would mean that we've to enumerate $2^{4w}$ $w$-bit subkeys to jointly recover $(K_1,K_2,K_3,K_4)$. If we fix $P_2$, $P_3$ and $P_4$ to constant values, the intermediate $V$ can be rewritten as $V=S(P_1 + K_1) + c$ for some unknown constant $c$. We can perform the DPA on the "key hypothesis" $(K_1, c)$ taking $2^{2w}$ effort (and then repeat to recover $K_2$, and so on). Overall this takes roughly $2^{2w+2}$ time, less than jointly recovering all subkeys. (I've oversimplified a bit for the sake of the explanation, but you can find intermediates in AES where this technique applies.)

From here, there are other tricks you can use to target inner rounds. They are slightly more complicated and combine DPA with more traditional symmetric cryptanalysis. Although they are described in a very narrow and specific setting, usually they can be ported to different algorithms or scenarios. Here are some examples:

Handschuh and Preneel give in Blind Differential Cryptanalysis for Enhanced Power Attacks a differential attack assisted by side-channel information to exploit the third or fourth round of DES under a certain leakage model.
Collision attacks can also exploit leakage from inner rounds. An example is Enhancing Collision Attacks by Ledig, Muller and Vallete or Two New Techniques of Side-Channel Cryptanalysis by Biryukov and Khovratovich.
Here is a DPA attack that targets the third round of DES without requiring collisions by Gierlichs and yours truly. This attack uses DPA with a regular model and a cheap regular differential cryptanalysis step. This one is probably easier to follow than the others in this list.


Why are the shiftrows in AES in a fixed order? Can the order be changed?

No it would not make a difference to security, but it will no longer be AES since it does not match the specification.

As long as all 4 rows have a different rotation count through 0-3 bytes, the permutation will fully mix the state after 2 rounds.


How many Hashes to find a digest of 2^{n−k}?

The expected number of hashes would be $2^k$.

Here's why: if we model the hash function as a random Oracle, then each distinct message would have probability $2^{-k}$ of satisfying $H(m) < 2^{n-k}$.  The probability for each message is independent, and so the expected number of trials before you hit an event with probability $2^{-k}$ is $2^k$.


How long to reestablish PKI if Diffie Hellman and Factoring are in classical $P$?

Can we have a full-fledged PKI with just a strong signature scheme when factoring and all varieties of DH are broken?

Of course we can; we have a number of signature algorithms that do not rely on either factoring or DH (or Discrete Log, for that matter)

how long would such an effort take?

That's the hard question; while efforts are currently underway (because of the possibility of Quantum Computers, which would be able to solve all the problems you have listed), it's not expected to fully replace RSA or E*DSA[1] for perhaps 10-20 years (10 years would be when the large majority of PKI would be "postquantum"; 20 years would be the time it'd likely take to convince every obscure webserver to convert).
In your scenario, all this would need to be drastically sped up.  The time that'd take would have to be an estimate; there are the problems that'd need to be solved (and I'll focus in on the PKI piece; there are other pieces, such as key exchange, uses of signatures disconnected from the global PKI, and more advanced crypto, such as IBE and PAKE, that would also need to be addressed).

We'd need to select a signature algorithm; such an effort is currently underway, however we're hoping to have two or three more years to gather information to allow us to make an informed choice; in your scenario, we can't wait that long.  I'm guessing the community would pick one (likely either Falcon or Dilithium) in a month or two - those two are the most likely, because testing has shown that neither would slow down TLS significantly, and the best evidence we have now show them likely to be secure (and we're hoping to firm up that last statement in the next few years).

The various PKI vendors would need to issue new root public keys using this new method (and distribute them).  How long this would take is more a question about internal company politics more than practicalities; some CA vendors will jump on the ball immediately; others (based on my conversations I've had with them over the years) are more likely to ignore the problem until forced to by customer demand.

Various browsers (and software libraries, such as OpenSSL) would need to incorporate these new methods and root public keys (and somehow deal with older websites that haven't updated yet).  From my experience, all the major browser vendors are likely to be fairly quick about this.  On the other hand, other clients (which might not be presented as browsers to the user) might be considerably slower to update.

Various websites would need to have new certificates issued to them, and to use the new signature method.  That's a long pole - the major websites (Google, Amazon) and website hosting services (CloudFlare) are likely to be quick about this.  On the other hand, there is a large number of smaller, not that well maintained servers that will be quite reluctant to upgrade (even if they are still being actively maintained).

Going through this list, my guess is that a significant amount of the web traffic would likely to be protected by an upgraded PKI in perhaps 6 months (of fairly intensive work by the community); however there will be some traffic that won't be for years...
[1]: E*DSA is my personal terminology for the collection ECDSA, EdDSA, Schnorr signatures and similar schemes.


Can I replace SHA-1 with SHA-512/160 to address Shambles?

Generic collisions

The generic collision attack on SHA-512 trimmed to $n=160$-bit will require $2^{80}$ complexity by the birthday paradox with a 50% success probability. The generic attack doesn't require any knowledge about the internals of the target hash function. It is about collecting hash outputs and looking collision among them by building a table and hoping that you find a collision. The cost is $O(2^{n/2})$ time and $O(2^{n/2})$ space to store the table.

If you are using a variant of Pollard's $\rho$ you can achieve constant $O(1)$-space with $O(2^{n/2})$-time. The best known is the van Oorschot–Wiener Time-Momory Trade-off technique with cost $O(2^{n/2})$. This can be parallelized with a linear speedup. Use $O(2^{n/4})$ machine to parallelize and get an answer in $O(2^{n/4})$ time at the same cost of $O(2^{n/2})$.

If you consider the Quantum attacks on hash functions, you should use 384 or 512 output sizes due to Brassard et. al' work. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function (for 256-bit $\mathcal{O}(\sqrt[3]{2^{256}}) \approx \mathcal{O}(2^{85})$). See the timing table in this answer.

SHA-1 weakness and Shamble

The researches use weaknesses that lie in the internals of SHA-1 and The Shambles' researches reduced the collision to $2^{61.2}$, see the list of other work in here. The Shambles' team used 900 GPUs that cost around $75.000 with their new method and calculated the forgery at most in two months. This is why they called practical. Their new records;

They reduced the use of neutral bits BCJ+05 and boomerangs JP07 from $2^{64.7}$ to $2^{61.2}$
Also, they improved graph-based technique (LP19) to compute Chosen-Prefix Collision from $2^{67.1}$ to $2^{63.4}$.

The Machines

There are machines already exist way before the attack's 900 GPUs, like the Summit in Oak Ridge that can reach $2^{63}$ SHA-1 calculations in a day. As long as, one cannot find a weakness in SHA-512/160, it will have an 80-bit classical collision resistance.

80-bit is no longer secure

Today, 80-bit collision resistance for any hash function is not considered secure. The NIST removed SHA-1 signatures from the recommendation in 2011.

  NIST formally deprecated use of SHA-1 in 2011 [NISTSP800-131A-R2] and disallowed its use for digital signatures at the end of 2013.

R2 in 2019 on page 18 NIST allows it for nonsignature, although by that time it's clearly a bad idea (Thanks to Dave).

Actually, one can consider that it is not the SHA-1 is removed, the 160-bit hash output is removed from the recommendation. The 160-bit was related to 80-bit security that was enough during the early 2000s. And, note that the 50% probability of the birthday attack is not negligible in the view of the attackers. One must consider the lower probabilities.

Recommendation

It is wiser to update the software to new recommendations like the SHA3 series with good hash sizes like 256, 384, or 512 if you are working with the US government. If not, you can also use other good hash functions like Blake2. If you consider Quantum attacks, you should bigger than 256.

You can use it if you are satisfied but not advised.

Migrating the software shouldn't be a big problem. It is strongly recommended.


Why is this treeheight not supported in the RFC?

I'm not Andreas, and he did not mention this to me specifically.  He has mentioned that the CFRG did ask him to limit the number of parameter sets he defined.  My speculation is that he couldn't imagine any situation that would need more than $2^{60}$ signatures generated from a single private key.
Do you have such a situation?  Even if you were able to generate a signature in a nanosecond (which is far faster than what is achievable today), it would take over 36 years to use up all $2^{60}$ signatures - do you have a use case that would go beyond that?

he XMSS RFC supports only tree heights of 60, which makes the chosen keypair to sign up to 2^60 messages, which is not practical for the use of SSL and so on

Why would $2^{60}$ signatures not be sufficient for TLS?


Significance of Gram-Schmidt coefficients in LLL algorithm

Say you have an integer lattice $\mathcal{L}$ with (ordered) basis $B=\{{\bf b}_1,\ldots,{\bf b}_n \},$ ${\bf b}_j\in {\bf Z}^m$, $n\leq m$. As you wrote the first condition of the LLL reduced basis $\{ {\bf u}_1,\ldots,{\bf u}_n\}$ is the process of size reduction. That is $|\mu_{i,j}|\leq \frac{1}{2}$, $j<i$. If you set $M_i=\mathrm{span}({\bf b}_1,\ldots,{\bf b}_i),\ i<n$ then this condition shortens the projection $\mathrm{proj}_{M_i}({\bf b}_{i+1})$, while the second condition (Lovász)  shortens the projection $\mathrm{proj}_{M_i^\perp}({\bf b}_{i+1})= {\bf b}_{i+1}^*$.

References

Phong Q. Nguyen and Damien Stehlé. An LLL algorithm with quadratic complexity. Siam J. Comput., 2009. doi:10.1137/070705702 [PDF]


Yes, RDSEED is a true random number generator.

From Wikipedia:

  The entropy source for the RDSEED instruction runs asynchronously on a self-timed circuit and uses thermal noise within the silicon to output a random stream of bits at the rate of 3 GHz [...].

RDSEED is however used as a seed for (software implemented) PRNGs of arbitrary width.


Is there a way to provide proof of batch RSA security?

RSA public key encryption should always be used together with a randomized padding scheme, such as OAEP or PKCS#1 v1.5. Only if you don't use such padding and encrypt the same message with a sufficiently high number of different public keys, an adversary might simply apply the Chinese Remainder Theorem to the cipher texts, and then calculate the E:th root of that value (E being the public exponent used by the RSA public keys).


Is equal length of primes in Paillier cryptosystem is mandate for security reasons?

No, exactly equal length of primes $p$ and $q$ is not mandatory for security (or proper functioning) in the Pailler cryptosystem. Sufficient requirements are that $p$ and $q$ are prime, $N=p q$ is hard to factor, and $\gcd(p q,(p-1)(q-1))=1$.

The requirement that $p$ and $q$ are of exactly equal size is usually made in the Pailler cryptosystem because this requirement

implies that $p<2q<4p$, which implies $\gcd(p q,(p-1)(q-1))=1$, which is a must for the Pailler cryptosystem to work;
is customary in RSA, and thus is an easily met condition, and unobjectionable from a security standpoint;
is a consequence of stronger conditions mandated by FIPS 186-4 and the earlier ANSI X9.31 RSA key generation standards, which both require $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for integer $k$ at least 512 (and further constrained, including to be a multiple of 64), because it simplifies implementations of RSA, including using the CRT method; and similar implementation considerations apply to the Pailler cryptosystem.

More precisely, on security:

even though imposing that $p$ and $q$ are of exactly equal size does reduce the choices for $N$, and thus helps at least some factorization algorithms (notably Fermat's and derivatives), it would be a surprise if such algorithms could be extended to factor with odds $\epsilon$ and expected cost lower than $\epsilon\min(p,q)^u$ operations, where $u\approx2/5$ in our wildest dreams, and even $u\approx1/2$ is hard to reach; thus such algorithms are not to fear in the first place, for they do not have odds worth consideration to factor products of two randomly-generated primes of approximately equal size if that size makes factorization by GNFS hard enough; says $N$ at least 768-bit (the current academic record), thus $\min(p,q)$ at least 350-bit, making $\min(p,q)^{2/5}$ at least 140-bit.
on the contrary, that $p$ and $q$ are of exactly equal size slightly increases the expected time to factor $N$ by the sub-exponential ECM for a given size of $N$, and does not lower the expected cost of any other sub-exponential algorithm that we know; thus can be regarded as more beneficial than not from a security standpoint.


Sorting over encrypted data with different symmetric keys

In short: What you ask for is impossible.

You want to sort ciphertexts, which are encrypted with different keys, without being able to decrypt them and not knowing the key(s). Let's assume for a moment that this would be possible.

And then there is an attacker, who just gets a single ciphertext. Now, you have to assume that the encryption scheme is public, and everyone can encrypt anything with any key. And there is a certain message space, e.g. a 256 bit integer.

Now the attacker chooses the integer in the middle, encrypts it under any key. With this value and the challenge ciphertext he uses the sort algorithm. Even if the sorting would be randomized, he still could detect his own input - he chose the key for that ciphertext. And from the sorting he now knows if the plaintext in the ciphertext is lower or higher than his own chosen message. If the ciphertext was lower, he will do the same again, with a value in the middle of the lower interval. Basically, this is just a binary search for the plaintext. Therefore, the encryption scheme is insecure even against a ciphertext-only attack.