How does the "biased-$k$ attack" on (EC)DSA work?

Nguyen and Shparlinski detail the method in The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces. I'll largely follow the notation in that paper.

The idea is to convert the determination of a private key from biased $k$ nonces in several ECDSA signatures into instances of the hidden number problem (HNP), and then solve the HNP as a reduction to the closest vector problem.

So you collect a lot of signatures and construct a lattice out of them, and reduce that lattice using LLL or BKZ, and then you can extract the private key from the reduced basis vectors.

Estimated computational effort required

I tested this with a hand-crafted LLL Python implementation (it's so slow it surely must constitute an upper bound in performance...) running on a Ubuntu 16.04 VM with 2GB RAM, and I have the following sample runs:

96-bit bias, 5 signatures: (failed) 31 seconds
64-bit bias, 10 signatures: (success) 4 minutes
32-bit bias, 12 signatures: (success) 12 minutes
16-bit bias, 17 signatures: (success) 49 minutes
8-bit bias, 19 signatures: (failed) 79 minutes
8-bit bias, 21 signatures: (success) 244 minutes
8-bit bias, 20 signatures: (success) 177 minutes

I stopped there.  Nguyen and Shparlinski were apparently able to recover the secret key with only 3 bits of bias with 100 signatures and think that recovery is possible with only 2 bits being known.

More problem details and setup

So let's say you know the low $\ell$ bits of $k$. (This paper describes one way of recovering those bits.) Then you can write $k$ as

$$k = a + 2^\ell b$$

In other words, you know $a \in [0, 2^\ell -1]$. For simplicity, let $a = 0$. Then the equation for $s$ in the ECDSA signature $(r,s)$ becomes

$$s = (h + rx) \cdot (2^\ell b)^{-1}$$

where $h$ is your hashed message and $x$ is your private key, and everything is modulo $q$, the order of your base point. Rewrite this as

$$xr \cdot (2^\ell s)^{-1} = -h \cdot (2^\ell s)^{-1} + b$$

Define $t \equiv r\cdot (2^\ell s)^{-1}$ and $u \equiv -h \cdot (2^\ell s)^{-1}$ and you have

$$xt = u + b$$

Remembering that $0 \lt b \lt q/2^\ell$, you have

$$xt - u \lt q/2^\ell$$

So this is basically the HNP. $b$ is smaller by a factor $1/2^\ell$ than $x$,$t$, and $u$, so approximate this equation:

$$xt - u \approx 0 \longrightarrow xt - u - jq \approx 0$$

since everything is mod $q$. So first collect $n$ signatures, giving you several tuples of $t_i$, $u_i$, and $j_i$, and you can construct a matrix out of basis vectors:

$$ \begin{pmatrix}
q & 0 & 0 & \cdots & 0 \\
0 & q & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots  & \vdots \\
0 & 0 & 0 & \cdots & q \\
t_0 & t_1 & t_2 & \cdots & t_n \\
u_0 & u_1 & u_2 & \cdots & u_n \\
\end{pmatrix}
$$

(The first $n$ rows contain all zeroes and one $q$, one for each of the unknown $j_i$.) This is an $(n+2) \times n$ matrix. Now let $T \equiv (t_0, t_1, \cdots, t_n)$ and $U \equiv (u_0, u_1, \cdots, u_n)$. Then the short vector of interest, $X$ is going to be something like

$$U - xT + \text{(other stuff)}$$

You can modify your matrix to include "sentinel values" $s_T$ and $s_U$ so that you can identify $X$; if you see a reduced vector $T'$ with $s_T$ as its last slot, most likely you'll see the next-to-last entry containing $-x\cdot s_U$ from which you can recover $x$. Disclaimer: I saw this trick in a cryptopals problem first and makes things way easier than just guessing. The modified matrix looks like:

$$ \begin{pmatrix}
q & 0 & 0 & \cdots & 0 & 0 & 0\\
0 & q & 0 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots  & \vdots  & 0 & 0\\
0 & 0 & 0 & \cdots & q & 0 & 0\\
t_0 & t_1 & t_2 & \cdots & t_n & s_T & 0 \\
u_0 & u_1 & u_2 & \cdots & u_n & 0 & s_U\\
\end{pmatrix}
$$

Now you can use an implementation of LLL from NTL or fplll, find the sentinel value, and extract $x$.


This is doable by
(1) opening all commitments $B_k$ with standard responses $Q_{k}(z)$ that are linear in challenge,
(2) proving that all $x_k \in \{0,1\}$ (with at most second-degree polynomials in challenge), and
(3) proving $m$ polynomial identities for (at most) third-degree polynomials in challenge
$$U_i(z) = T_{i,1}(z) T_{i,2}(z) T_{i,3}(z) $$
where
$T_{i,j}(z) = Q_{i,j}(z) - z l_{i,j}$ and
$Q_k(z) = v_k z + \alpha_k$
considered over the ring modulo group order and
$\alpha_k$ are initial random coins.

With such a $\Sigma$-like protocol, prover will send commitments to 3 coefficients of polynomials $U_k(z)$.
It is actually proven that such a polynomial is of 2nd degree, not 3rd.
Informally, we need at least one TRUE out of each triple for satifstiability,
so at least one constant (degree 0) polynomial for each $(T_{i,1}(z), T_{i,2}(z), T_{i,3}(z))$.
The well-known $\Sigma$-protocol would evaluate a linear (degree 1) polynomial at a random point chosen as a challenge.

(Soundness) For any (that is, dishonest) prover, there are at most 3 chances (unlike just 1 for the well-known $\Sigma$-protocol) for such a polynomial to evaluate to zero by choosing some random value for the free variable $z$.
See Schwartz-Zippel lemma for details.

One would choose the challenge from a large set comparable to (large) group order.
Or maybe from polylog-cardinality set for zero knowledge.

For point (2), one would prove that $Q_k(z) (Q_k(z) - z)$ is linear (not quadratic) by sending commitments to two coefficients.


What you are describing is One-Time-Pad encryption, and yes it does have perfect secrecy.

Note that for any ciphertext $y$ there is exactly one key $k'$ for each possible plaintext $x'$ so that $E_k(x') = y$. So if you choose the key uniformly at random the ciphertext gives no information on the plaintext, because any plaintext is equally likely.


How do I sign data that's been encrypted using public key? (RSA)

This is impossible - the receiver knows nothing about you so there's no way he can assure that the sender is in fact you.


Is Paillier secure from known plaintext attack for single character message?

Yes, Paillier encryption is secure from known plaintext attack (for single-character message, and any other supported message size). With high likelihood, three ciphertexts $c_1$, $c_2$ and $c_3$ for the same plaintext will be different.

When using public modulus $n$, each Paillier encryption draws a uniformly random number $r$ in range $[0,n^2)$ (in some descriptions: coprime with $n$, but that's overwhelmingly likely for secure choice of $n$, thus can be omitted). Different $r$ will lead to different cryptograms $c=g^m\cdot r^n\bmod n^2$.

For proper implementation, by the birthday problem 101, the probability is about $k^2/2n^2$ that among $k$ ciphertexts for the same plaintext, any two are equal. For security against factoring, $n$ must have some thousand bits, thus said probability is entirely negligible for any feasible $k$ and secure choice of $n$. It is much more likely that whatever generates $r$ gets defective, and hickups, leading to identical ciphertexts.

Note: Pailler encryption is homomorphic only for messages that are straight integers $m$. Padding with zeroes on the left can't change $m$ if the homomorphic property must remain.


How safe is a book cipher? How would you break it?

This isn't very secure. Generally, partial knowledge of the plaintext should not lead to leakage of other parts of the plaintext. In your book cipher it clearly does.

Say we guess the first part of the message. Then we can try and see which books would be correct for the given ciphertext. After the book (the key) is found we can then decrypt the rest of the message.


Can you use repeating numbers like $\pi$, and $e$, as the Key to OTP ciphers?

An OTP is completely broken if you use a key that can be predicted. As such, $\pi$ would be a terrible choice. The key needs to be unpredictable, nonrepeating, and completely random. $\pi$ satisfies the nonrepeating aspect, and (looks like it) satisfies the randomness attribute, but is predictable since I can simply search online for 1 million digits of $\pi$.
To clarify, any number people have actually heard of is a bad choice. $\pi$, $e$, the coefficient of rolling friction across a carpet, are all bad choices. You need to use a number that has never occurred before, and never will; aka randomly generated by you, not taken from a mathematical constant.


Linear cryptanalysis complete key guessing

As in @Guut Boy's answer it may be possible to brute force the remainder of the key bits.

Another technique would be to find  another multi round linear characteristic which can be used to brute force another subset of key bits. Of course your success probability in doing this would depend on the overall probability of the new linear characteristic, but if the key bits determined by the new characteristic overlap some of the key bits already guessed, this may speed up your attack.


Role of primitive roots in Pollard's P-1 factorization algorithm

I will follow the steps in the document, emphasizing where the primitive root comes in.

Let $n$ be a product of two primes, say $p$ and $q$, pick $1<a<n$, and choose some $L$. The document suggests some ways to choose $L$. Take the following steps:

Compute $d_0=\gcd(a,n)$.

1.1 If $d_0>1$, we are done.

1.2 Else, continue to 2.
Compute $d_1=\gcd(a^L-1,n)$.

2.1 If $d_1=1$, then $p\not\mid a^L-1$, i.e. $a^L\not\equiv1\pmod{p}$. Choose a new $L$ and repeat.

2.2 If $1<d_1<n$, we are done.

2.3 If $d_1=n$, choose a new $a$ and repeat.

The goal is to end up in situation 2.2, so we can wonder when we do not.

Instead, we could end up in 2.1. This happens when $a^L\not\equiv1\pmod{p}$, thus when $p-1\not\mid L$. As the document states, we actually want $p-1\mid L$. This is clearly a condition on $L$, independent of $a$, so we can simply choose a new $L$ and restart.

Finally, we could end up in situation 2.3. As explained, this happens when $$a^k\equiv 1\pmod{q}$$
where $k=L\pmod{q-1}$. For which $a$'s can this happen? Well, if $k=0$, then it happens for all of them. In this case we have been quite unlucky, and choosing a new $a$ has only a very small probability of being helpful.

If $k\neq 0$, then this can not happen for all $a$'s. Remember that a primitive root $x$ modulo $q$ is defined as a non-zero integer $x$ such that $x^n\neq1\pmod{q}$ for all $0<n<q-1$. In other words, $a^k\equiv1\pmod{q}$ can only happen if $a$ is not a primitive root modulo $q$. We can choose a new $a$, and hope that the new one is a primitive root.


The performance of the hash depends on the environment it is used in.

Keccak excels in ASIC type hardware designs, whereas Blake and Skein excel in x86 and x86-64 environments.

MD5 is still quite fast in software, but newer algorithms take advantage of SIMD instructions on newer processors.

There is also the question of performance on a per invocation basis or on a per byte basis for larger messages. Keccak also has different speeds that depend on the security level (and message size).

SHA512 operates on a maximum message size of 885 bits before more than 1 invocation of the hash is required to process it, whereas SHA256 has a maximum size of 447 bits. That means a hash of a 128-bit message will be faster on SHA256, but a hash on a 128MB message may be quite faster with SHA512. SHA512 is about 50% faster on larger messages, but can be half as fast on small ones. This type of performance will vary with CPU type.

Performance comparisons with multiple message sizes and CPU types can be found here: http://bench.cr.yp.to/results-sha3.html


Why work in a subgroup QR(n) of an RSA group $Z^*_n$?

Well, the reason that a specific cryptographical object needs to work in a specific subgroup probably has to do with the details of that object, and the cryptographical properties it needs from the subgroup.

One obvious possibility is that they need to avoid leaking information via the Jacobi symbol; that is an easily computed function that maps values in $Z^*_n$ into the values in the set $\{1, 0, -1\}$; it is interesting because the RSA operation preserves it; $Jacobi(x) = Jacobi(RSA(x))$ (where $RSA$ is either the public or the private operation, and $Jacobi$ implicitly relies on $n$).

Depending on what you're doing, this property may allow people to track which inputs refer to which outputs (for example, if you're shuffling values by encrypting them, and then randomly permuting them).  One way of making sure this sort of thing doesn't lead to a problem is to specify that all input values are in $QR(n)$; all these values have Jacobi symbol 1, and so there's no leakage.

It's also easy to create random values in $QR(n)$; pick a random number $r$ relatively prime to n, and compute $r^2 \bmod n$; that's a random value in $QR(n)$

As for the size of $QR(n)$, well, that'd be $(p-1)(q-1)/4 \approx N/4$; obviously, that's a fairly sizable group.


How should I store passwords that need to be available in plain text?

You could encrypt them using some key derived from the user's password (to your site).

Of course, this assumes that you get your user's passwords in plain text (or in any form which is always the same) - thus you need to have an encrypted connection to your user. Do not allow any non-SSL login.

You can use some key derivation function like PBKDF or bcrypt to derive the encryption key from the password (if this uses a salt, make sure the salt is not the same as you are using for your password checking). You could additionally use some server-secret here, but if your say that some potential attackers have (read-)access to the server anyway, this will not really increase security.

Then encrypt/decrypt the stored login information for the third party website using a standard symmetrical encryption algorithm like AES.

Of course, you also should use an encrypted connection to this third-party website.


Does the transposition cipher have a network application?

Transposition and substitution are heavily used in today's block ciphers. S-box means substitution box, and P-boxes transpose bits.

When you say transposition cipher you are referring to classical cryptography.  The heyday of the transposition cipher was before the end of World War I. The ADFGX and the ADFGVX were fractionated transposition ciphers used by the Germans (and broken by the French).  Double fractionation is stronger, especially when at least one iteration is disrupted (VIC cipher). But all of this belongs to the last century because it is now trivial to break classical transposition ciphers.

But transposition itself has not gone away, and modern methods are much better than those of 1918.


Possible to generate a one time secret which all nodes on the distributed network can know but cannot pre compute

If you have the bandwidth to do so, and good communication reliability between the nodes, you can perform a multi-party Diffie Hellman key exchange. The most efficient way to do so would be using X25519, resulting in a shared 256-bit secret between all parties. This can then be used to derive keys and other secret values.

This would also allow new nodes to be added to the network at any time, their public key would be added to the pool and all parties would calculate a new shared secret from the current secret. Parties would have to agree on the time it takes to distribute and calculate the secret, and use that to agree on a set time when that secret would go into effect. If it takes approx 5 mins to distribute all the public keys, they may start communicating to the network 7 mins in advance so there will not be a blackout period where some nodes do not have the secret calculated.

Bandwidth can be reduced substantially if a node trusts other nodes to forward a public key to other nodes on their behalf, and computation can be reduced if a node trusts other nodes to compute an intermediate shared secret from the rest of the network.

A ring-bus design could also be used, where nodes transmit to a single peer, and they receive from a single peer, and transmit the pool they receive which grows by 1 with each transmission. At the end all nodes should have the same list, and they can verify a hash of the key pool with other nodes randomly. If a peer does not have the same hash, but does have all keys, they may have been given an intentionally incorrect key(s), and procedures can be put in place which allow groups of peers to determine where the incorrect key(s) originated (traitor tracing).

The most reliable option is to have a node send its public key to all peers in the network, and receive the keys from all other nodes as well, resulting in $n^2-n$ total key transmissions for $n$ peers, then validate the list with several other peers.

Another option is available if all nodes have a permanent shared secret, the network is open, and nodes can access the internet without restriction. A high entropy public value, such as the output of the NIST randomness beacon, can be processed with HMAC, using the permanent secret as the key. The resulting output would not be able to be generated in advance of the beacon, and will be cryptographically secure because of the generation method, as long as the secret remains isolated to the network.

A combination method can also be used, in advance of the beacon publication, all nodes use Diffie Hellman to agree on a shared key for processing the next days beacon, this gives plenty of time to verify that each node has the same key. This would be the best option for nodes on an open network with a wide range of distribution (high latency), or a very large number of total nodes.


Perfect secrecy and known ciphertext length

You are correct that the security provided by a one-time pad is that a chosen-plaintext attacker can't distinguish between two messages of the same length, at least not with better advantage than their advantage at distinguishing the pad itself from uniform random.

Length, of course, can be a side channel for more interesting information, especially if variable-rate compression is involved!  For example, the distribution of page sizes when downloading Wikipedia is likely to be very different from the distribution of file sizes when downloading the WikiLeaks archive.

If you have a maximum message length, you could extend your messages up to that maximum length with (say) zeros.  But this can be costlier.  Alternatively, you could break messages up into chunks.  In any case, message length is something that a protocol designer must consider when striving for confidentiality!


Best way to reduce chance of hash collisions: Multiple hashes, or larger hash?

The risk of collision is only theoretical; it will not happen in practice. Time spent worrying about such a risk of collision is time wasted. Consider that even if you have $2^{90}$ 1MB blocks (that's a billion of billions of billions of blocks -- stored on 1TB hard disks, the disks would make a pile as large of the USA and several kilometers high), risks of having a collision are lower than $2^{-76}$. On the other hand, the risks of being mauled by a gorilla escaped from a zoo are at least $2^{-60}$ per day, i.e. 65000 times more probable than the SHA-256 collision over way more blocks than possibly makes sense. Stated otherwise, before hitting a single collision, you can expect the visit from 65000 successive murderous gorillas. So if you know what's good for you, drop that MD5 and go buy a shotgun.

Now for the suggestion of concatenating the outputs of two distinct hash functions, say SHA-256 and MD5. It turns out that this does not enhance security as much as one could believe. The total size of 384 bits would certainly not provide more security against collisions that what a 384-bit hash function would give; but it actually is much weaker than that: it would not be really much stronger than SHA-256 alone. See this previous question, and this research article for the gory details. This can be summed up as follows: when using several hash functions in parallel and concatenating the outputs, the total is not stronger against collisions than the strongest of the individual functions.

And, of course, MD5 itself is weak against collisions and as such should not be envisioned for newer designs.


RSA PKCS#1 OAEP Padding Schema - padding 0 for first octet?

According to RFC 2437...

RSAES-OAEP can operate on messages of length up to $k-2-2\cdot hLen$ octets, where $hLen$ is the length of the hash function output for EME-OAEP and $k$ is the length in octets of the recipient's RSA modulus.
The padding string $\text{PS}$ in EME-PKCS1-v1_5 is at least eight octets long, which is a security condition for public-key operations that prevents an attacker from recovering data by trying all possible encryption blocks.

Generate an octet string PS consisting of $emLen-||M||-2\cdot hLen-1$ zero octets. The length of $\text{PS}$ may be $0$.

concisely,  the length of zero padding will be $${emLen-||M||-2\cdot hLen-1}$$

Running with OpenSSL;
openssl rsautl -decrypt -inkey priv2.txt -in cipher.txt  -raw -hexdump
and the first line of the output is;
0000 - 00 25 2b 2c e4 b5 a8 6c-a1 d1 cc bd 0b 26 d2 9c   .%+,...l.....&..
You can see that the first byte above is 0x00


Can I use the same key pair for authentication and Diffie-Hellman?

While it's technically not (probably) an issue, you should definitely avoid sharing keys between different purposes. RSA uses separate keys for signing and encryption, for example, since an encrypted-and-signed message would cancel out. RSA only signs a hash of the original message, negating this issue, but it still avoids sharing keys because it's simply better not to use the same keys for different purposes.


Elliptic curve cryptography related key attacks

The answer depends on your definition of security:

Anonymity: this scheme will produce key pairs, and hence also public addresses, that are indistinguishable from random to anyone who does not know the hash function contents, if the hash function is modeled as a random oracle.
Cryptoeconomic security: People will not try and game your scheme if you can ensure that the value of gaming your scheme is less than the cost of doing so. In your example, if you use the blockhash within the protocol, an adversary controlling the blockhash may withhold the block they have successfully mined, in order to give themselves a better than average chance at winning your game.
With this knowledge, you can find the lower bound on how motivated and powerful an adversary attacking your scheme must be by defining a security parameter $n$ such that:
$$ \mbox{value gained by winning your game} < n * \mbox{bitcoin block reward}.$$

For your question of whether creating signatures with 'related keys' is secure, this is something I'm currently working on formally proving. With the hash function modeled as a random oracle, I believe we have the result that one can produce: $$a' = a + H(S),$$ and hence spend funds associated with an account if and only if they know the $A$ such that:
$$ A' = A + H(S) \cdot G,$$
with $G$ the generator of the elliptic curve group in question. However, this is dependent on your opinion of hash functions as random oracles. $H(i) = i$ would definitely not be sufficient, and $S$ is assumed to be secret.

EDIT: If $H(S)$ is not secret, there will be a de-anonymising attack on all transactions associated with your account, but people will not be able to forge transactions from you, or spend the bitcoin from that account, as they will not have the root private key $a$ necessary to form the private key. They will simply be able to scan the blockchain and group the accounts associated with you. This is how view keys and spending keys in anonymous cryptocurrencies such as Monero work.


Schnorr identification protocol security proof

It is important to understand that the simulator is a non-interactive machine; it does not interact with the prover (or with anybody else). What it can do is mimic (or simulate) a real interaction between the prover and the verifier, by playing the roles of both parties and internally "sending messages to itself". But it is not required to mimic the protocol exactly, only to produce an output that is close enough to the output of a real execution of the protocol. This is why it can internally repeat the protocol many times until it obtains a satisfactory output; there is no need for the prover to "cooperate", since again the simulator does not interact with the prover.


How much would it cost in U.S. dollars to brute force a 256 bit key in a year?

The average cost of electricity in the US is $\$0.12$ per kWh. For a single server, I'll use 3741 kWh annually as an estimate. That would be about $\$450$ per year for one machine.

Let's say you can do $10^{14}$ decryptions per second. That is $3.15\times 10^{21}$ decrypts per year for one machine. You need to do (on average) $2^{255}$ decryptions in a year, so you would need $\frac{2^{255}}{3.15\times 10^{21}} \approx 1.84\times 10^{55}$ machines. To figure your cost you would multiply that by $\$450$ and get about $\$8\times 10^{57}$ or 8 octodecillion dollars. Gross world product, or GWP, is about $63\times 10^{12}$, so brute-forcing a 256-bit key would cost about $10^{44}$ times the GWP.

You can follow similar math to get the cost of brute forcing a 128-bit key.

Note:

I am completely ignoring hardware costs, maintenance, etc. The estimate above is for electricity only. We can take a hint from the NSA on this. You'd be a lot better off hiring a few thousand mathematicians and have them work on breaking the cipher as opposed to trying to brute-force it.


The point (( also see this answer)) is that the hash calculation is free for everybody and we assume that your methodology is known by Kerckhoffs's principles. Anybody can calculate the hash of any information and this may leak the encrypted message.
In Cryptography, we consider the attackers computationally bounded, but not restricted to adapt any method on their advantage.
If the possible attacker one of the three-word agencies, that we can assume that they collect all public information, where available, including your personal information, your networks, your habits, etc. Then they can keep the hash of each information on their humongous database ( like the Utah Data Center ) and once they see a message is transmitted with $E_k(m)||H(m)$ then they will check the existence of the $H(m)$. A hit today will reveal the message you send. They will not stop here if they fail. They will store this message and regularly will check the hash with the updated database.
Therefore this is not a good way to authenticate the messages. In modern cryptography, we have Authenticated Encryption (AE) modes like AES-GCM and ChaCha20-Poly1305 that provide confidentiality, integrity, and authentication in a bundle. Remember nothing is perfect and keep the obligations like for AES-GCM to be secure.


Is AES key and cipher distance measurable? Could this be translated into a cost function?

Currently, there is the possibility for only one cost function $C(k, k')= (k \neq k)$ or $C(c, c') = (c \neq c')$. This function shows zero cost for a correct guess and full cost for an incorrect guess

Not quite. Hamming distance is an obvious candidate, as in the comments. Another candidate might be the compatibility of the two permutations $E_k$ and $E_{k'}$ or  $$\#\{x:E_k(x)=E_{k'}\}.$$ There are other distances on permutations such as Kendall tau, as well.

It's probably going to be difficult to do this except at a reduced scale, so I remain skeptical. Maybe try it on weaker or reduced round ciphers.


How to protect against brute force attacks in the case of a small dictionary?

I think you're looking for column level encryption.

It allows you to encrypt specific columns in your database, in your case the cloumn "country".

Another way would be to use database encryption, which can encrypt an entire database. The main disadvantage there would be the speed, because the size of the data to encrypt / decrypt is larger than just the data in a single column.

Just be sure to store the encryption key securely. You can find more information about this topic in this post: SecuritySE - Where to store a server side encryption key.

Edit:

  My question is not tied to the specific case of the column of a table. Rather, I am asking what are the algorithms to use when the dictionary size is small.

You could simply use a symmetric-key algorithm, i.e. AES in CTR mode to protect your data. It works for both small and large data.


The CBC-MAC construction indeed can use a PRF instead of PRP. It is now based on PRP due to historical reasons: the blockciphers used for CBC-MAC were based on permutations.

From the security point of view there will be no difference: the security proof for the CBC-MAC first converts PRP to PRF (which is indistinguishable up to $2^{n/2}$ queries) and then derives an actual upper bound on the adversary's advantage.


In DES we must distinguish the Initial Permutation; the Final Permutation, which by definition is IP-1; and the final swap (or lack thereof), which makes the last round different from the others. The final swap is formally in the specification of DES as a definition of the preoutput block as R16L16, when input and intermediary blocks are LiRi.

The rationale of making a Final Permutation parallels that of the Initial Permutation: in the original 8-bit-hardware implementation of DES, IP allows loading the plaintext as eight byte-wide accesses, with each of 8 bit of the IC's data bus line leading to the input of 8 shift registers in the IC, holding L and R. FP allows unloading the ciphertext by the same mechanism (the output of the 8 shift registers leads to the data bus). IP of decryption undoes FP of encryption, while FP of decryption undoes IP of encryption, because FP is IP-1.

The final swap consists in making an additional exchange of Left and Right registers after the last round (or, to the same effect, not doing in the last round the exchange of Left and Right registers performed in the other rounds). The rationale is that, combined with FP being IP-1, it makes encryption and decryption identical except for preparing subkeys in reverse order. That identity simplifies hardware and software that must adapt to both roles (when subkeys are precomputed as is standard practice for speed-optimized software implementations, the exact same code does encryption and decryption). Without final swap, in order for decryption to undo encryption, we'd have to move the exchange of Left and Right registers at the beginning of a decryption round, rather than at end in an encryption round.

IP and FP do not exist in all Feistel ciphers; they are rather specific to DES. On the other hand, the final swap technique works for any symmetric Feistel cipher, and is often considered an integral part of that design pattern.

Note: in some implementations or descriptions of DES (but not the standard), FP is taken to include final swap then IP-1.


Diffie-Hellman in Https: How are prime numbers picked?

TLS generally uses the DH groups specified in RFC7919.  The RFC selects the modulii it specifies so that $(p-1)/2$ is also prime (and so the value $g$ is selects generates a large prime subgroup) - those primes have a number of other nice practical properties.

In TLS 1.2, the client could specify its own group, however that is not greatly encouraged (both because the client might get it wrong, and because it makes it difficult for the server to do validity checking).

In TLS 1.3, they removed the option to specify your own group, and so the groups in RFC7919 (or an elliptic curve group or a private group) is your only option.


Send a message to an entire group of recipients

One of the major flaw in this approach is that you wont have the option to remove a member from the group. If you want to you will have to send a new shared secret to each of the other members which is not very scalable if the group is large or the number of people leaving the group is large.

There are a lot of ways to accomplish broadcast key distribution,
One of the methods is Logical Key Hierarchy (LKH). The basic idea of this scheme is arrange members at leaves of a key tree, each member receives keys on its path. In this scheme both entry and exit of members has low computation and communication overhead.


Is "Bit Independence" of SHA-2 hashes secure?

There is no known exploitable relationships between the words (32/64 bit "chunks") of SHA-2 but this is always a source of cryptanalysis.  There are some academic weaknesses against reduced round variants of SHA-2 but nothing against the full cipher.  Still hashes are cheap so why not just use multiple hash functions?

Seed = HASH(secret)  <- This should be a KDF instead see below
A = HASH(Seed)
B = HASH(A)
C = HASH(B)

If you need less bits you can just chop them down (it is good enough for NIST). Here is another option.

> Seed = HASH(secret)  <- This should be a KDF instead see below
> A = HASH(Seed XOR ConstantA)
> B = HASH(Seed XOR ConstantB)
> C = HASH(Seed XOR ConstantC)

Keep the constants the same same length as the output of HASH to avoid a biased result.

Use a KDF

I am assuming "secretKeyNonce256bit" is really a human generated password.  Using a simple unsalted hash to derive a key from a low entropy secret is a bad practice. You say "not the case here" but it is unclear if you mean it is not a password or not a "weak password". If "secretKeyNonce256bit" is a 64 byte random value from a CSPRNG then ignore this but if it is the result of any human selection you really should be using a true KDF (like PBKDF2, Bcrypt or Scrypt).


Cryptanalysis of Marvin32 compared to SipHash

It isn't a good cryptographical PRF (and, to be fair to the inventor, he never claimed it was).

Marvin32 starts with a secret state, and processing the message and the state to give a new state, and at the end, outputs the state.  However, it outputs the entire state, and the state update process is invertible (if you know the message); hence if you know the message and the output, you can reconstruct the original state (and with that, compute the output for any other arbitrary message).

Even if we ignore the state recovery attack, there are also issues with propagating deltas from the final message bits into the output; if we take a message and flip a bit in the final byte, it wouldn't appear that that change gets propagated to all the bits of the output with probability anywhere close to 0.5 (this effect is stronger if the message length isn't a multiple of 4); this raises questions whether it's a good statistical PRF.


Where is the authentication tag stored in file encrypted using AES-GCM?

The authentication tag is defined as an output parameter in GCM (see section 7, step 7 of NIST SP 800-38D). In all the API's I've encountered it's appended to the ciphertext. Where it is actually placed is up to the protocol designer. The protocol designer may well consider the place behind the ciphertext as ad hoc default though. The name "tag" of course kind of indicates that it should be tagged to the ciphertext and that may well mean direct concatenation.

The tag is often considered part of the ciphertext within an API. This means that the API is less flexible, and that it requires the buffering of the ciphertext (up to the size of the tag value) as the decryption routine otherwise doesn't know where the ciphertext ends and the authentication tag starts. This means in turn that the online property of the counter mode encryption is damaged.

So in generally it is better to treat the authentication tag as separate parameter as API designer, and leave the location of the authentication tag up to the protocol designer. The protocol designer may well choose to prefix the ciphertext with a length component, which would render the buffering unnecessary.

In your case it doesn't help to directly look at the GCM specification, you need the protocol or API specifications. I would suggest to look for it at the end of the ciphertext if the location hasn't been strictly defined. The tag size should be a valid, predefined parameter value.

In RFC 5116: An Interface and Algorithms for Authenticated Encryption the authentication tag is explicitly placed at the end of the ciphertext for GCM mode encryption. This is due to the following requirement in section 2.1:

  There is a single output:

  A ciphertext C, which is at least as long as the plaintext or
  an indication that the requested encryption operation could not be performed.

and further explained by section 5.1:

  The AEAD_AES_128_GCM ciphertext is formed by
     appending the authentication tag provided as an output to the GCM
     encryption operation to the ciphertext that is output by that
     operation.

This RFC is - for instance - used by the TLS specifications. Note that the size of the ciphertext is made explicit in those specifications, which means it should be easy to separate the tag from the actual ciphertext.


Is the additive discrete Logarithm problem always easy in Fields?

I will call the field elements "points" (as an analogy with elliptic curves). We can thus add points together and multiply points together. We can also multiply a point with an integer with a double-and-add algorithm (which will be reasonably efficient), and, similarly, raise a point to some integer power with a square-and-multiply algorithm.

Your additive Diffie-Hellman thus looks like this:

There is a conventional base point $G$.
The two parties select random integers $a$ and $b$ respectively, and compute $aG$ and $bG$ (point $G$ multiplied by an integer), that they send to each other.
They then both compute the common secret $a(bG) = b(aG) = abG$.

The attacker's goal is to find that secret.

Now if the field's order is a known integer $q$ then the attacker has it easy:

$$ (aG)(bG)(G^{q-2}) = abG^q = abG $$

Note that while this breaks Diffie-Hellman in that specific context, this does not mean that the attacker can break Discrete Logarithm per se.

If the field order is not known, then things become more interesting. What the equation above basically says is that the attacker, by multiplying the observed points $aG$ and $bG$, gets $abG^2$, and he wants $abG$, so what he needs is to multiply that value by $1/G$. So the problem really is: if the field order is not known, then can the attacker compute the inverse of the base point?

If $\mathbb{F}$ is a field, then its order $q = p^f$ for a prime $p$ and an integer $f$; $p$ is the field characteristic. For any point $X$ in $\mathbb{F}$, we have $pX = 0$. Thus, the additive order of $G$ is necessarily $p$ (the integers $a$ and $b$ are really integers modulo $p$). For the DH problem to be interesting, we must thus assume that $p$ is relatively large (and therefore odd). Correspondingly, $f$ must be rather small, otherwise the field elements will be unwieldy (very large in RAM). For instance, if $p$ is at least 200 bits in length (for "100-bit security" in DH) and field elements fit in 10000 bits when encoded, then $f$ can be no more than 50.

Therefore, if the group additive order ($p$) is known, then the attacker can exhaustively try successive values of $f$ (starting from 1), each time assuming $q = p^f$ and then trying to compute the inverse of $G$ as $1/G = G^{q-2}$.

If $p$ is not known either, then we are in a mythical "generic field" which is like the "generic group" but with two operations, and then I think that DH in the additive group would be fairly safe. The only problem here is that there is no proof that a generic field can exist at all (just like the generic group, because it would imply all sorts of things such as $P \neq NP$), and I have no idea how to build a plausible candidate. For generic groups, elliptic curves are one of our best approximations, and yet we know more about them than just having an addition on them (indeed, we can compute curve orders with Schoof's algorithm).

Summary: to make the additive DH safe, you would need at least your finite field to be such that its order and its characteristic (which is the additive order of your DH group) are totally unknown, and that seems to be a lot to ask for.


Can a shift cipher attain perfect secrecy?

The Caesar cipher (aka Shift cipher) has, as you said, a key space of size 26. To achieve perfect secrecy, it thus can have at most 26 plaintexts and ciphertexts. With a message space of one character (and every key only used once), it would fit the definition of perfect secrecy.

For the usual use with messages longer than one character, or multiple messages with the same key, none of the given options fit (other than the "None" option).


When we turn Random shuffle to Pseudorandom Shuffle

It is not possible to generate uniform real number of infinite precision.
Therefore, it is not possible to pick a random value $U$ arbitrary precision uniformly at random so that $0 \le U \le 1$, and that any number in the range is possible.

Instead, it is (typically) necessary to generate sequence of uniformly random bits and interpret them as floating point number. For instance, you may generate 32 random bits and represent them as integer and divide the result with 4294967295. [Exception: Some sources have range that is not binary, like ideal dice. They still have limited precision.]

This part actually works the same regardless of if you had truly random source or if you used pseudo random number generator capable of generating bits to generate your random numbers.

However, Fisher-Yates shuffle or Richard Durstenfeld shuffle algorithm you linked to actually does not need arbitrary precision random numbers. It need random numbers, which are in range $0 \le j \le i$. These in theory can be derived from random and uniform arbitrary precision float number between [0, 1), but in practice, you instead need to generate bits (as described above) and use them to select array element to shuffle. Because the range is not always power of two, it is often necessary to use algorithm, which can convert numbers to specific range without generation of bias. FIPS 186-4 provides some algorithms useful to convert bits to arbitrary integer range. See Appendix B.2.1 and B.2.2 for two choices: allowing some bias or testing candidates and rejecting out of range values.


Is it possible to use X.509 for a symmetric-key algorithm?

No, X.509 cannot be used for symmetric cryptography directly. Inside the certificate is a public key of the subject of the certificate. The subject controls the private key.

The X.509 name is a reference to CCITT / ITU-T X.509; X.509 certificates are used as base of PKIX,  the Public Key Infrastructure. PKIX is a tree structure where a Certificate Authority can be used to give trust to end entity certificates by signing them using their own private key. That way a chain of trust is created from the root certificate to the leaf certificate. These certificate chains can be validated if the end user received the root certificate or any intermediate certificate in an initial trust store. The verifier receives a leaf certificate which contains an issuer, which can be used to create a chain to a initially trusted certificate. Of course the certificate should also be validated: the entity name (the server name for TLS), the validity period, certificate status (CRL / OCSP) need to be valid for the certificate and the public key inside it to be trusted.

This kind of trust cannot be build using symmetric cryptography. It is obviously impossible to put the secret key in the certificate as that is supposed to be public; it needs to be trusted by the other party after all. As symmetric cryptography lacks a public key, symmetric cryptography cannot be directly used for X.509 certificates.

The most prevalent use of X.509 certificates is probably TLS. TLS may also be used using other authentication methods, but X.509 is most common. With TLS the initial trust store is distributed with your browser. TLS itself does use symmetric cryptography such as AES and / or HMAC. However, in that case X.509 is mainly used for entity authentication, authenticating the server and optionally the client. The

TLS 1.2 and earlier also used the public key within the certificate to encrypt symmetric master key material. This key material can then be used to derive the session keys. These session keys are used to protect the messages of the transport layer, HTTP data in the case of web technology. Generally however, the RSA key is only used to authenticate the Diffie-Hellman key exchange that performs key agreement creating the same master key material on both sides. In that case RSA is not directly involved in the symmetric part of the protocol. For TLS 1.3, RSA cannot be used anymore to directly establish keys by encrypting them and sending them over.

Generally X.509 certificates and their private keys can be used for any purpose that requires either authentication, non-repudiation (i.e. document signing) and encryption / decryption. The private key is used by the signer for the first two purposes and by the receiver for the latter.

Protocols that use X.509 besides TLS are: Cryptography Message Syntax (both document signing and encryption), XML-DigSig and XML-Enc including in Web-security, PDF signing, application code signing, Windows authentication etc. etc. There are use cases for sectors such government identification / authentication, driver licenses, banking...

Obviously autentication, non-rep and encryption / decryption is pretty broad so countless public or proprietary protocols can benefit from asymmetric crypto and therefore X.509 based PKI.

X.509 may be trickier to use if there is no networking is possible, as the checks for certificate status commonly rely on networking to be present. Similarly, a trusted time source is often needed as well, although with networking NTP is commonly possible. Obviously parties also need to trust one or more Certificate Authorities.

Finally, many protocols and schemes also require some kind of random number generator to be present. Finally, especially for embedded devices and (smart) cards, the processing requirements for generating keys, signing or decryption may be hard to fulfill or hard to secure.

As an extreme hack, you could use the same certificate / private key or two certificates for the same private key for multiple parties, turning the private key into a secret key of sorts. As a public key must be present in the X.509 certificate this is easier than adopting the PKI for symmetric cryptography.

However, to do that a good understanding of the cryptography used is absolutely required, as an adversary can for instance perform encryption with the public key, which is not possible when using symmetric cryptography.


A Sophie Germain prime is a prime $p$ such that $2p+1$ is prime (that later prime is deemed a safe prime). For small examples, see A005384 in the OEIS.

A random integer $n$ has odds commensurate to $1/\log(n)^2$ to be a Sophie Germain prime. Therefore, there's in the order of $2^{495}$ Sophie Germain primes of 511 bits, way too much to enumerate them, much less store them in a database.

In order to find a Sophie Germain prime that will allow to calculate safe prime of $k=$512, 768, 1024, 2048, 4096 bits, one can simply repeatedly find a random prime $p$ of $k-1$ bits, until $2p+1$ is prime (or repeatedly find a random $k$-bit prime $p$, until $(p-1)/2$ is prime); the smallest of the two related primes exhibited is the Sophie Germain prime, the other is the safe prime.

A large speedup is possible by sieving with small primes, noticing that $p$ and $2p+1$ being large primes implies $p$ odd; $p\bmod3=2$; $p\bmod5\in\{1,3,4\}$; and more generally $p\bmod q\not\in\{0,(q-1)/2\}$ for any small odd prime $q$.

For cryptographic applications, one can use the Miller-Rabin primality test.


What is the advantage of AES-GCM against CPA attack

I'll use the 2012 paper: "Breaking and Repairing GCM Security Proofs" by Iwata, Ohashi and Minematsu as my primary source.

In said paper, the advantages for the privacy and authenticity game are stated. Only the latter one is being influenced by the tag length $\tau$.

  Theorem 1. Let $\operatorname{Perm}(n)$ and $\tau$ be the parameters of GCM. Then for any $\mathcal A$ that makes at most $q$
  encryption queries, where the total plaintext length is at most
   $\sigma$ blocks and the maximum nonce length is at most $l_N$ blocks,
   $$\textbf{Adv}^{\text{priv}}_{\operatorname{GCM}[\operatorname{Perm(n)},\tau]}(\mathcal
 A)\leq
 \frac{0.5(\sigma+q+1)^2}{2^n}+\frac{2^{22}q(\sigma+q)(l_N+1)}{2^n}$$

with $n=128$ because you pick AES here.

  Theorem 2. Let $\operatorname{Perm}(n)$ and $\tau$ be the parameters of GCM. Then for any $\mathcal A$ that makes at most $q$
  encryption queries and $q'$ decryption queries, where the total plaintext length is at most
   $\sigma$ blocks,the maximum nonce length is at most $l_N$ blocks and the maximum input length is at most $l_A$ blocks,
   $$\textbf{Adv}^{\text{auth}}_{\operatorname{GCM}[\operatorname{Perm(n)},\tau]}(\mathcal
 A)\leq
 \frac{0.5(\sigma+q+q'+1)^2}{2^n}+\frac{2^{22}(q+q'+1)(\sigma+q)(l_N+1)}{2^n}+\frac{q'(l_A+1)}{2^\tau}$$

In theory you could just plug-in values into the theorem until you hit a security bounds that makes you feel uncomfortable and use it.

Or you could just follow NIST SP 800-38D Appendix C (PDF)'s guidance on short tags with AES-GCM. It contains nice tables and explanations thereof for 32-bit and 64-bit tags. If you do not intend to shorten the tag, then section 8 has guidance on message lengths.


Is there any existing analysis for this construction to turn a tweakable blockcipher into a PRF?

I don't have a proof myself, but here's how you could analyze this / prove it secure yourself, if you want to have a go.

Your construction is basically $F(M) = E_0(G(M))$, where $G(M) = E_1(M_1) \oplus \dots \oplus E_{\lambda+|M_m|}(0)$ (that long thing defined in the question).  To prove this secure, it suffices to prove the following:

The tweak values used in computing $G(M)$ are never $0$.
It is highly unlikely that the attacker can find a "collision".  In other words, say that two messages $M,M'$ form a "collision" if $G(M)=G(M')$.  Consider an (adaptive) attacker with an oracle for $F$, and let $M^1,\dots,M^q$ denote the $q$ messages that the attacker queries its oracle on.  Let $\mathsf{BAD}$ denote the event that there exists some $i,j$ with $i\ne j$ and $G(M^i)=G(M^j)$.  If you can prove that $\Pr[\mathsf{BAD}]$ is negligible, then you are home-free.  That's because $E_0(Y^1),\dots,E_0(Y^q)$ will be pseudorandom if $Y^1,\dots,Y^q$ are all distinct.

The first condition should be easy to establish, as long as you put appropriate bounds on the length of the message to ensure that $l+|M_m|$ and $\lambda+|M_m|$ never wrap around to become equal to $0$.

You will have to analyze the second condition carefully.  It looks like you might be able to establish that the second condition holds through some sort of case analysis, but that looks too tedious for me to do it -- so I'm going to leave that to you to establish.

Other comments.  I don't understand why you have $E_{l+|M_m|}(0)$ in the xor; that looks pointless to me.  I don't understand why you treat $M_m$ differently (premature optimization?).  I don't understand why you don't just use some existing construction, like PMAC.

If you're going to invent something new, the following seems cleaner and easier to analyze:

$$F(M) = E_0(E_1(M_1) \oplus E_2(M_2) \oplus \cdots \oplus E_m(M_m) \oplus E_\lambda(\text{length}(M))),$$

where $\lambda$ is a constant chosen to be larger than any possible value of $m$, and where $M_m$ is padded with zeros (say) deterministically.

Related work. I suggest you make sure ythat you read the following papers:

http://cseweb.ucsd.edu/~mihir/papers/xormacs.html - Describes a similar but not identical construction, and offers a proof of security.
A Block-Cipher Mode of Operation for Parallelizable Message Authentication - PMAC is also very similar, so make sure you take a look at it.  It's not clear to me why you have invented something new, rather than just using PMAC.  I don't see any advantage of your scheme over PMAC.
Improved Security Analyses for CBC MACs - I recommend you read their proof of security for ECBC.  It is the framework I outlined above (show that the input to a final PRF/PRP is free of collisions across all queries, then it follows that the output is pseudorandom).


Can any one explain why circuit privacy is needed on homomorphic encryption?

When we say circuit privacy, we actually mean that the distribution over the result of the computation is the same (statistically close) to the distribution over an encryption of the result. This is needed because typically the party computing the circuit has its own private input and we need to protect this. However, if you are using FHE to just offload computation to a cloud in a private manner, then you not need circuit privacy. Rather, circuit privacy is needed when multiple parties with private inputs collaborate to compute an output.


Bitcoin mining nonce and birthday attack

Wouldn't it be better to select a random nonce instead of incrementing the first by one?

This is often thought of by people who read (or understand) only a garbled version of the original Satoshi paper/design. I'm surprised it seems not to be a dupe here, although it is crossdupe in bitcoin.SX where it is more ontopic:
https://bitcoin.stackexchange.com/questions/80752/why-is-the-nonce-bruteforced-from-0-to-n-while-mining
https://bitcoin.stackexchange.com/questions/78214/how-are-nonces-decided-in-mining
and nearly https://bitcoin.stackexchange.com/questions/41949/what-is-the-precise-nonce-finding-protocol

Put more technically, if miners are racing to find a nonce which makes a particular block header hash to below the target, doesn't it duplicate work to have them all try the same sequence and/or wouldn't at least some do better using different starting points (or sequences)? On that premise, yes it would be better, but that premise is wrong in several ways.

First, even in the original design, independent miners (the only kind Satoshi imagined) don't try to find a nonce for the same block. Miners are incented by receiving a reward for 'solving' a block, and that reward is encoded as a 'coinbase' transaction, which is the first transaction in the block, and thus contributes to the Merkle hash tree root in the block header. Different miners thus use different block headers and even if they all search the same nonce space from 0 to 232-1 they are searching different hash inputs.

Second, since mining became competitive, and especially since it moved to GPUs and then ASICs, mining doesn't really consist of "find a (or the) nonce for a block making it satisfy the difficulty/target". At difficulty significantly more than 1 (and it's currently in the trillions), most possible and attempted blocks are not satisfied by any nonce value. Instead mining consists of "find a block, and particularly an extranonce in coinbase, for which any nonce satisifies the current difficulty/target, and use that nonce". Over 99.999999% of atttempted blocks are losers, and to determine a block is a loser the miner must try all 232 nonces, which takes the same work regardless of the sequence tried.

For pool mining, which has now become popular, there are multiple miners seeking the same reward (i.e. one paid to the pool), and in that case the pool manager does allocate different extranonce ranges to members to avoid duplication and increase the probability that the pool as a whole (though not any specific miner) wins.  Since members must communicate with the manager anyway in order to earn rewards for partial solutions, there is no need or benefit of distributed random choice over centralized deterministic choice.

  This way, the miner would make use of the birthday attack, which would make the probabilities of finding it higher (for a given number of trials).

Bitcoin mining is not a birthday problem at all. Starting at different points or using different sequences of trials is not a birthday attack, and does not on average improve a birthday attack. It can improve competitive performance in some cases, but as described above none of those cases apply to Bitcoin mining.


Do hash collisions persist if a file is modified?

TL;DR: when using SHA-1 or similarly weak hash, include unpredictable data at the beginning of the message.

Simplifying, there are three kinds of attacks to fear on practical (iterated) hashes that result in a collision, that is where the attacker ends with two different messages (of the same length) having the same hash. From easiest to hardest:

Collision attacks: the attacker can choose per operational constraints one meaningful prefix and one meaningful suffix. Messages are of the form
I will pay you $1,000,000.00 (Qn47y2NXu49ssmexutgno5!QsmtxG) have a nice day
I will pay you $1,000,000.00 (eCW3Y!=jLJK;q&vM+;gdPZma7JAP4) have a nice day
An example of such attack against SHA-1 is shattered.
Chosen-prefixes¹ collision attacks: the attacker can choose per operational constraints two meaningful prefixes (of equal length) and one meaningful suffix. Messages are of the form
I will pay you $1.00 (G&RyUbpwgnn6dYbkLLnkx2WqMu5RVZ!QsmxyG) have a nice day
I will pay you $1,000,000.00 (KE2nFdwUizu;uo!BKgSB$c&ULEQ!R) have a nice day
An example of such attack against SHA-1 is this recent paper.
Second-preimage attacks. The attacker can choose per operational constraints one of the two messages in full, the prefix of the other message, and have the two messages share a suffix. Messages are of the form
I will pay you $1.00 on presentation of this signed message, have a nice day
I will pay you $1,000,000.00 (48CMWaAb5gt9RopNsgw!W2&o9x54e) have a nice day
There is no example of such attack against SHA-1, nor even against MD5.

Note: the arbitrary portion typically has a minimum length of a few blocks (32 or 64 bytes for common hashes).

Note: depending on how the messages are interpreted, collision attacks (1) can still result in two messages  with appearance entirely under the adversary's control. In particular, it may be possible to have a prefix that selects between two arbitrarily different appearances both encoded in the suffix, with the one displayed according to one bit in the arbitrary portion. The prefix of the shattered attack was chosen to allows that for PDF documents. This trick can be played with images, executable code..

Attacks 1 and 2 can be useful to an adversary only when sh/e can chose part of the signed message, e.g. for messages like
I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw, have a nice day

  Can I protect myself by including some of my own text before signing?

Yes, but not quite per the method illustrated in the question. You can protect against collision attacks and chosen-prefixes collision attacks (1 and 2) by including some unpredictable data at the beginning (in the first block) of the signed message. E.g.
My Ref BzCP3dFT. I will pay you $1.00 per invoice PkictdyAxvaokEeTtEkVYEG24UYtK4GLiTqCWHtw

This technique is used by savvy certification authorities when generating digital certificates with unpredictable Certificate Serial Number. This guards against chosen-prefixes collision attacks where the prefixes include a predictable CSN and two different domain names (one the attacker's target and the other under control of the attacker), and some of the arbitrary data belongs to public keys.

  Can the attacker simply add the same text to their contrived file and get the same new hash?

Yes, the attacker can easily add or alter a suffix of two colliding messages. That's why the unpredictable data must be at start.

  Will my added information counteract the contrived information of the attacker?

Only if the addition is early enough in the message (e.g. first block), and if the adversary can not perform attack 3 (second-preimage). Critically, the unpredictable data must be at the start of the hashed message. It is pointless to add unpredictable data in the appearance of a PDF document or other structured message.

  Could an attacker add some obscure contrived information in advance (that gets committed and signed or whatever) and then introduce the malicious code later when the timing was right?

Yes, but only if the attacker (able to perform attack 1 or 2) can predict what's before the portion s/he has under control. This is avoidable when preparing a zip file, then hashed (and e.g. signed or referenced by hash): the zip creation process can add a random header, making attacks 1 and 2 infeasible. This is not avoidable when an adversary can post a whole file and the integrity of that file is insured per the hash of that file (attack 1 is enough for many file formats including most executables).

¹ Often written just chosen-prefix (collision).


Size and usage of lookup table in cryptographic schemes

This is a very / too generic question:

  Q1: What size is considered reasonable?

Any size that fits easily in the CPU cache(s) of the target platform. Otherwise it depends on the memory requirements for the algorithm in general.

  Q2: What make them (in)efficient?

If the CPU data cache needs to be refreshed continuously then they may slow down the algorithm and, if you're unlucky, leak side channel information as well.

  Q3: Are there heuristics to determine (without implementing anything) if a table will become interesting?

Probably not as it depends a lot on specifics of the underlying platform.

In general lookup tables are used to speedup calculations, so as long as the resulting implementation is faster, you're in business.

But note that there may be security implications when using them, all depending on what is being implemented.


Argon2id internal iterations vs multiple Argon2id calls ?

I'm adding my solution here for the record.

Rather than calling multiple times the Argon2d function when the user sign in, we can do something smarter, with a research of the best settings when the user sign up.

We can inform him we will take few seconds to adjust the security while 5 ~ 10 seconds. So if the browser block the process and warn the user, he's already informed and can let continue the process.

Technically, we trying different settings from the lower values (1MB / 1 iteration) until the delay measured require at least 1 second. Then, we could save the settings to use for this user's device. When the user sign in, we simply use the associated settings, and this will not take more than 1 ~ 2 seconds. So in theory this shouldn't be blocked by the browser, and we increase security in following the device's capabilities.

Some real tests:

Apple iPhone 4S (512MB - 1Ghz): ~1.7s ==> m=1MB,t=1
Apple iPhone 5 (1GB - 1.3Ghz dual-core): ~1.2s ==> m=4MB,t=1
Samsung S8 (4 GB, 2.3GHz / 1.7GHz quad-core each): ~1.4s ==> m=24MB,t=2
NUC i3 (8GB - 1.7Ghz quad-core): ~1.4s ==> m=24MB,t=2

Any feedback are welcome.


Verification in Threshold RSA or Threshold Paillier

This is to ensure $v$ is in the cyclic sub-group $G$ of $Z_N^*$ that has a large enough order $m=p'\cdot q'$. Moreover, with a large probability $v$ is a generator of $G$, so that $v_i=v^{s_i}$ is a one-to-one mapping from $s_i$ to $v_i$, which is important when proving correctness of the shares.


Decode & Verify Base64urlUInt-encoded RS256 Public Key from Google

Both values are unsigned, big endian values, encoded as base-64-url. Basically that means that there is no sign bit and that the most significant bit is all the way to the left (bit B_7 - zero based indexing - on byte index zero). So you first need to base-64-url decode the values and then convert them to a big number. Finally, you need to combine both big numbers to form the public key, by providing the numbers as modulus $n$ and exponent $e$.

If you cannot combine the numbers to a public key you may need to encode the public key as PKCS#1 public key or SubjectPublicKeyInfo, which is an X.509 structure. For both these operations you either need to create the encoding yourself (which is pretty hard) or you need to have access and understand how to use an ASN.1 library.

You may want to have a look at the RSA public key interface in the "hazmat" cryptography package, with load_rsa_public_numbers and public_bytes(encoding, format) with PEM and SubjectPublicKeyInfo.


Transfer and hide ciphertext with hash functions?

Yes, you can use a hash to "hide" messages like that. However, I don't see any advantage of this compared to normal symmetric encryption, which already is able to return a well randomized ciphertext.

Randomization in itself is not steganography as I've understood it. A fully randomized message may stand out, both on its own and when simply copied into a message. Let's perform a little thought experiment: with a bit of trouble you can create a block cipher with a block size identical to the output size from a hash function. I don't see how your scheme would be any different from that particular cipher or fare any better in hiding the plaintext / ciphertext.

Lets look at the drawbacks:

First of all, there is this relatively high amount of work to be performed by the receiving party.
Second, the method scales terribly bad. You can probably only have $2^{32}$ plaintext / ciphertext pairs, and that's already stretching CPU resources.
Thirdly, the ciphertext is much larger than it needs to be, even if it is static and limited to the output size.
And finally, as there is no IV, it is not semantically secure if you'd send multiple messages as the ciphertext would repeat.

As for the 4th point: introduction of a fully random IV send with the ciphertext is of course possible, but it would expand the ciphertext even further.

I can see some advantage if this code is used when a hash is already used, e.g. when authenticating an unencrypted message (or encrypted message with a known size) in signature generation or HMAC. In that case the other data is already present and doesn't need to be guessed. The scheme could then be used to create a subliminal channel, which is related to steganography I guess.

Of course you would want to make sure that the additional message is stuck at the end, rather than in front, so that you only have to hash the send message only has to be hashed once (except maybe for the last block). As for signature generation: you'd probably want to use PKCS#1 v1.5 padding to retrieve the full hash. Note that for signatures an adversary will be able to see that the original hash / signature doesn't verify, which kind of negates the hiding of the message.


What does the comma mean in m, c := E(K, m)

It's a comma to separate the two things.  Alice has $m$ and can calculate $c$ which is equal to $E(K_{e}, m)$.  Bob has $c$ and can calculate $m$ which is equal to $D(K_{e}, c)$.


RSA can not directly encrypt large data.
You need to generate a random key for a symmetric cipher (secure random), encrypt the large data with this key using a secure mode (e.g GCM).
encrypt the key with your RSA public key,
prepend encrypted key to encrypted data.
store.
This is just for understanding of what goes on, you should look for a library which does as much of this together as possible from a reputable source, start with libsodium which I believe has a pure JS implementation.


Use AES in Web Crypto with public/private key pair

No, it is not possible to achieve this with AES.

AES is a block-cipher and AES-CTR is a symmetric encryption scheme. In particular, it is therefore not a public key encryption scheme, and there do not exist any public keys for it.


Single public key for NaCL signing and encryption?

Is there some safe way to sign the private key used for encryption
  with the signing keys?

What you're talking about is also commonly referred to as "keychain" or "keyrings", a concept popularized by programs like GPG, which do exactly this:
They generate one master signature key, which you securely distribute and which then "certifies" the other public keys to belong to you. This way you can keep your master key offline and only use to sign your everyday encryption public key and your everday signature public key.


In general, no, you won't be able to find the key. The amounts of possible permutations that may be used by a block cipher is staggering. It's much higher than the key space itself. So without somehow breaking the algorithm you're out of luck.

Many cryptographic attacks require staggering amounts of storage to be even reasonably successful in bringing down the security of a cipher significantly. In that regard the increase of storage capacity is certainly beneficial. More storage capacity can certainly aid cryptanalysis. But that's something different as having a lot of pre-generated ciphertext.

Having lots of ciphertext can certainly aid attacks. Those attacks are however not so much on the block cipher itself - and, by implication the key - but on the mode of operation. Many modes of operation have maximum inputs or restrictions on their use. There are certainly protocols do not sufficiently take these into account. This can lead to repetition of blocks being used as input for the block cipher; this information can be used to leak information about the plaintext (rather than the key).

Stream ciphers are possibly more vulnerable against this kind of attack. There is no proof that these ciphers are secure so finding a pattern in a stream cipher may be somewhat easier than finding one in a block cipher. It's still not all that likely that you'd find a key though, other properties (such as the key stream being biased) are more likely to fail first.

It's very unlikely that you can find the key without performing an explicit attack on the cipher. Just looking for patterns isn't going to help you. Mercury isn't rising.


RSA encryption and decryption not resulting to the correct result?

Your $d$ is wrong, double check your EEA calculation. You picked up the wrong Bezout coefficient from $7795\times 402294340 - 67998447\times 46117 =1$. You should use
$d= -67998447 \equiv 334295893 \pmod {\phi(n)}.$


Even with PBKDF2, You wouldn't be able to use salt anyways, because salting relies on a one-to-one mapping between the salt and a user identifier (email). You cannot keep the email, so you wouldn't know which salt to use when a user comes back with his email.

Simply iterating SHA 256 for a large number of times is a way to discourage preimage searching. Other (more solid) cost-incurring algorithms include scrypt. Although time-space balance attacks still work if you don't have salt to work with. (Using SHA, possibly inserting large constant data after input string to further slow it down).


Why invent new hash functions for zero-knowledge proofs?

Let us see an example of how cryptographic hash functions are used in Zero-Knowledge Proof Systems. Following code written in Zokrates DSL Toolbox is an example of computing a Hash using Zero-Knowledge Proof systems. The programming instructions are compiled first. Then we will proceed to the setup of the arithmetic circuit through the setup. Then we export the verifier and will compute the proof.

import "hashes/sha256/512bitPacked" as sha256packed

def main(private field a, private field b, private field c, private field d) -> (field[2]):
    h = sha256packed([a, b, c, d])
    return h

Let us also analyse another code example to construct a Pedersen Hash in the construction of a Zero-Knowledge Proof using Zokrates Toolbox.

import "hashes/pedersen/6bit" as pedersen

def main() -> (field):

    field[6] e = [1, 1, 0, 0, 0, 0]
    field[2] d = pedersen(e)

    5483803361072598088157572477433311028290255512997784196805059543720485966024 == d[0]
    8712718144085345152615259409576985937188455136179509057889474614313734076278 == d[1]

    return 1

As we can see in these two examples, proving the knowledge of a preimage under a cryptographic hash function expressed as a circuit over a large prime field becomes one of the most computationally expensive parts in the arithmetic circuit construction in a zero-knowledge proof system. Hence all the pursuits for inventing SNARK and STARK friendly cryptographic hash functions are greeted with much of enthusiasms!

The paper mentioned in this question claims a reduction in the number of constraints per message bit than Pedersen Hash which would potentially improve the performance in the construction of polynomial commitments for ZKSNARK. Likewise, the proposed binary hash function STARKAD could be beneficial in the construction of ZKSTARK based systems in the near future.

  Our hash-function Poseidon uses up to 8x fewer constraints per message bit than Pedersen Hash, whereas our binary hash-function Starkad wins by a substantial margin over the other recent designs


Is there a method to combine encryption and ring signing?

Yes, like there are conventional signcryption schemes combining digital signatures with encryption into a single primitive, there are also ring signcryption schemes that realize the same for ring signatures and encryption. Look for instance here or just ask Google scholar.


Standard lightweight one-way hash functions for IoT devices

Here you have a study about different cryptographic methods in different IoT devices:
Midgar: Study of communications security among Smart Objects using a platform of heterogeneous devices for the Internet of Things
In this study, the authors (Sánchez-Arias, García, and García-Bustelo) explain the time that the different methods need to send messages and a comparison between the methods, about their current state and about the time that they needed.

Abstract
In last years, the Internet of Things has been a revolution in terms of applications and research. Currently, there are a great variety of nodes connected to each other to create different applications in areas, ranging from sport to business, inter alia. These applications compromise our private information about our bank accounts, health, and location. This makes us take safety measures to achieve a secure communication, where the interception of a message by a malicious user cannot compromise our privacy.


Using keys as Additional Authentication Data in GCM

Yes, we don't send the keys directly. One must keep the keys secret, all the time!
Instead, we send the key with a public key cryptosystem like RSA-KEM or better apply key agreement like Diffie-Hellman Key Exchange (DHKE) and better use Elliptic Curve version (ECDH). If you looking at some existing libraries look at libsodium or the age libraries for existing good implementations.
AAD is not mean to be secret, rather open and can be a part of the protocol like the record number, etc. It is additional information incorporated into the authentication tag calculation. Thus any change in AAD will be detected.
Digest commonly referred to as keyless hash, the GHASH, on the other hand, uses a 128-bit key to derive the authentication tag. If you insist, you can use it as a keyed hash function, too. But rather prefer HMAC instead of GHASH.


How to fairly select a random number for a game without trusting a third party?

The answer you posted is actually correct (more or less, see below): have each participant commit to their random number $r_i$ by publishing, e.g., $\mathcal{H}(r_i)$ in the first round. And then in the second round, each participant opens the commitment by publishing $r_i$ and everyone checks that it matches the committed value by hashing it. The final random number is the XOR of each $r_i$.

The commenter there suggested an attack if there is a collision. However the definition of a secure hash function is that its collision-resistant. For a good modern hash function like SHA256, that is the case.

There are two subtleties.

The first is that your scheme only works for large random number, large enough that an attacker couldn't try every possible value for $r_i$, hash it, and see if it matches. For committing to small values, you need a randomized commitment function. Good randomized commitments are based on discrete logarithms but you could construct one (with reasonable safeness) using a hash function by generating a large random value $a_i$ and then computing your commitment as $\mathcal{H}(r_i||a_i)$. To open, reveal both $r_i$ and $a_i$. To change $r_i$, you'd have to find a different $a_i$ so that the hash is the same: this is hard based on collision resistance. The bitlength of both $r_i$ and $a_i$ must be predetermined so it is clear from $r_i||a_i$ where to split the value into $r_i$ and $a_i$ (otherwise you could open it to different values by simply splitting in a different spot).

The second subtlety is that the last participant to reveal his value will learn the accumulated random number before he reveals his number (he can see everyone else's number and he knows his own). This may cause him to abort if he doesn't like the result. You can do more complicated things to provide fairness, but generally if any participant refuses to open their commitment, the protocol should be restarted from the beginning with that participant excluded.

Also read this answer from @D.W. on a different question where (s)he explains the same protocol.


Yes. If you are looking for AEAD ciphers wrapped around a single primitive, there are several in the CEASAR competition for authenticated encryption.

AEAD ciphers based on sponge constructions notably use only a single primitive, the F-function of the sponge permutation. These include NORX, Keyak, PRIMATEs-APE, and ICEPOLE, which are the 4 I find most interesting.

All of these use a central permutation, which generates a stream to encrypt the plaintext, accepts the plaintext to change the stream generation state, and finally generates the authentication tag.

Keyak also offers the ability to generate intermediate tags, so a ciphertext error can be caught before transmission is complete. NORX, ICEPOLE, and Keyak offer a parallel sponge mode to improve performance, and PRIMATEs-APE and ICEPOLE offer a secret message number to make them nonce misuse resistant under certain conditions. I believe Keyak has been modified to offer incremental addition of associated data, which PRIMATEs-APE also offers.

I have not looked at the permutation based ciphers, but they may also be built from a single primitive.

It is possible to build a block cipher mode to create a single primitive AEAD cipher, but it would have a performance deficit against purpose built ciphers. I built one over AES, and it is reasonably fast, almost as fast as OCB per block with longer startup and finalization. Making it purpose built around the AES round function makes it even faster than OCB with hardware acceleration, but as a mode it can be used with any 128-bit block cipher. My motivation was the complexity of generating the OCB offsets in 32-bit code.


Can the person who decrypts a homomorphically encrypted value know what operations were run?

No, not with SEAL at least. The noise is basically a measure of how much uncertainty there is after the operations are performed. Past a certain point there is simply too much and the decryption may be affected by it (the noise does not "round off" correctly), after which decryption may result in incorrect values. Because of this the "noise budget" is used in the library (invariant_noise_budget). Your results can safely be decrypted as long as the noise budget is positive.

It would probably be possible to gather some information about which types and how many operations (for some operations) occurred by analyzing the noise. Certain operations (rotation for example) do not consume the noise budget and would therefore be undetectable by a noise-analysis attack that depends on the amount of noise. Assuming SEAL does not have any huge flaws in it there shouldn't be any attacks that will let an attacker list out exactly which operations occurred.


I've heard hash values referred to as hash checksums, so my question is whether hash functions use some sort of polynomial division as well?

No, they do not.

Actually, the original meaning of "checksum" has nothing to do with polynomial division at all; instead, it was just a simple sum used to detect errors.  The usage has been generalized to mean anything added to the data to detect random errors; a CRC does that, and a hash of the data could be used as well.

These both work well about detecting random errors.  However, since we're in crypto stack exchange, we also get to worry about deliberate changes made by an intelligent attacker; in that case, neither CRCs nor hashes help (as the attacker can easily compute the CRC/hash of the modified data).  If this is the problem space you're in, you need to use either a Message Authentication Code or a Signature; they both depend on secret information that the attacker does not know.


Why is this authentication protocol with a nonce and tree parties not secure?

Suppose that the client and server were once connected by random number $N$, and adversary is eavesdropped these messages. So he has $I_C$, $N$, $E(K_{C,A}, N)$, $E(K_{S,A}, \{I_C, E(K_{C,A}, N)\})$ and $E(K_{S,A}, N)$. Now in the new session, the adversary can easily impersonate the identity of the server. To do so, just follow the steps below:

C⟶Adversary: $I_C$

Adversary⟶C: $N$

C⟶Adversary: $E(K_{C,A}, N)$

Adversary⟶A: $E(K_{S,A}, \{I_C, E(K_{C,A}, N)\})$

A⟶Adversary: $E(K_{S,A}, N)$

Note that in this protocol, the server can use $E(K_{S,A}, N)$ to verify client identity, but the client does not have any information about the identity of the server.

Edit: Also, an adversary cannot impersonate the client using $E(K_{C,A},N)$ because $N$ is generated by a valid server and will change in each session. Therefore, an adversary cannot find the valid $E(K_{C,A},N)$ using previous eavesdropped messages. To prevent this attack, you can modify the protocol as follows:

C⟶S: $I_C$

S⟶C: $N$

C⟶S: $E(K_{C,A}, N, M)$

S⟶A: $E(K_{S,A}, \{I_C, E(K_{C,A}, N, M)\})$

A⟶S: $E(K_{S,A}, N, E(K_{C,A}, M))$

S⟶C: $E(K_{C,A}, M)$

However, this is just a change, and the resistance of this protocol to other attacks should be investigated. "Cryptographic Protocol: Security Analysis Based on Trusted Freshness" By Ling Dong and Kefei Chen, is a valuable book on protocols that you can refer to for more information.


The math goes: add the integer assigned to a, the integer assigned to z, and from that constant (which can be pre-computed) subtract the integer assigned to the letter to encode; that gives the integer assigned to the encoded letter.

This works for a to z and encodings with consecurive letters of the alphabet assigned consecutive integer values (including ASCII; assigning 0 to a and 25 to z; assigning 1 to a and 26 to z). Usual associativity and commutativity rules for addition in $\mathbb Z$ are enough to prove that a is encoded to z, and vice versa. The rest follows by uh, intuition? Or induction if we really strive for rigor.

In C, that gives

char Atbash(char x) {
  return ('a'+'z')-x;
}


Orthogonal generators of a group in Lelantus protocol

A GUESS: the author meant that three numbers $a,b,c \in \mathbb{Z}$ such that $$g^a\cdot h_1^n \cdot h_2^c =1$$ are infeasible to compute. While the term "orthogonal" seems inappropriate, This is a fairly standard assumption.


What are usable entropy sources in a headless machine without /dev/random or any cryptography API?

I believe that on any CPU that you should be able to find at least two sources of noise with physically proven behaviors to create a purely random number.  The first is through oscillator sampling, assuming that you have a fast clock and a slow clock.  The second assumes that you have DRAM, and through the two-way shot noise in the channel, you should be able extract random bit flips in DRAM if you can control the timing.

Clock Sampling

The clock in a system is not a precise as you'd hope.  Generally, you have a core clock that is generated through a PLL, and you also have some sort of realtime clock at 32.768kHz because that will overflow after bit-15 to give you a 1-second pulse.   By sampling the fast clock with the slow clock, you can generate a series of bits; however, there's a few caveats:

oscillator jitter alone is not enough to create randomness
you can actually degenerate the randomness by trying to make it random if you have a poor circuit model.

As an x86 was mentioned (I know the least about this CPU btw), the time stamp counter combined with a 8254 on older machines or HPET on newer machines will get you a fast and a slow clock source.   Michael S. McCorquodale dissertation should have a very good analysis on the clock jitter in both cases, or at least he did at this defense.

DRAM

If you can control the timing of the DRAM, you very likely could get a random noise source due to the fact that the noise in a semiconductor channel is a function two-way shot noise (and not classical Johnson Noise). Let's limit the scope to a single bit.  You would have to put charge on the DRAM capacitor and then gradually delay the timing until that bit gave you a 1 or 0.  The charge amplifier on the DRAM rows would also add to the noise, but I will ignore that component for now.  Carver Mead and Rahul Sarpeshkar both use shot-noise in their neuromorphic engineering papers as a source for entropy on silicon neurons, and circuits people can derive it but I really don't know where an external reference is.  The caveats:

DRAM timing control
assume that you are not near "freeze out" as the shot noise goes away.

I believe that either of these, combined with a hash, could be used as a means to generate a true random number as the noise sources are rooted in physics.  You'll need to grab a cryptographer to take what I described to the next step.


Rejection Sampling reasoning for Lattice Based Signatures

Narrow means that, with high probability, the ouput of the distribution is is small.
Small is meant in the sense of the Euclidean norm of a vector in the Euclidean space $\mathbb R^n$. More concretly, $v$ is informally said small to mean $\|v\| \leq B$ for some value $B > 0$ chosen large enough for a given scheme to work out, but small enough for the lattice problem SIS to remain hard.
It is not a problem outside lattice based crypto because in a finite group $G$, if $x \in G$ is uniform, so is $x+c$. We can't simply do that over an unbounded space such as $\mathbb R^n$.


Is there any Private Set Intersection scheme that only leak whether intersect or not without the real intersection value?

What you are asking for is also known as a test for disjointness of private datasets.

Kiayias, who introduced this problem in 2005, called a protocol solution the Private Intersection Predicate Evaluation (PIPE) protocol.

Reference:
Kiayias, Aggelos, and Antonina Mitrofanova. "Testing disjointness of private datasets." In International Conference on Financial Cryptography and Data Security, pp. 109-124. Springer, Berlin, Heidelberg, 2005

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.61.7661&rep=rep1&type=pdf


Is DDH hard in the subgroup of order $2q$ of $\mathbb{Z}_p^*$

No, it is not.

If you define the function $F(x) = x^{q} \bmod p$, then for any $x$ is\n the group of order $2q$, we have $F(x)= 1$ if $x$ is a member of the proper subgroup of order $q$, and $-1$ if it is not.  And, exactly half of the elements will be in that subgroup.

You will always have an even number (either 0 or 2) of $F(g^a)$, $F(g^b)$, $F(g^{ab})$ be -1; if you find that an odd number of $F(g^a)$, $F(g^b)$, $F(g^c)$ be -1, then you have determined that is not a DH triple.

This logic applies to any group that has an order with a small factor.


Is it possible to affect the output of HMAC w/ SHA-512 by providing it with a custom message?

Consider an HMAC algorithm that uses SHA512 with an unknown private key. Is it possible to affect its output, either partially or totally, by providing it with carefully crafted messages?

Sure, however you will get totally unrelated HMAC output even if you change (or add or remove) even a single bit from the HMAC input. So each bit flips with a 50% certainty. Creating "crafted messages" doesn't have any effect on this property.

If you are looking for a specific output then you won't be able to get it, assuming that at least, say 64, bits of HMAC output is kept (if that's the case you might try and brute force). Similarly for other properties, the outcome of HMAC is totally dependent on chance if you don't know the key and /or input message.


Does AES CTR mode store header information in encrypted files?

I would like to ask if that is true for every AES CTR mode implementation?,

Doesn't have to be. You can store the nonce anywhere. You could even send it to the recipient via a different channel (e.g., email the ciphertext and use SMS to transmit the nonce). Storing it at the beginning has its advantages. For example, if streaming the data, you can begin decrypting immediately.

  and If we want to decrypt a certain block from the middle, we first have to extract the nonce from the first 8bytes and block count in the second 8 bytes ?

Yes, if you want to decrypt a particular block in the middle, you must extract the nonce first, and figure out what the proper counter value should be. Then you can decrypt.


If PRF is non invertible, why does Ctr-mode work?

CTR consists of two parts: construction the key stream using a counter, and XOR-ing the output of the key stream with the plaintext/ciphertext. The key stream can be generated using a PRF, in which case it is of course not invertible. The key stream can also be created using a PRP (e.g. a block cipher like AES) in which case it is invertible.

As indicated, CTR mode encryption requires the XOR-ing of the plaintext / ciphertext as well. A PRF is a pseudo random function, so given the same input it will generate the same key stream. The XOR-ing of the key stream is perfectly reversible; you just have to perform the XOR with the key stream again. So CTR mode encryption is always reversible, even when it relies on a PRF to generate the key stream.

Because of this, CTR-mode is indeed not a PRF.


Just for completeness sake, CBC is defined as follows:

The error you have made is that:

$$M;N = (M_1, ..., M_n, N_1 ⊕ \mathbf{T_m}, N_2, ..., N_n)$$
(I've changed notation from M||N to M;N to reflect this isn't just concatenation)

You need to cancel the tag from the message $M$, not the tag from the $N$ message.
In that case, $T_{M;N}=T_N$ as required.


The Inverse Affine Transformation of AES Sbox uses different additive constant?

Those are, of course, two equivalent ways of writing the same function, so it really doesn't matter which one you use.  If you're implementing AES, you can use whichever form of the S-box you find more convenient — or even something else entirely, as long as it gives the same results.*

That said, it's often desirable to share as much code and/or circuitry between the encryption and decryption implementations as possible.  Thus, it can be convenient to implement the forward and reverse S-boxes so that they have the same mathematical form.  Thus, if you're going to implement the forward S-box using formula (1), it can make sense to implement the reverse S-box using formula (3), since the only difference between them is the choice of constants.

*) Of course, however you choose to implement the S-box, you'd typically want to make sure that it runs in constant time and doesn't leak any sensitive data via any other potentially exploitable side channels.


How to adjust scrypt parameters for Moore's Law?

Can formulae for equivalent year cost be constructed to determine the parameters as functions of time since those tests were performed?

Yes, but you have to make a lot of assumptions. First, though, note that the paper says:

  We caution again that these values are very approximate [...] Nevertheless, we believe that the estimates presented here are useful for the
  purpose of comparing different key derivation functions.

The estimates are not necessarily very accurate as absolute values, but only in relation to each other. They are based on numbers from 2002.

That said, there are three parameters to tweak in scrypt: $N$, $r$ and $p$. Increasing $p$ increases only the computational cost. Increasing $r$ or $N$ also increases memory use. The effect of $p$ is easiest to estimate:

Doubling $p$ doubles the time taken per try, so the attacker needs twice as many devices to calculate the same number of hashes in a year, so the attack cost doubles.

Now how much cheaper has computing power become since 2002?

A 2002 Northwood P4 had 55 million transistors while a 2014 Haswell i7 has 1.4 billion. That's about a 25x increase.
The 2002 130nm process could put about 0.38 million transistors on a square mm, while the 2014 22nm process can put 7.9 million. That's about a 20x increase.
The "doubles every two years" version of Moore's law implies a 64x increase.

Conservatively, then, you could increase $p$ from 1 to e.g. 64 to account for the increased performance/\$ potential, but that would likely increase the time it takes significantly, at least unless your implementation is parallelized (for $p>1$ the different SMix invocations can be calculated in parallel).

Increasing $N$ would be even better, because of the increased memory use – not only would the attacker need twice as many devices, but each of those would be more expensive as well. However, the effect of that is more difficult to estimate. Additionally, that may not be doable in a low memory environment, like mobile or in the browser.

In practice, I think a better approach is to set a target time and find the highest numbers you can use and still make a target time.


Is BLS signature scheme strongly unforgeable?

BLS signatures are computed by hashing the message $m$ from the message space $\mathcal{M}$ to a source group of a bilinear pairing $e: \mathbb{G} \times \mathbb{G} \to \mathbb{G}_T$ using a hash function $H: \mathcal{M} \to \mathbb{G}$ and exponentiating $h$ with the secret key $x$, i.e., a signature $\sigma$ is of the form $$\sigma := H(m)^x.$$

The hash function maps each message to a uniquely determined value (there could be multiple messages which are mapped to the same value), and $x$ is fixed by the public key $g^x$. This means that BLS signatures are even unique. That is there is only one signature for each message. This is an even stronger property than unforgeability, i.e., every existentially unforgeable and unique signature scheme is also strongly existentially unforgeable.

For more details, one could refer to Hovav Shacham's PhD Thesis (one of the inventors of BLS signatures). He also argues that he does not further consider strong unforgeability, as the schemes presented in his thesis (including BLS signatures) are all unique (cf. Page 19 before Definition 3.2.1).


Lamport-Diffie + attempting to invert OWF

The only requirement is $i,b \neq i^*,b^*$ where $i^*$ is a random value from $1$ to $l$ and $b^* \gets\{0,1\}$ So if $b^*=0$ then $b=1$.

Don't get confused by the $x$, it has nothing to do with the secret key, it's just a variable that later becomes $y_{i,b}=f(x_{i,b})$. It could as well be called $a$.


Can I construct a PRP by sorting results of a PRF?

Even if this worked in principle, I don't see how this could possibly be practical to implement for any but the smallest sets, since it requires you to enumerate (and sort) the set you want to permute.

Also, it seems to me that, unless the codomain of the PRF is much larger than its domain, you're going to have an issue with ties, i.e. with inputs $x_1 \ne x_2$ for which ${\rm PRF}(x_1) = {\rm PRF}(x_2)$.  I don't see any obvious way to break such ties that could not be potentially used to distinguish the resulting PRP from a random permutation.

All that said, if you really just want to pseudorandomly shuffle a small set of values, feeding each of them to a PRF with a sufficiently large domain (like HMAC-SHA256) and sorting the values by the result should be a perfectly good and secure solution.  Specifically, consider an adversary that tries to distinguish your pseudorandom shuffle from a truly random shuffle.  For such an adversary to succeed (with probability greater than ½), they must either:

somehow distinguish the PRF from a random function, or
observe a collision among the PRF outputs.

The probability of option 1 will depend on the PRF (and on the assumed capabilities of the attacker), but it must be negligibly small for all practical attackers for the PRF to be deemed secure.  On the other hand, assuming that the PRF is not distinguishable from a random function, the second probability can be calculated:

Specifically, given $k$ inputs to a PRF with an $n$-element codomain (where e.g. $n = 2^{256}$ for HMAC-SHA256), the probability $p$ of observing at least one collision is less than the expected number of collisions, which itself equals $\frac{k^2 - k}{2n} < \frac{k^2}{2n}$.  Thus, for example, if $k \le 2^{64}$ and $n = 2^{256}$, then $p < \frac{(2^{64})^2}{2\cdot2^{256}} = 2^{-129}$.


Can specific Weierstrass curves be some benefit from Montgomery/Edward form?

Curves P-256 and Secp256k1 cannot be converted to Montgomery or Edwards forms because they are of prime order.

Let's take the example of Secp256k1 and try to convert it to a Montgomery curve:

A Montgomery curve $by^2=x^3+ax^2+x$ has a point of order 2. Such a point verifies $2P=\mathcal{O}$ or think of it equivalently $P=-P$ which means $(x,y)=(x,-y)$ so these points are on the $x$-axis. It is obvious then that the point $(0,0)$ on a Montgomery curve has order 2. Now given the secp256k1 curve $y^2\equiv x^3+7 \pmod p$ where $p=2^{256}-2^{32}-2^9-2^8-2^7-2^6-2^4-1$, we are looking for points on the $x$-axis which means those that satisfy $x^3 \equiv -7 \pmod p$. There is no solution to this modular cubic equation.

In general curve P-256 and Secp256k1 cannot be converted to Montgomery form because they have a prime order ($\ne 2$) and thus they cannot have a point of order $2$ (otherwise $2$ would divide a prime number beacause of Lagrange's theorem).

The same reasoning works for Edwards curve $x^2+y^2=1+dx^2y^2$ because the point $(0,-1)$ has order $2$ and the points $(\pm 1, 0)$ have order $4$.