How many trials does it take to break HMAC-MD5?

You can find a collision in MD5 at much lower cost than $2^{64}$ evaluations of MD5.  You could do the same for HMAC-MD5, if you knew the key, which renders it unfit for unusual applications such as commitments.

But the standard security conjecture of HMAC-MD5 is that it is a pseudorandom function family, which assumes the adversary doesn't know the key.  Any program the adversary writes which takes a function as a parameter and evaluates it as an oracle at arbitrary messages of its choice won't behave much differently whether you feed it (a) HMAC-MD5 under a uniform random choice of key, or (b) a uniform random choice of function.

f0_memo = {}
def f0(x):
    if x not in f0_memo:
        f0_memo[x] = os.urandom(16)
    return f0_memo[x]

k = os.urandom(32)
def f1(x):
    return hmac_md5(k, x)

def distinguisher(prf):
    y0 = prf('hello world')
    y1 = prf('query query quite contrary how does your crypto grow')
    ...
    return 1 if i_predict_it_was_f1 else 0

# Then the probability that distinguisher(f0) = 1 is not much different
# from the probability that distinguisher(f1) = 1.

Formally, we define the PRF-advantage of a random algorithm $D$ at distinguishing a family of functions $f_k$ (e.g., $\operatorname{HMAC-MD5}_k$) from uniform random to be:
\begin{equation*}
  \operatorname{Adv}^{\operatorname{PRF}}_f(D)
= \lvert\Pr[D(f_k) = 1] - \Pr[D(u) = 1]\rvert,
\end{equation*}
where $k$ is a uniform random key for the family $f_k$, and $u$ is a uniform random function.  We conjecture that for any distinguisher algorithm $D$, $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is small enough we're not worried anyone can exploit it, as long as the computational cost of $D$ is within reason—fewer than $2^{128}$ bit operations, for instance.  This formalism will come in handy later, but let's look at distinguishing strategies first.

Let's suppose $k$ is 256 bits long.  It could be as long as 512 bits for MD5 and fill an entire block, or technically longer, but there are problems with using keys that fill or exceed a block in HMAC, and 256 bits is perfectly adequate for serious security.

You could try to guess $k$ and see if evaluating the oracle at some message $x$ yields $\operatorname{HMAC-MD5}_k(x)$, but there are $2^{256}$ possibilities for $k$, rendering that strategy computationally impossible—though formally we can conclude that there exists a distinguisher $D$ that queries the oracle only once such that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = c/2^{256}$, where $c$ is the number of times $D$ can afford to compute HMAC-MD5.*

What about collisions?
If you evaluate the oracle at $2^{64}$ different inputs, you would probably find a collision.  That is true for HMAC-MD5 under a uniform random key and true for a uniform random function, so a priori, finding a collision doesn't break the security of a PRF by distinguishing them on its own.  However, MD5 also has the property that if $x_0 \ne x_1$ collide under MD5, with $\operatorname{MD5}(x_0) = \operatorname{MD5}(x_1)$, then so do $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$ for any common suffix $y$, as long as $x_0$ and $x_1$ have the same length.

So if you query the oracle on a whopping $q = 2^{64}$ inputs, with high probability you will find a collision $x_0 \ne x_1$; then to tell whether the oracle is HMAC-MD5 or a uniform random function, pick a suffix $y$, say a single zero bit or a GIF of a funny cat video, and query the oracle at two more inputs: $x_0 \mathbin\Vert y$ and $x_1 \mathbin\Vert y$.  If they still collide, the evidence is overwhelming in favor of HMAC-MD5 over a uniform random function.†  In particular, the conditional probability that $x_0 \mathbin\Vert y$ and $x_0 \mathbin\Vert y$ collides is 1 for HMAC-MD5, and $2^{-128}$ for a uniform random function.  For any number of queries $q$ with this distinguisher, by the birthday paradox, $$\Pr[D(\operatorname{HMAC-MD5}_k) = 1] \approx q^2\!/2^{128}.$$

It turns out that this generic attack on HMAC over any iterated hash function is the best known attack on the PRF security of HMAC-MD5.  (There are other distinguishers for HMAC-MD5 from ‘HMAC’ over a uniform random function, but this is not really important for applications like MACs below, and their area*time cost is infeasibly large, well over $2^{128}$.)  So the security conjecture for HMAC-MD5 is that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) \leq q^2\!/2^{128} + c/2^{256}$$ for any random algorithm $D$ making at most $q$ queries with area*time cost at most $c$.  And since $2^{256}$ is a very large denominator, you do not have enough spare change rattling around your pocket to afford a computer large enough for long enough to make a dent in it, so we might skip that term altogether and call it $q^2\!/2^{128}$.‡

What about using HMAC-MD5 in an application, for instance as a message authentication code?  It turns out that any pseudorandom function family makes a good message authentication code.  The security goal for a message authentication code is unforgeability: an adversary wins if, after querying an oracle to learn the authenticators on for $q$ messages of their choice, they can forge an authenticator on a message not previously sent to the oracle.

def forger(mac):
    y0 = mac('hello world')
    y1 = mac('The Magic Words are Lightning Sloth Race')
    ...
    return (authenticator, 'another message')

The MAC is secure if the forger has negligible probability of winning, which we formally define to be the MAC-advantage of a random algorithm $F$ at forging authenticators: $$\operatorname{Adv}^{\operatorname{MAC}}_f(F) = \Pr[(a, m) = F(f_k), f_k(m) = a],$$ for any random algorithm $F$ that returns a message it didn't send to the oracle.  As above, the forger could submit $2^{64}$ queries to the oracle and probably find a collision $x_0 \ne x_1$; then query the oracle to find the authenticator for $x_0 \mathbin\Vert y$, and forge it as the authenticator for the message $x_1 \mathbin\Vert y$.  Is this the only way?  We could study strategies for forging HMAC-MD5 directly, but there's a simpler way to understand the MAC security of HMAC-MD5 if we accept the PRF security of HMAC-MD5, using the formalism above.

Suppose we had a successful forger subroutine which and succeeds with probability $p$.  Then we can define a distinguisher:

def make_distinguisher(forger):
    def distinguisher(f):
        a, m = forger(f)
        return 1 if f(m) == a else 0
    return distinguisher

If $f$ is HMAC-MD5 under a uniform random key, the forger succeeds and the distinguisher returns 1 with probability $p$.  If $f$ is a uniform random function, the distinguisher returns 1 with probability $1/2^{128}$, because the probability that any fixed 128-bit string $a$ is equal to $f(m)$ when $f$ is a uniform random function is $1/2^{128}$.  So we have
\begin{align*}
  \Pr[D(f_k) = 1] &= p = \operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F), \\
  \Pr[D(u) = 1] &= 1/2^{128},
\end{align*}
from which we find that $$\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) = \lvert\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) - 1/2^{128}\rvert.$$  But the security conjecture for HMAC-MD5 is that $\operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D)$ is very small for any distinguisher $D$.  We can use that to conjecture that the forgery probability must also be very small: $$\operatorname{Adv}^{\operatorname{MAC}}_{\operatorname{HMAC-MD5}}(F) \leq \operatorname{Adv}^{\operatorname{PRF}}_{\operatorname{HMAC-MD5}}(D) + 1/2^{128}.$$

So, what does it cost to find HMAC-MD5 collisions?
Without knowledge of the key, an adversary can find a collision in about $2^{64}$ trials by the birthday paradox.  With knowledge of the key, it's a parlor trick, but if you tell the adversary your key, you're violating the security contract of HMAC-MD5.  I recommend avoiding HMAC-MD5 for any applications with anywhere near $2^{64}$ messages under a single key!  I also recommend not telling the adversary your key.

* If $D$ tried 1000 keys, it would obviously have a higher chance of success than if it tried only 1, but there is a higher cost to trying 1000 keys, whether you try them on one computer sequentially or a thousand computers in parallel.  Note that multi-target attacks against $n$ targets at once may be cheaper than $n$ single-target attacks separately, but for a 256-bit key the difference doesn't matter for all imaginable numbers of targets $n$ in human existence.  But beware using HMAC-MD5 with 128-bit keys!

† Of course, exactly the same strategy will distinguish any iterated hash function from a uniform random function, but won't distinguish between two different iterated hash functions!  It could just as well be HMAC-HAVAL128 or anything else with a 128-bit state.  That's not the concern of the pseudorandom function family's security claim, which is only about distinguishing the family in question (HMAC-MD5) from a uniform random function of the same domain and codomain.

‡ It may sound like there is a high cost $c$ to storing all the outputs of the oracle to search among them for a collision, but actually the collision search can be done with negligible additional computation and storage using Pollard's $\rho$, and, if the oracle allows, can be parallelized to run faster (at the same total cost) with the van Oorschot–Wiener algorithm.


My encryption message system & question about security

Based on the details given in the question and the comments, it appears your protocol does nothing to protect the key exchange. The client sends a hash to the server, the server uses that hash to generate a key which it then sends back to the client. Client and server then use that key for future encryption.

Thus, anyone snooping on the key exchange will see the key and can then use it to decrypt and modify future messages. This is a major vulnerability.


The proper definition of avalanche effect is defined in the paper of Webster, A. F. "On the design of S-boxes". Advances in Cryptology - Crypto '85 as :

  For a given transformation to exhibit the avalanche effect, an average of one half of the output bits should change whenever a single input bit is complemented.

It is also seen as each bit should have 50% chances to change if you change 1 bit of the input.

This basically mean that in order to test an avalanche effect, you have to apply an algorithm similar to the following.

# result array
array res[n] = {0, ..., 0}

# compute all inputs
for each inputs x of size n
   ref_val = H ( x )

   # compute all possible 1 bit change
   for i in 0..n-1
      test_val = H ( X ^ (1 << i) )

      # compute statistics per bit
      for j in 0 .. n-1
         res[j] += ((test_val ^ ref_val) >> j) & 1

# in the end forall k, res[k] / (n * 2**n) should be around 50%.

Due to the size of the inputs, you can test with a relative precision whether or not $\operatorname{SHA256}$ does have a strict avalanche effect. But by doing a sampling over a large number of inputs where you flip each bit once, you can have a measure.But in most cases we usually analyze the components of the primitive in order to assert whether or not the avalanche effect is respected.


Well, consider if Bob is communicating with Alice; Bob sends Alice a random $r^e$, Alice recovers $r$ and sends it back.  Then, they proceed to use the same RSA modulus to negotiate a secret key; for example, Bob picks a secret value $m$, computes $m^e$, sends that to Alice, who recovers $m$, and then they both use $m$ to generate secret keys, and use those keys to exchange messages that they want to keep secret.

Here's what can happen; the NSA can then start communicating with Alice; they can send Alice the value $m^e$, Alice (thinking that this is someone else she is supposed to be talking to) recovers $m$, and sends it back.  The NSA now has enough information to recover the secret keys that Alice and Bob used to communicate.

And, if you're thinking "well, can't Alice remember the values that she used to communicate with Bob, and refuse to decrypt that", it turns out that's not sufficient.  What the NSA can do is pick a random value $k$, compute $k^e$, and send the value $k^e \cdot m^e = (km)^e$.  Alice will recover the value $km$, which will look like a random selection, and send that back; the NSA can then compute $km \cdot k^{-1} = m$, and is then able to decrypt the secret traffic.


is there any hash collision attack that is not defeated by adding a salt first?

Suffix salt
If you add the salt after the message, $\operatorname{MD5}(m \mathbin\| salt)$, that doesn't prevent Alice from finding two collisions. Example;
Consider that if the message $m$ of Alice is an exact multiple of the block size of the $\operatorname{MD5}(m \mathbin\| salt)$ then your signature will be vulnerable to hash chosen-prefix collisions. Because Alice can prepare two messages $m_1$ and $m_2$ so that $$\operatorname{MD5}(p_1\mathbin\| m_1) = \operatorname{MD5}(p_2\mathbin\| m_2)$$
Once Alice found the pairs such that
$$strlen(p_1\mathbin\| m_1)=strlen(p_2\mathbin\| m_2) = t \cdot 512$$
then adding your salt, even not known to Alice before, will not prevent Alice to forge. This is due to the Merkle-Damgård construction;

Both messages have the same internal compression values before the length added padding. Adding anything after those will not affect their collision.

If you add the salt after the message $\operatorname{MD5}(m \mathbin\| salt)$, that doesn't prevent Alice from finding two collisions. Example;

Prefix salt
If you add the salt before the message, $\operatorname{MD5}(salt \mathbin)$, this will prevent  Alice from finding two collisions.
We may see this in this way; the salt, especially it is one block, will be like an IV to MD5 since the first call of the compression function will calculate
$$ h_1 = C(salt,IV),$$ then $h_1$  will be a new IV for the rest of the compressions. This can be considered that you are using a family of MD5 hashes with different IV's. Since the IV is no control of Alice this is secure. Actually, this is similar to what HMAC does;
$$  \operatorname{HMAC}(K, m) = \operatorname{H}\Bigl(\bigl(K' \oplus opad\bigr) \parallel
\operatorname{H} \bigl(\left(K' \oplus ipad\right) \parallel m\bigr)\Bigr) $$
Consider the inner hash and, you will have a similar structure to change the IV of the hash function.
Your construction is vulnerable to length extension attack, however, since the resulting hashes will be different after the extension, this will not cause a forgery.
And note that HMAC is proven to be not affected by the collisions of the hash function, even it can be safe for MD5, however, we don't advise, use at least HMAC-SHA256.


In this case it denotes arbitrary state passed from $A_0$ to $A_1$. This is a common idiom in interactive security game definitions.

Conceptually a security definition should involve a single adversary who plays some game. The adversary is modeled as arbitrary algorithm. If there is some query/interaction adversary can do repeatedly, we often model this as giving oracle access to some function.

But suppose the game has a significant event that should happen only once (in this case, asking for and receiving a challenge ciphertext). This is not so easily modeled by providing oracle. Instead, it is common to formalize the situation like the authors have done here. $A_0$ is the part of the adversary that runs up until requesting the challenge ciphertext (it terminates by giving the two chosen plaintexts). $A_1$ is the part of the adversary that runs after receiving the ciphertext. To follow our intuition that there is just a "single adversary" this whole time, we allow $A_0$ to pass arbitrary information (without loss of generality, its entire internal state) to $A_1$. That's what $st$ is here.


There is no way to recover $x$ in this scenario; there is not even a way to say "this value of $x$ is more likely than that value"

One demonstration is that if we attempt to test a particular value $x'$; we can compute the necessary values:

$$y_i = c_i x - k_i$$

However, if all the values $y_i$ are randomly distributed, and given that we have no further restriction of what the values $y_i$ might be, this distribution is no less probable than any other distribution; hence these relations give us no information about $x$.

Since those relations are the only thing we know about $x$, that means we have no criteria to say which values are more or less probable.

This holds true for any sets of values $c_i, k_i$, and specifically if we have $c_i = c_j$ or $k_i = k_j$.


SHA1 usage for passwords, alternatives and advantages?

If your password database will never be compromised, you can store plaintext passwords and nobody will be bothered. The only thing about plaintext passwords is that they can be accidentally remembered by admins who see them - a simple base64 will fix that. Equivalently, MD5 or SHA1, with salt or without, is just as fine.

If your password database is possibly compromised at some point in the future, a single SHA-1 with salt still means that 99% of the user passwords are crackable on a laptop - basically no protection at all, except inconvenience. So if this is the attack you are worried about, you need to switch to something which has a sequential iteration count that isn't trivially small. PBKDF2, bcrypt and scrypt are all good choices for this.

(Note: assuming your password database will never be compromised is a really bad idea, if it wasn't already obvious from the answer.)


I'm not sure I completely understand the point of your question. First of all, the property Additive implies the property MultiByScalar. Indeed, to multiply a ciphertext $E(a)$ by a scalar $b$, you can simply use a square and multiply algorithm, adding a ciphertext to itself to multiply its plaintext by two, which allows to multiply in polynomial time $E(a)$ by $2^k$, for all the positions $k$ corresponding to a $1$ in the bit decomposition of $b$, then summing all those ciphertexts to get $E(ab)$.

Note that the additive variant of the ElGamal ciphertext does also satisfy this property, but unlike Paillier or LWE/RLWE, the decryption is not efficient.

Ciphertexts with the additive property have automatically this multiplicative property; they are sometimes called partially homomorphic. Somewhat homomorphic encryption schemes refer to schemes in which you can both add and multiply encrypted value (and not just an encrypted value and a scalar), but you can do so a limited number of times (say, lots of additions and a few multiplications).

So, every additively homomorphic encryption scheme (Okamoto-Uchiyama, Goldwasser-Micali, Benaloh, ElGamal, LWE/RLWE...) satisfies your two properties (and only these two properties, regarding homomorphism: only some very specific lattice-based encryption scheme are both additively and multiplicatively homomorphic).


Patterns aren't hidden. Assume you've got a pair of plaintext blocks $p_1, p_2$ then the encryption of $p_2$ will always be the same: $c_2=E_k(p_1 \oplus p_2)$ as it only depends on the plaintext. So you haven't basically solved the basic problem of ECB (patterns remain) but rather moved it (to the more rare case) that two blocks repeat.
Plaintext isn't random. In most cases an attacker can predict plaintext. As you basically use plaintext as IV for each block you make the scheme vulnerable to attacks like BEAST, where attackers use predictable IVs to gain information about target connections. See this related question.

Corrected my speed concerns. Encryption and decryption can be parallelized, speed should be comparable with CTR.


Probability that n is prime such that n fails the Miller-Rabin test N times

Just one step more, your last expression is

$$\frac{4^N}{4^N +\ln(n)-1}=1-\frac{\ln n -1}{4^N+\ln n -1}\geq 1-\frac{\ln n -1}{4^N}\geq 1-\frac{\ln n}{4^N}.$$


No, TLS is not secure against VM reset attacks. There are at least two attacks that are made possible by VM reset attacks, off the top of my head:

AES-GCM nonces are typically generated deterministically from the message counter value. If you set the snap shot prior to the local peer sending a plain text message that will change after resetting to the snap shot, you will have a severe nonce reuse vulnerability. As specified in RFC 5288, the 64 bit explicit nonce that is sent per packet MAY equal the message counter. The current TLS 1.3 draft removes the explicit nonce and replaces it with the implicit message counter xor:ed with the static IV values that were derived from the master secret. The same nonce generation is specified in the chacha20-poly1305 draft, which consequently has the same vulnerability. The traditional CBC cipher suites would be less vulnerable, in particular if used in encrypt-then-mac mode. Edit: In practice, the VM engine might be implemented to automatically close all TCP connections when suspended, and not necessarily reconnect when resumed after a reset. This might help to make the attack less practical against normal TLS connections directly over TCP. TLS over other types of channels and DTLS over UDP might be a different story.
Session master secrets are supposed to be discarded after any fatal alert corresponding to the session, such as failures to verify the finished messages. An attacker that is able to reset the local peer would obviously be able to circumvent this. This means e.g. that an attacker might attempt to perform session resumptions using the session id belonging to another peer, even after an initial failure. Such attacks against the session state do not depend on in which state the VM engine leaves the network stack when resetting to a snapshot.


With TLS and ECDHE, how does curve selection work?

As described in section 5.1 of RFC 4492, the client announces what curves it supports in an extension message, included in the ClientHello message. This gives the server the possibility to check whether client and server both support at least one specific curve, before choosing whether elliptic curves will be used at all.

Then the server chooses the curve. The curves named in the Supported Elliptic Curves extension are ordered by client preferences, so a courteous server may elect to follow the client's preferences, i.e. the first one in the client's list that the server also supports (where "supports" means "has the code for it, and deems it acceptable"). But, really, the server chooses.


Why can't we give block ciphers larger keys?

I saw many people complainig about AES , twofish and serpent that these ciphers all could be crackable in the near future and even today with big datacenters .

This is a good example of why we should always ask for citations and explanations, rather then just accepting what people say at face value with no scrutiny. These claims are about as far from reality as possible.

  But all these ciphers use max. 256 bit keys . And because there is no better way of finding the key then bruteforce the ciphers are equally strong .

These 3 ciphers all have similar if not identical parameter configurations because they were all designed for the AES competition. It is true enough for practical purposes (but not exactly so) that all three are equally strong and that the only way you'll break them without side channel attacks is via brute force.

Which is to say that you won't break them, at all.

  Would it be possibel to take these algos e.g AES and just change the key size from 256 to 512 or 1024 ?

It is not possible to just increase the key size for an algorithm like AES; There are other aspects that are derived from the size of the key that you would have to take into account and modify as well. For instance, the AES key schedule (which is part of the AES block cipher) of AES-128 and AES-256 differs.

  I mean the algo is well tested , you would just have to modify the key and blocksize .

Ok, let's concede and say we construct such a thing, and also assume we don't somehow introduce additional points of failure while doing so: What problem have we solved by increasing the key/blocksize? It was already impossible to search. Perhaps this is a good question to ask those people that were complaining about how easy it is to break AES, twofish, and serpent...

Why can't we give block ciphers bigger keys

We can, we do not need to. You can always construct make an algorithm use more space and time. The goal is to use the least amount of resources possible to get the job done. Once you understand this, it will be clear why we do not use massive keys or hundreds of cipher rounds.


Does displaying HMAC hashes of user inputs compromise the HMAC validation?

Does allowing users to test VALUEs increase the likelihood that SECRET will be broken or illegal hashed values generated, relative to the CONTROL scenario?

By definition a cryptographic Message Authentication Code such as HMAC is secure only if resists existential forgery under chosen-plaintext attacks. i.e. if allowing users to test VALUEs increases the likelihood of discovering the SECRET or generating illegal hashes, then HMAC would not be a secure MAC (and the current state of our knowledge is that it is strong when used with a half decent hash function).

In your particular usage though, unless the HASH value is tied to a particular cart/session it might be possible to replay HASH values obtained from previous interactions.

  By how much?
  How is this calculated or proved?

The 2006 security proof for HMAC by Mihir Bellare provides a proof and tightness bounds on that proof, but for your purposes you could probably treat the difference as negligible.


A dishonest verifier does not need to sample the challenge randomly. What if he just computes it as the evaluation of a one-way function on let's say a string "Alice authenticated, it's true". Later it can publish the string and the description of the function. What does this say about the deniability of the transcript of the protocol? Guess that should be sufficient to figure out the details on your own.


Rijndael S-boxes: Where do the $\mu$ and $\nu$ polynomial ring elements come from?

Finally I've went to the source and I've mailed the Rijndael's authors. They have answered very fast and very nice.

I've understood the other way around. The affine transformation is over the vector space $((GF(2))^8$ and what they've say as simplicity was that, between all the possible affine transformations they select one that can also be described as product and addition in the ring defined by modulo $z^8+1$.

There is no mathematical argument to select as $\mu(z)$ any of the invertible elements above the others. And for the $\nu(z)$ selection something similar happens but here exist the restriction to avoid any fixed or opposite fixed points.

Then the only argument to choose one or another can be the calculation time, but once the S-Boxes are pre-calculated it doesn't provides any extra advantage.


It's easier to take the questions out of order.

  what can be said about the distribution of exponents a+b mod p when b is taken at random from Zp, but a is fixed?

If $b$ is a uniform independent random value from the range $[0, p-1]$, that is, the probability of each possible value is $1/p$, and $b$ is distributed independently from $a$, then $a+b \bmod p$ is a uniform independent (of $a$) random value from the range $[0, p-1]$; that is, the probability of $a+b \bmod p$ being any possible value from the range is also $1/p$, and information about the distribution of $a$ (such as having it be a fixed value) does not change this.

The easiest way to see this (for a fixed $a$) is to note that, for any target value $c = a+b \bmod p$, there is a unique value of $b = c-a \bmod p$ that must be selected for the value $a+b \bmod p$ to be that value.  The probability of $b = c-a \bmod p$ occurring is $1/p$ (because that value is in the range, and we assumed the probability of all values in that range be $1/p$), hence the probability that $c = a+b \bmod p$ is also $1/p$.

With this, your first question is easy:

  I would like to ask here why in question 2 old post, we cannot distinguish the two distributions, even with unlimited computational power?

Alice sees either $g^b$ or $g^{a+b}$; an adversary with unlimited computational power can solve the discrete log, however that gives him either $b$ or $a+b$ (for random $b$); both probability distributations are identical, and so he cannot distinguish them.


A question regarding relevance of vulnerability of MD5 when linking multiple records together

If MD5 is used to hash "something like patient name or SSN or some unique personal identifier" in order to "ensure that a multiple prescriptions of the same patient (as identified by the personal identifier) are linked to each other, without revealing the identifier itself", then that solution is technically imperfect, but not for reasons related to weaknesses of MD5 highlighted in the question (there are better arguments in the legal memo itself, and some of the documents that it references).

Fact is, the risk of collisions with MD5 used in this way is negligible as far as the cryptographic community knows, even facing an adversary that deliberately attempts to create collisions. That's because the known weaknesses in MD5 currently only allow to create collisions between two artificially crafted data sets, not among a legitimate and an artificial data set, must less between two legitimate data sets. Thus MD5 collisions are a non-issue in that application, because they won't happen; and more importantly, the real issue is elsewhere.

The real issue (and what the legal memo is mostly about) is to protect the anonymity of patients, and that's something MD5, or any hash, is not designed to do, and does not. Knowing the input of the hash ("Patient name or SSN or some unique personal identifier"), it is possible to compute the output and check it against the hash to determine if a case/file belongs to that patient. Change MD5 to any better hash function like SHA-512, and that problem remains.

One option could be to use a MAC of patient info, with the key held by a trusted authority (in some cases that could be a Smart Card). That makes it impossible for a party with no access to the trusted authority to check if a file matches a patient id, unless she knows a file pertaining to that patient; further, access to the trusted authority can be logged, which is a deterrent against misuse. That's imperfect, and comes with a cost, and new risks (e.g. that patient info could be intercepted in transit to the trusted authority, or in the logs), thus I am not even sure this is preferable. But if we do use a MAC, we should use HMAC-SHA-512 rather than HMAC-MD5 (even though there is no known attack against HMAC-MD5; rationale is the same as for the car engineer, who won't use tires known to explode at high speed, even on a low-speed car when they would be safe, and save a little cost and energy).

Private Information Retrieval aims at solving the kind of issues the medical research community has. It works, but is a significant departure from existing practice. For pharmacies, some (not me) might advocate an intelligent tag that answer yes or no when asked if it is for a given patient, and reset after a number of no.


Elliptic curve ed25519 vs ed448 - Differences

Edwards25519 is the twisted Edwards curve $$-x^2 + y^2 = 1 - (121665/121666) x^2 y^2$$ over the prime field $\mathbb F_p$ where $p = 2^{255} - 19$.  The coefficient $d = -121665/121666$ was chosen to so that this curve is birationally equivalent to the Montgomery curve $y^2 = x^3 + 486662 x^2 + x$, called Curve25519, whose coefficient 486662 was chosen to be the smallest integer in absolute value satisfying the security criteria[1].  The group of $\mathbb F_p$-rational points has composite order $8 p_1$ for a 253-bit prime $p_1$, and its twist has composite order $4 p_2$ for a 253-bit prime $p_2$.  Edwards25519 is designed to make the cost of a discrete log computation cost at least about $2^{128}$ bit operations to break the first of any number of targets.

Edwards448, also known as Ed448-Goldilocks, is the twisted Edwards curve $$-x^2 + y^2 = 1 - 39081 x^2 y^2$$ over the prime field $\mathbb F_p$ where $p = 2^{448} - 2^{224} - 1$.  The coefficient $d = -39081$ was chosen to be the smallest integer in absolute value satisfying the same security criteria as edwards25519, together with the additional constraint that the order of the group of $\mathbb F_p$-rational points have order below $p$, namely $4 p_1$ for a 446-bit prime $p_1$.  There is also a birationally equivalent Montgomery curve $y^2 = x^3 + 156326 x^2 + x$ derived from edwards448, called Curve448.  Edwards448 is designed to make the cost of a discrete log computation cost about $2^{224}$ bit operations to break the first of any number of targets.  Of course, since $2^{128}$ bit operations is already infeasible, edwards448 is really a hedge against modest cryptanalytic advances.

Ed25519 is specifically an instance of the EdDSA signature scheme[2][3] with edwards25519 as the curve, SHA-512 as the hash function, an optional context identifier for compatibility, etc.; likewise Ed448 is an instance of EdDSA with edwards448 as the curve, SHAKE256 as the hash function, an obligatory domain identifier, etc.  See RFC 8032 for the details of EdDSA instantiation, and RFC 7748 for the curve definitions.

The only major substantive differences are in security level and performance:

Security level: Edwards25519 aims for a ‘128-bit security level’, and edwards448 aims for a ‘224-bit “Spinal Tap-grade” security level’—not actually a meaningful difference in the real world unless there is a modest cryptanalytic advance in computing elliptic curve discrete logs.
Key size: Edwards448 points and scalars are 1.75x the size of edwards25519 points and scalars.
Fixed-base scalar multiplication: Edwards448 costs about 1.5x what edwards25519 costs.
Variable-base scalar multiplication: Edwards448 costs about 5x what edwards25519 costs.

(See SUPERCOP dh and sign for details.)

Edwards25519 has $p \equiv 1 \pmod 4$ while edwards448 has $p \equiv 3 \pmod 4$, so there are some differences in protocols beyond DH and signing, but not really substantive: for encoding points indistinguishably from uniform random strings, edwards25519 supports only Elligator 2, while edwards448 supports Elligator 1 and Elligator 2[4], but I don't know of any advantages to Elligator 1; both support a prime-order group encoding that avoids pitfalls with cofactors[5], with a couple of different software implementations, Ristretto  and libdecaf.  Both curves are designed for traditional discrete log applications and pass the SafeCurves criteria; neither curve is pairing-friendly.

In brief, the two curves were designed with essentially the same qualitative security criteria and differ only on quantitative security level and performance.


Steganography in speech by adding extra "filler" syllables

To the extent that I think this is a cryptographic question (which I don't!), I don't think these language games qualify as steganography.  Steganography conceals the existence of a message by encoding it into (hopefully) undetectable modulations of another message, which is meant to appear innocuous to an adversary.  As Wikipedia puts it:

  The advantage of steganography over cryptography alone is that the intended secret message does not attract attention to itself as an object of scrutiny. Plainly visible encrypted messages—no matter how unbreakable—arouse interest, and may in themselves be incriminating in countries where encryption is illegal. Thus, whereas cryptography is the practice of protecting the contents of a message alone, steganography is concerned with concealing the fact that a secret message is being sent, as well as concealing the contents of the message.

But languages games like Pig Latin or jeringonza don't generally fool adversaries into thinking that the message is innocuous.  Some of these games produce output that is linguistically very marked.  For example, Hola amigo is pronounced ['o la 'mi ɣo] (International Phonetic Alphabet; stressed syllables are prefixed with apostrophe as is standard), with broadly trochaic stress (LOUD-soft-LOUD-soft) as is typical of Spanish (default penultimate stress).  But Chi-ho chi-la chi-a chi-mi chi-go, as in the Caribbean variant of the jeringonza game, is strictly iambic (soft-LOUD-soft-LOUD): [tʃi 'o tʃi 'la tʃi 'a tʃi 'mi tʃi 'ɣo].  So this particular language game produces outputs that are systematically different from regular Spanish phonology.  Nobody's gonna mistake this for small talk about the weather.

And while I stress that I don't think these language games are properly cryptographic, if anything they often resemble ciphers more closely than steganography.  One capsule explanation of modern cryptography is that it achieves security by transforming messages using trapdoor functions—schemes where messages are transformed in ways that are cost-effective to honest parties but prohibitively expensive for adversaries.  And if you squint really hard these language games approximate that paradigm—they transform a message in a way that the ingroup has mastered through practice (dare I call this "precomputation"?) but the outgroup hasn't.


The relationship between the key length and encrypt time in Xor algorithm?

For simple XOR-based encryption algorithms such as OTP, the key size must be the same as the message size. If you choose a smaller key and try to divide the message into chunks, you would not have a perfectly secure scheme anymore.

Now, since you tagged java, I'm assuming that this increase in time for smaller key sizes is due to the code trying to divide the message into chunks. In that case, this doesn't have much to do with the algorithm, but rather with how you are writing your code.


in reduction you have two problems A and B, A$\leq$B means that if you can solve problem B then you can solve problem A , now in most reductions ,the level of efficiently for the solver for A that you construct is the same as B unless you add more steps. so this means you cant know if its the most efficient , it may be and it may not.


Can deterministic ECDSA be protected against fault attacks?

As already said by fgrieu in his answer, this is possible.

There are multiple ways to protect deterministic ECDSA against fault attacks, but these ways will depend on your fault model.

If you consider only a single fault model, then any construct requiring the attacker to perform two faults to achieve his goal will be an acceptable countermeasure... On the other side if you consider the attacker is ubiquitous and can perform faults of her choosing at any point in time at any location of the chip, then you most likely won't find any way to counter her. It is a common assumption, backed by practical experiment that performing two localized faults on the same computation is hard, even more so if the value of the fault is important.

So, how could you deal with single faults in deterministic ECDSA?

Well you could do as fgrieu says and do the verification process, but then a second fault in the very last step could simply trigger the verification to output "true" instead of "false", yet you would be in another fault model, where the attacker can do two faults... Now, there are other ways which would render the second fault even harder for the attacker:

The first way is described by Thomas Pornin himself in RFC6979 section 3.6 (emphasis mine):

  Additional data may be added to the input of HMAC, concatenated
  after bits2octets(H(m)):

     K = HMAC_K(V || 0x00 || int2octets(x) || bits2octets(h1) || k')

  A use case may be a protocol that requires a non-deterministic signature algorithm on a system that does not have access to a high-quality random source.  It suffices that the additional data k' is non-repeating (e.g., a signature counter or a monotonic clock) to ensure "random-looking" signatures are indistinguishable, in a cryptographic way, from plain (EC)DSA signatures.
  In [SP800-90A] terminology, k' is the "additional input" that can be set as a parameter when generating pseudorandom
  bits.  This variant can be thought of as a "strengthening" of the
  randomness of the source of the additional data k'.

This is the way chosen by XEdDSA, used in Signal, to prevent faults to have an impact on its security. It allows for both the additional security of deterministic ECDSA against biased random sources, still appears perfectly compliant with ECDSA, and will be effective against fault attacks as described in the XEdDSA document. But then you don't get the determinism of the signatures anymore, sadly.

A second way to achieve this same goal might be to sign twice the same data and compare the output of both, if they match to proceed, otherwise there was a fault or multiple unsynchronized faults in the computations. This has the benefit, especially for EdDSA, to not bear the cost of a complete verification, since verification is a way more costly operation there (it also more costly for ECDSA). But still renders the process twice as slow.

A third possibility would be to use so-called "infective" countermeasures as introduced for RSA so that a fault in any part of the final computation would randomize the faulted output. Here is a recent paper (published for FDTC 2017) featuring such a countermeasure for EdDSA. Such a countermeasure would typically combine two different implementations of the same hash in a way that allows recovering the correct value if both output the same data, but would otherwise give nothing of interest. But it is very "local": it might not protect against faults occurring at other steps of the signature process.

I personally like adding back randomness into deterministic ECDSA, which I find both elegant since it's indistinguishable from standard ECDSA and efficient since it bears almost no cost in practice, unlike many other ways.

PS: by the way, Barenghi and Pelosi say that EdDSA shows a structural resistance against these kinds of attacks, but this is actually not the case since it's still possible to obtain sufficiently secret material to mimic valid signatures in a way that only the secret key's owner can detect.


Securely derive AES and ED25519 keys from a ED25519 seed

You should pick a key-based key derivation function, such as HKDF-SHA256.  Then:

Generate a master key $k$ uniformly at random.
Derive an Ed25519 seed $k_0$ from it by $$k_0 = \operatorname{HKDF-Expand}_k(\text{info=‘Ed25519 signing key’},\, \text{size=32 bytes}).$$
Derive an AES key $k_1$ from it by $$k_1 = \operatorname{HKDF-Expand}_k(\text{info=‘AES encryption key’},\, \text{size=32 bytes}).$$
Derive any other keys you want for any other purposes—perhaps even other Ed25519 or AES keys, just for different purposes—using HKDF-Extract with the same master key and a distinct info parameter for each distinct purpose.

You can organize the tree as you see fit to distribute subtrees with partial authority, like the authority to sign (give out $k_0$ but not $k$ or $k_1$) or the authority to encrypt/decrypt (give out $k_1$ but not $k$ or $k_0$).

Any other reasonable keyed XOF, such as KMAC128 from SHA-3 or keyed BLAKE2x, will serve too.  Functions with fixed-length outputs like HMAC-SHA256 or keyed BLAKE2s are a little finickier in case you need, e.g., a 64-byte key for some reason instead of just a 32-byte key; HKDF is a generic way to turn these into a variable-length output.  HKDF also includes an optional initial step, HKDF-Extract, to turn a nonuniform but high-entropy seed—such as a computer-generated BIP39 passphrase—into an effectively uniform random master key.

There is no need for a password-based key derivation function (or just ‘password hash’) such as PBKDF2 because the input—your 32-byte master key—is already a uniform random bit string.  All that you really need is derived subkeys—$k_0$, $k_1$, etc.—that are apparently independent.


Can Elgamal be made additively homomorphic and how could it be used for E-voting?

Elgamal can be made additive by encrypting $g^m$ instead of $m$ with traditional Elgamal for some generator $g$ (usually the same one used to generate the public key). This variant is sometimes called exponential Elgamal. The difficulty is decryption: running the standard decryption gives you $g^m$ and recovering $m$ requires you to solve the discrete log. As long as $m$ is small, this can be done algorithmically or with a lookup table.

See this answer for how to build a voting scheme from it (or this paper for the full description). Exponential Elgamal is great for things like voting because after you tally up all the votes, you'll still have a number that is reasonably small.

Paillier is additively homomorphic as well, and can support a proper decryption of any sized message. Dispite this, many voting schemes still use exponential Elgamal because it is faster, easier to do distributed key generation, and not patented.


Clarification questions about timestamp servers

In 1991, Stuart Haber and Scott Stornetta proposed a method for time stamping a digital document. In their method, when someone (Alice) wants to timestamp a document, she send the hash of her document to a Trusted Third Party (TTP). TTP (similar to figure 1) puts this hash in a Merkle tree and sends back to Alice a proof that her document is in the Merkle tree and then publishes this Merkle root [RH(i-1)] in a newspaper or Usenet post, just for time stamping, adding a specific time (publishing day) to RH(i-1).

Next day, TTP does a similar job with a difference: for calculating the Merkle root RH(i), he uses the previous day's Merkle root [RH(i-1)]. It is called linking and hash pointer and linked list made it possible. Hash pointer (figure 2) is a pointer to hash of some information that it will guarantee that the information hasn’t changed, because if someone wants to change a previous hash, he should change all next hashes and informations in the chain.

Bitcoin uses a hash pointer (figure 3) for creating the ledger of transactions (Tx), with a difference: for calculating hashes of the chain, it uses Hashcash. Hashcash added the proof of works to bitcoin. In hashcash, miners scanning for a value that when hashed, the hash begins with a specific number of zero bits. For finding this specific hash, miners changes Nonce parameter in the blocks of chain.

In bitcoin, with a peer to peer network, hashcash-based timestamp server and the ledger of transactions is distributed and all miners have a copy of it, so bitcoin doesn't need a Trusted Third Party (TTP).


Dual system encryption:New Techniques for Dual System Encryption and Fully Secure HIBE with Short Ciphertexts

It uses an artifact of pairings over groups of composite order.

Specifically, if the order of $G$ is $p_1$ and the order of $H$ is $p_3$ and $p_1, p_3$ are relatively prime, then $e(G, H) = 1$.

This can be easily seen by considering the order of $e(G, H)$; we know that $e(G, H)^{p_1} = e(G^{p_1}, H) = e(1, H) = 1$, hence the order of $e(G, H)$ must be a divisor of $p_1$.  Similar logic shows us that the order must also be a divisor of $p_3$.  Because $p_1, p_3$ are relatively prime, the only common divisor they have is 1; hence the order of $e(G, H)$ must be 1.

Section 2.2 of the paper gives a different derivation of the same result.

Once we have that, we can see that $e(K_1, C_1) = e(g^r R_3, (u^{id}h)^s) = e(g_r, (u^{id}h)^s) \cdot e(R_3, (u^{id}h)^s)$.  Since the order of $R_3$ (which $p_3$) and the order of $(u^{id}h)^s$ (which is $p_1$) are relatively prime, the second half is a constant factor 1, and so this reduces to $e(g_r, (u^{id}h)^s)$ (and thus $R_3$ disappears).  Similar logic gets rid of $R'_3$ as well...


Deciphering the RSA encrypted message from three different public keys

In the question, the same message is directly encrypted to three different public keys using textbook RSA. This has dire consequences, including the following (with 1./2./3. not using the multiple public keys, and the answer likely thought at 5. or its extension 6.):

It severely limits the size of the message (to less than 128 octets).
A guess of the message can be checked by anyone with a public key $(N_i,e)$ and the ciphertext $c_i$, which by a standard assumption in cryptography includes adversaries. They simply encipher a guess of $m$ with $(N_i,e)$ and check it against $c_i$. Poof goes confidentiality if the message is a name on the class roll, a guessable password..
If $m$ is less than say $2^{70}$ , there is a good chance that there exits $r<2^{30}$ and $s<2^{40}$ with $m=r\cdot s$. In that case, regardless of $e$, there's a meet-in-the-middle attack recovering $m$: the attacker computes $c_0/r^e\bmod N_0$ for all candidates $r$ and store that for quick search (10 GiB of RAM for hash tables and 128 GiB of seldom used disk will do); then for each candidate $s$ computes $s^e\bmod N_0$ and searches that; it there's a match, $m$ is found as $r\cdot s$ .
If $e$ is small, and/or the message $m$ is small enough (less than about $2^{1023/e}$ ), then $m=\sqrt[e]{c_i}$ (where $i$ is the index of the largest $N_i$ and it is used straight, not modular arithmetic). Even though the $c_i$ are distinct, this attack could still work in the case at hand, when $m$ is close enough to the limit $\sqrt[e]{\max(N_i)}$ . Further, that eth root attack can be easily extended to like $m<2^{1060/e}$, and much more when we consider the multiple encryptions, see 6.
If $e=3$, the system is plain vulnerable to the archetypal RSA broadcast attack (also the simplest form of Håstad's broadcast attack). $e=3$ is a common choice in textbook RSA, because that allows the fastest encryption, using modular squaring and one modular multiplication; and is as safe as can be when $m$ is essentially random in an interval like $[0,N_i)$ and chosen independently for each encryption (contrary to the situation at hand where the same $m$ was used thrice).

We should first check that the three $\gcd(N_i,N_j)=1$ for $0\le i<j<3$. Otherwise, the GCD is a non-trivial factor of $N_i$ and $N_j$, and we have factored $N_i$ and $N_j$ (at least in two-factors RSA), and can compute a working private exponent and decipher, per the normal way in textbook RSA. Succeeding in that way is not supposed to happens, but does here and there, due to Random Number Generators that are not true, and gave the same results on different platforms, when they should not; and in academic exercises.

Having thus checked (or blindly assumed) that we can invoke the Chinese Remainder Theorem, we use it to solve for $x$ the system of 3 equations $x\equiv c_i\pmod{N_i}$ for $0\le i<3$ with $x\in[0,\prod N_i)$. That goes:

$x\gets c_0$
$N\gets N_0$
For each $i$ with $1\le i<3$

$x\gets(((N^{-1}\bmod N_i)\cdot(c_i-x))\bmod N_i)\cdot N+x$
$N\gets N\cdot N_i$

At that point $N=\prod N_i$, and $x$ is the desired solution.

Then we computes $m=\sqrt[3]x$ (which will be an exact integer); this is a non-modular cube root, and thus easy. This will always work because $m<\min(N_i)$, thus $m^3<N$, thus $m^3=x$ since by the CRT, there's no other $m$ with $m^3\equiv c_i\pmod{N_i}$.
Attacks 4. and 5. combine and can work for some $e>3$. If $m<\sqrt[e]{\prod N_i}$ , then after computing $x$ just as above it comes $m=\sqrt[e]x$ (which will be an exact integer).

This can be extended to $m$ up to about $(3072+k)/e$-bit with with $O(2^k)$ work; with $e=5$ perhaps $m$ up to $\approx78$ bytes (out of the maximum capacity of $<128$ bytes). An idea is to scan integers $r$ with $0\le r<2^k$, until $\sqrt[e]{r\cdot N+x}$ is an exact integer.

Further, we can save significant computational work in this search by reusing an approximation of $\sqrt[e]{r\cdot N+x}$ in order to test if $\sqrt[e]{(r+1)\cdot N+x}$ is an integer, and computing an approximation of $\sqrt[e]{(r+1)\cdot N+x}$.

And perhaps that attack can get even better; see this answer wondering about extending the eth root attack by combining Coppersmith's theorem with lattice methods.

Conclusions:

Do not use textbook RSA without random encryption padding, unless enciphering a mostly random $m$ nearly as wide as the public modulus, and enciphering that $m$ only once.
Rather, use a sound random padding for each RSA encryption, and hybrid encryption for the whole thing.
Do not conclude that a large $e$ like $e=65537$ will always save the day; it does not. Apply the above!


Is $H(x) = x^2 \bmod p$ pre-image resistant, second pre-image resistant and/or collision resistant

It is neither pre-image resistant, second pre-image resistant nor collision resistant.

It is easy to compute square-roots modulo a prime (assuming, of course, a square root exists, it will half the time).  If $p = 3 \bmod 4$, then the simple formula $x^{(p+1)/4} \bmod p$ will work; for $p = 1 \bmod 4$, it's a tad more complicated but still sufficiently easy, for example, by the Tonelli-Shanks algorithm
It is easy to compute second pre-images, even if we consider images outside the range $0 \le x < p$ to be invalid, by taking advantage of $H(x) = H(p-x)$
The easy of computing second pre-images implies a lack of collision resistance.


Yes, two-key triple DES has a 112-bit keyspace.  That is to say, it has 2112 distinct possible keys, each of them made up of two arbitrarily chosen 56-bit single DES keys.*

Note that, for historical reasons, DES keys are typically represented as strings of 8 bytes, with each byte containing 7 key bits and one parity bit, for a total of 56 + 8 = 64 bits.  But since the parity bits cannot be freely chosen (they are calculated based on the key bits) and are not used for any cryptographic purpose, they are not counted as part of the effective key length.  As 3DES keys are made up of single DES keys, they inherit this historical peculiarity.  Thus, a two-key 3DES key would typically be stored as 16 bytes containing a total of 112 key bits and 16 parity bits.

It's also worth noting that the keyspace size is not necessarily the same as the security level of a cipher, even though both are commonly measured in bits — they are only the same if there is no known way to break the cipher faster than by exhaustive brute force enumeration of the key space.  Two-key 3DES does have known attacks that are faster than brute force, which is why, despite its 112 bit key length, its security level (as estimated by NIST) is only about 80 bits.  That is to say, breaking two-key 3DES encryption using the best known attacks is estimated to require about as much computing power as exhaustively testing an 80-bit keyspace by brute force would require.

And no, as Christoph Egger notes, two-key triple DES is not the same thing as double DES.  While both have the same keyspace size, double DES is vulnerable to even worse attacks than two-key triple DES, and its security level is not significantly higher than the approximately 56-bit security level of plain old single DES.

*) Sufficiently pedantic readers might quibble about whether all of those 2112 keys should really be considered valid.  Certainly one could argue that keys where both 56-bit halves happen to be identical, or where both halves happen to be weak, should be avoided.  But that really makes no difference either way, since such questionable keys only make up a vanishingly small fraction of the full keyspace.


Is it possible to unscramble a scrambled ed25519 SSH key?

Is it possible to unscramble a scrambled ed25519 ssh key?

I think you confuse the encryption with the scrambling. Scambling doesn't require a key and it may require a large amount of memory even for the owner to unscramble it if it is a true permutation. Yes, scrambling is a permutation.
Assume that there are $n$ elements that you want to scramble then there are $n!$ permutation if we consider they are all distinct. To store the permutation one needs $n! \times n \times x$ bits where $x$ is the number of bits to represents the elements. For generic cases the repeating is not necessary, so live with this huge number.
We can find the number of base64 characters for $m$ bits with the formula $\lceil(m / 3) \cdot 4 \rceil$. Place the length of the PEM file or just the private key 256 bits that is 32-byte then we have $\lceil 128/3 \rceil = 43$ base64 character for the private key. That will require $43! \times 43 \times 64$ bit to store. This makes approximately $2^{186.7}$ bits, impossible!
This is why we use block ciphers to encrypt and we call a block cipher a family of permutations. Those are expected to select a random permutation from all possible permutations with a key. Even the total number of the permutations of a 128-bit block cipher is tiny compared to all possible permutations $(2^{128})!$. We can see this with the help of Stirling's formula
$$2^{b}! \approx \sqrt{2\pi 2^{b}} \bigl(2^{b}/e\bigr)^{2^{b}}.$$
$$2^{128}! \approx \sqrt{2\pi 2^{128}} \bigl(2^{128}/e\bigr)^{2^{128}} \!=  \sqrt{2\pi 2^{128}} e^{-2^{128}} \bigl(2^{128}\bigr)^{2^{128}} \ggg 2^{128}$$
So, as long as you are not playing a game with a friend ( like CTFs), then secure scrambling has no practicality.

Then i take the private key file and randomly scramble the order of base64 encoded characters. Is it practically feasible to recover the original key from this scrambled file?

The source you linked is using a passphrase for the encryption of the contents of the PEM file - that is not scrambling -. This passphrase is hashed with SHA-1 (old version uses MD5) to derive a key and then the contents of the PEM file is encrypted with AES-128 in CBC mode with this key.
AES-CBC is CPA secure and to break it you need to search $2^{127}$ keys on average.
The common attack is not the key, the user's bad passwords. John the Ripper password cracker and the hashcat are ways to break it. There are currently  613M pwned passwords to easily test! They are already in SHA-1 format as ssh uses SHA-1 to derive the key.
The usual advice to mitigate this is using the diceware based passwords to have passwords with good strength. Or, see XKCD 936.


Is the 'nonce' in bitcoin really a nonce?

I will assume you mean the nonce that bitcoin miners iterate. Depending on e.g. wallet software other salts or nonces may be involved.

That nonce is only used once, because every miner1 will be hashing a different transaction block (hash) – one which sends the reward for solving the proof of work to their address. A miner could reuse a nonce but they would be recomputing something they have already done so it would be a waste of time.

Since the nonce is only 32 bits, miners will eventually reuse values, but that will be with a new timestamp, or even a new previous-block hash (when someone else solved a block).

1 Slightly more complex for mining pools, of course.


Sigma proofs for Pedersen commitments arithmetic under different bases

This is certainly possible using only standard Sigma-protocols and compose them together. But first, let's introduce the used standard Sigma-protocol building blocks:

Equality of committed values in two Pedersen commitments

Given Pedersen commitments $P=g_1^a h_1^{r_1} $ and $P'=g_2^{a'} h_2^{r_2} $, one can show in zero-knowledge using a Sigma-protocol that $a=a'$. Note, that all generators could potentially be different in the statement.

Equality of opening of two Pedersen commitments

Given Pedersen commitments $P=g_1^a h_1^{b} $ and $P'=g_2^{a'} h_2^{b'} $, one can show in zero-knowledge using a Sigma-protocol that $a=a'\land b=b'$. Note, that all generators could potentially be different in the statement.

Proving the conjunction of different statements using Sigma-protocols

Given several statements $\{\mathit{stmt_i}\}^{n}_{i=1}$, it is possible to prove their conjunction, i.e. $\wedge^{n}_{i=1} \mathit{stmt_i}$. In this case, for every statement the verifier samples the very same challenge value.
For a more thorough treatment on these building blocks, please refer to this post.
Now, it should be straightforward to devise a Sigma-protocol for your statement. Let's use the notation introduced in the question. First, prover computes $P'=g_3^a h_3^{r_1}$ and shows the equivalence of openings of $P'$ with $P$. It does the same for $Q'=g_3^b h_3^{r_2}$ and $Q$. Finally, prover can show the equality of committed values for the point $P'*Q'=g_3^{a+b} h_3^{r_1+r_2}$ and $R=g_3^{a+b} h_3^{r_3}$. The conjunction of these statements can also be easily proven by sampling the same challenge value for all the constituting Sigma-protocols.


ABE (attribute based encryption) vs ABS (attribute based signature)

Attribute-Based Encryption (ABE) schemes are a way to securely send (i.e share) a plaintext (message) amongst some particular receivers. The data owner (sender) consider an access policy to encrypt the message under this policy that a data user (receiver) is able to decrypt the ciphertext if and only if he/she satisfies the policy. So the ABE schemes just provide the confidentiality for a sensitive data because all certified users are able to calculate the ciphertext corresponding a particular policy (the data owner secret key is not an input for encryption algorithm).

In this point, the Attribute Based signature (ABS) schemes should be considered to achieve authenticity. In these schemes, the data owner who has a bunch of secret keys corresponding to his/her attributes wants to convince the other users about this claim (I am a person with some specific features, for instance, I am "Tall", "Male" and so on). The receiver authenticates this claim if and only if the signature which is produced by the sender based on her/his secret keys satisfy the published access policy with the plain message. In the other word, if the verification algorithm runs correctly then the conditions will be passed.

Overall, in the former schemes, the secret key condition is on the receiver side while the latter focus on the sender side to ensure the secret key corresponding the claimed attributes.

Also, the Attribute-Based Singcryption (ABSC) schemes follow the same target and satisfy not only the authentication but also the confidentiality properties. Precisely, ABSC schemes are the merge of ABE and ABS while are more efficient than executing both ABE and ABS, separately. [https://eprint.iacr.org/2018/263.pdf]


Padding to increase entropy and size of (otherwise) small JSON objects

Encryption cannot be brute-forced: verifying a guess is as hard as decrypting. You can encrypt a 1-byte string — even a 1-bit string — and any sane encryption scheme guarantees that an adversary cannot tell which value is encrypted.

You do need to take care that the encryption algorithm is non-deterministic, in that if you encrypt the same plaintext twice, you get different ciphertexts. Otherwise an adversary could tell when you've sent the same message twice. All recommended encryption modes (i.e. anything found in typical libraries other than ECB) provide this guarantee, provided you use them correctly (e.g. using a random IV, which is necessary anyway with some modes).

An adversary can tell the length of the plaintext, or more precisely, can tell in which 16-byte interval it lies (16 bytes being the block size of AES (regardless of key size)). For example, {"order_id": 7} might encrypt to 32 bytes while {"order_id": 17} would encrypt to 48 bytes. You may want to pad all your objects to a constant size to avoid this, or at least arrange for variable-size values to be padded. The padding doesn't need to be random, you just need to manage the length. Given that you're encrypting JSON representations, adding space characters at the end should be fine.

Note that encryption only guarantees that the encrypted message remains secret. It doesn't guarantee that the message hasn't been modified in transit. For that, you need authentication. JWT offers A128CBC-HS256 (AES-128-CBC + HMAC-SHA-256) which combines encryption for confidentiality and a MAC for authenticity; if available on your implementation (it's only recommended in the standard), use the authenticated encryption mode A128GCM (AES-128-GCM).


FIPS 140-2, Level 1 validation vs. compilation

I wouldn't give much hope in finding a native Javascript crypto implementation that's FIPS certified.  The reason is zeroization; FIPS is particular about knowing when CSPs [1] are zeroized; Javascript does garbage collection, which means that you're never quite sure when things are zeroized.
And, if by cross-compiling, you mean taking a certified implementation, and automatically converting it into Javascript, well, you won't solve the problem.
Sorry, but I wish I had better news for you.

[1]: Critical Security Parameters; essentially FIPS terminology for keys


Can the proof of elasped time (PoET) consensus algorithm be exploited by multiple nodes?

Yes, here's an article stating that "SgxSpectre Attack Can Extract Data from Intel SGX Enclaves".

  According to researchers, SgxSpectre works because of specific code
  patterns in software libraries that allow developers to add SGX
  support to their apps. Vulnerable SGX development kits include the
  Intel SGX SDK, Rust-SGX, and Graphene-SGX.

  Academics say an attacker can leverage the repetitive code execution
  patterns that these SDKs introduce in SGX enclaves and watch for small
  variations of cache size. This is a classic "side-channel attack," and
  is quite effective.

However, Intel stated that an update for the Intel SGX SDK that adds SgxSpectre mitigations will be released on March 16, 2018.

Also, Here's a research paper that does some theoretical analysis on compromising a blockchain network using SgX and finally states that "Yes, it might be possible".

The title of this paper is "On Security Analysis of Proof-of-Elapsed-Time (PoET)". I'm adding relevant snips of the paper to ensure that in case dead links occur, at least the summary of what they say is available in this post.

The brief of this paper states that

  "To fulfil this gap, we develop a theoretical framework for evaluating
  a PoET based blockchain system, and show that the current design is
  vulnerable in the sense that an adversary can  jeopardize the
  blockchain system by only compromising Θ(log log n/ log n) fraction of
  the participating nodes, which is very small when n is relatively
  large.

  Based on our theoretical analysis, we also propose methods to mitigate
  these vulnerabilities"

They go on to summarise that there are ways to mitigate these problems.

  Changing the probability distribution of F. If the probability distribution F does not rely on n, then adversaries have to compromise
  a a+µ fraction of the nodes in order to compromise the system.

  Allowing blocks generated by honest mining nodes to be rejected. We assume that the statistical test will not reject a block that is
  generated by an honest node, whereas the adversaries can simulate the
  fastest honest node in the system. It is possible to get beyond the
  threshold of Θ(log log n log n) if we allow the statistical test to
  reject blocks generated by honest users.

However, it is important to note that this paper does not mention a concrete method to compromise the safety of the PoET algorithm running in an SGX enclave and merely states that

  "SGX and other trusted computing technologies are not 100% reliable.
  Especially, they may be vulnerable to sophisticated adversaries with
  necessary resources and skillsets."

But given the SGXSpectre attack, it is not an academic question but a practical one ....

UPDATE: Here's an excellent video titled "34C3 - Microarchitectural Attacks on Trusted Execution Environments" where Keegan Ryan
explains in great detail about how TEE attacks are performed. This is absolute gold for a person interested in defending against security breaches.

TLDR: Yes, it is indeed possible to compromise the PoET algorithm (SGXSpectre attack) as also by compromising a small fraction of the participant nodes. There are also some ways to mitigate if not resolve this issue (SGX SDK Patch, other approaches).


Using password-based encryption as a hashing scheme

Essentially, instead of checking against a (salted) hash of a password, you suggest using the hash (since you can choose hashing = keygen) as a key to encrypt a kind of test value. The main question is whether this adds or reduces security.

If you store the hash/key directly, the chance of a randomly chosen password hashing to the same value is $2^{-n}$, where $n$ is the length of the hash in bits.
If you use the key to encrypt a string from the dictionary in your example (10 out of 256), the chance that a random key (from a password guess) decrypts the stored value to a valid $k$-bit string is $(10/256)^{k/8} = 25.6^{-k/8} \approx 1.5^{-k}$.

To have equivalent security you need to store a longer verification string. For example, to match the security of a 256-bit hash value, you'd need to encrypt a 439-bit value.

In addition, the whole process would allow an attacker to discard wrong guesses slightly faster than the verification process takes, since most encryption algorithms encrypt in blocks and if the first block is a mismatch, the whole thing must be.

That's without considering the inherent insecurity in using a complex scheme that relies on multiple primitives for its security.

You could get back to an equal length-to-security ratio by encrypting a known string (like a string of zeros) instead. The downside of complexity would remain, without a clear upside to compensate. It could be more resistant to a weak hash, but that might be difficult to prove.


How to solve the reverse of an equation that uses MOD?

If $a$ is a prime number and you know $r$ and $b$, and want to solve $v$ given the equation $r = v*b\mod a$, all you have to do is to apply the extended Euclidean algorithm for finding the multiplicative inverse $b^{-1}\mod a$, and then calculate $v = r*b^{-1}\mod a$. Alternatively, you could apply Fermat's little theorem and calculate $v = r*b^{a-2}\mod a$.


Dictionary attack on pass-phrases on common algorithms?

"Brute force" is a loosely-defined traditional expression to designate a kind of attack of low mathematical cleverness, namely trying all possible values for some unknown. For instance, in the context of symmetric encryption with AES, using a 128-bit key, "bruteforcing" would be trying all possible sequences of 128 bits as possible keys, until one matches (and there are so many such sequences that the average attack cost will be astronomical, hence totally impractical).

A dictionary is a set of "possible passwords", and a dictionary attack is about trying all possible passwords from a dictionary. Thus, a dictionary attack can be called "brute force". However, the expression "brute force" somehow suggests unsubtlety, and there can be quite some psychological finesse in the definition of a dictionary. As I said, "brute force" does not have a well-established mathematically meaning.

In "to force users to choose at least 3 words in the dictionary", the worst word is "force". Enforcing password rules on users tend to be counterproductive. Users should cooperate, and if you antagonize them, then they will actively seek countermeasures with great creativity. You really do not want the users to resent the password as a burden. Remember that almost none of your users will have a mathematically correct notion of password entropy; most will not care, and most of those who care will think about passwords in the same way as passwords are used in movies: witty allusions to some events or objects, supposed to defeat attackers through some "cleverness".

The second worst word in your proposal is "choose". To defeat a dictionary attack, the dictionary (as "the set of potential passwords") should be huge. The set of potential passwords is what users will effectively choose, not the length of the list you gave them. If you give them a list of 1000 words and tell them to "choose" one of them at random, many will pick a word in the first 10. Human beings are simply not good at doing things with uniform randomness. The password selection process should involve a physical device (e.g. dice, or a coin) and -- that's the important point -- the user MUST stick with the randomly selected words. If users are free to choose as they see fit, most will see fit to select words with a meaning (e.g. a sequence of words which "says something") because that's what they will remember best.


If someone has a large set of values:

$$B + \epsilon_0, B+\epsilon_1, B+\epsilon_2, …, B+\epsilon_n$$

One can average all these values together.  If the values of $\epsilon_0, \epsilon_1, \epsilon_2, …, \epsilon_n$ are independently distributed with a mean of 0, the average of these values will be closer to $B$ (essentially reducing the size of the error value by a factor of $\sqrt{n}$ on average).

So, if the attacker has access to a sufficiently large set of values, he can get an arbitrarily close idea of where the underlying $B$ is.

So, what Google is mandating is that you don't get the adversary access to such an independent set of $\epsilon$ values; if you always use the same error vector each time for a specific $B$ value, this averaging tells the adversary nothing he didn't already know.


Testing a steganalysis technique on realistic data

Are there such things as standard "test vectors" for steganalysis?

Not that I am aware of.

  How could I do this?

Your best bet would be to look for steganographic systems that are out there (either software or a paper describing it). Implement those systems and see how your steganalysis method works. Then you can implement other steganalysis methods from the literature and compare how well yours does vs those.


ECIES is DHIES restricted to an Elliptic Curve group, when DHIES is defined for any cyclic group, including but not limited to $\Bbb Z_p^*$.

Mihir Bellare writes on his web page on DHIES: An encryption scheme based on the Diffie-Hellman Problem that it

  describes a Diffie-Hellman based encryption scheme, DHIES, (formerly named DHES and DHAES)..
  The SEC1: Elliptic Curve Cryptography, v1.0 standard by SECG includes DHIES

and SEC 1: Elliptic Curve Cryptography Ver. 1.0 (dated September 20, 2000) mentions ECIES stating that "It was proposed" in that article, referenced under the old name DHAES. SEC 1 Ver. 2.0 references that article under the new name DHIES. Both versions of SEC1 are elliptic about the origin of the name ECIES.

Update: I read in Victor Shoup's A Proposal for an ISO Standard for Public Key Encryption (version 2.1 dated December 20, 2001) that there was ECIES as proposed in P1363a (as drafted July 21, 2001), and ECIES-KEM, with only the later secure against adaptive chosen ciphertext attack (thru some compatible restriction).

The P1363a rationale (as drafted July 16, 2003 shortly before adoption) clarifies:

  C.3.5 For the DL and EC families, why was the DL/ECIES encryption scheme selected?
  Several proposals on DL and EC encryption schemes were presented to the P1363 working group during the development of IEEE Std 1363-2000. None of the proposals was considered mature enough to include in IEEE Std 1363-2000 and it was expected that a suitable encryption scheme would be established during the P1363a effort. The DL/ECIES scheme has emerged as a common reference in several other standards efforts, including ANSI X9.63 [B12] and SEC-1 [SEC-1], with accompanying security analysis, and is thus considered appropriate for the amendment. DL/ECIES has two modes: non-DHAES mode, which is compatible with ANSI X9.63 and SEC-1 but does not have the full set of security properties of the DHAES scheme on which it is based (see Abdalla, Bellare, and Rogaway [ABR98]); and DHAES mode, which has the full set. (..)

In the end my reading is that draft DH(A)ES is history, DHIES never had issues, and ECIES is its restriction to an Elliptic Curve group.


Trying to implement ring-LWE KE to understand the concept

It seems to me that the problem lies in your setup of the vector/matrix multiplication.

What you have now: $a, s, s'$ are row vectors of ring elements.

$$ \text{Alice: } sB' = sa^ts'$$
$$ \text{Bob: } s'B = s'a^ts $$

Obviously, matrix multiplication is not commutative, but multiplying the underlying ring elements isn't either, because they're, well, ring elements.

So you need to shuffle and transpose some things.

Let $B = a^ts$, and $B' = s'^ta$.

Now let Alice calculate $B'^t s^t$, and Bob calculate $s'B^t$. If you work it out, this will give Alice and Bob consistent keys.

Proof: I modified your sage script, it returns true now.


The academic and regulatory complexity of triple encryption with two keys is nowhere near that of a cipher with twice the key size. There is a line of thought that 2-key 3DES has like 80-bit or even down to 56-bit security in practice depending on the number of available plaintext/ciphertext pairs, see Chris J. Mitchell: On the security of 2-key triple DES, in IEEE Transactions on Information Theory, 2016, and this quote of the superseded SP 800‑57 Part 1 Rev. 4

Determining the security strength of an algorithm can be nontrivial. (..) For 2TDEA, if exhaustion were the best attack, then the strength of 2TDEA would be 56 × 2 = 112 bits. This appears to be the case if the attacker has only a few matched plain and cipher pairs. However, the security strength of 2TDEA decreases as the number of matched plaintext/ciphertext pairs increases. If the attacker can obtain approximately $2^{40}$ such pairs and has sufficient memory and computational power, then 2TDEA can provide an estimated maximum security strength of about 80 bits; if the attacker has $2^{56}$ plaintext/ciphertext pairs, with significantly more memory and computational power, then the estimated maximum security strength would be about 56 bits.

See this for a partial rationale and more references.
My assessment is that even with DES, attacks against 2-key triple encryption require so much memory and memory accesses (a fair fraction all DRAM ever built and accesses thereof) that they are extremely impractical (see this for more). And that such attacks against AES are pure fiction, for the same reasons, plus the amount of plaintext/ciphertext pairs needed. But facing a regulatory requirement, my assessment won't stand.
The best known generic attack is still essentially Paul C. van Oorschot and Michael J. Wiener: A Known-Plaintext Attack on Two-Key Triple Encryption, in proceedings of Eurocrypt 1990. Translated to AES-128, it has expected cost over $2^{256-k}$ encryptions when there are $2^k$ blocks of known plaintext.
Triple AES-128 with two keys (in K1/K2/K1 order, perhaps preferably all encryption rather than EDE) is practically safe from meet-in-the-middle attack. In an embedded context, the risks are plain negligible compared to side channels attacks and other non-purely-cryptanalytic methods of key extraction. There remains to convince whoever holds the rubber stamp. Being able to put a reasonable limit on the number of plaintext blocks corresponding to the same key that an adversary could obtain may help (see last section).

Later references that extend to variants of basic triple encryption (with 3 or 2 keys) include Eli Biham's Cryptanalysis of Triple Modes of Operation, in Journal of Cryptology, 1999; and Helena Handschuh and Bart Preneel: On the Security of Double and 2-Key Triple Modes of Operation, in proceedings for FSE 1999.

I advise against double AES-128 (as in the question's current implementation), even with a very limited amount of ciphertext per session key. No reasoning concluding that this gives near 200-bit security can stand competent examination. There is a straightforward attack, requiring only 3 plaintext/ciphertext pairs, feasibly little memory and communication, showing this can't have more than about 130-bit security, by applying techniques in Paul C. van Oorschot and Michael J. Wiener, Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.

What would be the best suggestion for achieving this requirement («the wireless communication needs at least 200-bit encryption») with only AES-128 at hand?

A reasonable option could be:

Use as building block triple AES-128 encryption with two keys, with encryption of 128-bit $X$ under two 128-bit keys $K_1$, $K_2$ per $E_{(K_1,K_2)}(X)\underset{\text{def}}=E_{K_1}(E_{K_2}(E_{K_1}(X)))$
Demonstrate that any 256-bit key for that is used less than $2^{48}$ times, by the sheer time it would take to exceed that limit (if the overall system has no safeguard against multi-target attacks, it might be best to show that all the devices an attacker could use won't reach that $2^{48}$ limit).
Assert that this gives (with some headroom) $256-48>200$ bitof security against key recovery by known cryptanalytic attacks, citing Mitchell confirming earlier analysis by van Oorschot and Wiener, and the NIST advice (see above references). Be aware that an operative word is known, and there are many caveats, including the fact that the last AddRoundKey of an encryption step and the first AddRoundKey of the next reduce to a single one, denting any rationale considering AES-128 as a black box.

If use of the rubber stamp is decided by reason, there is good chance the focus will move to examination of if the key can leak otherwise, if IV can't get reused even facing deliberate attacks attempting to cause that, how the key is drawn and shared, and other real problems.


AugPake implementation Doubt K computation

This is not ordinary real-valued division.

The computation you are looking at is done in the field $\mathbb F_q$ instead of $\mathbb R$, that is $1/x$ actually is the modular multiplicative inverse of $x\bmod q$.


How exactly would someone attempt to analyse ciphertext produced by popular encryption products such as Truecrypt/PGP?

From the perspective of someone who is a non-cryptographer but runs penetration tests against, well, anything really, there is a very simplistic answer that is generally correct in the real world:

Assuming the implementation of the encryption algorithm is not flawed (I know, not always a good assumption, but the common open source tools get a lot of peer review so it is an assumption I use) and a strong algorithm is used with a strong passphrase or shared secret, the reality is that breaking such a system is usually successful through misconfiguration or lax procedures on the part of operators.

This may lead to finding a copy of a passphrase on paper, in shared memory, in a backup, through a keylogger or even used for something else with weak password protection. So a real world attacker will usually take the easy route and look for wetware failure.

A strong passphrase and strong algorithm, by their very nature, are used to make the average time for a brute force attack beyond any useful time (caveat - the tool could get it on the first try, which is why we use averages, but as @Thomas says - you could win the lottery this week. Odds are just very very low!)


The answer to your question can be found in the paper Why Textbook ElGamal and RSA Encryption Are Insecure by Boneh et al. It is an easy paper to read and worthwhile going through the details there.


SHA1 collision for first 32 bits for two different messages

To find a collision it would be best to perform a birthday attack (as I already commented below the question).

You could use abc123 as prefix and then append a counter (using any encoding), creating the message to hash. Then you'd calculate a hash over the message and take the first 4 bytes. You'd create a map using the 4 byte hash as key (e.g. encoded as hexadecimals) and the message.

Now you simply add these key / value pairs until you find a duplicate key. In that case you print out the current message and the message in the map, and - of course - the hash collision that you found.

Because of the birthday problem you'd expect to find a match in less than a second and minimal memory use.

Proof:

Found match: abc123_owlstead_1255 and abc123_owlstead_59131 -> 992156E0
That took approximately 430 milli seconds

Note that if you post this as an answer, the word "owlstead" should raise some questions and google will quickly find this answer. So I would not copy paste this answer if I were you.


AES ECB mode for both encryption and authentication

[1] - For a single block, AES ECB is a secure MAC.

[2] - AES ECB encryption for a single block suffers from one of the problems that AES ECB suffers from in general, namely that it is deterministic. The same message encrypted with the same key results in the same ciphertext. How big of an issue is that for your application? Only you can answer that at the moment because we don't have the details of the application.

[1] - https://crypto.stackexchange.com/a/18947/706
[2] - https://crypto.stackexchange.com/a/8053/706


In order to assert the diffusion of a block cipher you need to show that every bit of the output depends on every bits of the input. This can be done by hand when the block cipher is not too complex.

A simple case: AES

AES you can see that a difference in a word will be propagated into the full block after 2 rounds (look at the $\star$).

This proves the word diffusion, now you need to prove that the S-box is actually safe. In other word show that any bits in the input have an influence on any bits in the output of the S-box (testing for differentials cryptanalysis is one of the way to do it).

A more complex case: Twine

Twine uses a 16 branches  Feistel network with a round function. This round function uses multiple logical operations: $\lor, \land, \oplus$.

In order to show the bit dependency, we could take the code of the block cipher, and replace every of these 3 logical operators by $\lor$. We could also replace all the 4-bits S-box by a direct transposition to $15$ or $0x1111$ in binary.

Using a null input where only 1 bit is flipped (thus in the case of Twine, 64 test), and passing it through the modified, we verify that  all the output bits are set to 1.

Also note that the bitwise shift << >> and rotations <<< >>> are preserved.

This approaches guarantees that any bits in the output depends of every input bits.

However we modified the S-box, therefore it is left to prove is that these S-box also have a nice diffusion using differential cryptanalysis for example.

This approach is the same as the one presented in this analysis of MD5.


Find some hash function with deliberate collisions

If you just want to prescribe up front that a set of messages $m_1, m_2, \ldots, m_k$ will collide in an otherwise innocuous hash function, without regard for any cryptographic security properties…

…then the question is off-topic for crypto.SE, but you can just pick a hash function $H\colon \{0,1\}^* \to \{0,1\}^\ell$, pick your favorite hash value $h$ for the messages $\{m_i\}$, and define $$H'(m) = \begin{cases} h, & \text{if $m \in \{m_i\}$;} \\ H(m), & \text{otherwise.} \end{cases}$$  In this case, $H'(m_i) = H'(m_j)$, but $H'$ otherwise behaves like whatever kind of hash function $H$ is.  It is unlikely that you can compress the description of $H'$ more than this without additional structure to the fixed messages $m_i$.

Another approach would be to define $\hat H(m) = f(H(m))$ where the polynomial $f \in \operatorname{GF}(2^\ell)[x]$ is the Lagrange interpolation of of the function $H(m_i) \mapsto h$: $$f(x) = \sum_i h\cdot\prod_j \frac{x - H(m_j)}{H(m_i) - H(m_j)}.$$  If the $m_i$ are larger than the $\ell$-bit hash values, this has a substantially shorter description: it is a degree-$k$ polynomial with hash-value-sized coefficients.  (Caveat: If $H(m_i) = H(m_j)$ for any $i \ne j$, this formula doesn't work as written—the denominator $H(m_i) - H(m_j)$ is zero.  In that case, just discard that term.)

Note that unlike $H'(m)$, $\hat H(m)$ does not coincide with $H(m)$ when $m \notin \{m_i\}$.  Whether $\hat H(m)$ has any properties one might expect of the kind of hash function you mean, I leave as an exercise for the reader to ascertain.

(Original answer)  If you were concerned about cryptographic attacks…

You can make a public-key collision-resistant hash function.  Anyone can evaluate the hash function; knowledge of a secret key enables finding collisions; without knowledge of the secret key, finding collisions is conjectured to be difficult.

One example is $x \mapsto y^x \bmod n$ for random $y$, where $n = pq$ is an RSA modulus.  If you know the factors $p$ and $q$ of the modulus, then it is easy to find a collision; if you don't, then it's probably not.  Specifically: any algorithm that can compute a collision with nonnegligible probability can be used as a subroutine to solve the RSA problem, computing roots modulo a large semiprime of secret factorization, without much additional effort.  Under certain additional conditions, finding a collision can't be much easier than factoring for an analogous reason.

VSH is a somewhat more well-known example, defined on arbitrary bit string messages.

These don't allow you to prescribe collisions, however: you get no choice in the messages that collide, only the ability to find them.  Actually you even get the ability to find preimages and second preimages, but again, no control over which sets of messages collide.


Does hashing a hash of a password over and over again increase its security?

What your describing is the core of many password hashing algorithms like bcrypt or pbkdf2. However, these are all complicated functions which don't just iterate. They are very commonly used with salt. If you would hash a password as you described n times, a reasonable choice would be bigger then 100.000.

However this is only for storing the password. If you would do this for, say, a website, it would take about 2 seconds. And if you're clients arent finding it nice to wait that long, you should lower it.


Why do all SSH-RSA Keys begin with "AAAAB3NzaC1yc"?

The public key blob doesn't consist of just the numbers that make up the public key: it begins with a header that says “this is an SSH public key”. The repeated prefix encodes this header.

RFC 4254 specifies the encoding of public key in SSH key format.

  The "ssh-rsa" key format has the following specific encoding:

 string    "ssh-rsa"
 mpint     e
 mpint     n

  Here the 'e' and 'n' parameters form the signature key blob.

The string is encoded as 32-bit big endian length followed by the literal string:

0,0,0,7,'s','s','h','-','r','s','a'

Encoding this sequence of bytes in Base64 gives:

AAAAB3NzaC1yc2E

The public exponent is also usually the same, so the common prefix is even longer. The bulk of the key is the public modulus, and that is completely different in different keys.


What kind of attack could one perform if you generate private keys using SHA3(master_key || nonce)?

KDFs

What you are trying to describe are different implementations of a key based key derivation function (KBKDF) which in turn is a specific form of key derivation function (KDF) that uses a key (and not a password).

The attacker would not be able to reverse the hash when using SHA3(master_key || nonce). The reversal could not even happen for SHA-1; the fact that SHA-1 is broken for collision resistance does not matter for this construction. HMAC is more appropriate because a keyed hash / PRF has better cryptographic properties than a hash.

$H(k | c)$ is actually a known KDF called KDF1 or 2 (those just differ in initial counter value $c$). As described here it is probably still secure. However, if you want real, standardized, proven security I'd probably recommend HKDF using SHA-512 as underlying hash. That should be secure until SHA-512 is broken to the extreme.

On HMAC

HMAC protects the underlying hash function against certain attacks. It should always be secure if a large enough key is used and the underlying hash is sufficiently secure - but that's even the case for MD5. HMAC also alleviates length extension attacks for the underlying hash. However, for SHA-3 there should be no length extension attacks possible, so SHA3(master_key || nonce) would not be affected by length extension attacks anyway.

HMAC is rather overkill for SHA-3 as it hashes the key twice after applying two different masks, while the protection it offers is inconsequential to SHA-3. So HMAC-SHA3 could considered an option because the HMAC construction is secure with any sufficiently secure hash. The more efficient KMAC construction is described in SP 800-185 and could be used instead - if it is available in the programming environment anyway.

TL;DR

Now that you know that you need a KBKDF, I suppose it is a good idea to use a well described one. I'd strongly recommend HKDF or HKDF-expand. NIST SP 800-108 has a few more KBKDF's, but NIST standardized HKDF afterwards for good reasons.


Zero-knowledge problem of Pinocchio (verifiable computation)

It is true that the verification procedure needs the values of the input wires, but "input wires" refers only to the wires of $u$, the value provided by the client.  The wires for $w$ are considered "middle wires", and are included in the computation of $v_{mid}$, $w_{mid}$, and $y_{mid}$ (i.e., their indices are included in $I_{mid}$).

On a higher level, the protocol does this:

The client sends (to the worker) values for some (not necessarily all, and possibly even zero) wires.  The wires for which a value is provided by the client are called the "input wires".

The worker sends (to the client) two things:

Values for some wires of the circuit whose values have not been provided by the client.  The wires for which a value is provided by the worker are called "output wires".  All wires that are not input or output wires are called "middle wires".
A proof of the following statement: It is possible to assign values to all the middle wires of the circuit so that "everything works", meaning that the input and output wires for every gate of the circuit are correct for the operation that the gate is supposed to perform, and moreover, the worker knows some such values.  This proof can be zero-knowledge; in that case it reveals nothing about the values of the middle wires.

The case where "input wires" (resp. "output wires") in the above sense correspond to the input and output wires of the circuit in the usual sense is actually just a special case, which corresponds to the "non-ZK" case discussed in the paper.  In the ZK case discussed in the paper, the "input wires" in the above sense correspond to only some of the input wires of the circuit: the wires for $u$. The wires for $w$ are "middle wires", so that the worker proves, in zero-knowlege, that it knows appropriate values for those wires.


Collision Resistant Hashing from One-Way Functions?

Simon [Sim98] showed that is not possible to build a collision-resistant hash function from a one-way permutation (which is a stronger statement) in a black-box manner .

The main idea is to use the so-called oracle-separation technique. You can read more about it either here or in this survey.

[Sim98]: Daniel Simon. Finding collisions on a one-way street: Can secure hash functions be based on general assumptions? Eurocrypt'98.