SHA-1 – Would using a SHA-1 CSR be a risk?

No, it is not. The SHA-1 attack requires pre-computation. It is basically not possible to get a hash collision for data that is not controlled by the attacker. You'd need the attacker and the submitter of the certificate signing request to cooperate to create two different CSR's that have the same hash value within the signature calculation / verification.

Even then, it makes no sense to do this. As you correctly identified the RA would validate the CN. So you would not have achieved anything (if the wrong CN is accepted then the RA code itself is at risk, and this would have nothing to do with the certificate request itself).

It may be good to note that the main reason for signing the CSR is for the CA to validate that the entity filing the request and the entity holding the private key are the same entity.

Regardless, using SHA-2 for CSR's should of course be preferred over using a broken hash such as SHA-1.


What is the computational cost of guessing symmetric keys for two ciphers that decrypt to the same input?

I stick to a symmetric, non-authenticated cipher; and unless otherwise specified I consider it as a black box.

By an entropy argument, for the problem to be consistently solvable, we need $m$ to be slightly larger than the key size if $m$ is known, or slightly larger than twice the key size if $m$ is unknown (I'll suppose that); otherwise, chance is that there are multiple solutions, and we have no way to find which is correct.

Things  depends on if $m$ is given or not, and if the cipher is deterministic (e.g. a block cipher, or one in ECB mode) or randomized (e.g. a stream cipher or a block cipher in CTR mode).

If $m$ is given and the cipher is deterministic, we can enumerate keys $K$ among $2^k$ (say incrementally), encipher $m$ with $K$, and conclude that $K$ is neither the desired $K_1$ nor $K_2$ when the ciphertext matches neither $c_1$ not $c_2$ (which is, most of the time). Our explored $K$ will include both $K_1$ and $K_2$ with probability $1/2$ after exploring $2^{k-1/2}$ keys (rather than $2^{k-1}$ for one key). The expected number of encryptions to find both keys is $2^{k+1}/3$ (rather than $2^{k-1}$ ), an increase by $1/3$. The expected work is increased slightly more (because of the extra comparison).

Per request: The number of encryptions is $\max(K_1,K_2)+1$. The keys behave as two uniform and independent discrete variables in $[0,2^k[$. As $k$ grows, the ratio of the expected number of encryptions to $2^k$ thus converges (quickly) to the mean value of the largest of two continuous variables in $[0,1[$. Thus a first-order approximation of the expected number of encryptions to find both keys is
$$2^k\int_{x=0}^1\int_{y=0}^1\max(x,y)\ \mathrm dx\ \mathrm dy=2^k\int_{x=0}^1\left(\left(\int_{y=0}^x x\ \mathrm dy\right)+\left(\int_{y=x}^1 y\ \mathrm dy\right)\right)\mathrm dx\\=2^k\int_{x=0}^1\left(x^2+1/2-x^2/2\right)\mathrm dx=2^k(1/6+1/2)=2^{k+1}/3$$

If $m$ is given and the cipher is non-deterministic, we can enumerate keys $K$ as above, decipher $c_1$ and $c_2$ with this key, and compare against $m$. As above, our explored $K$ will include both $K_1$ and $K_2$ with probability $1/2$ after exploring $2^{k-1/2}$ keys. However, until we have found one of the key, we need to decipher twice with each $K$. The expected number of decryption is $2^k$, twice as much as for one key. The expected work might be increased rather less, depending on internals of the cipher (e.g. for AES, the derivation of round subkeys can be shared between the two decryptions in the phase where neither key is available).

If $m$ is unknown, we can use a Meet-in-the-Middle attack: we decipher $c_1$ using all (or most) $K$, building a dictionary of possible $m$; then we decipher $c_2$ enumerating $K$, until we find the resulting $m$ in the dictionary. The expected number of decryption is $2^{k+1/2}$, three times as much as for one key and known $m$. A lot of memory is necessary, but there are workarounds at the cost of only moderately more work; see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website)

If we "open" the cipher's black box, things change, possibly sizably. In particular, for ciphers allowing on-the-fly encryption/decryption, we need not fully encipher/decipher a large $m$ in full. And for some ciphers (e.g. 3DES), there might be shortcuts.


No, that is not correct.  Assuming that the lock combinations are assigned randomly, and you have no apriori knowledge of the combination, you need 500 tries before you get a 50% chance of success.

What the birthday paradox means is that if you have 38 locks (not 33, and assuming that the combinations were assigned randomly and independently), there is a better than 50% chance there are two locks with the same combination.  This doesn't help you with finding the combination of any particular lock.


I have a concern regarding the security of the scheme -- let's suppose that there are only two possible messages, $m_0$ and $m_1$. Then, the encryption is done by multiplying, in the field, the chosen message with the $x$-coordinate of an unknown point on the curve.

What I highlighted is your problem; that is an invalid way of combining the point which is the result of the DH exchange with the plaintext.

In the standard El Gamal scheme, we use the 'modular multiplication' operation as the group operation within the key exchange, and hence we use that to combine the plaintext with the DH value.

So, when perform the operations on an Elliptic Curve, we do the same.  So, what you need to do is (somehow) convert the plaintext into an elliptic curve point, and add it to the point derived from the DH exchange; if the plaintext point is in the same prime-sized subgroup is the DH generator, you're safe.

Alternatively, you can just do ECIES, and not have to worry about translating plaintexts into points...


secp256k1: is it theoretically possible to generate same signature with different key, message hash and k?

We want $(r,s)$ same for two different set of $d,k,h$
In ECDSA

$r = x_0([k]G) \bmod n$ where $k \in [1,n-1]$ and $x_o$ is the x-coordinate of the scalar multiplication $[k]G$
$s = k^{-1}\cdot (h+r\cdot d)$ where $h$ is the left  most bits of $h$ to fit in the group order ( for simplicity we called it $h$ again).

Now we want same $(r,s)$ for $d,k,h$ and $d',k',h'$

$r = x_0([k]G) = x_0([k']G)$ although this may indicate that $k=k'$ it is not. The reason is that the coordinate field $p$ is smaller than the order $n$ of the base point. Therefore we can have solutions other than the trivial.

$s = k^{-1}\cdot (h+r\cdot d) = k'^{-1}\cdot (h'+r\cdot d')$,
then with $k'=k$ we have;
\begin{align}
   (d'-d)\cdot r &= (h-h') \\
  \end{align}
then with $k'\neq k$ with $c = k^{-1}$ and $c' = k'^{-1}$ ( for our eyes) we have;
\begin{align}
   c'\cdot h + c' \cdot r \cdot d &= c\cdot h' + c \cdot r \cdot d' \\
   c'\cdot h -c\cdot h'  &=  c \cdot c \cdot d' -c' \cdot r \cdot d \\
   c'\cdot h -c\cdot h'  &=  r \cdot ( c \cdot d' -c' \cdot d) \\
  \end{align}

As we can see by knowing $r$;
Either

we need to find a proper $d'$ for a given $d$ for given different hash values. This is free since we found the private key by just arithmetics.
OR, we need to find a message that produces desired hash value $h'$ so that we have equality. This is hard since we need to break pre-image resistance of SHA256.

As we can see it is possible but hard.
For the case $k'\neq k$ the calculations are similar.


Kryptos : K2. What is the origin of the “abscissa” keyword?

I think the best theory is crib-dragging the phrase "virtuALLYINVISIBLE" from the morse code sections. This will line up with "itwastotALLYINVISIBLE" from K2 and reveal the entire keyword, repeating and removing any doubts.

Come to think of it, it may very well have been the intension of Sanborn to have us decode K2 first by this method, and then from K2's ending (IDBYROWS/XLAYERTWO) derive the word palimpsest, because that´s basically what it is. One text scraped away to make room for another text and hinted at by the use of "LAYER TWO".


Is it possible to predict a randomly generated BigInteger that uses Java's default Random library?

Isn't the answer plainly yes by simple deduction?  The BigInteger constructor is simply a linear function as: BigInt ~ F(LCG).  Ergo if LCG is predictable, BitInt is too. It's not much deeper.

Could you do BigInt ~ F(SecureRandom)?


Strength and weaknesses of this JavaScript charCodeAt based login script

You don't need to brute force it. Since the passcode is the product of all its character codes, you can just find all prime factors of the passcode. I used an online tool which yields $2^6\cdot 3\cdot 5\cdot 7^2\cdot 61^2\cdot 97$. It looks like an ASCII passcode of length 5.

This doesn't get you anywhere since this is just a check for a web page to open. Now you need to "brute force" all possible combinations of $2^6\cdot 3\cdot 5\cdot 7^2\cdot 61^2$ ($97$ is more of less fixed to be a) and then try for each combination all permutations. You can further filter a little since only lowercase letters are used. For each permutation you would need to download the password+'.html' file. When you finally get an HTTP 200 code you're done.

Of course if you assume that every letter is lowercase then you can assume that $2\cdot 61$ is z. Now the question is to find a 5 letter word with letter zza in it.... The other prime factors will get you p and i.

Note that you only need to do this for passcode, usercode is not used.


Why does GPG ciphertext length differ with fixed plaintext length?

TL;DR: There are different possibilities: A timestamp is included before compression, and can result in slightly different compressed message lengths. The encrypted session key is stored as multi-precision integers, which are of dynamic length. Finally, ASCII-armoring adds a padding that might enlarge the size difference slightly.

Compression and Timestamps

When using OpenPGP, different operations are performed one ofter the other, you could compare them to multiple layers put around the original data. The message is wrapped with some meta information (the "literal data packet"), then compressed, finally encrypted. Often there are different alternatives in the individual steps, but in the end it mostly boils down to these operations. I especially ignore the fact OpenPGP is a hybrid cryptosystem, as this adds complexity but is not relevant to this question.

Using a kind of formula notation, you can simplify the operations as

encrypt(compress(literal(message, filename, timestamp)))

If you observe this, you will realize repeatedly encrypting the same message will always return another result: the timestamp is also contained as message metadata (there's also some randomness in choosing symmetric keys, but that's another story that leads to completely different crypto texts). As the timestamp is also subject to compression, different timestamps might compress worse or better, this can indeed lead to minor differences in the size of the encrypted message.

faketime

This might or might not be the only reason, but you should be able to easily evaluate using the handy faketime tool available for probably all unixoid systems. Most Linux distributions include it in their packet managers. It sets a fixed system time for the application executed. If the timestamp is the only reason for different message sizes, you should get messages of the same size now:

faketime 2015-12-02 gpg --encrypt ...

Multi Precision Integers and Session Key

The encrypted random session key used for encryption of the message is stored as multi precision integers, which do not have fixed length. Although these session keys are expected to be of similar size, the might be rare cases (one out of 256) that the encrypted key has all first 8 bits set to 0: as a result, the result can be stored with one byte less (and still being the same number). In very rare cases this might even lead to multi-byte differences.

ASCII armoring

Finally, ASCII armoring cannot be the reason for different sizes, but can enforce already existing differences because of padding the output to multiple of three bytes, adding up to two bytes if necessary (resulting in a message larger by only a single byte being padded by up two additional bytes).


MD5 hash: retrieve an element of a source string

TL;DR; The success depends on the size of the element3.

The MD5 pre-image resistance theoretically is broken bu not practically. Instead of the generic preimage attack with $\mathcal{O}(2^{128})$ complexity, there is an attack by;

Sasaki and Aoki: Finding Preimages in Full MD5 Faster Than Exhaustive Search, EUROCRYPT 2009.

This attack requires $2^{123.4}$ complexity. MD5, however, is not practically broken. You cannot reach the 123-bit search space in a meaningful time. Consider the collective power of BitCoin miners; in 2020/1/17 they reached 126.1314 Exahashes per second, that makes

$2^{67}$ SHA256 double hashes in a second, and
$2^{92}$ SHA256 double hashes in a year. So you need $2^{21}$ years with that power.

Apart from the above; we don't expect special data would make the pre-image attacks easier.

The below is totally depending on the size of the element3

  you can get element3 if there's a rainbow table which includes MD5_hash_output

Actually, using only once, a rainbow table is not necessary. You can build one with a special reduction functions; like $$R(md5(previous)) := \texttt{element1:element2:} \mathbin\| md5(previous)|_{target\;length}$$

The size of the table depends on your target length. It may not be possible to build one after $2^{63}$ (not an exact number) due to the memory requirements to process.

Instead of building the Rainbow Table, if it is only used once, just search the all possible space. As seen above, there is a limit on the search space that one can achieve in a meaningful time. If you somehow agree with all the Bitcoin Miners (though some of the use of special hardware that cannot be changed), you can search the 8-byte space less than a second. If not, maybe one can use the Summit Supercomputer to reach $\approx 2^{63}$ in a day and $\approx 2^{73}$ in a year (those are calculated on SHA-1 capabilities). Therefore 12-byte is far far away.

  you can get element3 if it is guessable (easy to guess: a default device password ...for instance)

If you have the collection like the commons password, knowledge about the target, etc. you can easily check them with some script.


Stream cipher example for an introductory cryptography course

The shrinking generator (open to divide and conquer) or self-shrinking generators are possibilities.

If you use a nonlinear combination generator with 3 relatively prime length primitive LFSRs and a nonlinear boolean function $f(x_1,x_2,x_3)$ you can also illustrate the tradeoff between nonlinearity and the degree of the function (Xiao-Massey lemma) as well as have some room for divide and conquer. You can spend 10 minutes on Geffe and show how its weaknesses can be ameliorated with this generator.

It also enables you to explicitly compute the nonlinearity via $f(L_1, L_2, L_3)$ over the integers.


An interesting cryptanalytic attack on Diffie-Hellman is the small subgroup confinement attack. The attack works if the DH parameters are chosen without caution. Here is a brief explanation on how it works.

DH works in multiplicative groups. Say we are working in $Z^*_p$. As $p$ is prime, the order of this group ($p-1$) is composite, therefore by Lagrange's Theorem there exists subgroups. The attacker basically reduces the key space to one of these subgroups having much smaller orders by interfering the communication and modifying it.

Let our DH group to be $(Z_p^*,*)$ and $\alpha$ to be the primitive root used. Normally Alice computes a random $s_a$ and keeps it secret. Alice sends $\alpha^{s_a}$ to Bob, but the attacker Eve receives it first. Eve looks up for possible subgroups by searching through factors of $(p-1)$ and finds a small factor $q$. By Lagrange's Theorem she knows there exists a subgroup of order $q$. She computes $t=\frac{p-1}{q}$ and sends Bob $(\alpha^{s_a})^t$. Bob also computes his secret random value $s_b$ and computes the shared secret $(\alpha^{ts_a})^{s_b}$. Bob then sends Alice $\alpha^{s_b}$ but Eve intercepts. Eve sends Alice $(\alpha^{s_b})^t$ and Alice also computes the shared secret as $(\alpha^{ts_b})^{s_a}$. Both have the shared secret, yes, but their shared secret is of form $(\alpha^t)^x$. Numbers of this form are generated by the subgroup with generator $\alpha^t$ which is known to be of order $q$. As $q$ is small (by our hypothesis of DH parameters have been selected poorly), Eve can simply compute the DH discrete logarithm problem by bruteforce as there are much less trials.

How to protect?

Pick $p$ such that $p=2q+1$ where $q$ also is a prime (see Sophie-Germain primes). Having this property, the group order will be $p-1=2q$. As $q$ is prime, only factors of $p-1$ are 2 and $q$. So when setting up shared secrets with DH, check if your group order is 2. If this is the case you know that you've been attacked.


OpenSSL not producing messages of expected size

You have 16 bytes to encrypt in your file. You did not set -nopad option, therefore, the OpenSSL will use the default padding, PKCS#7. This padding adds characters so that the input is multiple of the block size. If the input is already multiple of the block size then an additional block is added that contains byte 10 16 times. The rule can be simplified as

$$paddingSize=b−(messageLength \bmod b)$$ where $b$ is the block length and padding char is char(paddingSize). This will make the input 32 bytes and with the ECB mode, the output (ciphertext) will be 32 bytes, too.

Next, you set the option -base64 this will convert the output to base64. The base64 converted output length can be calculated by formulas. The unpadded base64 output size is $\lceil 4 \cdot n / 3 \rceil$ where $n$ is the number of characters. $\lceil 32*4/3 \rceil =  42$ and this will round up to the multiple of 4 that makes 44 bytes. The below is the hex dump of the output file;

$hexdump -C 2.txt
00000000  33 53 37 53 43 56 33 4b  69 63 2b 38 65 69 4a 39  |3S7SCV3Kic+8eiJ9|
00000010  34 6a 69 77 76 76 58 2f  67 48 45 6d 62 54 38 57  |4jiwvvX/gHEmbT8W|
00000020  6a 4b 55 6c 64 57 51 43  5a 39 51 3d 0a           |jKUldWQCZ9Q=.|
0000002d

The missing $45-44=1$ byte is the 0a character at the end of the ciphertext, it is the line feed character.

Note: Since this is Cryptography, we must say something about the ECB. If there isn't a really special issue to use the ECB, don't use the ECB mode, this is insecure leaks patterns and enables frequency attack. In modern Cryptography we prefer Authenticated Encryption (AE) modes like AES-GCM. To use it with OpenSSL, use -aes-256-gcm option instead of -aes-128-ecb. AE modes provide Confidentiality, Integrity, and Authentication. And, your obligation for the AES-GCM, is never using an IV again. Even a single AES-GCM nonce reuse can be catastrophic.


Security of HOTP over an unencrypted channel for controling an actuator

Can HOTP algorithm be used over an unencrypted channel securely?

Yes.

Essentially, HOTP is a stateful function that keeps an internal counter and then computes an HMAC over that counter followed by some truncations to get the right format. In the process the counter is also incremented.

So assuming we can model HMAC as a PRF then the output of each HOTP query is freshly random and unrelated because that's what a random function would do with distinct inputs (and that's how HMAC behaves because it's a PRF). This in particular means that an adversary cannot predict anything about future HMAC outputs or about past unseen outputs.

Of course the only guarantee you get from this is that an adversary cannot predict new authentication tokens and that new tokens likely won't be valid ever again. In particular HOTP by itself does not protect you from things like relay attacks or attacks where the adversary buffers a token and sends it later at a more convenient time.


AES CBC with unique key per message, but fixed IV

What you are describing is related to the synthetic initialization vector or SIV family of authenticated ciphers, where the cipher is a deterministic function of a key and a message without a separate initialization vector or nonce.  Such ciphers cannot conceal repeated messages, but that is the only inherent flaw.

Some ciphers also admit specifying an IV or nonce, and if the nonce is always unique, then they work like standard nonce-based ciphers, but if the nonce is ever repeated, then they fall back to failing to conceal duplicates but nothing else—we call these nonce-misuse-resistant or NMR.

SIV or NMR ciphers are not very popular right now, partly because nobody agrees on which ones to use, and partly because the security bounds or data volume limits on the most common ones like AES-SIV and AES-GCM-SIV are not very good owing to the small block size of AES—indeed, the name ‘AES-GCM-SIV’ has undergone many revisions over the past couple years in attempts to improve the bounds, and its definition is still not standardized.

The general structure of (a) deriving a key or IV as a pseudorandom function of the message, and then (b) applying a standard cipher with the derived key or derived IV, is generally fairly safe as long as everything involved is large enough to have a low collision probability—if we're talking HMAC-SHA256 to derive an AES-256 key, that should be fine.  The main difference between instances of this structure is cost.  (Just make sure you don't reuse keys for multiple purposes.  For example, if elsewhere you reveal the HMAC-SHA256 under signing_key of public messages, you might leak which public message you just encrypted.)  If the cost of HMAC-SHA256 is acceptable to you and to your auditor, great!

What you describe is not exactly an SIV cipher because you derive the key rather than the IV as a pseudorandom function of the message.  With ciphers like AES, this incurs a somewhat high cost per message, because AES has an expensive key schedule, which is why AES-SIV is more popular than a hypothetical ‘AES-SK’ with synthetic keys.  In contrast, ciphers like ChaCha and Salsa20 have zero overhead to changing keys.

  If I'm understanding this right, the concern is that if an attacker possesses N ciphertexts and knows that their plaintexts all start with a common prefix P at least one block in length, then the attacker can encrypt P under various keys until they duplicate the first block of one of the ciphertexts, at which point they will have discovered the key for that ciphertext. It seems like N needs to be quite large to make this practical, particularly for a 256-bit key.

The area*time cost (a good proxy for euros or joules) of a generic attack on a cipher with a $b$-bit key given $n$ ciphertexts is $2^b/n$, using Oechslin's rainbow tables to save hash evaluations, on a $p$-way parallel machine for $p \geq n^2$ to save memory and communication costs, which runs in the time of $2^b/np \leq 2^b/n^3$ sequential AES operations.  This is why, for example, AES-128 should not be considered to provide a ‘128-bit security level’—if a billion users use the application (or, your users in aggregate make a billion ciphertexts under different keys using your synthetic key scheme), the cost of breaking one of them is well below $2^{100}$.

If $b = 256$ as for AES-256, it would take $2^{128}$ different targets before the cost drops below $2^{128}$.  In other words, you don't have to worry about this.  This is why, if you're aiming for a 128-bit security level, you should use ciphers with 256-bit keys like AES-256.

(Actually I don't recommend AES-256 either because it invites timing side channel attacks on software implementations, but if you must use AES you should use AES-256 instead of AES-128 unless you have an overwhelming performance consideration that can be carefully justified within your security goals.)


NACL with public key encryption and authentication

If I understand properly, you want to use ephemeral keys, and verify the identity of the sender.

A HMAC would not be enough to verify the identity of the sender, because the recipient is able to compute a valid authentication tag as well.

Signing the message before encrypting it solves this. Note that in that case, the message can simply be a random session key. So, for most applications, the cost is pretty low: signing is only required once, during key exchange. If this is acceptable for your application, this is probably the easiest route to go.

Otherwise, the Noise framework can be used to build secure key exchange protocols, according to what each participant knows about its peer. I would highly recommend using these patterns instead of inventing your own.

Do both the client and the server know about each other's public keys? The Noise KK pattern is likely to be the one you are interested in. Or if you have a single client, NNpsk0 is faster as it requires a single DH operation.


For any $n>0$ and any fixed $A$ the function $f_A : x \mapsto (A \oplus x) + x \bmod 2^n$ is affine over the field with 2 elements, i.e., $f_A(x\oplus y) = f_A(x)\oplus f_A(y)\oplus A$ (as $A = f_A(0)$).

A proof that the analog map $g_A : x \mapsto (A \oplus x) - x \bmod 2^n$ is affine, you can find in Louis Goubin's CHES 2001 paper A Sound Method for Switching between Boolean and Arithmetic Masking. For $f_A$ I do not know any published reference.

$f_A(x) = B$ is equivalent to $f_A(x)\oplus A = B\oplus A$, so you have to find out if the vector $B\oplus A$ is in the image of the $\mathbb F_2$-linear map $x\mapsto f_A(x)\oplus A$, and if it is, a preimage $x$. This is linear algebra, hence easy from a complexity-theoretical point.

For solving the linear equation you have first to check if $B\oplus A$ is a linear combination of the image of a bases, so taking the base $1, 2, 4, 8, 16, \dots$ you have to look if $B\oplus A$ can be written as a sum of a subset of the vectors $f_A(1)\oplus A=((A\oplus 1)+1\bmod 2^n)\oplus A$, $f_A(2)\oplus A=((A\oplus 2)+2\bmod 2^n)\oplus A$, $f_A(4)\oplus A=((A\oplus 4)+4\bmod 2^n)\oplus A, \dots$ using something like Gaussian elimination.

If it is, and let's say, for $I\subseteq \{0, 1, \dots, n-1\}$ you get $B\oplus A = \bigoplus_{i\in I} (f_A(2^i)\oplus A)$, then $x = \bigoplus_{i\in I} 2^i$ is your solution. EDIT: In general, you will get all solutions in this way. Linear algebra tells us that the set of solutions is either empty or an affine subspace, i.e., of the form $\{x_0+v| v\in W\}$ where $x_0$ is any solution and $W$ is an $\mathbb{F}_2$-subspace of the $n$-dimensional vector space of $n$-bit vectors.

So from a security point, I do not expect an improvement using this equation,  (EDIT:) as the solution set can be efficiently calculated and described (using one solution and a basis of $W$ of order $\le n$).


Point multiplication twice - can it be squeezed into one equation?

Yes, on an elliptic curve $\mathcal C$, we can use that $\forall d_1\in\Bbb Z, \forall d_2\in\Bbb Z, \forall G\in\mathcal C$
$$\begin{align}
d_2\times(d_1\times G)&=(d_2\cdot d_1)\times G\\
&=(d_2\cdot d_1\bmod n)\times G
\end{align}$$
where $n$ is the order of the curve, and also for $n$ the order of $G$ (which divides the order of the curve). That more generally holds in any finite group $(\mathcal C,+)$ with scalar multiplication $\times$ defined from the group law $+$ (even if not commutative).

For $d_1$ and $d_2$ random in $[0,n)$, the form $(d_2\cdot d_1\bmod n)\times G$ will typically be fastest, for decent implementation of the modular multiplication. It is best to use $n$ the order of $G$ (which can be smaller than the order of the curve). Beware that the modular multiplication could lead to a side channel.

If $d_1\times G=\infty$ with $G\ne\infty$, and the implementation of $d\times X$ fails when $X=\infty$, then both $(d_2\cdot d_1)\times G$ and $(d_2\cdot d_1\bmod n)\times G$ will prevent that failure (the end result will be $\infty$ all the same and the implementation should be able to deal with this). If the implementation fails when it internally encounters $\infty$ in some internal operation, the change in method of computation can potentially remove or create the condition triggering the issue; that depends on internals.

I have used $\cdot$ for integer multiplication, and $\times$ for point multiplication by scalar/integer.


It is the permutation group operation, which is the result of first applying the first permutation (listed on the left), and then the second permutation (listed on top).

For example, the permutation listed as [3, 1, 2] is the permutation that maps the element 1 to 3, the element 2 to 1, and the element 3 to 2.

And, the permutation listed as [1, 3, 2] is the permutation that maps the element 1 to 1, the element 2 to 3 and the element 3 to 2.

So, if we combine these two permutations, applying [3, 1, 2] first, we can compute this by tracking what the permutations do to the specific elements.  For example, it maps the element 1 to 3 (which is what the first permutation does), and then mapping the resulting 3 to 2 (which is what the second permutation does).  Similarly, 2 is mapped to 1 (again, the first permutation), and then the second permutation maps the resulting 1 to 1.  And, the element 3 is mapped to 2 by the first permutation, and that is then mapped to 3 by the second.

Hence, the resulting permutation is [2, 1, 3], which is what is listed in the [3, 1 2] row and the [1, 3, 2] column.


Can a CCA-secure cryptosystem be used as a CMA-secure MAC?

Let $(\mathsf{KGen},\mathsf{Enc},\mathsf{Dec})$ be a CCA secure encryption scheme. I'm assuming you're asking about the following construction of a MAC $(\mathsf{KGen'},\mathsf{Mac},\mathsf{Vfy})$:
$$\mathsf{KGen'}(1^n) := \mathsf{KGen}(1^n) \qquad \mathsf{Mac}(k,m) := \mathsf{Enc}(k,m) \qquad \mathsf{Vfy}(k,m,\tau) := (\mathsf{Dec}(k,\tau) \stackrel{?}{=} m)$$
If that is what you're asking about, then no. This construction is generally not even unforgeable under a no-message attack. Let $m^*$ be some arbitrary fixed message from the encryption scheme's message space. We can construct a new encryption scheme $(\overline{\mathsf{KGen}},\overline{\mathsf{Enc}},\overline{\mathsf{Dec}})$ as
$$\overline{\mathsf{KGen}}(1^n) := \mathsf{KGen}(1^n) \quad \overline{\mathsf{Enc}}(k,m) := 1\|\mathsf{Enc}(k,m) \quad \overline{\mathsf{Dec}}(k,b\|c) := \begin{cases}\mathsf{Dec}(k,c) & \text{if } b=0\\ m^* & \text{otherwise}\end{cases}$$
It is easy to show that this scheme is also CCA secure, but I will leave this as an exercise to the reader. It is however trivial to forge the above MAC when instantiated with this scheme. Just output $m^*,0^{\ell(n)+1}$, where $\ell(n)$ is the length of a ciphertext under $\mathsf{Enc}$.


Method for creating any involutive permutation

The Fischer-Yates shuffle can be used to generate random (i.e. uniformly distributed) permutations. As mentioned in the comments, generating "any" permutation is trivial.
So I'll make the assumption that you want an algorithm to generate random involutions on $\{1, \ldots, n\}$, such that each involution has equal probability.

It is easy to see that any involution $\pi \in \mathrm{Sym}_n$ is the product of disjoint transpositions (i.e. all cycles have length at most two). This observation leads to the following simple strategy to generate random involutions: ($I_n$ below denotes the number of involutions on $n$ symbols)

Choose $1$ to be part of a one-cycle (with probability $I_{n-1} / I_n$) or a two-cycle (with probability $1 - I_{n-1}/I_n = (n-1)I_{n-2}/I_n$), i.e. $\pi(1) = 1$ or $\pi(1) = j$ such that $\pi(j) = 1$. In the former case, one can continue in tail-recursive manner by sampling an involution from $\mathrm{Sym}_{n - 1}$. In the latter case, choose $j \in \{2, \ldots, n\}$ uniformly at random and sample an involution from $\mathrm{Sym}_{n - 2}$ (again, recursively).

An important detail in the procedure above is how to sample with probability $I_{n - 1} / I_n$. It's probably best to precompute these probabilities and store them in a table.

I'm sure many references could be found for this simple method. For instance, the procedure above (with minor differences) can be found in Algorithm 9.4 of Jörg Arndt's thesis. An implementation in C++ can also be found there.


How efficient are the generic attacks regarding near-collision-resistance?

The hamming distance is going to have a binomial distribution. Given two $n$-bit hashes, the probability that the hamming distance is exactly $k$ is:

$Pr(n,k) = {{n}\choose{k}}\frac{1}{2}^{k}\frac{1}{2}^{n-k} = {{n}\choose{k}}\frac{1}{2}^{n}$

So if you want to know the probability of the hamming distance being $\le k$ you need to sum:

$p = Pr(n,0) + Pr(n,1) + Pr(n,2) + ... + Pr(n,k)$

For example, if $n=128$ and $k=32$ then the probability is approximately 0.000000006421. So you'll need to try 155,738,981 times on average.

If you want to apply the birthday attack thinking to this, where the probability of success increases with the number of hashes you collect, you'll need approximately $\sqrt{\frac{1}{p}}$ messages for a 50% probability. This is a rough approximation based on the idea that the number of message pairs grows quadratically.

So in the above example, you'll need to collect 12480 hashes.


What is the intuition behind AES or SPN?

The s-box and linear round operations would be entirely redundant if AES were only ever used to encrypt 128 bits per key (i.e. if you changed keys for every 128 bit block).  Because then you would have the one-time pad, which is secure just by xoring the key with the message.

However, ciphers like AES are based on computational complexity (rather than information theoretic security), and purport to securely encrypt plaintext that vastly exceeds the length of the key.  The claim of security is that realistic opponents, using realistic amounts of computational resources, have only a vanishingly small chance of recovering any information about the plaintext or the key.  Or in other words, recovery of unknown plaintext information that has been encrypted with AES and an unknown key is supposed to be a computationally hard problem.

If AES did not have highly non-linear s-boxes, then the problem would be very easy, as daniel points out in his answer.  This is because AES would then be an entirely linear system (linear in the Galois finite field of characteristic 2), and given a small amount of plaintext (just one or two blocks worth should be sufficient) we could use Gauss-Jordan elimination to solve the system and thereby recover the unknown key (or at least enough of it to decrypt and encrypt whatever we liked).

If AES did not have the linear operations (the byte permutation step and MixColumns step), then it would be easy for a different reason.  Those steps provide 'diffusion', whereby information about one part of the 128-bit block is  'mixed' with information from other parts of the block.  If there was no mixing, then each 8-bit section (byte) of the 128-bit block would be 'segregated' from every other byte.  So differences in one byte in the input plaintext would result in differences in only that same byte of the output ciphertext (which can reveal information about the plaintext).  Also, you would only have to guess that small part of the key that interacts with a single byte in order to 'decrypt' that byte, and it is much easier to decrypt by brute-force-guessing a small part of the key rather than the entire key.

Together with the s-box, this diffusion means that after just a few rounds, every single bit of the output is a very complex, high-degree, non-linear function of every single bit of the input and the entire key.  Highly non-linear systems of equations are much harder to solve than linear systems of equations.

That said, the reason why AES uses that particular s-box and those particular linear steps has to do with the methods of cryptanalysis in use at the time it was designed.  AES was carefully designed to resist two very powerful types of attack called differential cryptanalysis and linear cryptanalysis (and some related variants) that broke many block ciphers in the generation prior to AES.  To have an 'intuitive sense' of why AES is the way it is, you need to understand those two attacks.


As I noted in this earlier answer to a related question, the rotor permutations in your example are written using a shorthand notation that only shows the output alphabet of the permutation, with the implicit assumption that the input alphabet is always ABCDEFGHIJKLMNOPQRSTUVWXYZ.  That is to say, your rotor descriptions:

EKMFLGDQVZNTOWYHXUSPAIBRCJ | Rotor I wiring
AJDKSIRUXBLHWTMCQGZNPYFVOE | Rotor II wiring
BDFHJLCPRTXVZNYEIWGAKMUSQO | Rotor III wiring

actually describe the following permutations:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ | Rotor I
EKMFLGDQVZNTOWYHXUSPAIBRCJ

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ | Rotor II
AJDKSIRUXBLHWTMCQGZNPYFVOE

ABCDEFGHIJKLMNOPQRSTUVWXYZ
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓ | Rotor III
BDFHJLCPRTXVZNYEIWGAKMUSQO

Also, there are two other issues with your example encryption:

You're applying the rotor permutations in the wrong order; the rotors are conventionally listed from left to right, but the wiring from the input/output to the reflector goes from right to left.  So in your example, rotor III should actually be applied first, then rotor II and finally rotor I (and then the reflector and the inverse rotors in the opposite order).
The rotors are stepped before each letter is encrypted.  So if you start with all rotors in the A position, when the first letter of the message is encrypted the rightmost rotor (i.e. rotor III here) will have already rotated into the B position.  This means you have to shift the letter right by one step in the alphabet before it enters the rotor, and back left by one step after it leaves the rotor.

Put all together, the correct path of the first letter is:

A ⤑ B → D ⤑ C (rotor III in position B)
C ⤑ C → D ⤑ D (rotor II in position A)
D ⤑ D → F ⤑ F (rotor I in position A)
F ↔ S (reflector B)
S ⤑ S → S ⤑ S (rotor I in position A, reverse)
S ⤑ S → E ⤑ E (rotor II in position A, reverse)
E ⤑ F → C ⤑ B (rotor III in position B, reverse)

For each rotor, there are effectively three permutations to apply: an alphabet shift to the rotor's current position (i.e. 0 steps for position A, 1 step for position B, 2 steps for position C, etc.), the fixed rotor wiring permutation and finally the reverse shift back from the rotor's position.

In the list above, I've used a dotted arrow ⤑ for the shifts and a solid arrow → for the rotor wiring permutations (and a two-headed arrow ↔ for the reflector).
 In this example, two of the three rotors are still in position A, so for them, the shifts have no effect, but I've shown them anyway for completeness.  Also, just by chance, the wiring in rotor I happens to map the letter S to itself.


Most efficient way to perform secure bitwise multiplication

The most natural method for this task would be to use oblivious transfer: on input a bit $x$ for Alice and a bit $y$ for Bob, Alice plays the role of the sender in an oblivious transfer with input $(x_0,x_1) = (0,x)$, and Bob plays the role of the receiver with input $y$, and learns $x_y = x\cdot y$. By repeating this method in parallel for all the bits of their input, Alice and Bob get the bitwise multiplication.

This is probably the most natural and efficient method to perform this task. An alternative is to use ElGamal over a group $\mathbb{G}$ with generator $g$ and public key $h$ for which Alice knows the corresponding secret key.

Alice sends an encryption $(c_0,c_1) = (g^r, h^rg^{x})$ of $g^x$. Bob computes $(c'_0,c'_1) = (c_0g^{r'},c_1^y)h^{r'})$, that is, a rerandomized encryption of $g^{xy}$, and sends it back to Alice, who decrypts and get $g^{xy}$. As $xy \in \{0,1\}$, she easily recover $xy$ from that. Again, by repeating this method in parallel for all the bits of their input, Alice and Bob get the bitwise multiplication.


Proof of the standard pseudorandom generator + XOR encryption scheme in Goldreich

The inequality is obtained by a distance argument.

Consider two points $X,Y$ on the real line. Taking another point $Z$, you have $|X-Z| + |Y-Z| \geq |X-Z+Z-Y| = |X-Y|$.

Applying this "triangle" inequality to your equality 1, we have for any $z \in \mathbb{R}$,
$\begin{array}{l}
 \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z\bigr\rvert
 + \bigl\lvert \Pr[A(y\oplus g(U_n))=1]- z\bigl\rvert \\
 \geq \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - z + z - \Pr[A(y\oplus g(U_n))=1]\bigr\rvert \\
 = \bigl\lvert\Pr[A(x\oplus g(U_n))=1]-\Pr[A(y\oplus g(U_n))=1]\bigr\rvert \\
 > 1/p(n). \\
\end{array}$

By setting $z = \Pr[A(x \oplus U_m)=1] = \Pr[A(y \oplus U_m) = 1]$, we have
$\begin{array}{l}
 \bigl\lvert\Pr[A(x\oplus g(U_n))=1] - \Pr[A(x \oplus U_m)=1]\bigr\rvert \\
 + \bigl\lvert \Pr[A(y\oplus g(U_n))=1]-\Pr[A(y \oplus U_m) = 1]\bigr\rvert \\
 > 1/p(n). \\
\end{array}$

The one of two absolute values is bigger than $1/(2p(n))$.
Therefore, WLOG, you obtain your equation 3.


Is the private key static or variable key in the elgamal algorithm?

I never thought Alice and Bob would get international counterparts. Anyway, in reading your question I've spotted some issues.

Bashir generates a public and a private key. The private key you call a private session key, which is a bit confusing and may lead to errors like the one below.
In order for Amina to encrypt something for Bashir, she has to use Bashir's public key and also generate another value, (b), which is called the ephemeral key  or session key, hence the confusion I mention above.

To answer your question: Amina has to generate a new ephemeral key (b) for each message. If she uses the same key for all messages, and two messages happen to be the same, the corresponding ciphertexts will be the same as well. Moreover if someone gets his hands  on a plaintext, he can figure out the ephemeral key and seriously compromise all the messages encrypted with the same ephemeral key. Therefore Amina must generate a new ephemeral key every time.


When only using one-way hashing, is it possible to tell the number of characters changed between the old and new password?

No. If the hash function is strong, even a single bit change will give a completely different hash.

The only way to tell how many characters differ between a particular unknown hash value and a known password would be an exhaustive search, which might be possible for determining e.g. that more than one character must differ, but not in general.

  That got me thinking, how can Solaris (or any system) detect which characters have changed between passwords if it is using a one-way hash to validate passwords?

Most likely answer: it asks for both your old password and the new when changing passwords, and can compare them at will.

Alternatively: it stores something other than just a hash (e.g. an encrypted password) that does allow comparisons. You should suspect this if a system has rules that concern more than one previous password. That is not a secure way to store passwords.


How does TLS ensure the use of the best crypto method both the server and client share?

It does not. The server is responsible for selecting the cipher and there is no guarantee that it will select the best. But, if a man-in-the-middle tampers with the ClientHello to change the ciphers offered to the server, then this tampering will be detected at the end of the handshake, because their is a final signature over all data of the handshake and this signature will not match anymore.


hardware and software optimizations for Salsa20

Looking at the Crypto++ 5.6.2 implementation for Salsa20 it seems they do have an SSE implementation, but it doesn't use intrinsics so it doesn't look very portable between compilers.

If you're not exactly set on using Salsa20 I would recommend using ChaCha20, which is a small modification of Salsa20 by the author (Daniel Bernstein) that is slightly faster and cleaner. And if you really value speed I would recommend using Salsa12, which reduces computation time by about 40%.

For ChaCha20 I would recommend the crypto_stream\chacha20\krovetz implementation found in SUPERCOP. Similarly for ChaCha12.

For Salsa20 I suggest you look inside the crypto_stream\salsa20 folder and look for an appropriate implementation for your target platform. You can see timings for various platforms at these pages.


How much time to generate a proof in ZK-snark?

I just run example code from ZoKrates manual and measured time and memory usage.

Here is how "proof of preimage" problem defined in ZoKrates:

def main(field a, field b, field c, field d) -> (field):
    h0, h1 = sha256packed(a, b, c, d)
    h0 == 263561599766550617289250058199814760685
    h1 == 65303172752238645975888084098459749904
    return 1

For such a simple program:

setup takes ~20 seconds and ~350 Mb memory;
generating witness and proof takes <5 seconds and ~150 Mb memory.

For something more complex like proving UTXO in ZCash proving may take tens of seconds and couple of gigabytes (see here).

Following steps are required to run the proving protocol.

1. Compile human readable code into arithmetic circuits (~7 seconds, ~240 Mb):

$ time zokrates compile -i hashexample.code
2.08user 5.14system 0:07.24elapsed 99%CPU (0avgtext+0avgdata 238044maxresident)k
0inputs+21641416outputs (0major+70866minor)pagefaults 0swaps

Generated arithmetic circuit is 15Mb.

2. Trusted setup (~15 seconds, 350 Mb)

$ time zokrates setup
13.73user 0.94system 0:14.68elapsed 99%CPU (0avgtext+0avgdata 354912maxresident)k
0inputs+66248outputs (0major+90965minor)pagefaults 0swaps

On this step proving key (32Mb) and verifying key (2.6Kb) are generated.

3. Computing witness from known arguments (~1 second, ~150 Mb)

$ time zokrates compute-witness -a 0 0 0 5
0.82user 0.92system 0:01.75elapsed 99%CPU (0avgtext+0avgdata 148620maxresident)k
0inputs+1440outputs (0major+39469minor)pagefaults 0swaps

Witness is 458 Kb in size.

4. Generating the proof (~3 seconds, ~106 Mb)

$ time zokrates generate-proof
2.71user 0.06system 0:02.78elapsed 99%CPU (0avgtext+0avgdata 106188maxresident)k
0inputs+40outputs (0major+36676minor)pagefaults 0swaps

The proof is 1.4 Kb in size.


Using XOR to derive a data key for ECIES

As written, it makes an additional security assumption on the symmetric cipher; that the attacker can't flip bits in the key (and modify the ciphertext) to gain some advantage.  That is likely true for most ciphers we would use in practice, but is nevertheless an additional assumption.
This is not difficult to fix; we don't select a random symmetric key $K_d$, instead, we generate a random value $J$, and set $K_d = \text{Hash}(J)$.  Then, in step 4.2, we then instead set $A_i = K_i \oplus J$.


How can I prove the result of a long computation with a short string?

There are several option - none of which is trivial to implement.

A bit of background first. Essentially, verifiable delegation of computation boils down to being able to prove relations between inputs and outputs, so that the verification time is way smaller than the computation time, for relations that can be computed in polynomial time. In contrast, the famous SNARGs are way more powerful, as they also allow to prove any NP statement, even those that are not known to be computable in polynomial time. So in a sense, delegating computation is "easier" than constructing SNARGs. However, two remarks are in order:

A very large effort has been devoted to the analysis and construction of SNARGs, even leading to some implementations (e.g. zcash). Therefore, it might be that the current best way of verifying delegated computation in practice goes through SNARGs
A sense in which SNARGs are harder than verifiable computation is with respect to the underlying assumptions: while we have strong indications that SNARGs require non-standard assumptions, we know how to base verifiable computation on standard assumptions. But if you are looking for a practical solution, you might well not care about the theoretical issues of the underlying assumptions.

For those reasons, even in SNARG is an overkill from a theoretical point of view, it is not necessarily the case if what you care about is practice, and you can easily find some implementations (there are more recent ones, such as the famous Pinocchio, or the even more recent Geppetto).

That being said, there are several natural approaches for delegation of computation. The first that comes to mind is this approach, which is the seminal paper on the topic of delegation, and that works for restricted classes of computation. This approach was refined several time, culminating with this beautiful paper that gives a very satisfying solution for delegating evaluation of boolean circuit, with reasonable efficiency. I believe they have implementations, I do not know how easy it is to find and reuse these implementations.

The second, that I only mention for the sake of completeness, is to use techniques for batch verification: the prover evaluate the same program $P$ on many inputs $x_1, \cdots, x_n$, in time $O(sn)$ ($s$ being the time needed to evaluate $P$ on a single input) and the verifier can check the correctness of all computations in time $O(s + n)$, instead of $O(sn)$.

Another natural approach (see also this paper, this paper, and papers that reference them on Google scholar) for delegation of computation essentially requires to ask the server to perform the computation in the encrypted domain, via fully homomorphic encryption. It is based on homomorphic MACs, which can be constructed from FHE. From my understanding, they are conceptually quite simple - you essentially have to execute the computation several time in the encrypted domain, and there is an easy check for the verifier. The main issue is the cost of using FHE - but if your circuit is small enough, using this recent FHE scheme (see also the follow up) which performs bootstrapping in less than 20ms, this might be quite feasible. For more restricted computations, one can also avoid using FHE.

I've not read it yet, but if you have access to the ACM digital library, there was a recent survey on the subject of verifiable computation, by one of the leading researchers in the area (Rosario Gennaro), called "Verifiable Outsourced Computation: A Survey".


How to implement oblivious transfer where probability of the receiver getting secret is exactly 1 out of 4?

I'll try to answer both your original question, and your question in the comment section.

The original definition of oblivious transfer is the following: a sender holds a message $m$ and interacts with the receiver. The receiver gets to know $m$ with probability $1/2$, without the sender being able to know whether the receiver learned $m$ or not. i'll call it "Rabin OT" to distinguish from the other definition.

Nowadays, the definition of oblivious transfer which is universally used is the following:
The sender S holds two messages $m_0$ and $m_1$
The receiver holds a selection bit $b \in \{0,1\}$
At the end of the oblivious transfer, the receiver learns $m_b$ (and does not learn anything about $m_{1-b}$) and the sender learns nothing (and in particular nothing about $b$).

This"classical" oblivious transfer easily allows to implement the Rabin OT: the sender holds $m$, picks a bit $x$ at random and sets $m_x \gets m$ and $m_{1-x} \gets r$ for a uniformly random value $r$. The receiver picks his selection bit $b$ at random. Then they perform a classical oblivious transfer; with probability $1/2$, the receiver learns $m$, else he learns a random $r$ (hence nothing). More generally, if you have a $1$-out-of-$N$ OT (where the sender holds $m_1, \cdots, m_N$ and the receiver an integer $i$ between $1$ and $N$ and gets to learn $m_i$), you can easily implement a Rabin OT with probability $1/N$.

Now, there are several ways to answer your question. If you are asking whether $1$-out-of-$2$ oblivious transfer can be used to implement other kinds of oblivious transfers, the answer is yes, as $1$-out-of-$2$ oblivious transfer can be used to implement any kind of two party functionalities (more formally, it implies general two-party computation, in the honest-but-curious model - but that's just to be a bit formal in my statement). But in practice, you will probabily not want to construct a $1$-out-of-$3$ oblivious transfer directly by calling "in black box" a $1$-out-of-$2$ oblivious transfer.

However, most known constructions of $1$-out-of-$2$ OTs do easily extend to $1$-out-of-$N$ OTs (see for example "Efficient Oblivious Transfer Protocols" by Naor and Pinkas).

Here is an example of such a protocol (taken from the article of Naor and Pinkas) :

We fix a group $\mathbb{G}$ in which the DDH problem is hard. Let $g$ be a generator of $\mathbb{G}$. We also have access to a hash function $H()$ which is seen as a random oracle.

The sender has an input $M_0, \cdots, M_{N-1}$. He picks random group elements $C_1, \cdots, C_{N-1}$, a random exponent $r$, and computes $g^r$. He sends $C_1, \cdots, C_{N-1}, g^r$ to the receiver.

The receiver has a selection integer $j \in \{0, \cdots, N-1\}$; he picks a random exponent $k$ and sets pk$_j \gets g^k$. If $k \neq 0$, the receiver also computes pk$_0 \gets C_j/\text{pk}_j$. He sends pk$_0$ to the sender.

The sender computes $\text{pk}_0^r$ and for $i=1$ to $N-1$, $\text{pk}_i^r = C_i^r/\text{pk}_0^r$. Then, he picks a random $R$ and sends for all $i$ the value $E_i \gets H(\text{pk}_i^r,R,i) \oplus M_i$ ($\oplus$ is the xor) to the receiver, together with $R$.

As he knows $k$, the receiver can compute $(g^r)^k = \text{pk}_j^r$, hence he can compute $H(\text{pk}_j^r,R,j)$ by himself, and therefore recover $M_j$. One can show that if $H()$ acts as a random oracle and the DDH assumption holds, he cannot learn anything else on the other inputs of the sender.


I'll port the contents of the link of Henrick:

  Within the United States, one key forum for profile collaboration is the Open
  Systems Environment Implementors Workshop (OIW), which is hosted by NIST. OIW
  recently expanded its domain of concerns from communications to the full range
  of Open System Environment issues (interoperability, portability, and consistency of user interfaces, parallel to the IEEE 1003.0 Guide), although no  II specific projects have been defined for OIW yet. OIW is the regional workshop for the Americas, collaborating with parallel bodies in Asia (AOW) and in Europe (EWOS). Together these groups have the authority to forward documents for approval by JTC1 as "International Standardized Profiles," which reflects the ideal status for information infrastructure specification: a coherent suite of well-defined standards adopted by the international standards community.

Not very helpful in itself, but this is the most concise meaning so far (it doesn't make it clear what it actually does or who it consists of at all though).


Exploit RSA , given some information about n

The question spezifies $n_1 = p*q_1$, $n_2 = p*q_2$. With that we can calculate $gcd(n_1,n_2) = p$ which lets us solve $n_1 / p = q_1$ and $n_2 / p = q_1$. Now we have every information needed to calculate the private part of Bob's key and thereby decrypt all messages sent to him.


Which AES modes can decrypt from anywhere in the ciphertext

The practical answer is that you should almost certainly be using authenticated encryption, in which case authenticating an individual encrypted message requires you to process all of it anyway.  Once you throw in this element, random access into encrypted data becomes not a matter of message encryption modes, but rather of how to split your data into a collection of messages that you can encrypt and authenticate individually.

The literal answer is that among the classic confidentiality-only block cipher modes, CBC and CTR can start decrypting from any block, while CFB and OFB cannot.  You can read this pretty straightforwardly from mode diagrams; here's CBC decryption (diagrams from Wikipedia entry):

Neither of the inputs to each block cipher call require the output of any other other block cipher call—there are no arrows going outside of one block cipher decryption box and into another, unlike for example with OFB mode:


Is there a rule of thumb for ZK protocols?

As usual, choosing the security parameters represents a tradeoff between the security and the efficiency. Therefore, it also strongly depends on two things:

how crucial it is that no one breaks the security guarantee (if an adversary succeeds at "guessing correctly" the challenge, hence can break soundness, how dangerous is that? How strong is the incentive for an adversary to break the system? Could he e.g. become super-rich by succeeding at doing so?)
how widely deployed might the system become (will it be used a few times, or hundredth of thousands of time?)

A very rough rule of thumb in this case could be (note here that we are talking about a statistical success probability during a run of a protocol, things would be very different if this was instead a computational security level, e.g. the average number of operations needed to break a scheme):

When the system has initially a soundness $1/2$, and reaching a better soundness involves parallel repetition of the entire protocol:

If the system should be very efficient and does not protect extremely valuable resources (or alternatively, if the incentive to break the system is not huge), a basic choice could be to settle for a $2^{-40}$ success probability.
If the system protects very valuable goods, or if there is a very strong incentive to cheat, but getting good efficiency is also very important, settling for a $2^{-80}$ success probability should be fine.
If people using the system are paranoid, or achieving strong efficiency is not such a concern while security is of paramount importance, go for $2^{-128}$ success probability.
In all cases, divides the target success probability by the number of times the system might be used in its lifetime (or the number of tries an adversary can plausibly get). E.g. a widely deployed system can be expected to be used by, say, $2^{20}$ individuals a few times each, so divide the target success probability by at least $2^{20}$ (such that the initial number, before dividing, becomes the probability that someone eventually ends up breaking the security by chance during the lifetime of the system).

When the system has natively the possibility to use a larger challenge space (e.g. Schnorr proof):

in this case, dividing the success probability by $2^k$ often involves sending only $k$ more bits in the proof. When soundness is that cheap, there is no need not to settle for a completely safe security margin, without optimizing for a few bits - e.g. going for a $2^{-128}$ or $2^{-256}$ success probability looks reasonable.


Well, think about it this way. If breaking one encryption with brute force will take longer than the lifetime of the universe, are you any safer with an encryption scheme that will take twice the lifetime of the universe? No. The first encryption cannot be broken. Adding a second encryption just adds computation overhead with no real benefit.

Think about it this way, if it is estimated to take 500 years for a prisoner to chew through the bars on his prison cell to escape, is the public any safer if we add a second set of bars so that it will take 1000 years to chew through the two sets before the prisoner can escape? Not really.

UPDATE
Given the update in the question, I thought I'd update.

So, you fix an $n$ and choose $e_1$ and $e_2$ as public exponents and compute $d_1$ and $d_2$ as the private exponents.

To encrypt, you are proposing $(m^{e_1})^{e_2}\bmod{n}$ and wondering why this is not stronger than just $m^{e_1}\bmod{n}$ in a brute-force attack[*].

So, you haven't given detail as to what the "brute-force" attack is, so let's look at two options.

Factoring $n$. If I factor $n$ using a brute-force attack, I then use the factorization to compute $d_1$ and $d_2$. Computing both $d_1$ and $d_2$ is not much more than just computing $d_1$ since you broke the factorization.
Instead of factoring $n$, what if you try to brute force $d_1$ and $d_2$. Recall that $d_i$ is chosen such that $e_i d_i\equiv 1\bmod{\varphi(n)}$. Furthermore, $(m^{e_1})^{e_2}=m^{e_1e_2}$. Raise that to $d_1d_2$ and you get $m$ back. Therefore, you really need to bruteforce $d_1d_2$ instead of $d_1$ and then $d_2$ (or vice-versa). If you assume each of the $d$s are $l$ bits, brute forcing $d_1$ then $d_2$ would be like brute forcing $l^2$ bits. Brute forcing $d_1d_2$ on the other hand is $2l$ bits. One could argue that this is harder, but asymptotically it isn't.
Brute force only $d_1$ then factor. It turns out if you know $d_1$ you can easily factor $n$ then use the factorization to compute $d_2$. (This comes from @CodesInChaos comment).

Any other brute force options you had in mind?

[*] My description of double encrypted RSA here is assuming textbook RSA. For padded RSA (which is what you find in the real world), points 1 and 3 are still valid, 2 however is not.


Actually, the algorithm is distinguishable.

Let us assume that the attacker has two input, output pairs $(x, fx), (y, fy)$.  Then, he can test whether $fy^x = fx^y$.  If $fx = g^{sk\cdot x}$ and $fy = g^{sk\cdot y}$, this test will succeed, as $fy^x = g^{sk\cdot y \cdot x} = g^{sk\cdot x \cdot y} = fx^y$.

Furthermore, given $x$ and $g^{sk \cdot x}$, the attacker can (with nontrivial probability) recover $g^{sk}$.  The nontrivial probability is that whether $x^{-1} \bmod p-1$ exists; if it does, then $g^{sk} = (g^{sk \cdot x})^{x^{-1}}$.  The attacker can use that to evaluate the function for any input.

The above assumes that the attacker knows $p$.  Even if he doesn't, he can still practically distinguish (and recover $p$) if the sets he was given had inputs there were either

Small, for example, if the inputs $x, y, z$ are sufficiently small that the attacker can compute $\gcd(fy^x-fx^y, fz^x-fx^z)$
Related (e.g. $x, 2x, 4x$ with the corresponding outputs).


Key management for military GPS receivers

Am I going to regret posting this? There seems to be enough non-classified information available about GPS to answer this question.

I see 3 reasons why P(Y) encryption is different and less likely to be hacked than game console encryption:

Hardware containing the GPS decryption key is more difficult to obtain than hardware containing the game console decryption key.
Now that selective availability is turned off, even civilian receivers have positioning accuracy about as good as military receivers -- eliminating the biggest benefit of obtaining the GPS decryption key.
(The other abilities that key gives a person -- receivers that are more resistant to spoofing, and spoofing transmitters that can cause even anti-spoofing military receivers to give bad location data -- are useless unless someone broadcasts spoofing transmissions, which for various reasons few people are willing to do).
From what I read on Wikipedia about the selective availability anti-spoofing module (SAASM) and the previous PPS-SM system,
there is apparently no master key.
Periodically a fresh new (and I suspect completely unguessably random) key is generated, distributed to all military units that require it, and then uploaded to the GPS satellites.
After that the old key is pretty much useless.
So even if one GPS decryption key did leak, it would only be useful for a short time.


Are there key-derivation functions that are safe to use in parallel on the same secret?

You need to split this up into two separate problems:

you may have a low entropy password (as you indicate you want to have "tunable difficulty");
you need the keys of a specific user not to reveal any information about the password or the other keys.

Lets solve this in two steps:

First you need a salt and a work factor or iteration count. You can do this by choosing a secure password hash or Password Based Key Derivation Function (PBKDF). Passable options include PBKDF2, bcrypt, scrypt and Argon2 (ordered from standardized/available to secure).

You've indicated that you worry that the server knows the salt. This is however not a problem as a salt may be a publicly known value. The salt is mainly used to assure that:

you cannot search all the password hash results of the separate users using a single salt until you find a match;
you cannot find indications of duplicate passwords by looking at the password hash results.

OK, so now you should have a secret that depends on the password and the publicly available salt. It is possible to simply create create a large secret and split that up into multiple keys. The output of the PBKDF should be indistinguishable from random so as long as you don't mistakenly have an overlap between keys the keys should be independent of each other.

It is however much nicer to use a Key Based Key Derivation Function (KBKDF) such as HKDF for this step. You would then use the result of the PBKDF as key for the KBKDF. In that case you can use a label for each key, e.g. Authentication_key and Data_encryption_key. Those keys would both depend on the master key, but they would otherwise be independent of each other.


When we say key size is $n$, we consider $n$ in bits, n-bit key size. For example, AES has 128, 192 and 256-bit keys sizes. Therefore, we have $2^{128}$ key to search for AES-128 and that is exponential, $ \mathcal{O}(2^n)$

In cryptography, we use also a security parameter that measures the input size of the problem.  The security parameter is represented as unary representation ( $\lambda-\text{times }1)$ so that the complexity of the cryptographic algorithms will be polynomial time.

For RSA like systems, when we say the security parameter is $1^\lambda$, the $\lambda$ represents the number of bits of RSA modulus $n$. So the positive integer $n$ must be between $0,\ldots,2^{\lambda-1}$.

Note: We usually don't say AES (and other block ciphers) have security parameter 128, we just say 128-bit key.


is it possible to extract a "hint hash" of some kind from another hash?

Cryptographic hash functions are designed to have certain properties, which is collision resistance, preimage resistance and second preimage resistance. If those definitions are not clear, we could state informally:

If you only have hash values of some input data, then you can't do anything except check for equality. You can't compare the input data, you can't check if they have a common substring, and most importantly you can't get back the input from the hash. So imagine a hash function as a one-way street, where you can afterwards just check for equality. Any other structure is lost.

And this is the behavior, which is wanted from cryptographic hashes.

So if you consider your database, when you have access to the plain text, you could just use a hash function with only the user ID as input:

$h_1 = hash(FullPlaintext)$
$h_2 = hash(User ID)$
Save tuples $(h_1,h_2)$, e.g. in a table

If you want to add some keys to those inputs, you have to consider that using a different key means getting a different example, and there is no way to tell if just part of the input was equal or not. But with this table you could do your lookups. But it is impossible to get $h_2$ from $h_1$ or vice versa. In a cryptographic hash function, you simply can't go backwards.


Determine whether a given function is a pseudorandom generator/function

I have fully solved the questions now.

Not a pseudorandom generator since the first bit of $G(s)$ is always equal to the XOR of the second and third bit, i.e. a distinguisher can easily tell $G(s)$ apart from a truly random string $r$.
Not a pseudorandom generator. We can for example construct a distinguisher $D$ that, on input of a string $w$, outputs 1 if and only if the final bit is 0. If $w$ is uniformly distributed then the final bit is 0 with probability $\frac{1}{2}$ but if $w = G(s)$ for a uniformly distributed seed s  the final bit will be 0 with probability $\frac{1}{4}$.
Not a pseudorandom function. A distinguisher D could tell $F_k$ apart from a truly random function $f$ in the following way: Given access to an oracle $W$, D queries $W(0...0)$. If $W = F_k$ then the result will always be 0, but if $W$ is a random function then it should be 0 only with probability $\frac{1}{2}$.


In principle it should be possible to use 128 bit EC domain parameters / keys with any hash:

For Alice to sign a message m, she follows these steps:

Calculate $e = HASH(m)$, where $HASH$ is a cryptographic hash function, such as SHA-1.
Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bit length of the group order $n$.

Source: Wikipedia

However, implementations may reject combinations that would result in a very strange mix of security levels. Normally, I would try and use EC key sizes that are equal or larger than the digest algorithm used. It may be that some implementations refuse to perform step 2, only using the full hash instead of cutting it down to a smaller size.

Note that SHA-224, SHA-512/224 and SHA-384 kindly supply hash output sizes that can be combined with 224 and 384 bit ECC. Please have a look at keylength.com for more information about choosing matching sizes for algorithms.


Point of Diffie-Hellman key exchange when public keys are known

Diffie-Hellman allows for forward secrecy. In the protocol you describe, if the private key is ever leaked all previously exchanged keys are leaked.

If we only use RSA to authenticate keys created with Diffie-Hellman, past keys are safe even if you lose control over your private key in the future.


Can the ECDSA still work without present of hashing function?

The truthful answer here is that I don't know. I am pretty sure actually that the better answer is that this is unknown.  The assumption that the hash is only required for collision resistance is blatantly false, since typically one needs a random oracle for such schemes. In ECDSA specifically, we don't have actually have proof of security even with a random oracle, so it's even worse. However, given that it's been around for so many years, its security is essentially a well accepted assumption. However, as soon as you change something, and not hashing the message is certainly changing something, then it falls apart.


Example of existentially unforgeable and identity of the signer

The goal in this context is to guarantee that given a signature, or a set of signatures, you can confidently determine the public key that made them.

For a trivial example of how this might break down, consider an Ed25519 signature under a public key $A$, namely is a pair $(R, s)$ of curve point $R$ and scalar $s$ such that $[8 s] B = [8] R + [8 H(R, A, m)] A$, where $B$ is the standard base point and $m$ is the message.  If we didn't hash $A$ in with $R$ and $m$, the verification equation would be $[8 s] B = [8] R + [8 H(R, m)] A$.  There are several other public keys under which the same signature satisfies that verification equation: $A' = A + P$ where $P$ is a point of order dividing 8, since $[8] P = \mathcal O$.

That doesn't mean, given a target public key for which you don't know the corresponding scalar, you have any hope of finding a message/signature pair you didn't already have—i.e., it does not violate existential unforgeability.  It just means that you can find another public key under which a message/signature pair you already have is also valid.

One of the basic ideas of Chaum's ecash was to anonymize transactions except fraudulent double-spending transactions, so given one signature neither you nor the bank could determine who made it (but you could still confirm its legitimacy), whereas given two signatures the bank can deanonymize the fraudster.  However, rather than drop spoilers in your lap, I will leave you now to learn the thrilling details from the paper you are no doubt enjoying!


How to make the range of modulo $p$ to $[-\frac{p}{2};\frac{p}{2}]$?

If the value $x$ is in the set $\{0, 1, 2, .., p-1\}$, which is the "natural" set of residues moduli $p$, then, you just have to check if $x$ is greater than $\frac{p}{2}$ and if so, subtract $p$.

If $x$ does not belong to $\{0, 1, 2, .., p-1\}$, then you can first do the usual modular reduction to transform $x$ in a element of this set and then, do the subtraction if needed.

my_modular(x, p)
    if 0 <= x and x <= p-1
        if x > p/2
            return x - p
        else
            return x
    else
        new_x = x % p # usual modular operation
        return my_modular(new_x, p)

Notice that I am assuming the usual modular operation will not return negative values as you are saying the NTL's mod operation does.

Try to find a modular operation that return values in $\{0, 1, 2, .., p-1\}$.


What is the best-practice for encrypting small files?

The most important best practice in cryptography is: Don't invent your own algorithm, and to a lesser degree, don't invent your own protocol. An encrypted file format is a protocol.

Use an established format, like the OpenPGP message format, for your files. (This does support password-based encryption, too.)

This has the main advantage:

You can be quite sure that it is correct, i.e. no mistakes in the design which would allow easy cryptanalysis. (Not 100% sure, but at least a lot more eyes looked at it than will ever look at your own protocol.)

Another nice bonus is that your customers then are able to use the encrypted files also without your program, if necessary (e.g. when your program is not available on the system, has bugs, gets lost, or similar).


Bit-strength of discrete logarithm for a group of integers modulo a safe prime

For a proof of work scheme, you're probably better off making $p$ large enough that you don't have to worry about NFS (e.g. 2048 bits or more), or alternatively, using an elliptic curve group (e.g. P256 or Curve25519).

Instead, you'd tune things so that the generic attacks (e.g. Big-Step-Little-Step) are the optimal attacks, and use that to select the difficultly (range of $k$); if the solver knows that $0 < k \le M$, then these generic searches will take circa $\sqrt{M}$ group operations (modular multiplications, elliptic curve additions), and that's the best the searcher can do (assuming that he doesn't have any further insight into the group structure - that's what we're trying to ensure by making NFS infeasible).

Now, while this would work as a 'proof-of-total-work', I'm not sure if it really meets your requirements, because someone with significant amount of parallelism (e.g a botnet farm) may be able to accelerate this computation significantly.

A better approach might be to have the serve publish integer $g$, $k$ and a composite $n$, and ask the client to compute $g^{2^k} \bmod n$; this type of operation isn't greatly parallizable (because each squaring operation must be done sequentially), and the server (who knows the factorization of $n = pq$) can verify this by checking a claimed answer $A$ by the relation $A \equiv g^{2^k \bmod p-1} \pmod p$


What is the maximum length of a X.509 OID?

OIDs don't have a maximal length / depth specified. There is no real value where you can safely cut them off - or rather reject them (raise an exception or error). Anything over 20 bytes seems ridiculous, so that should be plenty. Limiting to a measly 1 KB of RAM should be fine on a non-embedded platform (desktop / server) as well, if you must set a limit.

When planning to protect against DoS attacks from certificates it is more useful to limit the amount of bytes of the entire certificate. It's not very efficient to limit each and every component within the certificate.

When programming in C/unmanaged C++ it is more reasonable to bother about ASN.1 based buffer overruns; those are common enough and extremely dangerous.


Why is this authentication procedure using Rabin crypto not useful?

A is acting as a square-root oracle in that protocol. We can use that oracle to factor $n$ and break the scheme.

Suppose you are an attacker that wants to impersonate A. You:

Pick a random $m$;
Send $m^2$ to A;
Compute $p = \gcd(m_1 - m, n)$, thus factoring $n$.

This works with probability $1/2$ for each attempt.


How to interpret a specific mathematical notation in "FIPS 202" (SHA-3 / Keccak)

It means the length of $Z$ in bits; in other words, squeeze out consecutive $r$-bit blocks from the sponge until you have a $d$-bit string, truncating the last block if necessary.

I expect you may overestimate the number of people who proofread this document with an eye for details like that.  Most cryptographers studying it will have read the Keccak reference, which uses slightly different notation meaning the same thing; most implementors will likely correctly guess that $|Z|$ and $\operatorname{len}(Z)$ mean the same thing when $Z$ is a bit string, or compare to another reference to confirm.


Is precomputing AES-CTR key stream secure?

Q0 : Is the precomputed key stream vulnerable to side-channel attacks like a lookup table for exemple ?

Of course not; once it is precomputed it sits in memory. Even if it is accessed, no actions are performed that depend on the randomized stream - other than the XOR with the plaintext of course. In principle that could be vulnerable, but since nothing is really location dependent, I guess that the risk is relatively low.
If the energy usage of the inputs of the XOR can be monitored then you can still leak information about the bits. E.g. if a large all zero plaintext is usually expected then you might be able to see an all one plaintext. Similarly on some systems even copying data can be dangerous, independent on the contents. So yeah, it depends on the system if side channels exist and if they are applicable at all.
And of course, if you store the key stream then anything accessing it breaks the scheme. The longer you store it, the higher the risk (e.g. against direct attacks against the RAM (Row hammer) or CPU (Spectre / Meltdown). You could of course argue that you're screwed even without a key stream if those apply...

If the precomputed key stream is very large like a few MB, it may be paged out to the disk, can another program access the key stream while it is in the disk like a file ( which will allow it to decrypt the corresponding plaintext easily

Generally not, as the OS will not allow a process to access another process memory. Of course, if you e.g. have an application server or virtualized system then other protections need to be in place. Beware that this doesn't say anything about the security of the page file if another system can be loaded. For that the page file should be encrypted and many operating systems at least contain that kind of functionality (if it is enabled by default is another matter).

Is there any other security issue with precomputing key streams ( real issues or wrong hypothesisies ) ?

Loosing sync would be one of my main issues. Also, a key stream directly used for CTR mode may indicate that the implementation is not authenticated.
Finally, AES is pretty fast on most processors. I would worry if the implementer would know what they were doing. It is likely that they e.g. use a managed implementation rather than a native / CPU supplied one. I would mainly use key streams to avoid latency issues rather than throughput issues.


Changing the public key in an MD5 certificate

Given an existing certificate, it isn’t practical.

MD5 is preimage-resistant, so it is not practical (given $x, y: x = \text{MD5}(y)$) to find $z: z \neq y \land \text{MD5}(z) = x$

But MD5 is still a TERRIBLE choice

MD5 allows for trivial collisions.  This has been used by malware to forge code-signing certificates.


Application of MDS matrices in serial and round-based implementations

what types of MDS matrices can be applied to serial or round-based
  implementations or both of them?

Serial matrices utilise a trade-off to reduce hardware requirement while incurring additional time cost. Examples of MDS matrices that can be serialized implemented are : cyclic , Hadmard, linear feedback serial (LFS), sparse diagonal serial invertible (DSI), ref. LED, PHOTON, PRIMATES use efficient serialized MDS matrices, ref.

It is possible to transform serial MDS to round-based , as following stated in ref.

  One may also consider unrolling DSI/LFS matrices to simulate round-
  based matrices for comparison with cyclic/Hadamard matrices in a
  round-based implementation scenario. That is to implement k copies of
  DSI/LFS matrices in series to achieve the MDS property in one clock
  cycle. The XOR count of all the matrices would simply be k times of
  what the tables have shown

MDS matrix is defined over $F_{2^n}$ and the choice of basis is important on implementation efficiency. for round-based hardware implementation, the choice of basis is important in lightweight construction. ref

I sugest to read the following papers to obtain deep knowledge:

Lightweight MDS Serial-type Matrices with Minimal Fixed XOR Count
Shorter Linear Straight-Line Programs for MDS Matrices Yet another XOR Count  Paper
Lightweight Multiplication in GF(2n) with Applications to MDS Matrices


Security strength of RSA in relation with the modulus size

Those appear to be based on the complexity of the General Number Field Sieve, one of the fastest (if not the fastest) classical factoring algorithms. I confirmed this in Mathematica.

Here is the complexity for the GNFS (source):

$$\exp\left( \left(\sqrt[3]{\frac{64}{9}} + o(1)\right)(\ln n)^{\frac{1}{3}}(\ln \ln n)^{\frac{2}{3}}\right)$$

where $n$ is a number to factor. Evaluating the above expression at $2^b$ is a rough approximation of the the time needed to factor a $b$-bit integer. Here's a table showing the bit-length of the evaluation at $2^{1024},2^{2048},\dots$:

Strength  RSA modulus size   Complexity bit-length
  80        1024               86.76611925028119
 112        2048              116.8838132958159
 128        3072              138.7362808527251
 192        7680              203.01873594417665
 256       15360              269.38477262128384

I generated these numbers with the following Mathematica code:

({#, N@Log2@gnfsComplexity[2^#]} &) /@ {1024, 2048, 3072, 7680, 15360}

where gnfsComplexity is defined as:

gnfsComplexity[n_] := Exp[(64/9 * Log[n])^(1/3) * (Log[Log[n]])^(2/3)]

which is not the prettiest thing I've ever written, but it seems accurate. (For those unfamiliar with Mathematica, the second code snippet defines a function that's a transliteration of the above GNFS complexity for a number $n$. The first code snippet evaluates that complexity at $n=2^{1024}, 2^{2048}$, etc., takes the logarithm base 2, and converts it to a numerical approximation — a decimal number — instead of an exact result like a fraction.)

As for the reasoning behind the larger key sizes for RSA, the explanation's not too difficult. If you look at the document in the question, you will notice that the "bits of security" for block ciphers correlate almost perfectly with the size (in bits) of the keys for that block cipher (with rare exceptions). This is because our best attack on a secure block cipher essentially is a brute-force search for the key, which on average takes $2^{n-1}$ time where $n$ is the bit-length of the key.

However, for RSA, our best line of attack is not to execute a brute-force search for the key; instead, we "simply" factor the (public) modulus, so the security of the scheme revolves around the efficiency of factoring. The GNFS has a sub-exponential but still super-polynomial time complexity, and one can use this time complexity to roughly approximate the security offered by the scheme. I believe that's what the NIST is doing here.


What is the difference between a hash and a permutation?

As Henrick notes, permutation is a mathematical term for a function (or map; these two words are essentially synonymous in mathematics) that rearranges the elements of its domain so that exactly one input is mapped to each output.

In other words, a function $f$ from a set $S$ to $S$ is a permutation if and only if:

no two inputs are mapped to the same output: $f(x) = f(y) \implies x = y$, and
some input is mapped to every output: for all $y \in S$ there exists $x \in S$ such that $f(x) = y$.

For finite sets $S$, these two conditions are in fact equivalent: either one implies the other.  This is easy to see using a counting argument: since the number of possible inputs equals the number of possible outputs, if any two inputs are mapped to the same output, there must be at least one output which is left without any corresponding input, and vice versa.

(In fact, some mathematicians prefer to reserve the word "permutation" only for the case where the domain is finite, and use the word "bijection" for the more general case described above; others treat the two words as more or less synonymous.  Also, in some branches of mathematics, a permutation of an $n$-element set $S$ is commonly defined as a function from the set $\{1, 2, \dotsc, n\}$ to $S$, rather than from $S$ to $S$.  However, these variations in usage don't really make any significant difference for most purposes, certainly not in cryptography.)

A useful mathematical property of permutations is that they are uniquely invertible: that is, given a permutation $f: S \to S$, there exists a unique permutation $g: S \to S$ such that $g(f(x)) = x$ for all $x \in S$.

The number of different permutations of an $n$-element set $S$ — that is, functions $f: S \to S$ which satisfy the definition above — is $k! = 1 \times 2 \times 3 \times \dotsb \times n$.  A random permutation of a set $S$ is simply a function chosen uniformly at random from the set of these $n!$ possible permutations of $S$.

For cryptography, the significance of random permutations is that they are ideal ciphers for messages in the set $S$: the invertibility means that a message encrypted using the permutation $f$ can be decrypted using the corresponding inverse permutation $g$, and if $f$ is chosen randomly from the set of all permutations of $S$, the encryption $y = f(x)$ of any given message $x \in S$ will also be uniformly random, and thus provides no information about the original message $x$ to anyone who does not know $f$.

For small sets $S$, it's possible to examine all the possible permutations of $S$ one by one, but as the size of the set grows, the number of possible permutations quickly becomes truly enormous, and it becomes meaningful to speak of pseudorandom permutations.  These are functions chosen from some smaller (but still very large) subset of the full set of permutations of $S$, but in such a way that there is (hopefully) no way for anyone to efficiently distinguish a permutation randomly chosen from the subset from a truly random permutation chosen from the full set of permutations of $S$.

A common type of pseudorandom permutations in cryptography are block ciphers.  These are permutations of $b$-bit bitstrings, for some fixed number $b$, where the mapping of inputs to output is determined in some complicated way by a $k$-bit bitstring called the key.  (Block ciphers are normally also constructed in such a way that the inverse permutation can also be easily computed based on the key.)

Typical values for $b$ and $k$ might be, say, 128 bits each.  Now, clearly, the number of possible keys, $2^{128}$ (which generally equals the number of distinct permutations achievable using a given cipher algorithm, assuming that the cipher has no equivalent keys) is a vanishingly small fraction of the total number $(2^{128})! \approx 2^{2^{133}} \approx 2^{1.3 \times 10^{40}}$ of possible permutations of 128-bit bitstrings.  However, it's still a huge number: if we had a billion ($10^9$) computers, each running at 1 THz with one instruction per cycle, it would still take 10 billion years for these computers just to execute $2^{128}$ instructions.  Thus, it's completely impossible to tell if a permutation is chosen from a $2^{128}$-element subset or from the full set of $(2^{128})!$ permutations of $128$-bit bitstrings just by comparing it with each of the permutations in the subset in turn; and we hope that, for modern block ciphers like AES, there is also no other, significantly more efficient way to distinguish them from a random permutation than such a "brute force" attack.

OK, so that's what a permutation is and how they're used in cryptography.  What about hashes?  A hash function is a map from the infinite set of all bitstrings of any length to the finite set of bitstrings of length $b$ for some fixed number $b$.  Thus, a hash cannot be a permutation (in any sense of the word): the set of possible inputs of a hash is strictly larger than the set of possible outputs, and thus it must map multiple inputs (in fact, infinitely many of them) to the same output.

In particular, this means that a hash function cannot be invertible, since, at least for some outputs, there's no way to tell which of the many possible equivalent inputs produced that output.  Even if we restrict the inputs to bitstrings of some constant length $\ell$, this holds whenever $\ell > b$ (and is likely to hold even for somewhat shorter inputs).

Hashes are closely related to message authentication codes (MACs), which can, in some ways, be viewed as families of hash functions, where the choice of the specific function from the family is determined by some secret key — just like a block cipher is a family of permutations, from which one permutation of chosen by a key.  In this sense, secure MACs can be seen as pseudorandom functions, which resemble truly randomly chosen functions from their respective input set to their output set in the same way as pseudorandom permutations resemble truly random permutations.

(Actually, the usual definition of a secure MAC doesn't really require complete pseudorandomness, but merely "unforgeability".  However, any pseudorandom function from the set of all bitstrings to a set of fixed-length ones does satisfy the definition of a secure MAC, even if not all MACs are necessarily  pseudorandom functions.)

However, what we normally require from cryptographic hash functions is both something more and something less than pseudorandomness.  This is because hash functions differ from MACs in that they have no secret key, and so anyone can calculate the same hash for a given input equally well.  In particular, this means that it's trivially easy to distinguish any given hash from a random function just by comparing the outputs to those of a known instance of the same hash function.

Instead, what we typically require from cryptographic hash functions is resistance to collision and preimage attacks.  That is, even an attacker who knows how the hash function is calculated, and can calculate the hash for any input they want, should be practically unable to either:

find an input that hashes to a given output value (first preimage resistance),
find another input that hashes to the same output as a given input (second preimage resistance), or
find any two inputs that hash to the same output (collision resistance).

So, no, a hash is never a permutation — and, other than that, the two concepts really don't have much to do with each other at all.


How can I generate a deterministic evenly distributed random number in a blockchain

You are looking for a Verifiable Delay Function (VDF). Roughly VDFs are functions which are hard to parallelize but easy to verify (for some sense of easy).

One simple example is to just iterate a hash function, although this has linear verification time while more advanced functions may have sublinear verification complexity.

Here is an overview of VDFs for deterministic unpredictable values


Is there short period in AES 128 key schedule?

During each round of the AES key schedule, they stir in an 'rcon' value.  This constant differs for each round, and so even if the state of the key schedule just happened to be exactly the same in, say, rounds 2 and 5, the differing rcon values would mean that the keys during round 3 and 6 would differ.  Hence, the AES 128 key schedule is nonperiodic.

So, if you take the last subkey, and reuse it as the key for the next block, the only way you can come up with a repeating pattern is to generate the same AES 128 key.  Since that's the normal way to use AES, that's not a problem.

On the other hand, doing what you propose would mean that the AES keys you use are related; that the subkey for the last round is exactly the same as the first subkey for the next block.  Now, AES-128 is not known to be vulnerable to related key attacks, and the related keys for the known AES-192 and AES-256 vulnerabilities are considerably different; however it does bear wondering whether this is something that you should trust.


Recover secret SHA-1 constants given Oracle

No.  If it were, that would demonstrate a PRF distinguisher against the SHA-1 compression function, which would be an astonishing result showing that SHA-1 is far more broken than anyone has ever seriously anticipated.


Yes, it can be implemented as an AEAD cipher, although the common definition uses ChaCha20 instead. ChaCha is a cipher with slightly better diffusion and better performance characteristics; both ciphers are by Daniel Bernstein. If you want to use Salsa instead, then just replace ChaCha20 with Salsa20 - but I would rather not do that.

ChaCha20 / Poly1305 is for instance implemented in a TLS 1.3 cipher suite, which references RFC 8439: ChaCha20 and Poly1305 for IETF Protocols, section 2.8, which defines AEAD_CHACHA20_POLY1305. A well used RFC is a clear indication of standardization.


As a MAC, HMAC is fine, with any of the SHA-* functions. It's even fine with MD5, even though MD5, as a hash function, is quite broken. One interesting characteristic of HMAC is that it requires no nonce or IV, which makes it quite harder to get it wrong. It's also very easy to implement (over a hash function implementation), and a straightforward implementation will even be constant-time.

Now, HMAC is defined with two nested hash function invocations, so as to provide a secure MAC when the underlying hash function is a Merkle-Damgård design (like SHA-1 or SHA-256). SHA-3 was defined so as to make that double invocation unnecessary; with SHA-3 you can simply hash the concatenation of the MAC key and the data, and that is a good MAC, while doing the same with SHA-256 or SHA-512 would fall prey to the so-called length extension attack. However, you can also use HMAC with SHA-3, it works and is not insecure.

Over long input data, HMAC has about the same performance as raw hashing, so it is quite fast, and it takes some effort to find a situation when that speed is not already more than sufficient. If you found a case where you actually need an extra boost, then there are other MAC constructions that can give it to you, e.g. Poly1305. However, they are more difficult to implement, and even more so to use properly, because they need a non-repeating nonce, which is not a simple requirement in many contexts.

That being said, most usages of MAC are, in practice, part of protocols that combine MAC and encryption. Making both safely is known to be fraught with perils (SSL, famously, got it wrong), so you would be well-advised to use an authenticated encryption mode that will do the job in a cryptographer-approved way. Usual AEAD modes include AES/GCM and ChaCha20+Poly1305. Selecting such a mode voids the question of choosing a stand-alone MAC.

Speaking of good advice, Schneier and Ferguson got it wrong (at least in the first edition of their book), in that they recommend to use MAC-then-encrypt (MAC on the plaintext, not on the ciphertext), which is exactly what plagued SSL/TLS before TLS 1.2 introduced AEAD-powered cipher suites.


When $c=1$ and $d = r^2$, an Edwards curve $x^2+y^2=c^2(1+dx^2y^2)$ becomes $$x^2+y^2=1+r^2x^2y^2 \iff x^2(1-r^2 y^2) = 1 - y^2$$
With the $(Y,Z)$ notation, a point $P = (x,y)$ is represented as a pair $(Y:Z)$ satisfying  $ry = Y/Z$.  Note that this representation does not allow to distinguish $P = (x,y)$ from $-P = (-x,y)$.

Given a pair $(Y:Z)$, one can recover $\pm P = (\pm x, y)$ where $y = Y/(rZ)$ and $\pm x$ is the square root of $(1-y^2)/(1-r^2y^2)$.


Lenstra's ECM Algorithm - field requirement

In Lenstra's ECM algorithm, $\#E(\mathbb{F}_{p})$ is required to have small prime factors. Why is this so?

Actually, it is not required to have small prime factors; it does work better (that is, succeeds quicker) if it happens to have small factors.  To explain it fuller, we'll look at ECM and the p-1 method, which brings up your comment:

  I understand that the p-1 method is efficient for factoring N with small factors.

Actually, what it is good at is factoring N that happens to have a prime factor p where $p-1$ is smooth; that is, consists only of small factors.

The p-1 and the ECM method both work this way: we take our composite number $n = pq$ (where, in general, can have more than two prime factors), and set secret values $p - \epsilon_1$, $q - \epsilon_2$.  Then, we keep on guessing prime factors of $p - \epsilon_1$, $q - \epsilon_2$; if we guess all of the prime factors of one of them, then we immediately get the factorization (and other than time, there's no penalty for making incorrect guesses).

That's what they have in common; now, here's the difference between p-1 and ECM.  With the p-1 method, we always have $\epsilon_1 = \epsilon_2 = 1$ (and that's what having $p-1$ smooth is important; we'll guess small factors, and so $p-1$ works when all the factors are small).  Now, with ECM, $\epsilon_1, \epsilon_2$ are small (compared to the magnitude of $p, q$), but can vary to a large extent (depending on the curve).

And, that's the advantage of ECM: the p-1 method is entirely dependent on something beyond the algorithms control.  If both p-1 and q-1 contains a large (unguessable) factor, it's out of luck, and there's nothing the algorithm can do about it.  With ECM, we can try lots of different curves (with different $\epsilon_1, \epsilon_2$ values), and we might get lucky with one.


What are the two parts of SHA1's compression function called?

The part where 16 words are expanded into 80 words is often called message schedule (the name in FIPS 186-4) or message expansion; that's also the key expansion phase of the cipher at the core of the compression function (SHA1's message block is the key of that cipher, due to the Merkle-Damgård + Davies-Meyer structure of SHA-1).

The rest of the compression function would be the compression itself; or the encryption step of the cipher followed by the Davies-Meyer final combination (which, in SHA-1, is five additions modulo $2^{32}$, rather than XOR).