Why do people worry about the exceptional procedure attack if it is not relevant to ECDSA?

Regarding your first question:

It is relevant for the Elliptic Curve Diffie-Hellman (ECDH) key exchange. In this scenario the user performs a scalar multiplication with the other user's public key, which is a variable point chosen by a possible attacker.

Note that another reason for the attack to not apply on ECDSA is because the scalar in ECDSA is a randomly selected integer different for each signature, which makes the attack ineffective as the attacker needs to test several base points with the same target scalar.

Regarding your second question:

It is not that simple. There might be condition where exceptions occurs even on prime order curves. For example if you don't restrict your scalar to be smaller than the curve's order or if you do a computation different from the classic double and add or if you don't use the standard formulas to achieve regularity (as the formula of Brier and Joye) or speed (as for example some Co-Z formula).

One of the point djb is making is that using the montgomery ladder on montgomery curves is extremely efficient and exception-free that you don't want to consider other solutions. And that works very well for ECDH.
While for signatures you might rely on Twisted Edwards where similar properties apply.

Overall the message is not that we can't do exception free constant time implementation on the good old prime order curves. It's just that it is not as simple and in particular not as efficient then do it on Montgomery or Twisted Edwards curves.


Historically, both the difficulty and the risks involved in securely establishing shared keys in large networks has led to the invention of public-key cryptography. So you might first want to consider using digital signatures/asymmetric encryption instead of sharing the same secret between parties.

If you need all (or some) of the parties to collectively sign or encrypt a message, consider using threshold signature schemes with a Distributed Key Generation protocol. That will produce a key pair that is distributed among $N$ participants such that at least $k$ of them need to collaborate for performing a key operation. For discrete-log cryptosystems there's a paper by Gennaro et al that describes such a setup.

Edit: If you only need to establish a common secret (instead of a key pair) between all the parties, a simpler solution would be to use a generalized Diffie-Hellman key exchange instead. This works for honest participants with insecure communication channels. If the participants can be malicious, a more robust solution is described by Tseng, 2005.


However, at the decryption side, after decrypting the final block, how does Bob know whether the final block was XORed with K1 or K2?

CMAC is not an encryption scheme but a MAC - and more precisely a PRF - by design. As such the input you get during authentication is a subset of the input you get during verification. In particular during authentication you get the message and the key $(k,m)$ and during verification you additionally get a transmitted authentication tag $(k,m,\tau)$.
Verification then works by computing the MAC on $(k,m)$ yourself and checking the result against $\tau$. As you now have the message to be authenticated yourself you can use the same decision strategy as the original signer to decide which key to use for the final block.


how many blocks are encrypted at a time in DES Algorithm?

Guess what: in counter mode DES doesn't encrypt blocks of plaintext at all. In counter (CTR) mode DES encrypts a counter which is XOR-ed with the plaintext.

DES itself doesn't do anything with multiple blocks. DES is an algorithm called a block cipher which handles one block of input and permutes it to a block of output. The chosen permutation depends on the key.

To encrypt anything that is not precisely a block with DES (or any other block cipher) you need a block cipher mode of operation . There are many modes of operation in which a block cipher can be configured as underlying primitive.

How many bytes are actually encrypted by the mode of operation depends on the mode and implementation. One instance of DES - the block cipher - will only handle one 64 bit / 8 byte block at a time.


MuSig/Schnorr key aggregation: How get the combined private key

Yes, it's possible if you eventually know all the parties' secret keys! However, note, that in most realistic application scenarios, where there is at least one honest party whose secret key is not known, it is computationally infeasible to recover the aggregated secret key, under the  Discrete–Logarithm assumption,  given the secret keys of the corrupted parties. In the following let me use the notations introduced in the MuSig paper by Maxwell et al.

Let $L$ be a multiset (the same public key can appear multiple times in $L$) of signers' public keys: $$L=\{X_1=g^{x_1},\dots,X_n=g^{x_n} \}. $$ The message to be signed is denoted as $m$, $H$ denotes a hash function and $R=\prod_{i=1}^n R_i=\prod_{i=1}^n g^{r_i},$ where $r_i$ is a share generated by $i$th participant. Challenges are computed as: $c_i=H_{agg}(L,X_i)\cdot H_{sig}(\tilde{X},R,m),$ where we define $a_i= H_{agg}(L,X_i)$ and the aggregated public key is defined as $\tilde{X}=\prod_{i=1}^n X_i^{a_i}.$

Since $\tilde{X}=\prod_{i=1}^n X_i^{a_i}=g^{\sum_{i=1}^n a_i x_i}$ Therefore it is easy to see that the aggregated secret key is $\sum_{i=1}^n a_i x_i.$ The verification equation for an $(R,s)$ aggregated signature on message $m$ is: $$g^s=R\tilde{X}^c, $$ where $c=H_{sig}(\tilde{X},R,m)$.
Although note that the aggregated secret key has no role in verifying aggregated signatures and does not play any role in the MuSig scheme.


Efficiently map $2^n$ unique 64-bit vectors to $2^n$ $n$-bit vectors where $n < 64$?

In general, no. There are:
$$ {2^{64} \choose 2^n} = \frac{2^{64}!}{2^{n}!(2^{64}-2^n)!} $$
possible ways of selecting $2^n$ distinct 64-bit vectors. This is a huge number; using Stirling's approximation of factorials, when $2^{n}$ is substantially smaller than $2^{64}$ (i.e. when $n$ is smaller than $55$ or so), this number of combinations is approximately equal to:
$$ \sqrt{\frac{1}{2\pi}} 2^{-n/2} 2^{(64-n)2^n} $$
Therefore, any generic method for doing the mapping you seek must, necessarily, use enough memory on average to accommodate that many possible combinations. For instance, if $n = 32$, then you will need a minimum of 137 gigabytes. In fact, the naive method of storing all $2^{32}$ 64-bit vectors in a sorted array, using a binary search to locate the index of a given value, will use twice as much, but if the values are sorted and more or less uniformly spread over the space of 64-bit vectors, then the difference between two successive vectors will fit in less bits (a bit more than 32) so you could, realistically, do your mapping with 160 gigabytes or so.

Of course, the argument above is for generic methods. If you know how the $2^n$ 64-bit vectors are generated, then a more efficient method may be possible. As an extreme case, if the 64-bit vectors all end with 32 bits of value 0, then simple truncation will work for your mapping.


How to only encrypt a subset of the plaintext

You can get what you want programmatically. No special ciphers or modes needed.

You say there is a single, continuous subset that needs to be encrypted. Thus, you could have a function where the programmer specifies the start of the portion of the plaintext that needs to be encrypted and the number of bytes to encrypt. The function could pull that part out, encrypt it (using a good block cipher and mode) into a buffer. Then write out the part preceding it, the ciphtertext, then the part following the portion that needs to be encrypted.

If you require integrity checks too, a simple HMAC of the plain-part-one + ciphertext + plain-part-two using a different key would do.


How to prove hardness of approximate-GCD problem?

I am stuck at the point where I proved that the complexity is $O(2^\rho)$ using brute-force approach. How shall I proceed?

Well, a proof that assumed a specific attack strategy is of limited use, as that proof would be inapplicable if the attacker used some other strategy.

Instead, what we typically do in a proof is assume that the adversary had some Oracle that could break your system, and then show that, using that Oracle, he could break the hard problem (in this case, approximate-GCD).  This has the advantage that it doesn't matter how the adversary breaks your system; if he can break it by any means, then he can solve the hard problem; hence, if he is unable to solve the hard problem (which is our assumption), then he can't break your system.


Why do we need Collision Resistant Hash Function for the Merkle Tree Signature Scheme?

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask.

Actually, that's not why XMSS has the bit masks; as you point out, second preimage resistance is essentially all you need for hash based signatures to be secure; the attacker needs to find a preimage or a second preimage (depending on where in the hash scheme we're talking about) for one of a number of hashes.

Rather, it has to do with proof technique.  As mephisto points out, if you're happy with the random oracle model (and its proof method), it's straightforward to design a simple HBS method that is secure (that is, you have to find a preimage or second preimage to break).

However, what XMSS tries to do is be secure in the concrete model; that is, they try to argue that, because the bitmasks randomize the input, that what you need to do is find a (second) preimage of an effectively random string.


In an ordinary ID-based scheme, you won't get strong PFS.  The center always knows a secret that can be used to recover your private key and thus can violate PFS.

One approach is a hybrid scheme, such as the following.  You could do a (non-ID-based) Diffie-Hellman or ECDH key exchange, with messages signed and authenticated using an ID-based signature scheme.  You'd use the Diffie-Hellman/ECDH key exchange to derive an ephemeral session key for encrypting the rest of the channel.  That would get you PFS (against passive eavesdroppers), along with the advantages of ID-based cryptography.

Apparently, the following paper describes an even better scheme.

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead.   Rosario Gennaro and Hugo Krawczyk and Tal Rabin.  IACR ePrint 2010/068.

Their paper apparently provides PFS against passive attackers and PFS against active attackers (even if the center is corrupted, apparently).  Thanks to Alex for pointing this out.

The "advantage" of ID-based schemes is that you can use, e.g., someone's email address as their public key.  The disadvantage is that you must trust the center an awful lot, because the center knows or could compute everyone's private keys.  This is standard and you can find a lot written about ID-based key exchange that explains these tradeoffs in detail.


I'll turn my comment into an answer:

  Given a lattice L, with a good base B1 and a bad base B2, what stops an attacker from simply re-creating the lattice structure from the public base B2?

There's nothing stopping them, the lattice structure isn't secret. Like you say, examining the lattice structure is trivial. The use of lattices in cryptography derives from the fact that even if you know the lattice's structure (i.e. have some basis B), deriving a "good" basis is hard.

  Still, deriving the lattice structure wouldn't mean that one could, for example in a CVP problem, easily output the closest vector?

No. :) When you visualize this problem in low dimensions, like 2, it seems like it should be that way, no? But in high dimensions, this problem is very difficult when you have a random (i.e. bad) basis.

Try out your technique. Suppose we have $n$ dimensions. Our basis $B$ is a bunch of vectors going in random directions. We want to enumerate the points close to $\mathbf{t}$. How many points could potentially be "close" to the target? How do you generate these points efficiently with your basis $B$?


Prepending random data to encrypted file

It's much easier to add a cost factor to the key derivation from the password than to add a lot of data to an encrypted container. See the PBKDF's PBKDF2, bcrypt and scrypt for more information, or see this Q/A for GPG. In general, an iteration to derive the key is of course much more efficient than adding overhead at the start of the file.

If a key with an entropy over 100 bits and if there are no vulnerabilities in the encryption routine (this is likely true for GPG / CAST5) then brute forcing the key is already not possible, and the measly amount of time required to  decrypt a small amount of data is not much of an additional deterrent.

Note that CBC mode encryption can be decrypted from any location in the ciphertext, as long as the previous ciphertext block is available. As for the trick with the truecrypt volumes (wasn't that software deprecated?), how would you know as a legit user where to start reading/writing?


How to compute the dot product on encrypted values?

Yes, there is a solution.  Ricky Demer pointed to it.  (Thank you, Ricky!)

In particular, the following paper provides an elegant and efficient solution to your problem:

Evaluating 2-DNF Formulas on Ciphertexts, Dan Boneh, Eu-Jin Goh, Kobbi Nissim, TCC 2005.

They show how to build a public-key encryption algorithm $E(\cdot)$ with the following two useful properties:

Additively homomorphic. Given $E(x)$ and $E(y)$, anyone can compute $E(x+y)$.
Can multiply (once). Given $E(x)$ and $E(y)$ (neither of which was generated as a result of a multiplication operation), anyone can compute $E(x \cdot y)$.  You can use the result in addition operations, but you cannot use it in any multiplication operations (the result of a multiplication is tainted, and tainted values cannot be used as the input to another multiplication).

This is enough to let you compute the inner product.

Here how this is helpful.  Suppose you are given encryptions of $a_1,\dots,a_n,b_1,\dots,b_n$, where each ciphertext was encrypted using the scheme mentioned above.  So, you have $E(a_1),\dots,E(a_n),E(b_1),\dots,E(b_n)$.  By using the "multiply (once)" scheme, you can compute $E(a_1 b_1), \dots, E(a_n b_n)$, i.e., an encryption of $a_i * b_i$ for each $i$.  Now you can use the "additively homomorphic" property to compute the sum of these, i.e., to compute $E(a_1 b_1 + \dots + a_n b_n)$.  This is an encryption of the inner product, as you requested.

In short: given encryptions of the $a_i,b_i$ values, you can compute an encryption of the inner product, using the above scheme.  This solves your problem.  The encryption algorithm is pretty efficient (vastly more efficient than fully homomorphic cryptography).  Incidentally, you don't need fully homomorphic encryption to solve your problem, which means that you should be able to obtain a much more efficient solution (using the above scheme) than if you tried to use fully homomorphic crypto.


Key exchange and authentication using libhydrogen

All the key exchange schemes provided by libhydrogen (actually the Noise protocol) are secure against MITM.

With the N variant, the client has to know the server's public key, and will not return a valid shared key pair unless the response comes from a server that has the corresponding secret key.

If you need the server to authenticate the client as well, use the KK variant instead.

Signatures are not needed, unless you want keys to be signed by a certificate authority.


Binary verification of application image before loading it into DRAM

The obvious flaw of approach 2. is that you need the same key to sign and verify.
This means that whoever reverse-engineers one device and gets out the verification key can now sign their own application images which will be accepted as genuine by other devices.

The standard way of application signing is by using asymmetric algorithms (RSA-2048 is a minimum, or ECDSA-256). That way the device has only a public key (hopefully stored in a read-only memory so that it's not replaceable) and no one is able to sign application images even if devices get reverse engineered.


One way communication with forward secrecy?

Is there a known protocol that can do this?

It's easy to see that forward security is impossible with the constraints you have.

Suppose an attacker breaks into B to create a B' with the exact same state.

Then, from now on, when A sends a message to B, the attacker takes that message and also submits it to B'.

B and B' are essentially identical; if B can understand the message, so can B'.

This remains true even if B can generate some local entropy (e.g. has an entropy source whose output the attacker cannot predict); as B cannot send its entropy back to A, it has to understand the message from A no matter what the entropy is (and hence B' can as well, even if its entropy sample is different).


It is not a secure hash function. For example, one can easily break the
collision resistance property: let $q$ be the order of $g$, then $m$ and $m+q$ have the same hash value, $H(m+q)=g^{m+q}=g^m=H(m)$.


How to crack Vigenere ciphertext if multiple keys of coprime length are used?

Turns out the way you break it is by using the Kullback Test.


You're saying we're looking at messages of length one block and a variant of CBC-MAC that uses a random IV. (I'm assuming we're looking at CBC-MAC for fixed length messages, i.e. we can ignore padding issues.) Then we have
$$am:=(ai,E(k,a\oplus ai))$$
To forge a MAC for message $b$ we can reuse the second part of the tag if we choose $bi$ such that $$b \oplus bi = a \oplus ai$$$$ \implies bi = a\oplus ai \oplus b$$

I.e., given $a$ and $am=(ai,t)$ simply output $bm=(a\oplus ai \oplus b,t)$.


Any historical accounts of cryptanalysis of Jefferson's wheel cipher?

Wikipedia gives an answer although it provides no reference.

The Bazeries cylinder was a relatively strong system at the time (compared to many other systems in use), and Etienne Bazeries, a competent but very opinionated man, is said to have regarded it as indecipherable. In fact, it is hardly impregnable, and the "Pers z" code-breaking group of the German Foreign Office cracked the M-138-A in 1944. However, by that time the Americans had much more sophisticated cipher systems in operation. Many of the decrypts of Allied communications presented to the German high command were disregarded, because all they did was confirm bad news that nobody wanted to acknowledge in an environment where defeatism was potentially a capital crime.
de Viaris (aka Marquis Gaetan Henri Leon Viarizio di Lesegno) who is famous for one of the first printing cipher devices (1874), solved the Bazeries cylinder in 1893, so Bazeries alleged confidence in the system was ill-placed.
One major weakness of the Bazeries cylinder is that the offset from the plaintext letter to the ciphertext letter for the cipher alphabet on each disk will be exactly the same.

It intuitively seems easy to brute-force with a partially known plaintext. The chance that two disks will have the same distance from $C_i$ to $P_i$ is negligible. You then brute-force the possible outcomes and compare them against a dictionary. You've arrived at a small subset of possible plaintexts so you select the one that makes more sense. A second message coded with the same key will verify the results.


What are Alternatives to basic ROT-n Ciphers which Don't Lose 'Context'?

Any letter (simple) substitution cipher will do (it might be necessary that it special-cases any character that your text-generating software special-cases, like space, tab, linefeed, perhaps punctuation).

ROT-n is a particular case of substitution cipher, with a much smaller key set (if we restrict to uppercase letters, ROT-n has $26<2^5$ keys, versus $26!>2^{88}$ keys for a general substitution cipher; that less than 5 bits versus more than 88).

Depending on what the text-generating software does, it might also work to substitute words, in addition to letters. That further increases the key space.

Substitution ciphers are hopelessly insecure, thus it is unclear what this achieves, or what is attempted.


Is Wikipedia's table about SHA-2 collisions correct?

No. The wikipedia article is in my honest opinion misrepresenting this article on a reduced round attack on the SHA-2 family of hashes.

  Although these attacks improve upon the existing reduced round SHA-2 attacks, they do not threaten the security of the full SHA-2 family.

In other words, no collisions have been found in any of the SHA-2 hashes.

The numbers that the are shown in the table mean different things for SHA-1 and SHA-2. In the case of SHA-1, the theoretical attack finds a collision in the actual SHA-1 algorithm. In the case of SHA-2, the collision is found in a modified algorithm with only 24 of the normal 64/80 rounds. In practice, this means that the best collision attack against SHA-256 still has the theoretical upper bound of $2^{128}$ complexity, and the best collision attack against SHA-512 a $2^{256}$ complexity.


how calculate plaintext file size from length of encrypted one without decrypting

As far as I understand ,all original files with length between let’s say 33 and 47 will have length 48 bytes after aes-128-cbc encryption (should be rounded to next 16 byte block).

Actually, if you are using the standard padding pattern (and you don't count the space the IV takes up - you do use a different IV for each ciphertext, don't you), then the range of original plaintext strings will be 32-47; those will all encrypt to 48 bytes, and no one without the key can determine the original length.
However, if you do have the key, you can determine the length without decrypting the entire message; you only need to decrypt the last block - that is sufficient to determine the original length.
That last block is $P_n = C_{n-1} \oplus D_{key}( C_n )$.
For a 3 block message, the savings aren't huge; however if you are trying to determine the exact length of a multi-megabyte plaintext, the savings are more significant...


How about:

Alice and Bob both have to answer a series of yes-or-no questions by the doctor. Alice and Bob have to answer these questions separately.

Before they answer any question they agree that "1" is "yes" and "0" is "no", but the doctor doesn't know which is which. The doctor also has shuffled the questions so that Alice and Bob can't make some sort of predefined pattern for their answers.

One of the questions could i.e. be: "Does Bob have diabetes?".

Alice and Bob both know the correct answer to this (let's say that Bob doesn't have diabetes) and they both answer to this question with "0".

The doctor is not allowed to ask them questions that he knows the answer to, i.e. "Does Alice have blue eyes?"

The doctor now has both of their answers and compares them. If they both have the same answer to each question (assuming they answered truthfully and didn't make any mistakes) the doctor can be sure that they told each other their results.

The zero-knowledge part of this is, that the doctor still doesn't know anything about their medical results.


CCA-2 key recovery attack to an homomorphic scheme?

An interesting approach would be to determine if your CCA attack can be done in the first or in the second phase of the game. That is, before or after the challenge ciphertext is generated. This corresponds to a CCA1 or CCA2 attack, respectively.

CCA2 as usually understood cannot be attained by HE schemes, but CCA1 can. Therefore, your attack may be trivial if it is actually a CCA2 attack, or not if it is a CCA1 attack.
Anyway, in the end, it all depends on the claimed security notion of the HE scheme. If they never said it is CCA1/2, then there may be little value to your attack...It's like finding a CPA attack on textbook RSA or a CCA2 attack on textbook ElGamal.


ElGamal signature: Forging a signature of a specific form

I assume that the deadline for the homework is passed, so I will provide an answer:

Let us assume that we have the public key $y=g^x \pmod p$ and the private key to be $x$.

Computing an ElGamal signature for a message $m \in Z_p^*$ amounts to:

choosing $k\in Z_p^*$
$r\equiv g^k \pmod p$
$s\equiv (m-xk)k^{-1} \pmod{p-1}$ which is equivalent to  $m\equiv xr+sk \pmod{p-1}$

The signature for $m$ is the pair $(r,s)$ and verifying the signature amounts to checking whether $g^m \equiv y^r r^s$ holds and it is easy to check that this holds, since we have $y^r r^s \equiv g^{xr+sk} \equiv g^m \pmod p$.

We have to show that given a signature $(r,s)$ allows to forge signatures of the type $m'\equiv (m+bs)a \pmod{p−1}$ for $a=g^b$ with $b\in Z_p^*$ chosen by the adversary.

You got a hint $g^{m'} \equiv g^{am+abs}$, but it is better to see if you go one step further:

$g^{m'} \equiv g^{am+abs} \equiv g^{a(xr+sk)+abs}\equiv g^{axr+ask+abs} \pmod p.$

Now, on the right hand side of the verification equation $y$ is fixed. So we have to figure out how $r'$ and $s'$ need to look like such that the verification equation can hold:

$g^{axr+ask+abs} \equiv y^{r'}r'^{s'}$

Observe that for the first term we have to set $r'\equiv ra \pmod p$ which is equal to $g^{k+b}$. Consequently, we are still missing $a$ and thus set $s'\equiv as \pmod{p-1}$.

If we now look at the left hand side of the verification equation, we obtain:

$y^{r'}r'^{s'} \equiv y^{ra}r'^{as} \equiv g^{xra}(g^{k+b})^{as}\equiv g^{xra+ask+asb}\equiv g^{m'}$

which shows, that the verification relation holds for these types of forgeries.


I used the following python code to compute the private exponent and perform decryption. It uses the extended euclidean algorithm:

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def main():

    p = 1090660992520643446103273789680343
    q = 1162435056374824133712043309728653
    e = 65537
    ct = 299604539773691895576847697095098784338054746292313044353582078965

    # compute n
    n = p * q

    # Compute phi(n)
    phi = (p - 1) * (q - 1)

    # Compute modular inverse of e
    gcd, a, b = egcd(e, phi)
    d = a

    print( "n:  " + str(d) );

    # Decrypt ciphertext
    pt = pow(ct, d, n)
    print( "pt: " + str(pt) )

if __name__ == "__main__":
    main()

The private exponent is:

$522550976146069021499058157764354003336248628589338241039193114657$

The plaintext is:

$83678269879577658472958479799572658268$

which works out to a 128-bit value, so I'm assuming it's correct.


Is it fair to say that MACs use a signing algorithm?

You misunderstood something. HMAC-SHA-1 does not use SHA-1 as the signing algorithm. The signing algorithm is the HMAC-SHA-1 calculation, not an intermediate SHA-1 calculation. The signing algorithm takes the key and the message as inputs and produces the MAC value as output.
The usual terminology for the hash algorithm that an HMAC construction uses is “underlying hash algorithm”. Note that having an underlying hash algorithm is not a universal property of MAC. For example CMAC has an underlying block cipher, but no underlying hash algorithm.
Asking whether it's “fair” to use a word is meaningless. There is no ethical consideration. The right question is whether it's potentially confusing — but terminology choices are to some extent arbitrary.
The single pair of words “encryption, decryption” is used both for symmetric and asymmetric encryption. Does it create confusion? Maybe, but not much, in my experience. Confusion stems from not understanding the concepts, not from the use of the same words for two related but different concepts.
There's no intrinsic reason why authenticity would require different words for symmetric and asymmetric cryptosystems, but confidentiality would be fine with the same words. It's just a historical accident. And ”verification“ is already used for both symmetric and asymmetric cryptosystems.
The only reason not to use “signature” for a MAC is that it's uncommon. In cryptography, “signature” almost always means an asymmetric signature cryptosystem, the signature operation of that cryptosystem, or the output of that signature operation (or the input of the verification operation). However, if the context of a symmetric system is established, there's no risk of confusion. In the context of a MAC, using the word “signature” to mean the calculation of the MAC value is unambiguous, and there isn't a really good alternative other than “MAC” itself (which also refers to the cryptosystem in general and to the value, so it is quite ambiguous).
So while “signature” for a MAC calculation is not well-established terminology, it should be. That would reduce confusion.


Certificate validation on an IoT device using few bytes

Generally you'd let the device establish a symmetric / secret key first, e.g. using ECDH and then use that secret key with a MAC algorithm to perform the message authentication. In that case 16 bytes / 128 bits is plenty.

For direct signatures, the BLS signature scheme is probably still the best out there, but for 128 bit level encryption - the lowest we commonly aim for - you'd still need a 384 bit signature.


If I compute the SHA-1 of all possible 40 digits hexadecimal strings, will I get all possible sha1 hashes?

No. And it's probably a good thing that that's not the case.

All cryptographic hashes (inc. SHA-1) are designed to have no obvious correlation between their input and output. If there is too much of a correlation, then they are considered broken.

If each string of 160 bits produced a different output, that would be a correlation.

That would also mean that all cryptographically secure pseudorandom number generators would have a small bias.

[It's very possible that there are some outputs that cannot be produced by SHA-1].


A psuedorandom permutation is a permutation in the "arrangements" sense if you examine all possible n-length blocks. It is not a shuffling of the block that you input to the function. The function takes the whole block and replaces it with another, completely different block.

To see this, picture encrypting a counter using a blockcipher with a given key. It would spit out one random block after another. Encrypt the same counter sequence using a different key, and it will spit out different random blocks. If you were to encrypt all possible values of the counter under the two different keys and examine the two resulting sets of ciphertexts, you would see two different arrangements of all n-length blocks. This is the "permutation" part of psuedorandom permutation.

The prototypical permutation producing algorithm is the Fisher-Yates shuffle. You could view a psuedorandom permutation like applying a Fisher-Yates shuffle to the sequence of counter blocks, where each entry is one possible n-length block.

As for the difference between a prp and a prf, I'm pretty sure we have an answer to that on the site already.


These prime numbers are called Solinas primes (because they were described by Jerome Solinas). The article details how they are found and how optimization works for them.

As a brief summary, consider a prime:
$$p = \sum_{i=0}^{k} b_i 2^{iw} $$
where each $b_i$ is either $0$, $1$ or $-1$, and $w$ is your "word size" (typically $w = 32$ or $64$ will yield the best results on usual computers). You also want $b_0 \neq 0$ ($p$ must be prime, so in particular it must be odd) and $b_k = 1$: the prime value is close to $2^{wk}$. To make things even easier to implement, make sure that $p$ is slightly below $2^{wk}$ rather than slightly higher, meaning that the highest non-zero $b_i$ (for $i < k$) has value $-1$.

With such a prime, modular reduction is easy because, modulo $p$, you have:
$$ 2^{wk} = \sum_{i=0}^{k-1} -b_i 2^{iw} \pmod p $$
from which you can infer:
$$ -x 2^{w(k+j)} = \sum_{i=0}^{k-1} b_i x 2^{w(i+j)} \pmod p $$
for all integers $x$ and $j$. Therefore, if you have a $n$-word value $X$ (with $n > k$):
$$ X = \sum_{i=0}^{n-1} x_i 2^{wi} \mathrm{\ \ \ \ \ \ where\ } 0 \leq x_i < 2^w $$
then you can compute the value $X'$:
$$ X' = X - x_{n-1} 2^{w(n-1)} + \sum_{i=0}^{k-1} b_i x_{n-1} 2^{w(n-1-k+i)} $$
This addition is easily computed because all the $b_i$ are $0$, $1$ or $-1$, so this amounts to adding or subtracting word $x_{n-1}$ to some other, lower words. With the relation above, you have $X' = X \pmod p$. But $X'$ now consists of $n-1$ words. So, with a few addition and subtractions, you have removed one word from your problem. Iterate.

Whether Solinas primes really give that much an advantage over a random prime (with Montgomery multiplication) is disputed. It depends on the implementation architecture. It has also been argued that choosing $p = 2^m - z$ for a small $z$ yields more efficient computations. As for all performance things, there is no absolute answer; it must be tried and measured, and any new language, compiler, processor version or architecture can change the answers.


Is there a symmetric-key cryptography based on key establishment techniques?

Yes, these are key derivation functions basically deriving a shared secret from information identifying the two parties (like their respective MAC addresses) and nonces and other session communication relevant information. See e.g. the PBKDF2 derivation function.


Security assessment between $g^{a_ix_i+r_i}$ and $g^{x_i+r_i}$

It is not entirely clear what your exact security requirements are and for which purpose you require this construction. I assume that the tags can not be manipulated by an adversary, e.g., are signed, and that users do not try to change their choice of $x_i$ after having a tag. Anyways, I give it a shot (although I may be wrong due to some information I do not have):

First Construction

Clearly, for the first construction you can simply try guessing $x_i$ and test against $g^{x_i}$ (which will be problematic if your $x_i$ come from a small set).

Second Construction

For your second construction, if $g^{\sum r_i}$ is revealed, then you can again test: Lets say for simplicity you have only one tag, then given the aggregate of the $r_i$ values (which happens to be $g^{r_1}$), you can just guess $x_1$ and test as in the first construction. Clearly, if there is more than one tag you can also test by cancelling out $g^{\sum r_i}$ from the aggregate of all tags, but the sum $x_1+\ldots+x_n$ in the remaining value $g^{\sum x_i}$ may not be unique anymore (so it depends if the $x_i$ can only take some specific values - then your sum could be unique but it must not be the case).

Thrid Construction

For the third approach with tags of the form $g^{a_ix_i +r_i}$: If the value $a_i$ is uniformly at random chosen by every user, then even when publishing $g^{\sum r_i}$ this will not give an advantage for testing, as even when cancelling out $g^{\sum r_i}$ in the full aggregate of all tags you still have $g^{\sum a_i x_i}$. Without knowing any of the $a_i$ values, you cannot test anymore (this is even unconditional hiding - for uniformly random $a_i$, the value $g^{a_i}$ is a random element and so is $(g^{a_i})^{x_i}$). So your last construction is secure even if the values $x_i$ are known to come from a small set (clearly, assuming that the values $g^{a_i}$ are not available to the adversary).


How does Python's pycrypto library generate primes?

The documentation is not directly telling the implemented algorithm. One can check from the source code. getPrime uses isPrime and that calls the Rabin-Miller Primality test.

getPrime generates a random odd number $\texttt{N}$ and calls isPrime

number=getRandomNBitInteger(N, randfunc) | 1
     while (not isPrime(number, randfunc=randfunc)):
         number=number+2

isPrime first checks for evenness and for pre-calculated Sieve primes, that list is the first 10000 primes. It may be a prime in the Sieve or divisible by one of them. If none of the cases, then the Rabin-Miller test is performed.

The Probability: The returned value of getPrime, if a probable prime, then the probability is given by
$$ 1 - \frac{1}{4^k}$$ where $k$ is the number of iterations.

The Number of iterations: The Library defines

false_positive_prob=1e-6

calculates the $k$ by

k = int(math.ceil(-math.log(false_positive_prob)/math.log(4)))

and from this, the number of iteration in the library is $k=10$.

Note that In my undergraduate, we used $k=20$. That makes false positive in the worst case 1e-12 where the library has 1e-6.

The Complexity: If modular exponentiation by repeated squaring is used then the complexity is $\mathcal{O}(k \log^3 n)$ where $k$ is the number of iterations to test that determines the probability.


Simple proof that shows AES is not a uniform permutation on any n-bit string?

There is no uniform permutation; there is a permutation uniformly chosen from the set of all possible permutations over $Z_2^{128}$.

It is evident that AES is not a uniformly chosen permutation, since its permutation is fixed for any key.

One can consider a family $\{AES_K\}$  of AES permutations under all possible keys $K$. Even if the key is chosen uniformly, the resulting permutation is not uniformly chosen, as not every permutation is an AES permutation with some key. This comes from a simple counting argument: there are $2^{128}$ 128-bit keys and thus $2^{128}$ AES-128 permutations, but the total number of bijections over $Z_2^{128}$ is
$$
(2^{128})! \approx \frac{2^{128\cdot  2^{128}}}{e^{2^{128}}} \approx 2^{2^{133.5}}.
$$


Struggling to understand Perfect Forward Secrecy

But I read a question here that PFS can be achieved by deriving session keys with a hash of an old session key. But if I were to know the master key (the pre-shared key?), I could easily calculate all session keys or am I misunderstanding something?

So the idea of PFS is that if the entire (secret) state of an entity at a time point $x$ is leaked and there exists at least one previous session, then there is a time point $x'<x$ where before that you lack knowledge to recover information from ciphertexts.

If we use this more formal definition and the participants do indeed erase old keys upon a key-update, then the scheme from the other question provides forward secrecy. If the initial key is now leaked, the first condition is violated as there is no previous session and the definition doesn't claim post-compromise security (where if you leak state at one point it will recover from passive adversaries). Now if you leak the state at a later point then obviously you cannot recover the key from a previous session because the hash is one-way.


Are there full cycle cryptographic/one-way hash primitives?

I'm sorry, but I don't believe that there are any known 'one way permutations' for small inputs (that stay one way if you know the 'key').

When we create a cryptographic permutation (or bijection; that's what we call a 'full cycle' function), we have two basic ways to do it:

We can take a series of easy to invert permutations ("round functions"), and glue them together to form a function that we hope is hard to invert.

This is the general design principle behind most block ciphers; we believe that if the key is secret, this can work very well.  However, if you give someone the key, it becomes easy to invert (by just inverting each individual round function).

We can take advantage of some mathematical relation which is one-to-one (that is, it avoids collisions), but it doesn't do it for any naively obvious reasons.

We often find these sorts of things within public key cryptography; one such is $f(x) = g^x \bmod p$ (for appropriate $g, p$); this function can map the inputs $(1, p-1)$ into the range $(1, p-1)$ such that every output is possible.

One problem with this is that these types of functions are large; in the specific case I mentioned, we need $p$ to be perhaps 2048 bits to be really secure, and that's hard to describe as a small range.


Is the seed block in Argon2 (H0) 64-bit or 64-byte?

In core.h of the Argon2 reference implementation, we can see that ARGON2_PREHASH_DIGEST_LENGTH = 64.  In core.c, we can see that ARGON2_PREHASH_DIGEST_LENGTH and ARGON2_PREHASH_SEED_LENGTH are used as numbers of bytes (to allocate a buffer in bytes and to specify the size in bytes of a BLAKE2b hash).

We can also reason that it makes no sense for the password, salt, optional secret key, and associated data to figure into the hash only via a 64-bit intermediate quantity—that would open it to preimage attacks on the intermediate quantity.

Please send email to the authors of the internet-draft identifying the incorrect ‘64-bit’ units!

Update: The November 22, 2018 revision of the Argon2 internet-draft, draft-irtf-cfrg-argon2-04, corrects the typo:

  Establish H_0 as the 64-byte value as shown below.

  —draft-irtf-cfrg-argon2-04, §3.2 ‘Argon2 Operation’


XOR Encryption with bcrypt password de-biasing

Any time you perform more than one evaluation of a password-hashing algorithm where it is a legitimate option to perform it only once you are doing something wrong. Here is why:

If one hash evaluation costs $C$, then 10 hashes with with the same cost-parameter will costs $10 \times C$.
Hashes can be evaluated by a cracker with a cost per candidate-password proportional to $C$. (Probably a lot less than C since they can build or buy systems optimized for and dedicated to password cracking.)
Given $x = H(\text{salt}, \text{password})$, one can guess a candidate password $p$ and compare $x$ to $y = H(\text{salt}, p)$.

If $x \neq y$ then $\text{password}$ is not $p$.
If $\text{password}$ is not $p$ then $x = y$ with only $1 / N$ probability where $N$ is the size of a hash's image set. *

Given knowledge of some $n$-bit long subset of one hash output's bits, a cracker can similarly evaluate the hash of one candidate password with a cost $\le C$ with a $2^{-n}$ false positive rate.

If the adversary knows one character of plaintext (8 bits), then out every 256 candidate passwords, 255 candidates can be eliminated with work proportional to $C$. Only 1 out of every 256 will need two or more hash function evaluations to check for false positives.
Because each 32 byte block can be tested independently, the password cracker will rarely have to do proportional to $10 \times C$ work but the legitimate password-holder will always do $10 \times C$ work,
The cracker has a significant advantage over the honest party compared to an alternate method: Use a single password hash evaluation (a password based key derivation function) to calculate  one key and use that key with a typical symmetric key message encryption algorithm.

One can put key derivation functions (which you can think of as hash functions used to deterministically generate keys) into two categories: password-based KDFs and key-based KDFs.

"Password hashes" (or "slow hash algorithms" as non-experts sometimes say) are used to describe password-based functions that "stretch" passwords. Passwords are usually low entropy (that is they're relatively predictable) and so password hashes and PB-KDFs are designed to be artificially slow for both legitimate parties and password crackers to evaluate with the hope that it makes password cracking less "profitiable".

Standard or "fast" hash algorithms are not necessarily insecure just because they are fast. If passwords were as unpredictable as a 128 bit key then password bases could just store SHA-2 hashes of passwords (preferably still salted for off-topic reasons) with no loss to security.

The right way to do things is to increase your password hashing algorithm's cost parameter by a factor of ten. You're doing the same amount of work, $$1 \times (10 \times C) = 10 \times (1 \times C)$$ so your CPU-time budget doesn't increase. On the other hand, the adversary, with only one slower hash function to crack, now needs to always do proportional to $10 \times C$ work instead of just $C$ work.

If you need more key material than a PB-KDF can give you without multiplying the amount of work you need to do, then derive just one master key from the PB-KDF and feed the derived key to a KB-KDF. You can derive many keys from a key-based key derivation function much faster than the run time of a password hashing function.

If for some reason you must use only hash algorithms instead of a stream cipher, then do
$$K_M = bcrypt_{10 \times C}^\text{**}(\text{salt}, \text{password})$$
$$K_i = \text{SHA-512}(K_M \| i \| \text{nonce})$$
$$\text{ciphertext}_i = \text{plaintext}_i \oplus K_{i + 1}$$

And send
$$\text{ciphertext} \| \text{HMAC-SHA-512}(K_0, \text{ciphertext})$$
because you need message authentication in addition to message secrecy.

In my previous cost analysis I treated the key-stream computation as if it were zero. If you choose a large $C$ then this is a reasonable assumption. Otherwise assume little $c$ is the cost of a "fast" hash. You CPU cost is $10 \times C + 13 \times c$. (Since HMAC is 2 more hashes and you derive one more key for HMAC.) And the adversary's cost is $10 \times C + c$. But both are approxmately $10 \times C$.

For your specific proposal, assuming you're using ASCII encoding of plaintext, you can easily infer 32 bits of every full 32 byte block because no standard ASCII character has a byte value with the most significant bit set.

For other types of plaintext it won't necessarily be so trivial, but you should assume that there are some other ways to guess at plaintext. If there is uncertainty then the adversary could just compare more plaintext-guesses to the same hash evaluation. You get more false positives obviously, but this doesn't prevent cracking. False positives can be distinguished from true positives by evaluating a hash with each salt then looking at the decryption to see if it makes sense. (Check if it contains real dictionary words, or do statistical tests comparing it to reasonable plaintext.)

* Assuming the hash function is unbiased, which is reasonable for good password hash algorithms and many common not-good ones. (SHA-1 and MD5 included among other bad ones.) For the plain-old password hashing use case (not your use) false positives (which are so improbable that it's safe to say they won't happen) are just as good as true positives.

** Use Argon2d if an optimized implementation is available instead of bcrypt. bcrypt is fine if it has an optimized implementation. Same for PB-KDF2 and balloon hashing.  (Don't request PB-KDF2 output length that is too long.) You can use scrypt as well if there is an optimized implementation and if you can give it a large CPU and RAM allowance. ... I'm beginning to see that people hear the "Use ___ instead of ___ for password hashing" advice that's beginning to reach a larger audience now and are taking away the cargo-cult-like idea that it means "Always substitute [password hashing function] for [normal hash algorithm or encryption algorithm]". That's wrong. Only use password hashing functions for password storage and for derivation of a master key.

Edit: Argon2d. not Argon2i.


Convert old and busted password encryption to something sensible

Sysadmins have switched from one password hash algorithm to another many times.
There is a standard process for this switch.

The Modular Crypt Format (MCF) is the standard scheme for formatting encrypted passwords, as used by passwd, crypt, etc.
(see Why are there $ signs in my passwd file? ).
MCF uses a single column to store the password hash algorithm and the hash of the password (etc.).
I don't understand why other answers seem to think you need to add a new column -- that seems non-standard and I don't see any benefit over doing it the standard way.

  would it then be possible to determine if the resulting
  stored-password is the new type or the old type?

Yes. If you use MCF for storing the password hash (and why wouldn't you?), it's pretty obvious whether a stored password hash is the new type or the old type.

As explained in Wikipedia: crypt (c) and Wikipedia: passwd, the printable form of new password hashes begins with dollar-digit.
Currently the most widely used password hash algorithms produce a printable form that begins with "\$2y\$", "\$5\$", or "\$6\$".

It is likely that you are storing password hashes in a form that never begins with a dollarsign, and so it will be pretty trivial to determine whether it is the old type or the new type.

If someone, in a TOTALLY HYPOTHETICAL scenario, currently stores password hashes in a format incompatible with MCF, perhaps that person could assign "\$0\$" to represent his old hash algorithm, and convert to a MCF by pre-pending that "\$0\$" to the beginning of all his old-style passwords (and tweaking his login-system so that it recognizes that "\$0\$" as indicating the old password hash algorithm).
There's a way to gradually make this change a little at a time, in a way that each step leaves the system in a "working" configuration where people can still log in.

As I may have said before at " Do I have to recompute all hashes if I change the work factor in bcrypt? ",

Rehash passwords one at a time, as people log in

Many UNIX-like systems are already set up so the sysadmin can change the "preferred" password algorithm, work factor, and salt length at any time.
Later, whenever a user logs in by typing their password, the system updates that user's row in the passwd file to use the system's current "preferred" work factor etc.
See a, b, c, d, e, f, g, h, i, j, k, L, m, n, o for how to tweaking the appropriate configuration file in order to set the "preferred" algorithm etc.
Typically this involves pluggable authentication modules (PAM).

Many passwd files (or thier equivalent) store, for each user,
not only the the salted hash,
but also the user-unique salt, the ID of the hashing algorithm used, and the work factor
(often dollar-sign delimited).
That allows us to gradually switch to a completely different password hash algorithm and salt width.

details:

For example, let's say we want to switch from inadequate amounts of salt and some obsolete hash to bcrypt with a work factor of 11.
The sysadmin sets the "preferred" algorithm, salt, etc. to "bcrypt with a work factor of 11", etc.

The next time a user logs in, resets their password, or changes to a new password -- i.e., uses the login or passwd programs -- those programs:

1) Hold on to the plaintext password the user typed in for a few moments.

2) Check the passwd file to see if that user's hash already uses the latest algorithm, work factor, and salt width. If so, continue with 4.

3) Authenticate the user with whatever old, obsolete algorithm the passwd file indicates for that user. If successful, additionally create a unique new salt with the latest salt width.
Run that salt, and the plaintext password that we're still holding on to, through "bcrypt with a work factor of 11" (or whatever today's preferred algorithm is) to get the new hash.
Update the passwd file for that user with the new hashing algorithm ID, the new work factor, the new salt, and the new hash.

4) Authenticate the user with the shiny new algorithm the passwd file indicates -- the latest algorithm, work factor, and salt width.

5) Then the server must forget the plaintext password.

After a month or two, if some rows of the passwd file still indicate some old, obsolete hashing algorithm and work factor -- i.e., those users haven't logged in for a month or two since you made the change -- you might send them a mail or call them on the phone and ask them nicely to log in soon.

After a few months, if there's still some user whose row of the passwd file still indicate some obsolete algorithm -- i.e., that user hasn't logged in for months -- perhaps you could reset that password and generate a new random unguessable password, more-or-less the same as if that user had forgotten the password and gone through the normal "I forgot my password" process.
If the user ever comes back, go through the normal "I forgot my password" process again to reset the password back to whatever the user wants to use.

See "Migrate old md5 passwords to bcrypt passwords"
for more discussion of this approach.

EDIT:

Modular Crypt Format is now common enough to be a de facto standard.

However, because it doesn't have an "official" standardization document, some argue that it isn't a "real" standard:
"Modular Crypt Format: or, a side note about a standard that isn't".

I recently learned that the LDAP / RFC2307 Hash format does have an official standardization document (RFC2307).
According to
passlib.hash - Password Hashing Schemes,
The LDAP / RFC2307 Hash format "the basic format {SCHEME}HASH has seen widespread adoption in a number of programs."


Does this protocol provide Perfect Forward Secrecy / are there potential security flaws?

No, this protocol does not provide perfect forward secrecy. Record the initial key transport message (shared via RSA-OAEP). If the attacker later gets access to the corresponding RSA private key, and decrypts the original key transport message, the entire symmetric key evolution sequence for that session will trivially unfold.


Is it possible to create a zero-knowledge proof that a number is more than zero, and less than x?

What you want is usually called a range proof: proving in zero-knowledge that some value (committed, or encrypted) is in a given public range. I had written a detailed answer on existing techniques for range proofs where answering this question.

I'm not sure I understood exactly how your scenario would work, but one possible issue with standard solutions is that they are based on algebraic primitives (like, commitments over abelian groups), while you seem to look for a proof related to something hashed in a Merkle tree, without any specific (algebraic) structure. Such statements are harder to prove, but this can be done, using techniques based on garbled circuits to prove knowledge of a satisfying assignment for a given boolean circuit (in your case, this boolean circuit would first check that the input is in the correct range, then hash it the way you want). The most relevant techniques are the recent protocols ZKBoo and Ligero.

One last thing: if you want access to a specific paper that seems relevant to you, but that is behind a paywall, you can contact me by MP (my institution gives me access to the database of most editors).


Proof of Disclosure? Is there such a thing?

You could probably achieve this with a distributed ledger (e.g. a blockchain). If you were to have an image taken of your document recipient holding the document, otherwise you would take the document back immediately or nullifying its effect (e.g. revoke a digital signature on the document that would've been useful for the recipient), and hash that image, and place that onto said ledger, you would have proof that you disclosed information to the recipient. The importance is that due to distribution, the record is redundant, immutable, and most importantly, irrefutable. This method could also be used as a proof of chronology.

One example of this is Bitcoinproof, a method of hashing image data into a Bitcoin address, and sending either a small transaction or no bitcoins to that address. By doing so, the transaction can be mined into a block, becoming a permanent record that can be verified using an image.

Finding the image hash as a Bitcoin address (SHA-256, RIPEMD-160, and base58check), which will have likely only 1 transaction to it, with a timestamp that cannot change, i.e. a proof of chronology. This can also be used as a proof of disclosure, as you mentioned.

That is, unless you're exceptionally good at Photoshopping an image of your recipient into holding your document.

And it might fail, if you lose the photo, or if the network becomes less popular.

Also, this wouldn't be good for private information. You would be using a public ledger, so in the event the receiver disputes your claim, you would have to reveal the information to the public in order to prove this. This means that the document is only good for gaining one time access to a system, through a digital signature.


Verilog simulation of Data Encryption Standard

This site is an interactive presentation of the various elements in DES, showing each intermediate result for the encryption or decryption of some data and key that you specify yourself. This should help you debug your implementation. There are also test vectors (which help check that your implementation is correct) in various places, e.g. there.


The question "why is preimage resistance needed for hash functions" is not really relevant. This is because collision resistance implies preimage resistance. Thus, it is just a fact that if you have collision resistance then you must have preimage resistance.

So, instead, I will relate to what preimage resistance is good for at all. In more technical cryptographic terms, a preimage resistant function is called a one-way function. One-way functions are the most basic cryptographic primitive and you can construct all of symmetric crypto from them (i.e., you can construct pseudorandom generators, functions, symmetric encryption, message authentication codes, and so on). [Note: you cannot construct collision-resistant hash functions from them in a black-box way.] Thus, from a theoretical perspective, these functions are very interesting; I say "theoretical" since the above constructions are all theoretical and not practical.

Note that preimage resistance is a necessary condition almost everywhere in cryptography, but it is usually not sufficient. This is because it does not mean that it's impossible to obtain half of the preimage, and it is also only meaningful for very high entropy - if not random - inputs. The use of preimage resistance in hashing passwords is used in practice, but is only heuristic. In order to analyze this properly, you actually need to model the function as a random oracle.

So, preimage resistance or one-wayness is a fact of cryptography. It is the minimal property that you need to do almost anything interesting in crypto (apart from all of the information theoretic crypto work which I won't discuss here). However, it is not a security notion that is usually of interest in and by itself.

A proof sketch that collision resistance implies one-wayness

Assume that there exists an adversary $A$ who can invert a function $H:\{0,1\}^*\rightarrow\{0,1\}^n$ with probability $\epsilon$ on a random input of length $2n$. We construct an adversary $A'$ who finds a collision in $H$. Adversary $A'$ chooses a random $r\in\{0,1\}^{2n}$, computes $y=H(r)$ and invokes $A$ on input $y$. If $A$ returns $s$ such that $H(s)=y$ and $s\neq r$ then $A'$ outputs $s$. Otherwise it outputs $\bot$. We now analyze the probability that $A'$ succeeds. We have that $A'$ succeeds if $A$ succeeds and $s\neq r$. Since the input is of length $2n$ and the output is of length $n$, we have that each output has on average $2^n$ premiages. Thus, the probability that $s=r$ is negligible. [This part of the proof needs some work, but I'll leave that to the readers as an exercise.] We therefore conclude that $A'$ succeeds with probability $\epsilon - neg(n)$ where $neg$ is a negligible function. Thus, if $\epsilon$ is non-negligible then the function $H$ is not collision resistant. We conclude that if $H$ is collision resistant, then $A$ could only succeed with negligible probability and so $H$ is one-way.


Trivial forgery: If you know the CRC polynomial, then you can add (‘xor’) any multiple of it to the message without changing the CRC.

Short answer.
If the hardware can only evaluate CRCs with fixed polynomials determined by the hardware designer, it's of little use to you for making a MAC.  If you can choose the polynomial and the hardware keeps it secret, well, you've already found some references on how to do this!

The standard way to make a MAC out of a CRC, which we might call a polynomial division MAC and is sometimes called Rabin fingerprinting after a similar idea by Rabin, is to choose a secret irreducible polynomial $g \in \operatorname{GF}(2)[x]$ and a secret polynomial $h \in \operatorname{GF}(2)[x]$ both of degree $d$, uniformly at random; then, to authenticate a single message polynomial $m \in \operatorname{GF}(2)[x]$, transmit the polynomial $h + (m \cdot x^d \bmod g)$ as an authentication tag.

(The Rabin fingerprint is simply $m \bmod g$; it preserves addition of any degree ${<}d$ polynomial to $m$, enabling trivial forgery even if masked by $h$, so it is useless as an in-band authenticator, though it is more convenient for other purposes.)

By a standard result of number theory (alternative exposition), when $d$ is prime, there are $(2^d - 2)/d$ irreducible polynomials of degree $d$; for composite $d$ there are fewer, so prime $d$ gives the most efficient key space.  But this does not cover all $d$-bit strings, and to generate a key, choosing an irreducible polynomial uniformly at random, e.g. using the algorithm in Rabin's paper (pp. 3–4), is costly.  Using a product of irreducible polynomials whose degrees sum to $d$ enables cheaper key generation, but key space and tag space is wasted even more than with an irreducible $g$—the forgery probability is exponential in the number of irreducible factors.

Worse, computing polynomial division in $\operatorname{GF}(2)[x]$ by an arbitrary divisor is costly.  Some CRC hardware admits programmable generator polynomials, but typical hardware uses a fixed polynomial, such as the Intel CRC32 instruction, which is useless for this—not to mention that a 32-bit tag is too small to provide any security.  And in software implementations one is tempted to use table lookups to get any semblance of performance—invariably leaking secrets through timing side channels.  So it's dangerous to design this into any protocols, because you're designing the temptation of timing side channels into the protocols.

There are perfectly good efficient MACs already for hardware and software: polynomial evaluation MACs.  Fix a field $k$; a one-time key is a pair of elements $r, s \in k$ chosen uniformly at random, a message is a polynomial $m$ in $k$ of degree at most $n$, and the authenticator of the message is $t = m(r) + s$.  The adversary's probability of success at forging a tag $t'$ on a message $m' \ne m$ given $m$ and $t$ is no more than $\#k/n$, by a standard argument of counting roots of the polynomial $m'(r) - m(r) + t - t'$ in the variable $r$.  The most common examples are Poly1305, where $k$ is the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$ convenient in software, and GHASH, where $k$ is the binary field $\operatorname{GF}(2^{128})$ convenient in hardware.

Generating keys—picking elements of a field uniformly at random—is fast: for a binary field, uniform random bit strings work; for a large prime field (${>}2^{128}$), rejection sampling on uniform random bit strings works, and the probability of rejection is so small you can ignore it safely.  Derive $r$ and $s$ from a PRF of a message sequence number or a sufficiently large random token and you get a many-time MAC.

The only reason to reach for a polynomial division MAC instead of a polynomial evaluation MAC is the bizarre scenario where (a) you do not have fast binary polynomial multiplication or integer arithmetic available, yet (b) you do have hardware that can efficiently evaluate polynomial division by arbitrary degree-${\geq}128$ divisors, and these performance constraints override all other considerations in your protocol design.


In a Vigenère cipher, the $i$-th ciphertext letter $c_i$ is calculated as $p_i + k_{i \bmod \ell}$, where $p_i$ is the $i$-th plaintext letter, $k_i$ is the $i$-th key letter, and $\ell$ is the length of the key.  Thus, the difference between two ciphertext letters at positions $i$ and $j$ is $$c_i - c_j = p_i - p_j + c_{i \bmod \ell} - c_{j \bmod \ell}.$$

Normally, for this difference to be zero, the difference between the key letters would have to just happen to cancel out the difference between the plaintext letters.  When $i \equiv j \pmod \ell$, however, the last two terms cancel out, leaving just $p_i - p_j$, which, since the plaintext typically has an uneven letter frequency distribution, is more likely to be zero than one would otherwise expect.

Now, consider the autokey cipher, where (beyond the first $\ell$ letters) $c_i = p_i + p_{i-\ell}$.  Now the difference between two ciphertext letters is given by $$c_i - c_j = p_i - p_j + p_{i-\ell} - p_{j-\ell}.$$  This time, when $i - j = \ell$, it's the middle terms that cancel, leaving just $p_i - p_{j-\ell}$ $=$ $p_i - p_{i-2\ell}$.

Again, it's a lot more likely for a single pair of plaintext letters to be identical than it is for the differences of two pairs of letters to cancel out just by chance.  Exactly how much more likely depends on details of the plaintext frequency distribution, but the qualitative behavior is quite robust and shows up for most naturally occurring letter frequencies.

Ps. Note that the conditions for this cancellation to occur are different.  For the Vigenère cipher, cancellation occurs whenever $i - j$ is a multiple of the key length $\ell$, producing a characteristic comb-shaped autocorrelation plot.  For an autokey cipher, however, cancellation only occurs when $i - j$ exactly equals the key length, resulting in just a single peak.


Is there an encryption algorithm with a key that can only be used to decrypt?

There's two fundamental difficulties with what you're asking for.

First, in the usual definition of public-key encryption, the public key is assumed to be, well, public.  That is, everybody is assumed to know it, and thus to be able to encrypt messages.

If you don't want everybody to be able to encrypt, then you're no longer doing public-key crypto in the usual sense, and you need to start paying attention to things like exactly who should be allowed to know the (not so) public half of the key pair and how the halves of the key pair should be distributed.

Second, in general, whoever first creates the key pair must, at least temporarily, possess the information necessary the construct both keys.  If they want, they can save that information and use it to both encrypt and decrypt any messages.

In standard public-key crypto this is not an issue, since it's usually assumed that the keys are generated by the private key holder, who is supposed to know both keys anyway.  But if the private key holder is not supposed to know the "public" key, then we need to either:

trust the private key holder to forget the public key (and any other information that could be used to reconstruct it) after generating it,
entrust the key pair generation to some trusted third party (who, if they're not as trustworthy as we think they are, could then eavesdrop on or tamper with any communications encrypted with the keys), or
somehow generate the key pair using some kind of distributed multi-party computation scheme that doesn't allow any party to learn any parts of the keys they shouldn't know (which is far from a trivial task, if it's even possible).

All that said, if we handwave all those issues away (e.g. by assuming a trusted third party that handles key generation and distribution), plain old RSA can be used like this.  In fact, I asked a question about using RSA in a very similar manner a while ago.

All we need to do is somehow ensure that:

only those who should be able to encrypt messages know the encryption exponent $e$,
only those who should be able to decrypt messages know the decryption exponent $d$, and
nobody (except maybe the 100% trustworthy key generator) knows the factors $p$ and $q$ of the modulus $n = pq$, or anything else (such as $\lambda(n) = \operatorname{lcm}(p-1,q-1)$) that could be used to reconstruct one exponent from the other.

(The modulus $n$ itself can still be public knowledge.)

Of course, this implies that we cannot use a fixed encryption exponent like $e = 65{,}537$, like most ordinary RSA implementations do, but must instead pick $e$ at random from the set of distinct possible encryption exponents (i.e. positive integers less than and coprime to $\lambda(n)$).

We can do this by repeatedly picking a random odd number $1 < e < \lambda(n)$ until we find one that satisfies $\gcd(e, \lambda(n)) = 1$, and compute $d = e^{-1} \pmod{\lambda(n)}$.  Or, equivalently, we can pick $d$ randomly in the same way, and compute $e = d^{-1} \pmod{\lambda(n)}$.  Modular inversion is a bijection, so picking $e$ uniformly at random from the entire set of invertible congruence classes ensures that $d$ is also uniformly distributed, and vice versa.

In fact, the latter scheme is essentially* what Rivest, Shamir and Adleman used in the original RSA paper.  Using a small, fixed $e$ is a later optimization introduced after it was realized that $e$, being public, doesn't actually need to be random.

The tricky part, of course, is that whoever generates the key pair will still end up knowing both $e$ and $d$, and — if they're not supposed to retain the ability to both encrypt and decrypt — must be trusted to securely forget at least one of these exponents, as well as any other values (including $p$, $q$ and $\lambda(n)$) that would allow them to reconstruct those exponents later.

*) The original RSA paper uses $\phi(n) = (p-1)(q-1)$ instead of $\lambda(n)$ when computing the modular inverse.  This has no real effect on security, it just sometimes produces larger exponents than necessary and allows multiple equivalent key pairs.  The original RSA paper also does not specify an actual range to pick $d$ from, but only that it should be "a large, random integer".


Well, what are we comparing Feistel networks to? The other major design paradigm is SPN: https://en.wikipedia.org/wiki/Substitution-permutation_network. In comparison to SPN, the cons are:

Not a direct implementation of confusion and diffusion. Feistel networks have more structure that has no clear justification. (Some point to the security proof but if you assume a cryptographically secure round function, how wrong can things go? A better question is: "if your round function is weak, what does the Feistel network add?").
Parallelism is about half of an equivalent SPN, which is a disadvantage for hardware implementations.


Could multicollisions be used to mine large amounts of cryptocurrency?

In the Bitcoin mining, hashcash version 2 (2002), one looks for the input $m$ such that $\operatorname{SHA256d}(m)$ is the desired output hash value that is below the current threshold of zeros. In other words  $$\operatorname{SHA256d}(x)/2^{(n-k)} = 0$$ where $k$ is the work factor, that is the number of leading zeros and $n$ is the output size that is 256 for SHA256. This was before factional is introduced;

$$\operatorname{SHA256d}(x)< 2^{(n-k)} $$

The required threshold is given therefore one look for the pre-images, that is given the hash value $x$ find a pre-image that the $\operatorname{SHA256d}(m) < \text{threshold}$. Since we are looking for a threshold the search easier than the preimage attack and still harder than the collision attack.

Note that BitCoin defines a term for this search pre-image with a partial output match.

The search doubles when the number of leading zeros is incremented by one. Therefore it is getting harder and harder. If someone is so lucky then they can find some of the required values easily but this probability is so lower than hitting your head with a meteorite!

The bitcoin miners reached $2^{92}$ double SHA2 searches in a year. If you consider that they find the block in one, they need two years, on average, or double the hardware and therefore the power consumption.

  Is my understanding of multi collision correct? If so, is the difficulty of finding a 2-collision the only thing preventing this from being done?

Yes, one firstly needs to find the collisions to apply multi-collisions. And, SHA256 is far from finding one.

Note: Finding pre-image is harder than collision attacks. The Cryptographic hash functions like MD5 and SHA-1 are collisionally broken since one can find collisions better than the generic collision attack, which is given by the birthday attack. However, none of the cryptographic hash functions, including the MD5 and SHA-1, are vulnerable to pre-image attacks. Currently, $\operatorname{SHA256}$ requires around $2^{256}$ hash computations to find a pre-image. Actually, during the search one can find nearly all the pre-images that have hash values with leading zeros.


Security of RSA public key depending on how it's computed

I'm now trying to figure out how the choice of totient function affects the security of the public key, if any.

Not at all.  The totient function used has absolutely no affect on the public key.  When you generate the public/private key pair, you usually select $p, q$ and $e$ (in some order), and then compute $d$ (using the totient); because the public key is a function of $p$, $q$ and $e$ (which were all selected before you used the totient), the totient has no impact on the public key.

The only effect it has would be on the $d$ parameter that is contained within the private key - we don't place that into the public key, and so the public key isn't affected.  And, even the holder of the private key (would can look at $d$) might not care - if he uses the CRT optimization, he would use the $p, q, dp, dq$ and $qInv$ parameters (which are also not affected by the totient) and typically ignore $d$.


How to break AES CBC PADDING with chosen ciphertext attack

I believe you can deduce the IV by passing in a chosen ciphertext. This ciphertext should be of the form C = C0||C0, where C0 is the first ciphertext block, and || is the concatenation operator. In other words, send the same block twice!

This will get you two blocks of plaintext, P0||P1. We have that

Decrypt(key, C0) ^ IV = P0
Decrypt(key, C0) ^ C0 = P1

Therefore,

P1 ^ C0 = Decrypt(key, C0)
P0 ^ P1 ^ C0 = IV


What are implementations of PRNGs based on ChaCha20?

Beyond what specific primitive your system will be based on, there are important things to consider while building a CSPRNG.

Bernstein's Fast-key-erasure random-number generators article is a good starting point, as well as how randomness generation is done in Amazon S2N.

Buffer output, but erase data as it's being read, frequently rotate the key, mix multiple entropy sources if possible.

Libsodium provides a Salsa20-based CSPRNG implementation. It is not used by default, as for most applications, reading /dev/urandom is perfectly fine.

ChaCha20 can be a drop-in replacement for Salsa20 here.


Cracking WWII-era codes - code found on a pigeon's leg in Surrey

A problem with this message is that the image in a press release from GCHQ differs slightly from one in a New York Times article, although the paper, with its tears looks the same.

The image below shows the two side by side, the one on the left from the NY Times and the right from GCHQ. There is a slight difference in the style of writing, i.e. more sloping to the right in the GCHQ image. There are also some word differences: word 7 is GOVFN from GCHQ and FOVFN in the other.

That the message was found in Bletch***ing***ley, Surrey may be a bigger clue.


Asymmetric CSPRNG where the public key only works backward

Disclaimer: I've not verified the security of my proposal.

You can achieve that in two ways: one pre-quantum, using RSA-like scheme, another post-quantum, using multivariate system.

The RSA version.

Generate an RSA key pair, keep the private key $(N,d)$ to yourself, give the public key $(N,e)$ to the second party.

To generating new numbers, calculate $x_{i+1} = x_i^d \pmod N$. This way, the second party can go backwards from known $x_i$ by calculating $x_{i-1} = x_i^e \pmod N$

The multivariate version.

This version is significantly more heavy-weight than the RSA version. Although there are several multivariate signature schemes in the NIST PQC "Competition" (it seems difficult to build secure encryption scheme using MV), many of them uses exotic methods to compress the public key, which may be optional depending on your use-case.

In its simple form, you have a public multivariate system $P$ which is the composition of private components $S \circ F \circ T$ where $F$ is a easily solvable quadratic system, and $S$ and $T$ are linear.

To generate new random numbers,

Calculate $u = S^{-1}(x_i)$
Solve $u = F(v)$ and choose arbitrary $v$
Calculate $x_{i+1} = T^{-1}(v)$

The second party can reverse it with $x_{i-1} = P(x_i)$

As mentioned by poncho in the comment, the solved $v$ may not be a unique solution, but that's not a problem because any generated $x_{i+1}$ satisfies $x_i = P(x_{i+1})$.

Edit

It seems you're not quite familiar with the notations.

In $x_{i\pm1}$, the $i\pm1$ is the subscript, so in terms familiar to programmers, it's x[i+1] or x[i-1].

$x_i$ is the current state of the PRNG. Since that is the output of some arithmetic operations, its bit pattern is not fully uniformly random (i.e. may fail some sophisticated statistic tests), so you may need to truncate it and/or hash it, to obtain some quality random bits - hashing is also done by the TLS protocol for the same reason.

And yes, it's an iterative generator, but I'm not sure what you mean by "algebraic", and why you believe it'd be inefficient in the second comment.


Which is more secure using a CSPRNG for a One-time pad, or AES?

First of all, a terminology nit: please don't say "a One-time-pad generated by a CSPRNG"; a one-time pad must, by definition, be generated randomly, and an important part of its security proof is that it was generated randomly (and so an attacker cannot disqualify any potential pad, even if that attacker had infinite computational resources).  Exclusive-or'ing a CSPRNG output with the plaintext to form the ciphertext is a stream cipher; while it is a perfectly usable primitive, it isn't the primitive known as OTP.
In addition, if we use a stream cipher, we usually don't generate the entire key stream on one side, and send that to the other.  Instead, we usually send the key (initial CSPRNG state) from one side to the other; that drastically reduces the amount of keying material that needs to be sent, and is no less secure.
Now, with those nits done, the answer to your question (which is more secure, GCM or a secure stream cipher) depends on what you mean by "secure".
If by "secure", you mean privacy (that is, an eavesdropper cannot obtain any information of the encrypted message), well both GCM and secure stream ciphers are perfectly secure against real potential adversaries; on this score, they are even.
If by "secure", you mean integrity (that is, someone in the middle that can intercept messages, and inject modified versions cannot fool the receiver into accepting a message that the sender did not send), well, classic stream ciphers run into a problem.  That's because stream ciphers are malleable; specifically, an attacker can flip a bit in the ciphertext. On decryption, the corresponding plaintext bit will be flipped (and thus an attacker who guesses what the plaintext is can modify the ciphertext so that it decrypts to whatever he wants).  This doesn't work with GCM; if the attacker modifies the ciphertext in any way, the integrity check within GCM will fail, and so the receiver will reject the message.  Yes, this means that an active attacker can cause messages to be rejected; an active attacker can do that in any case.
Now, there are standard constructions (such as a MAC) on top of the standard stream cipher apparatus which also provides integrity protection.  So, if we ask CSPRNG+MAC vs GCM, well, there isn't a great deal of difference from a security standpoint (but there may be practical differences, such as "what happens if a message gets lost; do you need to handle that case?").


Is there a computational security of public-key encryption which is similar to the one of symmetric key encryption

I am sorry, but I think you are misusing the term "computational security". This concept is a much broader than the definition you have written.

We say that a scheme is computational secure if it satisfies some security definition on which the attacker is supposed to have limited resources (typically, the attacker is supposed to run in polynomial time).

This concept must be seen as the opposite of unconditional security, which makes no assumptions about the resources available to an attacker.

That said, the definition you have provided to symmetric key encryption scheme is actually the definition of passive one-time semantic security, which you can find, for instance, on the book Introduction to Modern Cryptography (definitions 3.8 and 3.12 in the second edition. They are proved to be equivalent...)

There is no equivalent definition for public-key schemes because the attacker has the encryption key and knows the encryption algorithm (Kerckhoffs's principle), so one can't impede she/he from generating many pairs of cleartexts and ciphertexts (therefore, no one-time-like definition is possible). This is why we stick with IND-CPA security.

Moreover, this is also why the second security definition you have provided is not equivalent to IND-CPA: you are not supposing the adversary can chose several plaintexts and encrypt.

Considering the definition of IND-CPA on Wikipedia, you skipped the second step:

  The adversary may perform a polynomially bounded number of encryptions or other operations.


Why is PuTTYgen-created RSA public exponent(e) not in {3,17,65537}?

The answer is in the source, file sshrsag.c, line 9:

  #define RSA_EXPONENT 37             /* we like this prime */

This value $e=37$ matches the conditions for a reasonable fixed RSA public exponent:

$e$ is odd,
$e$ is at least $3$,
$e$ is reasonably small.

The later condition

is good for speed of operations involving the public key (encryption, and signature verification);
makes it harder to choose the prime factors of the public modulus so as to get an unnaturally small $d$, which could allow factorization.

That $e=37$ is prime simplifies the choice of the prime factors of the public modulus $N$, as explained in a later comment:

  Generate $p$ and $q$: primes with combined length `bits', not congruent to $1$ modulo $e$. (Strictly speaking, we wanted $(p-1)$ and $e$ to be coprime, and $(q-1)$ and $e$ to be coprime, but in general that's slightly more fiddly to arrange. By choosing a prime $e$, we can simplify the criterion.)

The only known drawback of $e=37=2^5+2^2+1$ compared to $e=17=2^4+1$ or $e=3=2^1+1$ is that raising to the 37th power modulo $N$ requires 7 modular multiplications, versus 5 for the 17th, or 2 for the 3rd.

We can speculate that the authors like $e=37$ because it is not of a special form, as are the Fermat primes $F_k=2^{(2^k)}+1$ with $0\le k\le4$, often used as RSA public exponents. A compromise between being large and allowing efficient public-key operation was likely not part of the considerations: the larger $e=41=2^5+2^3+1$ also requires only 7 modular multiplications (and as a bonus, is closer to the Answer).

The rest of this answer reports on my incomplete review of the RSA code of PuTTY 0.66, aimed at weakness related to the relatively small $e=37$. I have not identified any if the generated key is used by (that version of) PuTTY, and all other entities relying on the corresponding public key do so properly. Otherwise, I can't rule out that some systems have vulnerabilities that could be more easily exploitable with PuTTY's $e=37$ than the traditional $e=65537$ mandated as the minimum by several security authorities. I'm thinking in particular of

incorrect verification of PKCS#1 V1.5 type 01 signature, which abound; see Daniel Bleichenbacher's RSA signature forgery based on implementation error (archived account by Hal Finney of Crypto 2006 rump session); Ulrich Kühn, Andrei Pyshkin, Erik Tews, Ralf-Philipp Weinmann Variants of Bleichenbacher’s Low-Exponent Attack on PKCS#1 RSA Signatures; and yet other reports.
vulnerable (even if conformant) implementations of decryption per PKCS#1 V1.5 of padding type 02, as considered by Daniel Bleichenbacher's Chosen ciphertext attacks against protocols based on the RSA encryption standard PKCS #1 (in proceedings of Crypto 2008).

There is no known weakness associated to using small $e$ when RSA is used with good padding (as RSASSA-PSS and RSAES-OAEP in PKCS#1 V2). Other RSA paddings supported in PuTTY include lesser PKCS#1 V1.5 paddings, but I did not find the dreaded padding type 00, which essentially is no padding, unsafe, and even more unsafe for small $e$. PuTTY can use PKCS#1 V1.5 padding type 01 for signature, which has no known vulnerability for correct verification, as performed by PuTTY. It can use PKCS#1 V1.5 padding type 02 for encryption, but does not implement decryption with potentially vulnerable padding check.


Is it possible to decrypt an ECDSA private key if the same nonce is used across different private keys?

Is it possible to retrieve $x_1$ and $x_2$ in this scenario?

Yes. We multiply each equation by it's corresponding $k_i$ and reformat, giving
$$\begin{array}{rrrrrrr}
s_1\,k_1&&-r_1\,x_1&&\equiv&h_1&\pmod p\\
s_2\,k_1&&&-r_1\,x_2&\equiv&h_2&\pmod p\\
&s_3\,k_2&-r_2\,x_1&&\equiv&h_3&\pmod p\\
&s_4\,k_2&&-r_2\,x_2&\equiv&h_4&\pmod p
\end{array}$$
and that's a linear system of 4 equations in field $\Bbb Z_p$ with 4 unknowns $k_1$, $k_2$, $x_1$, $x_2$ for one knowing the 4 signatures and (the hash of) their respective messages. It has unique solutions except if $s_1\,s_4\equiv s_2\,s_3\pmod p$, which has no reason to hold, since the $s_i$ are non-zero and randomized at least by their respective $h_i$.

If I got the details right,
$$x_1=\frac{h_1\,r_2\,s_2\,s_3-h_2\,r_2\,s_1\,s_3-h_3\,r_1\,s_1\,s_4+h_4\,r_1\,s_1\,s_3}{r_1\,r_2\,(s_1\,s_4-s_2\,s_3)}\bmod p\\
x_2=\frac{h_1\,r_2\,s_2\,s_4-h_2\,r_2\,s_1\,s_4-h_3\,r_1\,s_2\,s_4+h_4\,r_1\,s_2\,s_3}{r_1\,r_2\,(s_2\,s_3-s_1\,s_4)}\bmod p$$
where operations including division are in the multiplicative group $\Bbb Z_p^*$.

Michael Brengel and Christian Rossow's Identifying Key Leakage of Bitcoin Users (in proceedings of RAID 2018) is an interesting attack against bitcoin implementations. It gives a good illustration that nonce must be generated with great care in ECDSA (and other DLog-based signature schemes).

A robust and perfectly interoperable option is to deterministically use $k=\text{HMAC}(x,h)\bmod p$ where HMAC uses a hash and output size much wider than $p$ (e.g. SHA-512 and full size output for up to ≈400-bit $p$), $x$ is the private key, and $h$ is the hash of the message as used in the signature production.

If for some reason we want a randomized signature, we can first generate a tentatively true random $d$ then compute $k=\text{HMAC}(x,(h\mathbin\|d))\bmod p$ or $k=(\text{HMAC}(x,h)\oplus d)\bmod p$. This insure that a failure of the true RNG will not reveal the private key.

These three methods to generate $k$ could theoretically give $k=0$ and that should be tested against, but if we encounter this, $r=0$, or $s=0$ in ECDSA signature, the practical line of action should be to declare attack and burninate every data manipulated that won't be an unbearable loss (including the copy of the private key if there is a backup).


Does the Blake3 hash have identities, due to its merkle tree structure?

No, any simple identity like that would violate the cryptographic properties that BLAKE3 aims to have. Finding these cases is supposed to require a brute force search.
BLAKE3 is a Merkle tree, but it isn't constructed by XORing things together. Instead, parent nodes in the tree are constructed by concatenating the hashes ("chaining values") of each child, and then calling the compression function again with that concatenation as the input. Other important details are that the compression function domain-separates chunk/leaf outputs from parent node outputs, and that it domain-separates the root node from non-root nodes. (As an aside, it also domain-separates each chunk/leaf based on its index. That's not necessary for the security property we're talking about here, but it accomplishes other things. See section 7.5 of the BLAKE3 paper.) Putting all that together, it should be difficult to find any relationship between the BLAKE3 hashes of any two distinct inputs.


Combining md5 collisions to create more collisions

Let $f$ be the compression function of a Merkle–Damgård hash function $\operatorname{MD}_f$, like MD5.  Suppose we have a cheap algorithm $C(h)$ which returns message blocks $m_0 \ne m_1$ such that $f(h, m_0) = f(h, m_1)$.  We can use this with the standard initialization vector $\mathit{iv}$ to find a two-way collision $(m_0, m_1) = C(\mathit{iv})$, so that $$\operatorname{MD}_f(m_0) = f(\mathit{iv}, m_0) = f(\mathit{iv}, m_1) = \operatorname{MD}_f(m_1).$$  Can we use it to find a four-way collision $(m_0, m_1, m_2, m_3)$?

Answer: Yes, we can use an algorithm $C$ for finding two-way MD collisions to find $2^n$-way collisions with only $n$ calls to $C$.

Let $(b_0, b'_0) = C(\mathit{iv})$.

Then $f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)$.

Let $h_1 = f(\mathit{iv}, b_0) = f(\mathit{iv}, b'_0)$.
Let $(b_1, b'_1) = C(h_1)$.  That is, use the common hash as a new initialization vector to find a new collision.

Then $f(f(\mathit{iv}, b_0), b_1) = f(f(\mathit{iv}, b_0), b'_1))$, etc., so the messages \begin{align} m_0 &= b_0 \mathbin\| b_1, \\ m_1 &= b'_0 \mathbin\| b_1, \\ m_2 &= b_0 \mathbin\| b'_1, \\ m_3 &= b'_0 \mathbin\| b'_1 \end{align} constitute a four-way collision.

Lather, rinse, repeat for as many distinct collisions as you want.

This family of attacks, and their impact on concatenating hash functions, is described in more detail in Antoine Joux, ‘Multicollisions in Iterated Hash Functions. Application to Cascaded Constructions’, in Matt Franklin, ed., Advances in Cryptology—CRYPTO 2004, Springer LNCS 3152, pp. 306–316.


Keeping the key and IV safe when AES256 encrypting publicly known data

Take a look at this article it explains the IV can be publicly known once you have encrypted your data.

  Is using (and storing) a different iv for each file sufficient? (Am I
  correct in thinking that I'd need to store the iv with the encrypted
  data?)

Yes, as a matter of fact i would not recommend using an IV twice, just for safety.

  Is this safe? (It looks to be, according to: Why is AES resistant to known-plaintext attacks?)

Yes, like the article says they would still have to bruteforce the key to get the cipher text

So there is no problem in doing this, though if data is public why would you encrypt it? everyone knows it, why go through all the trouble?

Use a MAC, to quote the page i linked to:

  Altering the IV Before Decryption

  If the adversary can alter the IV, without detection, before the
  ciphertext is decrypted, then they can corrupt the first block of
  plaintext. If the adversary knows the first block of plaintext is P
  and the original IV is OIV, and wants it to decrypt to Z, they can
  alter the IV to be P XOR Z XOR OIV, which will cause the first block
  to decrypt to Z (since (P XOR OIV) XOR (P XOR Z XOR OIV) = Z).

  Encryption provides secrecy, not authentication or integrety. If
  encryption is used in a setting where the adversary can modify the IV
  or ciphertext, it must be authenticated. The right way to do this is
  to have the sending party apply a keyed Message Authentication Code
  (MAC), like HMAC, to the IV and ciphertext, and have the receiving
  party check that the MAC is correct before decrypting.


As far as I understand, there isn't an easy algorithm to find the generator of a cyclic group used in DH Key exchange. Is it true?

No, it is easy, as long as you know the factorization of $p-1$.

A value $1 < g < p$ will be a generator to a prime $p$ iff for every prime factor $q$ of $p-1$, we have $g^{(p-1)/q} \not\equiv 1 \pmod p$

And, there will be enough generators (specifically, $\phi(p-1)$ of them) that just randomly selecting $g$ randomly, and then testing them by the above process is quite doable.

So, isn't factoring $p-1$ a hard problem?  Well, it wouldn't be for the 79 bit value you picked, but that's far too small to be used in a Diffie-Hellman exchange, it is generally accepted that you need at least a 2048 bit prime.  So, for a value $p-1$ that size, how do we factor it?

Well, what we don't do is select a large random prime $p$ and try to factor it; instead, we build a value $p-1$ with a known factorization, and check that $p$ happens to be prime.  One common way of doing this is to search for $p$ such that $(p-1)/2$ is also prime (this is known as a "Sophie Germain prime") and hence $p-1$ has a known factorization.

That said, you said you were doing this for Diffie-Hellman; generally, for DH, you don't want $g$ to be a true generator (as that'll leak, at the very least, the lsbit of your private exponent); instead, we more usually select $g$ such that the order $q$ is a large prime factor of $p-1$; if we know the size of the subgroup we want, we can stir that into the factorization of $p-1$ when we build it; either by:

Using a Sophie Germain prime (and so $p-1 = 2q$), if $p \equiv 7 \bmod 8$, then $g=2$ will generate the size $q$ subgroup.
Or by picking a prime $q$ perhaps 256 bits long, and then searching for a (possibly composite) value $r$ such that $p = 2rq + 1$ is also prime; we can find our generator by selecting an arbitrary $h$ and setting $g = h^{2r} \bmod p$; if $g \ne 1$, then that's our generator.

All that said, I expect that you don't know enough number theory to go through that yourself.  For decent DH parameters, I send people to this document for precomputed groups; I would recommend the "2048-bit MODP Group" settings.


Find IV and the key ? AES with CFB or OFB

In my specifications, it doesn't matter if someone can decipher the messages. However, someone should not be able to send encrypted messages that would be recognized by the recipient.

If that's the case, then encryption is the wrong solution; you are looking for a Message Authentication Code (MAC), such as CMAC.
With CMAC, you hand the message and the key to the CMAC code, which generates a 'tag'.  You send the message and the tag to the recipient, which takes the message (and their own code of the key) and calls CMAC to generate their own tag.  If the tag they computed agrees with the tag you sent, they accept the message; otherwise, they reject it.
CMAC (and any other MAC) was designed with the security property that, if you don't know the key, you cannot find a message/tag pair that validates (even if you were given a large number of valid message/tag pairs).  This is exactly what you want; someone cannot generate a tag that would be accepted (except for the message/tag pairs they have already seen).
Of course, if replay attacks are potentially an issue (that is, if an adversary takes a message/tag pair verbatim and resubmits it, would that be an issue?); if it is, you can add further protection (e.g. include a sequence number with the message; this sequence number always increases; the recipient verifies that it is higher than the previously seen valid messages, and the sequence number is included in the CMAC computations).
Obviously, someone listening in can find the message (it's in the clear); however you said you didn't care about it.
I suggested CMAC in particular because you appeared to have AES in mind (and CMAC based on AES is not a bad option); other good message authentication codes are HMAC and KMAC.


Bitwise operation on secret values revealing the result only to the participants

The concept of "bitfield" is in fact irrelevant in this case since it doesn't really matter to which algebraic structure the data belongs to, at the end you're not using this structure at all, you're just treating them as bit strings.

What you're looking for is Secure Multiparty Computation (MPC). A bit more specifically, you need Two party computation (2PC). There are many techniques to achieve this but since you're working over a binary representation I recommend you to take a look at Garbled circuits or TinyOT (the latter should perform well since your circuit has low depth).

As a note, you cannot achieve this with something weaker than 2PC since computing AND gates is essentially complete for 2PC, meaning that any other solution you find could potentially imply a 2PC protocol.


2 comparable hashes generated from one string

Deriving an encryption key and a password hash from a single password
Hash the password, along with a per-account salt.
hash1 = SHA256(password, salt)

hash1 is your encryption passphrase that you pass to GPG.
hash2 = SHA256(hash1)

You keep hash2 in your database to figure out when a user has logged in correctly.
(For additional security, change the first SHA256 out for scrypt, tuned for 50 milliseconds. More trouble than it's worth, IMO.)
Encrypting a file
Use a library like GnuPG. If you don't have GnuPG bindings for your language (I'm guessing you're using PHP), you can hack something together by running gpg from your program with the  -c and --passphrase arguments.
Note that if the user changes their password, you need to decrypt and re-encrypt using the new password.


Difficulty of generating a string "The (md5|sha1) hash of this string is (x)" that hashes to (x) vs. regular hash collision between files?

Yes, it would be much more difficult to generate a string of the form The (MD5|SHA-1) hash of this string is (x) where x is (in hexadecimal or binary) the hash of that string, than it is to find collisions for MD5 or SHA-1. In fact, even though we can generate collisions for MD5 at low cost including for short messages (64-octet), I don't think that we could plug this one. Main issue is that the string x that we can change is much too small, and the rest too constrained.

However, we can easily construct a family of $2^{128}$ octet strings all with the same MD5 hash that are valid PDF documents and display any desired 128-bit value in hexadecimal, including one such document (that we can exhibit) displaying its own hash. That also works for Postscript, non-signed executables.. It would be feasible to do this for SHA-1, but that would cost about 128 times more work than what was used for one collision.

The trick is to start from a PDF document that displays a value depending on its content at 128 bits changing in 128 different local changes that each leave the hash invariant; each change involving altering 2 message blocks for SHA-1, or just 1 for MD5.

Update: That trick was pulled for a GIF image!