Are common (secure) stream ciphers CCA1-secure?

For stream ciphers, IND-CCA1 and IND-CPA security differ precisely in that an attacker can choose the IV in the CCA1 game (because that's part of the ciphertext that can be submitted to the decryption oracle); but in the CPA game is constrained to whatever choice of IV the cryptosystem makes.

We can artificially construct a stream cipher vulnerable under CCA1, but not under CPA: consider AES-128 in CTR mode with random IV, except that the AES encryption block is modified so that for all-zero input block, the output block is the key. Decryption no longer works for the block cipher, but it still works for the stream cipher (albeit differently when the counter is initialized to all-zero, or reaches that). Under the CCA1 game, an adversary recovers the key by submitting to the decryption oracle a ciphertext with all-zero IV and first block of ciphertext; while there's no way to take advantage of the modified block cipher under the CPA game, and the stream cipher remains secure (the adversary has negligible odds to get the IV to reach zero, thus the stream cipher is indistinguishable from true CTR mode, which is IND-CCA1).

For a less artificial example, we can hypothesize a block cipher vulnerable to key recovery under CPA, but not under random Known Plaintext Attack. That weakness directly makes the derived CTR or OFB stream cipher vulnerable under CCA1, but not under CPA.

Thus if there was a block cipher vulnerable to key recovery under CPA but not random KPA, with the corresponding CTR or OFB stream cipher common, that would be a common stream cipher not IND-CCA1, answering the question in the negative.

However I know no common stream cipher that's vulnerable under CCA1. Much to the contrary, modern native stream ciphers like ChaCha20 and Salsa20/20 aspire and appear to be IND-CCA1. And modern block ciphers are believed secure under CPA, and their corresponding CTR stream cipher is accordingly believed IND-CCA1 (just as claimed in that other answer, even if I fail to follow it's proof sketch).


Is there a way of encryption that allows to check what encrypted values are close to their mean?

If I understand what you're looking for correctly, that would completely destroy the security.

First off, if an attacker can compute the difference between her value and the mean, it is trivial to find the actual mean. Simply encrypt the number $0$ and then compare it to the mean.

If she can compute the mean of any subset, it's pretty trivial to recover plaintexts: just compute the "mean" of a single ciphertext. Even if you somehow make it work only for subsets of a particular size or something, she can still decrypt an arbitrary ciphertext $c$ like so:

$$ d(c) = (N+1)(\mu(S\cup m)-\mu(S\cup e(0)))$$

Where $e(0)$ is the encrypted $0$, $S$ is some arbitrary subset of the ciphertexts, $N$ is the size of $S$, and $\mu$ is the mean of a subset.


The cloud trend brought its problems. While in the classical system your servers were near to you, so the side-channel capability was limited. They were mostly on the smart-card systems where the card reader is malicious.
There are side-channel attacks on the cloud if the attacker can co-locate with you for this you need to use a shared machine to reduce your cost. Co-locating is a real problem since you are not selecting your cloud machine when you use shared hardware where virtualization happens.
Cache-Attack
Assume the attacker located you, so both you and the attacker use the same hardware. What they can do? Cache-attack on the AES encryption. This attack works if you encrypt your files on the server and use software AES (not AES-NI) that was using T tables for the encryption.
During your encryption the attacker runs their process, fills all of the cache lines, waits, your AES runs, and they enter again, then they check the cache lines. If a line still has attacker's data this implies the cache line is not used during the encryption, if changed then it is used during the encryption. Cache hit and cache miss. After many many steps, the key is extracted. How cache works see B degnan's answer.
Some articles;

2007 - ACI ICMEZ, O. Yet another microarchitectural attack: exploiting
I-Cache.

2012 - WEISS, M., HEINZ, B., AND STUMPF, F. A cache timing attack
on AES in virtualization environments

2016 - Ashokkumar C.; Ravi Prakash Giri; Bernard Menezes (2016). "Highly Efficient Algorithms for AES Key Retrieval in Cache Access Attacks"

2018 - Mehmet S. Inci; Berk Gulmezoglu; Gorka Irazoqui; Thomas Eisenbarth; Berk Sunar, Cache Attacks Enable Bulk Key Recovery on the Cloud

2018 - Gorka Irazoqui; Mehmet Sinan Inci; Thomas Eisenbarth; Berk Sunar Wait a minute! A fast, Cross-VM attack on AES

2018 - Yuval Yarom; Katrina Falkner, Flush+Reload: a High Resolution, Low Noise, L3 Cache Side-Channel Attack
.

Now the above works if you encrypt on the cloud and use software AES.
Deduplication
The aim was to eliminate copies of the data in the memory so that the cloud provider can reduce the cost, and we have another attack vector.

2011 - SUZAKI, K., IIJIMA, K., YAGI, T., AND ARTHO, C. Memory deduplication as a threat to the guest.

2015 - Gorka Irazoqui, Mehmet Sinan Inci, Thomas Eisenbarth, and Berk Sunar Know Thy Neighbor: Crypto Library Detection in Cloud. PoPETs 2015, 1 (2015)

2018 - Jens Lindemann and Mathias Fischer A Memory-Deduplication Side-Channel Attack to Detect Applications in Co-Resident Virtual Machines

This helps the attacker to determine whats is going on with the neighbors ( on the shared machine).
Spectre and Meltdown

Whereas Meltdown allows unauthorized applications to read from privileged memory to obtain sensitive data from processes running on the same cloud server, Spectre can allow malicious programs to induce a hypervisor to transmit the data to a guest system running on top of it.

Spectre is the thread to the shared hardware with hypervisor and patching the Spectre is not an easy job.
If you encrypt locally and use the cloud only as a storage service, then this means you don't process your data then you are fine from this attack.
But if you want the encryption on the server, this brings problems, you may be lost your encryption key. To mitigate this, some cloud providers provide HSM on the cloud those are useful mostly for servers and of course have some additional costs.
Encrypt locally, most CPUs have AES-NI so you have fast encryption locally. Use a password manager to manage your key and use a good password like dicewire for the master password.
The problem starts when you want to access your files. Dou you want to search on them then you need a mechanism. This is another long story. Start reading from the Song's famous article about this.
In any case, Fully-Homomorphic Encryption is the holy grail of Cryptography to solve many issues about the operation on the encrypted data. Let write some applications, waits there.
An important note should be taken; due to the business consideration, the cloud-provider considered a semi-honest adversary that is semi-honest adversary obeys the protocol however, they can use all information they observed and deduce more if they can. Over time we understood that this approach is not correct. We should consider them as a covert adversary,

Covert
adversaries have the property that they may deviate arbitrarily from the protocol specification in an attempt to cheat, but do not wish to be “caught” doing so

So if you plan to store your data, even only for storage, use authenticated encryption to produce the integrity and authentication of your data. A Merkle Tree-based approach is necessary to ensure the freshness of your data ( to detect a possible rollback).


I want to know difference of calculation cost between SHA(hash) and AES(reversible encryption)

With AES/CBC mode, an attacker can modify the string, and have the result decrypt without errors; the only thing that can cause a decryption failure is an illegal padding pattern after decryption, and:

If the plaintext string is at least 17 bytes long, then the attacker can modify the string without affecting the padding bytes (and thus leave a valid padding pattern)
Alternatively, changing the entire ciphertext randomly leaves a 1/256 chance that, after decryption, the last byte of the ciphertext is 01 (which is a valid padding pattern)

Hence, to answer your question, HMAC-SHA256 is the best answer, as AES doesn't do the job at all.  If your crypto toolkit provides it, you might want to consider AES-CMAC instead (which is another right answer for this problem)


Should the signature be prefix or postfix to the message in the sign-then-encrypt scheme?

Secure encryption does not care about how the data is ordered.

With the typical single use symmetric keys that hybrid encryption uses, I cannot think of a way it could matter one way or the other. With key reuse (if you used symmetric encryption on signed data), there are some cases where having the "randomness" from the signature in the first blocks might help, but that would mostly be papering over security holes.

In practice, having it at the end may be preferable if it allows for a streaming interface where the data gets encrypted and maybe even sent before all data is ready to be signed.


First, PKCS#7 -- almost always considered to include its successor CMS in the same way "SSL" usually means TLS -- supports several cryptographic functions; you appear to be asking only about signing, so I will ignore the other parts. If you want more, read the RFC and/or add to your question.

PKCS#7/CMS has two options for signed data, one where the data is contained within the SignedData message, usually called embedded,
and one where the data is not in the message but must be available to the recipient, usually called separate, external, or detached.

PKCS#7/CMS messages including SignedData (but not necessarily external data) are first encoded in ASN.1 BER or DER
which can then be transmitted and/or stored in binary or in PEM format using the dashed BEGIN,END PKCS7|CMS lines around a base64 encoding. (CMS messages
can also be used in S/MIME messages with a slightly different formatting, but those are usually called S/MIME not PKCS#7 or CMS. In particular, a "clearsigned" S/MIME message contains a detached encoded signature plus a more-readable direct encoding of the data as parts of one email message.)

A PKCS#7/CMS SignedData can carry one or more signatures, but more is rare;
it can carry certificate(s) and/or CRL(s) that the signer believes the recipient(s) will or may need to verify the
signature, but this is not required if the sender knows or believes the recipient(s) have or can get the certificate(s) and revocation info by other means.

In fact, PKCS#7/CMS SignedData can be used with no signatures and no data solely to carry some related certs (and possibly CRLs);
this is commonly indicated as "p7b" or "p7c" format. This doesn't apply to your case, but could be confused with it.

You can determine which elements are present in a given message by parsing it; if particular, if you have or get
OpenSSL openssl asn1parse will by default decode a PEM file (ignoring the type stated in the BEGIN,END lines, which can even be omitted) or with -inform der a binary DER file.


This has to do with the physical nature of the storage device. Simply deleting the reference still leaves the data available for recovery. Writing once over randomly might still leave chunk traces of data which could be pieced together.

It is not generally considered easy to recover information overwritten once, and for your own pc... being donated or sold... once is probably enough. Depending on your own scale of paranoia you can use more passes.


I want to know what will happen if data is only 8 bytes?

If the data is already 8 bytes then you need an additional block that contains 8000000000000000 (15 0s) since the Padding method 2 is mandates adding 1 and necessary 0's.
Note that the Padding Mechanism 2 is not byte-oriented, it is bit-oriented. Whenever the data finishes you add 1 and add necessary zeros in minimal so that the data size is multiple of the chosen block cipher.

for 7 bytes

In this case, you just add 0x80. 7 zeroes are added after 1 to fit 64.

I should feed data directly to 3DES algorithm or I should first feed it to DES then feed it to 3DES?

This MAC is as known as

ANSI Retail-MAC
CBC-MAC-Y or
ISO/IEC 9797-1 algorithm 3.

With the DES it is also called the DES Retail MAC and uses two keys $K$ and $K'$.
Firstly it works as DES-CBC then the output performed like 3DES in Encrypt-Decrypt-Encrypt with two keys on the last block x-ored with $H_{q-1}$. One doesn't need a 3DES implementation to achieve this.
\begin{align}
H_1 & = e_K(D_1) \\
H_i & = e_K(D_i \oplus H_{i-1}), \quad (2 \leq i \leq q)\\
MAC & = e_K(d_{K'}(H_q)).
\end{align}
If we re-write the equation
\begin{align}
H_1 & = e_K(D_1) \\
H_i & = e_K(D_i \oplus H_{i-1}), \quad (2 \leq i \leq q-1)\\
MAC & = e_K(d_{K'}(e_K((D_q \oplus H_{q-1}))).
\end{align}
The Triple-DES (EDE) will appear in the end.
The attacks on DES Retail MAC
The attack on DES Retail MAC formalized as four tuple $[a,b,c,d]$ where

$a$ is  the number of offline block cipher encipherments
$b$ denotes the number of known data string/MAC pairs
$c$ denotes the number of chosen data string/MAC pairs
$d$ denotes the number of on-line MAC verifications, and
$k$ is key size
$n$ is the block size
$m$ is the zeros of padding.

On 1996, Preneel and Oorschot achieved  $[2^{k+1},2^{n/2},0,0]$ on
Key recovery attack on ANSI X9.19 retail MAC
On 1998, Knudsen and Preneel achieved $[2^k,1,0,2^k]$ on
MacDES: MAC algorithm based on DES
On, 2002 Mitchell achieved $[2^{k+1},0,0,(\lceil n/m \rceil +1) 2^{(n+m)/2-1}]$ on A new key recovery attack on the ANSI retail MAC

Therefore, if there is no specific usage, don't use it.


What are the odds of collisions for a hash function with 256-bit output?

Birthday problem for cryptographic hashing, 101.

Let $p_n$ be the probability of collision for a number $n$ of random distinct inputs hashed to $k$ possible values (that is, probability that at least two hashes are identical), on the assumption that the hash is perfect. That $p_n$ is also the minimum probability of collision with no hypothesis on the hash.

Obviously, $p_0=p_1=0$ (until there are at least two hashes, no collision is possible); and $p_j=1$ if $j>k\;$ (by the pigeonhole principle, with more than $k$ pigeons for $k$ holes, at least one pigeon needs to share a hole with another).

Let $q_j=1-p_j\;$ be the probability of no collision for $j$ hashes, with $q_0=1$. When we add another hash after there was no collision among the previous $j$ hashes, the new hash has probability $\frac j k$ of matching one of the $j$ previous hashes (creating the first collision), and probability $1-\frac j k$ of not creating a collision. Hence the recurrence: $q_{j+1}=q_j\,\bigl(1-\frac j k\bigr)$. It comes the exact:
$$p_n=1-q_n\quad\text{with}\quad q_n=\;\prod_{j=0}^{n-1}{\Bigl(1-\frac j k\Bigr)}\;=\;{\frac{k!}{(k-n)!\;k^n}}$$

That is also $\displaystyle q_n\,=\,P(k,n)/k^n\,=\,C(k,n)\,n!/k^n\,=\,{k\choose n}\,\frac{n!}{k^n}$, where $P(k,n)$ is the number of permutations of $n$ things among $k$, and $C(k,n)={k\choose n}$ is the number of combinations of $n$ things among $k$ (beware that $k$ and $n$ are reversed in this answer compared to the linked references).

This is fine for low $k$ and $n$, but impractical for large values. With $n\ll k\,$, applying that for small $\epsilon>0$ it holds that $\log(1-\epsilon)\lessapprox-\epsilon\;$, we get
$$\log(q_n)\;=\;\sum_{j=0}^{n-1}{\log\Bigl(1-\frac j k\Bigr)}\;\lessapprox\;-\frac 1 k\sum_{j=0}^{n-1}j\;=\;{-\,\frac{n\,(n-1)}{2k}}$$

In summary we have exactly
$$
\begin{align*}
p_n=1-q_n&=1-\frac{k!}{(k-n)!\;k^n}&&=1-P(k,n)/k^n\\\\
&=1-{k\choose n}\,\frac{n!}{k^n}&&=1-C(k,n)\,n!/k^n
\end{align*}$$
and as fair approximations when the above is inconvenient
$$p_n=1-q_n\quad\text{with}\quad
\begin{align}
&q_n\lessapprox e^{-n\,(n-1)/(2k)}&\text{(assuming $n\ll k$)}\\
&q_n\approx e^{-n^2/(2k)}&\text{(additionally assuming large $n$)}
\end{align}$$

From this we can derive that for large $k$ as used in cryptography, or a $b$-bit hash (where $k=2^b)$, probability and odds of collision for $n$ random messages are approximately
$$
\def\alignedcolumn#1#2#3#4#5{\phantom{#1}\llap{#3}\mathrel{#4}\rlap{#5}\phantom{#2}}%
% Specify the widest expressions on the left-hand and right-hand sides.
\def\ncolumn{\alignedcolumn{1.177\sqrt k}{2^{b/2+0.236\ldots}}}%
\def\pncolumn{\alignedcolumn{1-e^{-1/2}}{00.0\%}}%
\def\oddscolumn{\alignedcolumn{}{11/17}}%
\begin{array}{c|c|c}
n&\text{$p_n$ of collision}&\text{odds of collision}\\
\hline
\ncolumn{\sqrt k}={2^{b/2}}&\pncolumn{1-e^{-1/2}}\approx{39.3\%}&\oddscolumn{}\approx{11/17}\\
\ncolumn{1.177\sqrt k}\approx{2^{b/2+0.236\ldots}}&\pncolumn{1/2}={50\%}&\oddscolumn{}{\phantom{=}}{\hphantom{1}1/1}\\
\ncolumn{1.414\sqrt k}\approx{2^{(b+1)/2}}&\pncolumn{1-e^{-1}}\approx{63.2\%}&\oddscolumn{}\approx{12/7}\\
\ncolumn{2\sqrt k}={2^{b/2+1}}&\pncolumn{1-e^{-2}}\approx{86.5\%}&\oddscolumn{}\approx{19/3}
\end{array}
$$

The applied cryptographer is often interested in very low probability of collision $p_n$, as occurring for $n\ll\sqrt k$. The above approximation remains mathematically valid and usable for $q_j$, but can give inaccurate results for $p_j=1-q_j$ because the difference is orders of magnitude smaller than either term in the subtraction. We need another method.

Observe there's a collision when the $i$th hash equals the $j$th hash, for any pair $(i,j)$ with $1\le i<j\le n\;$; and for each of such $n(n-1)/2$ pairs, there is probability $1/k$ of a collision. Probabilities for such $n(n-1)/2$ events are not quite independent, but for low overall probability of collision this remains a valid approximation, as well as approximating very low probability that any of multiple events occurs to the sum of the probabilities of each event. We get these approximations
$$\begin{align*}p_n&\lessapprox{\frac{n\;(n-1)}{2k}}&\text{(assuming $n\ll\sqrt k$)}\\
&\lessapprox{\frac{n^2}{2k}}&\text{(additionally assuming large $n$)}\end{align*}$$

For example, with $n=2^{100}$ distinct random inputs (hypothetically) hashed to $b=256$ bits with a perfect (or even passable) hash, probability of collision is about $2^{2\cdot100-1-256}=2^{-57}$ (less than 8 chances in a million million millions, which can safely be discounted).

In the question, we have a hash with $b=256$-bit, that can thus take $k=2^b=2^{256}$ output values, and $n=2^{130}+1\;$. Here $k$ is large, $n\ll k$ and $n\not\ll\sqrt k$, therefore the appropriate formulas are

$$p_n=1-q_n\quad\text{with}\quad q_n\approx e^{-n^2/(2k)}\quad\text{(assuming large $k$ and $n\ll k$)}$$

The $+1$ term in $n=2^{130}+1$ is negligible, and we get $-n^2/(2k)\approx-\left(2^{130}\right)^2/\left(2\cdot2^{256}\right)=-2^{2\cdot130-1-256}=-2^3=-8\;$, giving $q_n\approx e^{-8}\approx0.034\%$ and $p_n\approx99.966\%\;$.

Notes: $n\approx2^{130}$ is so large that it is practically impossible to carry that number of operations, much less hashes. The question's body, and the present answer, thus does not contain anything that could help practically towards finding collisions for a hash function with a 256-bit output size (as in the question's original title).
The approximations 99.8% and 99.99% in the question are incorrect in their last digit, whatever the rounding convention.


The second point is very simple:
if you have $w_1, w_2, w'_1, w'_2$ so that $g_1^{w_1} g_2^{w_2} = g_1^{w'_1} g_2^{w'_2}$, then $$g_1^{w_1-w'_1} = g_2^{w'_2 - w_2},$$
and having $g_2 = g_1^{x}$ for some unknown $x$,

$$g_1^{w_1-w'_1} = g_1^{x(w'_2 - w_2)},$$
or equivalently
$$w_1 - w'_1 = x(w'_2 - w_2)\mod q,$$

where $q$ is an order of the group.

Finally, $$x = (w_1 - w'_1)(w'_2 - w_2)^{-1}\mod q$$

The first your point is rather due to witness-indistinguishability property


Eavesdropping experiment with private key

Here is a simple/laymans explanation of what the example is (most likely) about:

Suppose you are given a new ciphering scheme (set of encryption and decryption algorithms) and you need to find out if it is secure. In cryptography, the security can be analyzed by issuing a challenge to the eavesdropper or adversary $A$. If the adversary wins the challenge, the cipher is insecure and vice-versa. This exercise consists of the following steps:

The challenger $C$ (on the left in your figure) generates a random key $k$ of appropriate length: a randomly-generated $n$ bit key would mathematically be represented as $k \leftarrow Gen[1^n]$ or $k \leftarrow \{0,1\}^n$ (I find the latter representation clearer).
The adversary $A$ (on the right in your figure) inputs two messages $m_0$ and $m_1$ to the challenger. Assuming these are $n$ bit messages, one can represent them as $\{0,1\}^n$ too.
The challenger encrypts only one of these messages $c \leftarrow Enck(k,m)$ with $m$ = $m_0$ or $m_1$. (Think of the challenger tossing a coin; if he gets heads/tails, he encrypts $m_0/m_1$). In the figure, this operation is represented as $c \leftarrow Enck(k,m_b)$ which then depends on the value of a single bit $b$.
The ciphertext $c$ is handed to the adversary who analyzes it with all possible resources he/she possesses (remember though that they don't know the key) and at the end of the analysis, outputs a bit $b_0$.
If $b_0 = b$, the adversary has won the challenge.

Remember the last line is to be interpreted in a statistical sense, i.e., if the challenger-adversary game is played $2N$ times, $b_0 = b$ must be true for $>N$ times.


What is the major difference between FIPS 186-2 and FIPS 186-4?

To clarify scope:

FIPS 140-2 itself doesn't say anything about DSS, though it has 186-2 as a reference. It was published in 2001, before 186-3 and -4, and has not been superseded. After 140-3 spent 8 years in draft they recently decided to consider using ISO/IEC 19790 instead!
140-2 Annex A (Approved functions) is updated frequently and does now reference 186-4.
most people don't want just 140-2 implementation but rather 140-2 certification under the Cryptographic Module Validation Program (CMVP) and that is controlled by the 140-2 Implementation Guidance linked at that page (currently and usually under 'Announcements' because it keeps changing, and always in 'Standards').

The current IG has a section on 'Validating the Transition from FIPS 186-2 to FIPS 186-4' in W.2; formerly it was G.15. As indicated there, the technical changes between 186-2 and -4 were, if I haven't missed any:

delete several specific RNGs and instead require RBGs Approved by a separate standard, currently SP800-90A
DSA: add cases for $p$ size 2048 with $q$ size 224 or 256, and 3072 with 256, using hashes from FIPS 180 (now SHA-224 SHA-256 or SHA-512/224 SHA-512/256). Note 186-2 change notice 1 already eliminated $p$ sizes below 1024 which were in -0 through -2 original.
DSA: expand the parameter generation algorithms to prefer Shawe-Taylor provable primes while still allowing Miller-Rabin with optional Lucas probable primes, and use a strength-matched hash; explicitly specify parameter validation (including legacy parameters using the -2 and earlier method) which had been implicit
DSA and ECDSA: more robust privatekey and $k$ (nonce) generation
RSA: allow RSA signature schemes PKCS1-v1_5 and PSS from PKCS#1v2.1 (with a constraint on salt for PSS) in addition to previous X9.31. Note these were already Approved in 140-2 Annex A, so this just moves them to the correct place in the document set.
RSA: restrict $n$ size to 1024 2048 3072, restrict $e$ to $2^{16}+1$ to $2^{256}-1$, and specify RSA privatekey generation in detail with several options. This prohibits one traditionally popular $e$ namely 3; F4 (65537) is allowed and IME more popular anyway.

There were also major editorial changes between 186-2 and -3, reorganizing some things, changing notation, and adding a lot of explanation about what digital signatures are and aren't good for, and why privatekeys must be private, and so on. I'm not going to try to cover all that; get the docs and read for yourself if you want.


My implementation of Serpent is bit-sliced, so there is no initial permutation involved in generation of my round subkeys. It is also NESSIE byte ordered, which means that vectors will not match the AES submission package. I assume that IP will reorder the bits appropriately if you are using a non bit-sliced version. I just rewrote most of my implementation this weekend, so I am quite familiar with it. It has been confirmed to match NESSIE monte carlo test vectors.

You are also missing several very important sections of the key schedule algo. It actually works like this:
The key is copied into the first words 0-7 without modification.
The next word after the key gets a value of 1 (128 or 192-bit keys only).
Words 8-15 are filled the following algorithm:
$w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus\phi\oplus (i-8))\lll 11$

Words 8-15 are then copied back to 0-7.
Words 8-131 are filled the following algorithm:
$w_i=(w_{i-8}\oplus w_{i-5}\oplus w_{i-3}\oplus w_{i-1}\oplus\phi\oplus i)\lll 11$

The words are then run through the s-boxes sequentially in reverse starting at S3 to generate the subkeys; in the bit-sliced implementation they are run in groups of 4.

Also, the key in your post is only 224 bits, I assume it is missing a group of 0s and used that missing group below.
Here is what I get for round subkeys when taking your input key as a stream of bytes.
The endianness of these values may not match your print format, the bits were literally just copied directly to a byte array for printing. Display of the 32-bit values as per most methods will result in each octet being on the opposite side of the word.

All 32-bit values displayed in Big-Endian notation (bitstream)

Using 256-bit key (bitstream)
15fc0d48d7f8199cbe3991834d96f32710000000000000000000000000000000

Working register values w()
00 = 8e0f9f48 558a778c 8e84528e f8bb274b
01 = cb02403a 15bb83d7 773c9827 6d601cee
02 = 20fdb580 79cc8369 03e251cf ebf50867
03 = 270a1401 3a28bd26 8c44a3ca a69bab6d
04 = 94f117e6 d07657a0 d125f73a 7b47e4e0
05 = 913dccde d515c235 0fe9ca28 fb399a68
06 = 2c061be7 7b11eeee bb3809b3 10084a5f
07 = ce24252b a646b113 a7287b46 4779a4d3
08 = 3327429a 3ecc1d2a 39fe97b5 463d019c
09 = 8566ab56 a7af05c4 523d7fa8 36b82985
10 = caaea3c3 4a9c05ea 048c6348 0c41da4a
11 = 6b07d353 11b49c0f c8946c59 ce3af016
12 = 7180c410 7283b04f 0414c147 d4dec121
13 = ab75cc28 731f6211 c2957c45 156db9b5
14 = 5f10aa4a b42756e8 abacc2d9 4f037314
15 = fb072e3a 30c1ef9e cc754c08 017e5076
16 = 42c1ae8e 55ce696f 01a6211d 8cd0413b
17 = 33f4f608 dde45d09 58beb177 50ac5c0f
18 = 6e9105c9 380265e3 333baa94 7bdceb45
19 = f8a9fe9f a962f4dc 9f2cdae3 cf935f2b
20 = 2bd72c96 bae44cd1 6321b8d2 e433fa93
21 = 4123a404 1760729e 09cd114f 63512829
22 = 65d162dd cdbe1365 f6ccb936 48e5d43c
23 = 531782e2 489899e0 431bb9c3 041d43ef
24 = 82c345de 223844d0 b81b4280 fa59ffea
25 = 4a959268 412267dd d22d0891 45d03f66
26 = 8e688da8 fb208f24 0da48415 c6ca0b4e
27 = d03fb7f6 47304675 87f873ec ba4f5646
28 = 5de2230d 6acde1fb 1a8a7a13 10611eb1
29 = 21eb2e4d c06d5736 77900762 21c73996
30 = 136c8322 437b1fe5 41de13e1 75bcd7f1
31 = 8f9a9744 7bc9e639 88ee3ff7 d50aa5a8
32 = e18e5703 5eeec4bf 8d52541c 3e5cbde7

Subkeys k() after application of s-boxes (bit-sliced)
00 = afb59841 dd00fa8e a8bacf8d 23348a0b
01 = 4ce7073c d19dc3e3 86e147c4 525aa4f1
02 = 853bc859 5f198377 4ee8a43e 6c376530
03 = d822f75b f2fd42d8 98b30a6f 11f7a181
04 = efadfb05 ba6117b8 7e86447c 85e2b39e
05 = da3e695c b43a7faa be163115 bad05261
06 = 17de1812 50c1e509 bcee50b9 2bd843fc
07 = 7f8c346a a83511a9 ce60ef3e 2f2a7a6f
08 = 712b4b90 3cf45cb4 4aecd5b9 4116ca07
09 = c30e78e9 60e5fd3a 26cc8297 a9872e41
10 = 73419a9c 779cc5bc f72242d5 b9ae8317
11 = 93d62ca9 944cb0e3 96aa2c4c 361f0301
12 = 8f7d7fb9 d2c9f06e 834bb439 57973518
13 = 3378d836 4f10698b e5021786 07f2f3e5
14 = f0746a92 5b43f420 0bdb585b b46790d8
15 = 33726221 324d7e5a 07474c2c 06b48192
16 = 9a19a7c5 178fe6fc 8bf7878b dab98ed8
17 = c5420071 bea61b70 e610ee09 0951a980
18 = d2f63410 d188fea6 a71ade0c ceb051d9
19 = 67e1a0f4 167c85a8 dedb5160 c9f5d180
20 = 5629b32e 36012ad2 b4324a95 d300d005
21 = c2212005 a053bc2e b4307ab3 7cdc6bfd
22 = c19dd3ed 29777279 1e6498b2 ad38a341
23 = b07c1fd1 5409d92e 501da3c2 189138e3
24 = e0fbb92e 98a14284 e299fce4 58a2fab4
25 = 94da502a d92ae595 0f47e746 2765259f
26 = 055f707f 78f9f62c 459172a0 ce7dff99
27 = 57774833 28f02da9 3d4723c7 3ab7c26f
28 = bd94be54 3acce643 252584f5 2dc7b8e4
29 = 29efbe14 69c187af c869c0e4 96536f86
30 = db9ab3eb da15bccd c8d434cb 8ae22408
31 = 065824b1 8bd2a331 dcbe2f2a a17fcd93
32 = ad627b44 1232d6b8 0c4c3e5f c1b02e40


How to define the statistical distance between two functions?

It can be seen that statistical difference is equivalent to computational difference if a PPT algorithm is replaced by a computationally unbounded one, i.e. an arbitrary function. For distributions of random variables, if $A(1^l,s)=1$ when $\Pr[X_l=s]>\Pr[Y_l=s]$ and $A(1^l,s)=0$ otherwise, then $d_A^{\mathbf X,\mathbf Y}(l)=d^{\mathbf X,\mathbf Y}(l)$, and this is the maximum for any $A$.

For functions, a similar argument can be used: a computationally unbounded algorithm can return $1$ on an arbitrary subset of functions, so it seems that the best choice would be to return $1$ for such $f$ that $\Pr[F_l=f]>\Pr[G_l=f]$. Then,
$$d^{\mathbf F,\mathbf G}(l)=d_A^{\mathbf F,\mathbf G}(l)=\frac12\sum\limits_f\lvert\Pr[F_l=f]-\Pr[G_l=f]\rvert.$$
Here, the sum is taken over all possible functions. This sum well-defined, because all summands are nonnegative.


Does adding a salt to the message before HMAC processing add any security?

My question is: does it add any security to add a random salt to the message you are validating with HMAC?

This depends on what the HMAC is used for.

If you use a key to sign more than one secret message, a salt will prevent an attacker from knowing whether two of them are equal. (Or brute forcing a message if the key is revealed...)

It is more common that you send the message and its HMAC value through the same channel, in which case protecting the secrecy of what is authenticated does not matter (unless you encrypt and use encrypt-and-MAC). What may matter, however, is that an attacker could do replay attacks, reusing a previous message and HMAC pair.

To protect against replay attacks you need to add not just a salt, but one that the receiver can verify has never been used before. For example, an incrementing counter (that both parties store and compare), a close enough (monotonic) timestamp, or a salt that the receiver chooses e.g. randomly.


Difference RSA keypair creation openSSL and openPGP?

The difference is inconsequential in this context.

If you do some "processing" (e.g. generating a RSA key pair) using a deterministic and publicly known algorithm (e.g. OpenSSL's code) where the only parameter which is not known to the attacker is a random $n$-bit seed (e.g. $n$ = 256 for 32 bytes from /dev/urandom), then there is a theoretical possibility of an attack by exhaustive search on the seed: the attacker tries to guess your private key by trying out all possible seed values, until he finds one which yields your actual public key when fed to the deterministic key pair generation algorithm. The cost of that exhaustive search is, on average, $2^{n-1}$ tries. When $n$ grows, this cost soon becomes too prohibitive to be envisioned by the attacker.

Indeed, a 2048-bit RSA key can also (and still theoretically) be broken through integer factorization. How the cost of integer factorization relates to the cost of exhaustive search is not an easy question, because the involved algorithms have quite distinct characteristics (exhaustive search uses almost no RAM and is easy to make parallel, while integer factorization gobbles gigabytes or more of RAM and some parts of it are very hostile to parallel computing). You may peruse this site for various estimates from different groups of smart people. Bottom-line is that a 2048-bit RSA key can be deemed "as strong" as a symmetric key in the 100 to 115-bit range (which translates to an uncertainty by a factor of more than 30000, which shows how fuzzy these estimates are).

From this, we can conclude that any seed length beyond 115 bits is overkill: as long as the seed is "really random" (i.e. completely unknown to the attacker) and its length is at least 115 bits, then exhaustive search on the seed is not worth the effort for the attacker, since integer factorization will be easier (2048-bit integer factorization is not doable with existing technology anyway, but neither is a 100-bit exhaustive search). OpenSSL's 256 bits are thus total overkill with a wide margin; GnuPG's whooping 2400 bits even more so.

Then there is the recurrent debate about /dev/urandom vs /dev/random. To make things short, neither is "stronger" than the other (despite widespread myths), but /dev/random may imply usability issues (blocking at inopportune times) which can turn into actual security issues, so its use is discouraged. In that sense, OpenSSL does the Right Thing, and GnuPG errs. See this page for a well-explained summary of why /dev/urandom should be preferred.


Finding missing bits mathematicaly in a DLP situation

I suppose (for simplicity but it can be generalized I think) that the missings bits of $r$ and $s$ are the least significant bits. So, we have:
$$
\begin{array}{lll}
r = r_12^u + r_0&\text{with}&g^r \equiv h \pmod N \\
s = s_12^v + s_0&\text{with}&h^s \equiv g \pmod N,
\end{array}
$$
with $r_0 < 2^u$ and $s_0 < 2^v$ unknown.

Using the relation between $g$ and $h$, we can get the following relation:
$$
h^{rs-1} = 1 \mod N.
$$
The order of the multiplicative group $\mathbb Z/N\mathbb Z$ is $\varphi(N)$. Given the factorization of $N$, as in your example, this value is known and there exists $k\in\mathbb Z$ such that:
$$
rs - 1 = k \varphi(N).
$$
Let's call $x$ and $y$ the unknown part of $r$ and $s$ and we look at the precedent equation mod $\varphi(N)$ to get rid of $k$ and we have an equation in two variables:
$$
(r_12^u +x)(s_12^v + y) - 1\equiv 0 \mod \varphi(N).
$$
If the size of the unknwown part of $r$ and $s$ are not too big, then the Coppersmith technique in two variables (using lattice) may be used to recover those part. Lot of information here.


Secure and deterministic MACs which are not strongly secure?

A deterministic MAC can use canonical verification, but it doesn't have to.
Thus, the question allows you to create deterministic MAC without canonical verification. How can you use this to your advantage?

Hint 1:

   What if you add some auxiliary (constant) bit to the output of the  tagging algorithm of $\Pi$. How can you define the verification algorithm of $\Pi'$ to still be UF-CMA secure but not SUF-CMA secure?

Hint 2:

   This question is very similar to another question given here: Difference between INT-CTXT and INT-PTXT


Web Crypto API - deriveKey vs. deriveBits?

It sounds like deriveKey is just a composition of deriveBits and importKey.  There is no cryptographic difference between ‘generating an AES256-CTR key’ and ‘generating 256 bits uniformly at random’—this is at most an API distinction.  Support for one or the other is inconsistent, apparently, even though they both appear in the W3C recommendation.  How to get around this in practice in a web application is a question for a forum on JavaScript coding, not crypto.se, however.


Parallelizing MACs by subdividing the message and then aggregating results

There are two general approaches to parallelizing MACs:

Use a universal hash like GHASH or Poly1305 whose algebraic structure admits essentially arbitrary levels of parallelism.

For GHASH and Poly1305, the hash is polynomial evaluation:

\begin{equation}
      H_r(m_1 \mathbin\| m_2 \mathbin\| \dotsb \mathbin\| m_n)
        := m_1 r^n + m_2 r^{n-1} + \dotsb + m_n r.
   \end{equation}

The naive way to compute this is with Horner's rule:

\begin{align}
     h_0 &:= m_1, \\
     h_1 &:= h_0 r + m_2, \\
     h_2 &:= h_1 r + m_3, \\
         &\vdots \\
     h_n &:= h_{n-1} r.
   \end{align}

If you can compute two multiplications simultaneously, then by precomputing $r^2$ you can process the message two chunks at a time (handling an odd number of message blocks left as exercise for reader):

\begin{align}
     h_0 &:= m_1, \\
     h_2 &:= h_0 r^2 + m_2 r + m_3, \\
     h_4 &:= h_2 r^2 + m_4 r + m_5, \\
         &\vdots \\
     h_{n-2}
         &:= h_{n-4} r^2 + m_{n-2} r + m_{n-1}, \\
     h_n &:= h_{n-2} r^2 + m_n r.
   \end{align}

The same idea extends to an arbitrary degree of parallelism in an implementation without changing the semantics of the MAC you compute.  Other universal hashing MACs often have similarly parallelizable algebraic structure, e.g. UMAC which uses a combination of inner products and polynomial evaluation.
Use a PRF like BLAKE2 on a tree-structured encoding of a message—Merkle trees.

If $H$ is a uniform random (secret) function, then so is $$(x, y) \mapsto H(2 \mathbin\| H(0 \mathbin\| x) \mathbin\| H(1 \mathbin\| y))$$ on the appropriate domain, or at least nearly so—this construction is indifferentiable from a random oracle.  Then if you instantiate $H = F_k$ for uniform random $k$ where $F$ is a pseudorandom function family, the PRF-security of the construction $$(x, y) \mapsto F_k(2 \mathbin\| F_k(0 \mathbin\| x) \mathbin\| F_k(1 \mathbin\| y))$$ isn't much different from the PRF-security of the primitive $F_k$.  And of course a uniform random function makes a good MAC, so the PRF $(x, y) \mapsto F_k(2, F_k(0, x), F_k(1, y))$ makes a good MAC—for fixed-length messages.  Here $F_k$ might be, e.g., AES-CMAC or HMAC-SHA256.

You must take care to encode the message uniquely.  If you exposed oracles for $H$ (on short messages only) and $(x, y) \mapsto H(H(x) \mathbin\| H(y))$ (on long messages only), then an adversary could forge the authenticator for $(x, y)$ by querying the $H$ oracle for $x$, for $y$, and for $H(x) \mathbin\| H(y)$.  This mistake is not immediately obvious, and appears in real-world protocols like BitTorrent and certificate transparency logs, which is why proposed standards like BLAKE2 tree-hashing and Sakura exist.

Usually this technique is applied when we want to incrementally verify or modify part of the tree, but you could expand the radix to whatever fanout you want to maximize parallelism.  The BLAKE2bp and BLAKE2sp parallel-hashing modes do essentially this with the BLAKE2 compression function as a PRF, but if for some reason you had to use AES-CMAC or HMAC-SHA256, you could use those as PRFs instead in this structure (at considerable cost to performance), provided you uniquely encode all the parameters that figure natively into BLAKE2.

Merkle trees can attain an essentially arbitrary degree of parallelism, but you must agree in advance to change what MAC you use.  Maybe right now you like the idea of four parallel AES-CMACs; maybe tomorrow you would rather have chosen eight; maybe on Tuesday a customer with a small ARM system that can only do one sequential AES-CMAC is sad.

What about the constructions you suggested?

  T=CMAC(CMAC(M1)|CMAC(M2)|CMAC(M3)|CMAC(M4))

If this is a fixed-depth Merkle tree, then it may make a secure MAC, but the devil is in the details of what oracles you expose for CMAC under your key and how you encode the message into a tree structure.  Of course, CMAC doesn't have built-in space for encoding parameters like tree position the way the BLAKE2 compression function does, so you'll have to find another way to do that.

  CMAC(M1|CMAC(M2)|CMAC(M3)|CMAC(M4))

Similar to above, but now you are even more likely to accidentally expose an oracle for plain CMAC under your key.

  Edit #2: it appears the XOR case may be secure if each MAC is independently keyed, but I'd want to look into it more.

That post discusses $H_1(m) \oplus H_2(m) \oplus \dotsb \oplus H_n(m)$, where the $H_i$ are independently chosen MACs applied to the whole message $m$, but you have taken this to mean $H_1(m_1) \oplus H_2(m_2) \oplus \dotsb \oplus H_n(m_n)$ applied separately to the separate blocks $m_1 \mathbin\| m_2 \mathbin\| \dotsb \mathbin\| m_n$ of $m$.  The conclusion you inferred does not follow.  (You also have to spend additional time deriving subkeys, of course!)


Cryptography used for login and signing transactions

While I am not familiar with this particular device or bank, this looks a lot like Chip Authentication Program (CAP)

It's fairly standard in the UK, where banks use this to authenticate initiating a bank transfer to a new recipient. There is a python implementation (for study - it's obviously a bad idea to actually use this, as it would permit your PIN to be captured by malware on your local PC) available at http://sites.uclouvain.be/EMV-CAP/Application/

As I understand the protocol, your smartcard is used to sign a "cancel transaction" request using a shared MAC key (the key being securely stored on the smartcard). There is more information on the protocol at the wikipedia page: https://en.wikipedia.org/wiki/Chip_Authentication_Program#Protocol_details


is there a problem with the following private set intersection protocol

This is very similar to a well-known protocol that dates back to the following work.

  Catherine Meadows. A More Efficient Cryptographic Matchmaking Protocol for Use in the Absence of a Continuously Available Third Party. In IEEE Symposium on Security and Privacy. 1986

  Bernardo A. Huberman, Matt Franklin, and Tad Hogg. Enhancing Privacy and Trust in Electronic Communities. In ACM Conference on Electronic Commerce. 1999

It uses the commutative property, namely that $(x^a)^b = (x^b)^a$. This PSI protocol is usually used with the following modifications:

Usually Diffie-Hellman cyclic groups are used rather than RSA. This allows you to send around compact elliptic curve elements (e.g., 256 bits) instead of RSA group elements (e.g., 2048 bits). Diffie-Hellman groups clearly give you the commutative property that this protocol requires.

Also, RSA is commutative only when using the same modulus. In this setting, who chooses the modulus? Probably neither party should know the factorization.
It is not secure to exponentiate the raw items. Instead, they should be hashed under a random oracle first.

Consider if Alice holds items $x, x^2, x^3, \ldots$ and Bob only holds item $x$. Then Bob will eventually learn $x^{ab}, (x^2)^{ab}, (x^3)^{ab}, \ldots$. He will recognize $x^{ab}$ because he has item $x$ (this is what we expect). But he can also recognize the other values as $(x^{ab})^2, (x^{ab})^3, \ldots$, and conclude which of $x^2, x^3, \ldots$ Alice holds. Clearly this is a violation of privacy.

The parties should compute $H(x)^{ab}, H(x^2)^{ab}, H(x^3)^{ab}, \ldots$,  where $H$ is a random oracle. $H$ breaks the algebraic relations among the items, so that knowing $H(x)^{ab}$ doesn't help you predict $H(x^2)^{ab}$.
The RSA assumption and CDH assumptions give you the following property: "given $H(x_1)^{ab}, \ldots, H(x_n)^{ab}$ for random/secret $a$, it is hard to compute $H(x^*)^{ab}$ for $x^* \not\in\{x_1, \ldots, x_n\}$." This is not quite enough for security of the PSI protocol. We in fact need $H(x^*)^{ab}$ to be pseudorandom given $H(x_1)^{ab}, \ldots, H(x_n)^{ab}$ (not just hard to compute). This can be achieved by assuming DDH rather than CDH, or by applying an additional random oracle, so that Alice sends values of the form $H'(H(x)^{ab})$.


In Authenticated Encryption, the authors explained the framework and constructions for Authentication Encryption in detail.
In particular, In Theorem 3.2 they stated that "INT-CTXT" security together with "IND-CPA" security implies "IND-CCA" security.
Then, they introduced a general approach to an "Encrypt-then-MAC" construction that achieves both "INT-CTXT" and "IND-CPA" security, which further implies "IND-CCA" security.
Lastly, thanks for the comment given by @DannyNiu.


The article cited in the question (Eleni Diamanti, Hoi-Kwong Lo, Bing Qi, and Zhiliang Yuan: Practical challenges in quantum key distribution, in npj Quantum Information 2016, a Nature Partner Journal) gives a list of challenges facing Quantum Key Distribution, but forgets several important ones:

Not fulfilling the market demand for simplified key distribution. When Man in the Middle attack is a threat, QKD only extends a pre-existing initial secret key, which still must be distributed by trusted means such a courier. QKD is thus not easier to use than classical key distribution and offers no clear advantage compared to distribution of a USB key with a One Time Pad by that same courier.
QKD's claimed security covers keys distribution, not data transmission at commercial speed. The later still relies on classical symmetric cryptography (lacking mathematical proof), with QKD protecting only the low trickle of data that constitutes the keys for classical crypto. Therefore, use of QKD does not unconditionally prevent interception of the bulk data for later decryption by hypothetical improved attacks.
Incompatibility with deployed infrastructure: existing active electronics at optical fiber ends, including in repeaters (often underwater), are incompatible with QKD. Some of the existing fibers might be re-purposable, but at extremely low QKD rate, which worsens the above issue.
QKD does not scale to a global network. What's currently experimented is end-to-end only, or (marginally) with special optical routers that further reduce the usable distance. Blueprints for large networks require trust in the routers, when classical crypto does not.
Complexity of the indispensable information-theoretic (mathematically provable) paraphernalia necessary for QKD to work both reliably and safely. A most cited method for that appeared only 9 years after the birth of QKD, and despite its complexity leaves it to the practitioner to deal with power outages other than by using another courier for a fresh initial secret key.
Lack of security certification: there was no security-certified Quantum Key Distribution system last time I checked, nor any planned reference framework for such certification. Market and laws demand certification (rightly so: several QKD systems have been hacked).


Can I prove set membership and uniqueness without revealing the element?

Proving uniqueness

You can prove that the elements are unique in $O(m)$ time and space by pre-sorting them and then giving a zero-knowledge proof that they are in sorted order.  Details follow.

Assume the elements of $\Sigma$ are integers in the range $[0,K-1]$, where $K$ is a constant chosen in advance and made public.  Pick a large prime $p$ and a group element $g \in (\mathbb{Z}/p\mathbb{Z})^*$ of prime order $q$, such that $q > 2K$.  The scheme is:

First, sort the elements of $\Sigma$, so $\sigma_1 < \sigma_2 < \cdots < \sigma_m$.  Next, commit to all the elements, using a discrete log based commitment scheme with generator $g$; for instance, you might use Pedersen commitments.  Finally, prove that the elements are in sorted value, i.e., that $\sigma_i < \sigma_{i+1}$ holds for all $i$.

You can prove they are in sorted order using a range proof for discrete logs: for all $i$, you show that $\sigma_i \in [0,K-1]$, and you show that $\sigma_{i+1} - \sigma_i \in [1,K-1]$ (again, considering the $\sigma_i$'s as integers).  To prove that $\sigma_{i+1} - \sigma_i \in [1,K-1]$, it suffices to prove that $d_i = \sigma_{i+1} - \sigma_i \bmod q$ is in the range $[1,K-1]$: since you've proven that each $\sigma_i$ is in $[0,K-1]$, and since $q \ge 2K$, there can be no wrap-around modulo $q$.  All that remains is how to describe that each $d_i$ is in the specified range.

One standard way to do a range proof is to express each $d_i$ in binary, i.e.,

$$d_i = \sum_j b_{i,j} 2^j.$$

Then you commit to all the $b_{i,j}$'s, use the homomorphic property of commitments to show that the $b_{i,j}$'s are consistent with the $d_i$'s (i.e., that the equation above holds), and show that $b_{i,j} \in \{0,1\}$ for each $i,j$.  Of course, you can prove that the $d_i$'s were computed correctly by using the homomorphic property of discrete log-based commitment schemes: given the commitments $C(\sigma_{i+1})$ and $C(\sigma_i)$, anyone can compute a commitment $C(d_i)=C(\sigma_{i+1}-\sigma_i \bmod q)$ to $d_i$, even without knowing $\sigma_i,\sigma_{i+1}$.

When using this method of range proofs together with the idea above, it will give you a valid proof that the elements $\sigma_1,\dots,\sigma_m$ are mutually disjoint.

Proving it is a subset

You can show that $\Sigma \subseteq \Psi$ using the techniques in the paper you mentioned.


hash collision chance using a 5 chars hash made of a-z A-Z and 0-9 (62 chars total)

There are indeed $62^5 = 916\,132\,832$ possible hashes in that syntax.  If they are uniformly distributed, then the standard birthday paradox applies to the probability of a collision in $n$ independent choices of $k$ possible hashes.  For $n < \sqrt{k}/4$, the probability of collision is between $(n - 1)^2/(4k)$ and $n^2/k$.  For example, among 10 000 hashes, the probability of a collision is at least $$\frac{9\,999^2}{4\cdot916\,132\,832} > 2.7\%,$$ and at most $$\frac{10\,000^2}{916\,132\,832} < 11\%.$$

Of course, if these are hashes from a fixed public hash function like SHAKE128-30 (add two more characters to your alphabet like the base64 + and - to make the numbers work out), it is easy for an adversary to spend the energy to compute a few tens of thousands of hashes offline without interacting with you in order to find a collision with high probability.  The lower bound on the collision probability gives a guarantee on the adversary's chance of success after a certain amount of work.

So with numbers as small as this, not much can be said about fixed public hash functions.  On the other hand, this analysis remains relevant for a secret hash function, a pseudorandom function family (PRF), like SipHash or KMAC128 or keyed BLAKE2 under a secret key not known to the adversary.


If a popular encryption scheme is being used: No.

The typical solution is that symmetric stream/block ciphers generate a constant stream of new pseudo-random bits which are merged/XOR'd with the plaintext to produce the ciphertext.

The pseudo-random stream is seeded indirectly by the private key - so as long as the previous or future bits of the PRNG can not be infered from known bits (or infer the PRNG seed for that matter), the cipher is protected from classical known-plaintext attacks.


If it is available, how does it work. Will the Smart Card take a stream of encrypted bytes and then spit out a stream of unencrypted bytes?

No, that's generally not what happens. In general smart card simply supply an RSA operation that performs raw RSA, RSA PKCS#1 or RSA OAEP decryption. The result of this operation is a relatively small amount of bytes; e.g. in the case of RSA PKCS#1 about 11 bytes less then the key size (which is the size of the modulus for RSA). If a raw RSA operation is provided then the unpadding should be performed by the off card entity.

So what is used is a hybrid cryptosystem. Such a system uses a random, symmetric data key to encrypt the plaintext. This random data key - usually an AES key - is then encrypted by the RSA public key. The encrypted data key is stored together with the ciphertext using a container format such as CMS or Open PGP.

Upon decryption the AES data key is first decrypted with the private key on the smart card. This for instance requires a PIN code to be entered to gain access to the private key. Once the data key is decrypted it can be used to decrypt the rest of the data. Using authenticated encryption (such as GCM) should of course be preferred.

So the smart card only "accelerates" the private key operation. I put that between quotes as in general a mainstream CPU will be much faster than the speed of the cryptographic co-processor and the communication overhead provided by the card. The AES operations are performed off-card, and they bear the brunt of the work for any files above, say, a few KiB.


great discovery in the field of elliptic curves cryptography?

ECC is not resistant against quantum computers.

  Quantum complexity for breaking RSA and ECC are $O(\frac{s^9}{{(\log (s))}^5})$ and $O(s^3)$ respectively. Which $s$ is security level $(80-96)$.

So as SEJPM mentioned in comments, "ECC is less resistant against quantum computers than RSA".

One of newest post quantum cryptographic schemes is isogeny  based cryptography, and best known quantum complexity for breaking such schemes is exponential.

Also scientists believe that nowadays, providing such enormous quantum gates is very hard and may be infeasible . So 'quantum computers aren't risk for cryptography nowadays".


Will changing the RSA Padding in OpenSSL cause issues?

Yes, every RSA padding I'm familiar with is incompatible with the other schemes.


Using YubiKey to store a PIN-protected secret for disk encryption

Using 1) along with enabling and forcing the admin pin and potentially card pin.  You can the force touchauth which would force pin to unlock the yubikey and then continue as mentioned in 1)


Benchmark (hash rate) for SHA-3 (SHAKE128)

The hash rate decreases as the message size increases.

What's quoted by the benchmark decreases with the message size. But it is not a "hash rate", at least in hashes per unit of time on a certain computer as thought by the OP. The unit is cycles per byte, thus higher values mean proportionally more cycles spent, more time spent, and less hashes performed (with all of many other more important things being equal).

Assume computer(s) used to their full computing power for hashing, with a total of $u$ CPU(s), each with $n$ core(s) running a frequency $f$ (in Hertz), for total time $t$ (in seconds), to hash $m$ messages each $b$-byte, with each hash produced requiring $c$ cycles of one execution thread of one core of one CPU. It holds that
$$u\cdot n\cdot f\cdot t=m\cdot c$$
Derivation: Left side is the number of cycles across all $u\cdot n$ cores, with $f\cdot t$ cycles for each core given frequency and time spent. Right side is the number of cycles $m\cdot c$ necessary to hash the messages, given how many messages there are, and how many cycles are required for each hash. They are equal due to the assumed "used to their full computing power", which can be closely met when $m\gg u\cdot n$ by splitting the messages evenly among the cores.
What the linked benchmark quotes is $c/b$ in cycles per byte, where cycles are those actually used by one thread running sequential code computing the hash. This quantity $c/b$ depends a lot on the algorithm, the CPU architecture, and the quality of the code (including fitness to the CPU, compiler..); on the value of $b$, especially when low (see below), which is why $c/b$ is given for several values of $b$; and seldom on the rest.
Note: Thread(s) running on a core have to share that core's $f\cdot t$ cycles. My understanding of the benchmarks quoted is that the number of threads per core is considered part of the CPU architecture; if that could be adjusted, e.g. to 1 or 2 at boot time, there would be separate benchmarks or/and the $c/b$ quoted would be the highest achieved.
Note: The benchmarks quoted, and the present answer, stick to fixed hash output size, e.g. 32-byte. SHAKE128 has variable-size output, and this could be an extra parameter.

Most practical hashes (including SHA-3/SHAKE) group bytes (after padding) into block of fixed size $B$-byte ($B=136$ for SHA3-256/SHAKE128), and have an iterated structure processing blocks sequentially. It follows that $c$ grows with $b$ approximately as
$$c=c_0+c_1\lceil(b+b_0)/B\rceil$$
(ignoring cache and other effects), where $0\le b_0<B$ is a padding size in bytes ($b_0=1$ for all SHA-3), $c_0$ is a fixed overhead in cycles, $c_1$ is the number of extra cycles to hash an extra block (with $c_1<c_0$ for SHA-3), $\lceil x\rceil$ is rational $x$ rounded up to the next integer. The quantity $c/b$ reported by the benchmark is:

for small messages (up to $B-b_0$-byte), approximately $(c_0+c_1)/b$, decreasing quickly with $b$;
for large messages ($b\gg B)$, approximately $c_1/B$, largely independently of $b$.

Overall $c/b$ mostly lowers as $b$ increases (converging to some constant), but with initially noticeable sawtooth jumps.

In an earlier question and comment to another, the OP mentions wanting to hash 40-bit messages and wondering to what degree that's vulnerable to brute force search of the message. Let's evaluate how much time the hashing (which dominates the effort) would require to cover the whole message space.

Messages are $\lceil40/8\rceil=5$-byte, thus the appropriate column of the quoted benchmark is for $b=8$-byte messages (giving the same $\lceil(b+b_0)/B\rceil=1$). With an Intel Core i7-7800X featuring $n=6$ cores running at $f=3.5\text{GHz}$, it was timed SHAKE128 at a median of $c/b=112.25$ cycles per byte. Hence with $u=1$ such CPU, the time to hash all $m=2^{40}$ messages is:
$$t=\frac{m\cdot(c/b)\cdot b}{u\cdot n\cdot f}\approx\frac{2^{40}\cdot112\cdot8}{1\cdot6\cdot3.5\cdot10^9}\approx47000\text{s}\approx13\text{h}$$
Note: In this computation we used $b=8$ of the benchmark rather than $b=5$ for the number of bytes hashed, because we are trying to compute $c$ as $(c/b)\cdot b$ in a situation where $c$ is approximately independent of $b$. If we hashed a long message, we'd use the much lower $c/b$ benchmarked for that condition, and the $b$ for the message hashed, since we'd be in a situation where $c$ is approximately proportional to $b$. In between, we can compute the $(c/b)\cdot b$ quoted for the two benchmarks with the closest sizes, deduce the two corresponding $c$, and interpolate for our $b$ per a $c=c_0+c_1\lceil(b+b_0)/B\rceil$ model.
Note: The "Base" value of $f$ is what matters rather than the higher "Turbo", since the later can't be sustained for multiple cores, at least within manufacturer specs.

That search is easily feasible for an individual with a single computer. Further, a rainbow table would allow to make that computation only once, then invert any hash of a 40-bit message in seconds with e.g. a mobile phone.

The task is so easy that using CPU(s) is adequate (they are easiest to program). For larger attacks, after an initial coding effort, GPUs would be more effective on speed, or/and cost and energy (their superior performance comes from $n$ being many hundreds for each GPU). FPGAs and ultimately ASICs are even superior (they have potential to decrease both $c$ and additional investment per added hashing capacity, by exactly tailoring the circuitry to the task). That's how the aggregate of bitcoin miners gets a hash rate over $2^{82}$ SHA-256 hashes per day (May 2018, per that source reporting SHA256d hashes comprising two SHA-256).

  Core i3 has a higher hash rate than Core i7 for SHAKE128

After noting that hash rate is in cycles/byte, that observation amounts to: in a comparison, a core of a CPU with a higher digit following "Core i" in its Intel marketing designation happens to have the desirable property of requiring less clock cycles than the other one.

This is far from a general rule, as (for the Intel x86 line) $c/b$ depends much more on how recent the CPU is. The stated difference is largely attributable to architectural improvements increasing IPC between Q1'11 when the Core i3 referenced was introduced, and Q2'17 when the Core i7 referenced was.

The values of $b$, $u$, $n$ and $f$ have more essential influence on hashing performance of a computer, which is $m/t=u\cdot n\cdot f/c$ hashes per second, with $c$ proportional to $b$ for large $b$.


BIKE: Bit Flipping Key Encapsulation - Inverse encryption / decryption

I can't say for sure, but I don't think that will work for the following simple reason:
The secret key in BIKE is a sparse parity check matrix of an MDPC code $(h_0, h_1)$, and the public key is always dense.
The decryption of BIKE (in all versions) relies upon the sparsity of the parity check matrix of the secret key. If you were to swap the keys the bit-flipping decoder wouldn't work anymore - it's decoding failure rate increases linearly with the weight of the parity check matrix.
Hope I could help!


Secret shared input for garbled circuit?

Normally the inputs to garbled circuits are known by the party who owns the input and are plaintexts.

There are scenarios in which the functionality (implemented by GC) needs to be evaluated on shared input. For example, if the two parties are not trusted with the plaintext input (may be owned by a third party) and instead only get shares of the input. The garbled circuit then consists of two sub-circuits: (1) the first sub-circuit combines the shares and recovers the secret input, and feeds it (without revealing it) to (2) the sub-circuit that implements the functionality to be evaluated on the secret input. At the end, the output is given to the parties (or if you want, you can append another circuit to split the output into two shares and give one share to each party)


mDP kay agreement protocol where z's are found on the step where the common key is generated?

As said in page 6, Each $U_i$ proceeds as follows;

compute $\text{sid}_i:= U_1|y_1,\ldots,U_n|y_n)$,
$z'_{i-1,i} := H(k'_{i-1,i}, \text{sid}_i)$,
$z'_{i+1,i} := H(k'_{i+1,i}, \text{sid}_i)$,
$z_i := z'_{i-1,i} \oplus z'_{i+1,i}$,
$\sigma_i := \text{Sign}(sk_i, (U_i,z_i,\text{sid}_i ))$,
$\text{broadcast} (U_i,z_i,\sigma_i)$.

since in the beginning, the $(U_i,y_i)$ is broadcasted the above calculation is fine.

When a user $U_j$ gets all $(U_i,z_i,\sigma_i) , 1 \leq i \leq n$, he is ready to verify. Actually, they agree on a key with their neighbors by Diffie-Hellman Key Exchange protocol.


Is that possible to use encryption higher than 256-bit?

TLS does not support any cipher suite combination with a symmetric key size larger than 256 bits. Asymmetric key sizes are available up to 15360 bits, which correspond to a 256-bit symmetric security level.

RFC5246 lists the available cipher suite combinations for TLS 1.2

It should be noted that the symmetric security of TLS is not the weak point, and 128-bits should be more than secure enough for the next 30 years.


Why are these techniques not feasible to crack RSA?

You are correct in that knowing $\phi(n)$ it is trivial to get the private key back with a simple modular inversion.

However, we are only given $e$ and $n$, and it turns out that computing $\phi(n)$ from $n$ alone is computationally equivalent to finding the factors of $n$. Namely, if you know $\phi(n) = (p-1)(q-1) = (p-1)(n/p - 1)$, you can recover $p$ by solving the quadratic equation $p^2 + (\phi(n) - n - 1)p + n = 0$ for $p$.


whether the checksum: 0xFFFF-SUM(N[i]) i=1...32 will solve the problem?

Yes, it does.  That's exactly how both WOTS+ in XMSS and LM-OTS in LMS work


General method:

Let $X=\{222,112\}$ be a group of two traitors we focus on. Clearly (see my answer to your earlier question)
$$\mathrm{desc}(X)=\{1,2\}\times \{1,2\}\times \{2\}=\{222,122,212,112\}
$$
is the set of vectors these two users can create if they collude.
Since $\mathrm{desc}(X)\cap C=X$, this is not a contradiction to the code being $2-$frameproof.

Edit: Intuitively, two users can compare their symbols at each position and choose to use either symbol, if their symbols are distinct. If by doing this they can generate a third user's codeword, they can frame him/her by using his/her codeword. The code symbol alphabet will be very large and you can think of code symbols as cryptographic keys, and the whole codeword as a concatenated key. Thus it is infeasible to brute force the keys except by learning them with pairwise sharing between coalitions of users (called traitors).

You need to do this for all sets $X$ made up of 2 codewords and verify the e  equality holds. The overlap of codewords does not allow you a shortcut to decide if the code is $2-$frameproof.

For a small code:

Can we find two codewords that allow two traitors to build a third codeword thus frame a third user?

YES. Using $X=\{011,112\}$ we can build $012$ which is another codeword. So this code is not $2-$frameproof. Thus if Alice is the user who is assigned codeword $011$ and Bob is the user who is assigned the codeword $112$ they can generate the vectors in $desc(X)$ and in fact they can pretend to be Harry, the user who is assigned the codeword $012$, and frame him by, e.g. downloading a movie which will be charged to his account.


You're right: there is no need for key stretching if your key already has enough entropy to resist brute force attacks without it.  A 128-bit keyspace should be plenty for that.

AFAIK, there is no significant difference between HKDF and single-iteration PBKDF2 in practice.  Both effectively achieve the goal of expanding the input key to a potentially longer sequence of derived keys, in a way that does not allow the original input key to be efficiently recovered from the derived keys.

Arguably, using HKDF for this purpose is somewhat "tidier", in the sense that it has been explicitly designed for non-password-based key derivation, whereas using PBKDF2 with an iteration count of 1 is formally outside its original design parameters.  However, there are several existing schemes, such as scrypt, that do use PBKDF2 in such a way, and there is no apparent structural reason why PBKDF2, used in such a way, would not be a secure non-key-stretching KDF.  Also, if you are already using PBKDF2 for password-based key derivation anyway, implementing a second KDF might be seen as needless complexity (however minor).

Personally, my favorite approach, in situations that do call for both key stretching and the generation of more than one hash output block of derived key material, is to use hybrid PBKDF2/HKDF — that is, to use PBKDF2 (or another key-stretching KDF) to generate an intermediate pseudorandom key (of one hash output block size), and then use the HKDF-Expand function to generate the derived keys from the intermediate PRK.  This combines the best features of both PBKDF2 and HKDF, and is implicitly permitted by RFC 5869 section 3.3 (which says one may skip the HKDF extract stage if one already has a uniformly distributed pseudorandom key string).

Using this approach could allow you to support both password-based and random-key-based key derivation within a unified framework:

For password inputs, derive an intermediate PRK using PBKDF2 with a suitably high iteration count.
For random key inputs, derive the PRK using HKDF-Extract (or PBKDF2 with a single iteration), or just use the input key directly as the PRK.
In either case, derive the actual encryption and MAC keys from the PRK using HKDF-Expand.

Ps. Just out of curiosity, I searched for earlier answers I'd written mentioning HKDF and PBKDF2.  I don't think any of these questions are exact duplicates of yours, but the answers may be somewhat relevant:

Is a PBKDF2-derived master key easier cracked if very many Data Protection Keys are derived from it?
Should I salt an AES password at each encryption?
Does it make sense to stretch non-keys?
Securing content and login with "same" password


How do SignRecover and VerifyRecover work?

TL;DR: they might not.
PKCS#11 is a standard for the software interface to cryptographic tokens (such as HSMs or Smart Cards), aiming at compatibility between implementations made by different token vendors. It also allows the same API to use various cryptographic mechanisms performing similar tasks by changing only a few values, mostly the Mechanisms parameter (an integer with a standard-assigned value) and some sizes.
PKCS#11 was written under supervision of RSA Security, and archives of that period are linked from EMC's PKCS#11 page. PKCS#11 moved to OASIS, which turned these into (in particular) Base Standard v2.40c01 (2014-12-23) and Current Mechanisms v2.40c01 (2014-12-23); these are scheduled for approval on 2015-04-15 with minor changes.
PKCS#11 has an API for signature schemes with (total) message recovery; that is, a kind of signature scheme where the (whole) message being signed is conveyed in the cryptogram of the signature, and is an output of the signature verification, rather than an input (as in the case in a signature scheme with appendix, e.g. RSASSA-PKCS1-V1_5 or RSASSA-PSS of PKCS#1).
For signature production, C_SignRecoverInit and C_SignRecover are to signature schemes with (total) message recovery what C_SignInit and C_Sign are to signature schemes with appendix, with exactly the same interface. For signature verification, C_VerifyRecoverInit and C_VerifyRecover are to signature schemes with message recovery what C_VerifyInit and C_Verify are to signature schemes with appendix, with a difference in the interface of C_VerifyRecover: it produces as output the recovered message (nominally identical to the message passed on input to C_SignRecover), when C_Verify receives as input the message to verify (nominally identical to the message passed on input to C_Sign).
Reference: Definition of C_VerifyRecover, and my memory.

CKM_RSA_X_509 is the simplest Mechanism that may be supported with C_SignRecoverInit, C_SignRecover, C_VerifyRecoverInit, C_VerifyRecover. Basically that's textbook RSA.
For the CKM_RSA_X_509 Mechanism, ignoring checks pertaining to the session state:

C_SignRecover perform just as C_Sign; that is:

checks that the size of the message to sign is at most $k$ bytes where $256^{k-1}\le N<256^k$ and $N$ is the RSA public modulus
converts it to integer $m$ by big-endian conventions
checks $m<N$
produces $s=m^d\pmod N$ where $d$ is the RSA private exponent
converts $s$ to $k$ bytes by big-endian conventions, and output it.

C_VerifyRecover

checks that the size of the signature is exactly $k$ bytes
converts it to integer $s$ by big-endian conventions
checks $s<N$
produces $m=s^e\pmod N$ where $e$ is the RSA public exponent
converts $m$ to $k$ bytes by big-endian conventions, and outputs it.

Reference: Definition of the CKM_RSA_X_509 Mechanism; its table of sizes of inputs and outputs (where £ is to be read as ≤); and my memory.

Cautionary notes:
The CKM_RSA_X_509 Mechanism should only be used as a building block, because textbook RSA is unsafe.
The CKM_RSA_9796 Mechanism, used as example of signature schemes with message recovery in PKCS#11, should not be used, and is not secure under chosen-message attack, even though that was among its design goals. It is (a slight variant of) ISO/IEC 9796:1991 (perhaps on sale here), but withdrawn and next to forgotten (it was planned to be rechristened ISO/IEC 9796-1 but suffered fatal wounds before the ceremony formal approval: forgery is possible from the signature of 3 chosen messages).
The CKM_RSA_PKCS Mechanism (which may support signature with message recovery) should not be used to sign a message under direct control of the adversary, because it is not secure under chosen-message attack (it was not intended to be; variants that hash the message as required by RSASSA-PKCS1-V1_5, such as CKM_SHA256_RSA_PKCS, are stronger, but still are not recommendable except for compatibility with existing systems).
PKCS#11 does not have an API for signature schemes with partial message recovery, and does not support ISO/IEC 9796-2 (any scheme), which is often how message recovery is used (e.g. in Smart Cards for EMV banking, European Digital Tachograph certificates); ISO/IEC 9796-2 with PKCS#11 is thus typically implemented on top of PKCS#11 with CKM_RSA_X_509, or as a proprietary extension, or perhaps as an internal component of a (possibly standard) Mechanism such as CKM_CMS_SIG, rather than by PKCS#11.
Profiles v2.40c01 (2014-12-23), which lists features of PKCS#11 which support is required for conformance, is mum about message recovery; draw your own conclusions about the level of support it has among tokens found in the field. I have seen an implementation which documentation plain omits the SR/VR column in the all-important matrix of Mechanism vs Function support (yet dutifully mentions C_SignRecoverInit, C_SignRecover, C_VerifyRecoverInit, C_VerifyRecover has no limitation).


Is it possible for the Rho method against an Elliptic Curve to take more than the sqrt of the total state space?

The Rho method is probabilistic, so it's possible you could find the solution within the first few iterations, or after you've generated almost the entire space.

The probability starts getting in your favor around the square root of the order, because that's when the probability reaches approximately 50%. Since the probability increases quadratically, it's very likely to find a solution shortly after passing that point.


Function with no fast path and with fast proof

The following paragraph applies even if the honest prover does not use iteration.

Strictly speaking, only a constant-size part of the input can be read from in

constant time, so one could always find a suitable result in constant time.

For a deterministic verifier that makes at most k probes to an alleged result

consisting of M w-bit words, one can find a suitable result with  2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k  parallel

simulations of the verifier, each of which uses only  $(\hspace{.02 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}k)\hspace{-0.04 in}+\hspace{.02 in}$O(1)  words of overhead.

If instead the verifier is probabilistic, then either  $\binom{M}{\hspace{.02 in}k\cdot \hspace{.02 in}(1+\hspace{.03 in}\Omega(1))\hspace{-0.03 in}}$$\cdot$2$\hspace{.02 in}$w$\hspace{.02 in}\cdot$k$\cdot$(1+$\hspace{.03 in}$Ω(1))  parallel

simulations will be enough, or the adversary can very-efficiently go from an actual result

to one that makes the verifier's acceptance probability be between Ω(1) and 1-$\hspace{.02 in}$Ω(1).

However, it may well be possible to achieve what you're asking about with a probabilistic

word RAM verifier, by simply accepting that "the adversary ... be between ... ."

PCPs of proximity with highly-efficient verifiers do something that is somewhat similar.


What are the extended homogeneous coordinates in the EdDSA specification?

Extended homogeneous coordinates are a different form of coordinates that provide particularly fast methods of point addition and point doubling formulas for twisted Edwards curves, introduced in Huseyin Hisil, Kenneth Koon-Ho Wong, Gary Carter, Ed Dawson. Twisted Edwards Curves Revisited, 2008.

$X$ and $Y$ roughly correspond to affine $x$ and $y$, $Z$ comes from regular extended (also called projective) coordinates as a scaling and $T$ is the actually “new” element that contains $X\cdot Y$. In particular, section 3 of the paper by Hisil et al. introduces the extended homogeneous coordinates and how to convert to and from extended homogeneous coordinates.


How is the PKCS #10 signature generated?

The signature over PKCS#10 is defined in RFC 2986, specifically section 4.2 (on page 7).

  The signature process consists of two steps:

  The value of the certificationRequestInfo component is DER
         encoded, yielding an octet string.
  The result of step 1 is signed with the certification request
         subject's private key under the specified signature
         algorithm, yielding a bit string, the signature.

The signature is over all the significant information in the request and includes all the DER-encoded attributes in the PKCS#10 signing request.

If there are any missing or additional attributes in the PKCS#10 certificate request, or if any of the attributes differ by even one single bit, then the signature will be completely different. This could include using a different string encoding (printable ASCII string vs UTF-8), but also different dates etc.

If you want to find the difference, you can decode your certificate request here. You might have to strip your request in PEM format or convert your request in DER format to base 64 before using this tool. You could also use openssl asn1parse functionality for this.

Finally, it could also be that a different signing algorithm is used, e.g. PKCS#1 v1.5 padding vs PSS padding. They would both generate the same amount of bytes. PSS is non-deterministic (uses a random bytes) by the way; if it is used the signature would be different each time regardless of the input. Normally PKCS#1 v1.5 padding is still used though.

As Dave mentions,  the best way to validate the correctness of a signature is not to compare it but by verifying the signature and validating the attributes, possibly by using other software. That way non-significant changes won't play a role within the validation.


CodeInChaos has it right about the infeasbility of this against a random key; however, lets run the numbers to see how extremely correct he is:

Let us assume we are attacking HMAC-MD5 within TLS; this has a 128 bit key.

The fastest GPU server (actually, it has 25 GPUs internally) can test about 400 billion keys per second.

Let us assume that we, having a huge budget, have assembled 1 million of the above units; that means that we can test $4 \times 10^{17}$ keys per second; sounds impressive.

However, it'll take an average of $2^{127}$ keys tested before we recover the HMAC-MD5 key; at $4 \times 10^{17}$ keys per second, that'd be $4 \times 10^{20}$ seconds, or about $10,000,000,000$ years.  I'd call that somewhat impractical; if nothing else, the sun will become a red giant and destroy our set up before we're likely to find a result.

It gets even worse if we talk about HMAC-SHA1; that uses 160 bit keys; that increases the amount of time we'd expect to take by about 4 billion.

Yes, if what we're talking about is a key derived from a password, GPUs can be used.  However, when we're talking about random keys, they don't come close to scratching the algorithm.


Sending TLS messages with out encryption using openssl code

Yes, there are a number of TLS cipher suites that don't include any encryption.  These cipher suites are not normally used by OpenSSL, but they can be explicitly requested e.g. using the -cipher option to the OpenSSL tools.

Specifically, the suites offering no encryption and/or authetication are found under the NULL and aNULL cipher classes.  The openssl ciphers manual page describes them as:

  "eNULL, NULL:
  the "NULL" ciphers that is those offering no encryption. Because these offer no encryption at all and are a security risk they are disabled unless explicitly included.

  aNULL:
  the cipher suites offering no authentication. This is currently the anonymous DH algorithms. These cipher suites are vulnerable to a "man in the middle" attack and so their use is normally discouraged."

To get a list of the cipher suites included in the NULL class, run openssl ciphers -v NULL.  For me, the returned list looks like this:

ECDHE-RSA-NULL-SHA      SSLv3 Kx=ECDH     Au=RSA  Enc=None      Mac=SHA1
ECDHE-ECDSA-NULL-SHA    SSLv3 Kx=ECDH     Au=ECDSA Enc=None      Mac=SHA1
AECDH-NULL-SHA          SSLv3 Kx=ECDH     Au=None Enc=None      Mac=SHA1
ECDH-RSA-NULL-SHA       SSLv3 Kx=ECDH/RSA Au=ECDH Enc=None      Mac=SHA1
ECDH-ECDSA-NULL-SHA     SSLv3 Kx=ECDH/ECDSA Au=ECDH Enc=None      Mac=SHA1
NULL-SHA256             TLSv1.2 Kx=RSA      Au=RSA  Enc=None      Mac=SHA256
NULL-SHA                SSLv3 Kx=RSA      Au=RSA  Enc=None      Mac=SHA1
NULL-MD5                SSLv3 Kx=RSA      Au=RSA  Enc=None      Mac=MD5

To see if a specific server lets you connect to it using one of these suites, run:

openssl s_client -connect host:port -cipher NULL

Of course, for most services, this should cause the cipher suite negotiation to fail, like this:

$ openssl s_client -connect www.google.com:443 -cipher NULL
CONNECTED(00000003)
3073382600:error:14077410:SSL routines:SSL23_GET_SERVER_HELLO:sslv3 alert
handshake failure:s23_clnt.c:724:
---
no peer certificate available
---
No client certificate CA names sent
---
SSL handshake has read 7 bytes and written 139 bytes
---
New, (NONE), Cipher is (NONE)
Secure Renegotiation IS NOT supported
Compression: NONE
Expansion: NONE
---


Associative standard cryptographic hash function

If you don't need $H$ to be collision-resistant, you can use

$$H(a,b) = h(a) \times h(b) \bmod p$$

where $p$ is a large prime such that $p-1$ has a large divisor (and in particular, the discrete log problem modulo $p$ is hard), and with $h:\{0,1\}^* \to \mathbb{Z}/p\mathbb{Z}$ a hash function that outputs numbers in the range $[0,p-1]$.

If $h$ is a cryptographic-strength hash function, this will be one-way (preimage-resistant) in the random oracle model.  As poncho explains, it won't be collision-resistant, because $H(a,b)=H(b,a)$.

You could also consider

$$H(a,b) = h_0(a) \times h_1(b) \bmod p$$

where $h_0,h_1$ are two separate cryptographic hash functions (e.g., $h_b(x) = h(b,x)$).  This will be one-way and collision-resistant.  I don't know whether it will meet your needs, though, because it's not exactly of the form you mention.

See also MuHash, as described here: Does collision resistance stay when extending a hash function to a set domain?

You might also consider a generalization of this that provides associativity but not commutativity.  Let $\mathbb{G}$ be any non-commutative group.  Then one candidate construction is

$$H(a,b) = h(a) \times h(b) \bmod p$$

where $h:\{0,1\}^* \to \mathbb{G}$ a hash function that outputs group elements.

This gives a candidate construction for each non-commutative group.  Will it be secure?  I don't know, but I expect that will depend upon $\mathbb{G}$.  It seems plausible that with a suitable choice of $\mathbb{G}$, you might be able to design a hash function $H$ that is secure, i.e., one-way and collision-resistant (at least when we model $h$ as a random oracle).

I haven't tried to come up with a specific candidate, but one plausible choice might be letting $\mathbb{G}$ be a suitable set of $2 \times 2$ matrices over a some finite field $\mathbb{F}$, so that $\mathbb{G} = SL_2(\mathbb{F})$.  See, e.g., hashing with SL2: Non-commutitive and nonassociative algebraic structures in cryptography for a related scheme.  I haven't worked out all the details, but this might give you enough ideas to come up with a candidate scheme that meets all of your requirements.


How does the ring settings of enigma change wiring tables?

There's two missing pieces.  First, the ring setting changes the output letter, it doesn't rotate the whole exit pattern.  Second, the rotors are advanced before the letter is encrypted.

If your rotor (Enigma I Rotor I) is set up like this with the ring at A.

abcdefghijklmnopqrstuvwxyz
ekmflgdqvzntowyhxuspaibrcj

Then if you advance the ring to B all the outputs will be shifted up the alphabet by one.  A will become F instead of E.  B will become L instead of K.  And so on.

abcdefghijklmnopqrstuvwxyz
flngmherwaoupxziyvtqbjcsdk

This almost matches the simulator, but why is the simulator's output shifted over one?

abcdefghijklmnopqrstuvwxyz
kflngmherwaoupxziyvtqbjcsd

  Remember that, when depressing a key, the rotors advance before the electrical signal runs through the rotors. Therefore, to examine the current flow through the rightmost rotor in A position, the rotor must be set in the Z position before depressing the key (this also counts for the other rotors if they are due to step).

Source: Technical Details of the Enigma Machine

When you press A the rotor advances to B and encrypts the letter according to B.  Your simulator has to first advance the rotor and then encrypt the letter.


Abstract Algebra
Number theory
Statistics
Computer/Network security (so you can see the application)


What are requirements of the audio input to be encrypted using AES?

As LightBit notes in the comments, modern ciphers like AES work on arbitrary binary data, and don't care about what those bits represent.  Thus, you can use AES to encrypt any kind of (audio or other) files or streams.

That said, there is one detail to keep in mind: basically all practical encryption schemes (including AES in any of the commonly used modes) leak the length of the data being encrypted.  (Some schemes may round the length up to say, the next multiple of 16 bytes, but that still leaks the approximate length.)

When encrypting compressed data (like MP3 / AAC audio), this can in turn leak information about the content: for example, 1 second of silence compresses a lot better than 1 second of speech (which, in turn, compresses a lot better than 1 second of random noise).  Thus, just by observing the length of the encrypted messages or packets, an attacker may be able to learn information about the sounds encoded in the encrypted data.

This is not just an academic concern: precisely this kind of an attack has been used to break VoIP audio encryption by researchers a few years ago.  The CRIME and BREACH attacks on HTTPS also rely on compression leaking data about the plaintext via the message length, although those are not specific to audio.

The only general solution to message-length leaks is to ensure that all messages (or packets, for something like a real-time telephony protocol) have the same length (or, at least, that the message length only depends on things you're reasonably sure it's safe to leak, like the duration of the conversation).  For audio encryption, this might be achieved e.g. by first using an audio compression algorithm with a fixed maximum bitrate, and then padding any compressed packets to a fixed length before encryption.


For what kind of "concrete" application should we implement cryptographic algorithms on FPGA? Which secured application require such a huge data processing performance ?

Well, FPGAs are ideal for a wide variety of applications, from high-volume applications to state-of-the-art products.

Imagine you are…

a bank, or
a Big Data service provider, or
a governmental institution, or
a military force, or
…

and you need to encrypt terrabytes of data in the shortest amount of time possible, because…

time is money, or
your clients want their Big Data to be stored safely on your servers via a double-encryption, or
a huge stream of intercepted metadata needs to be protected from the public eye, or
the enemy is near your last line of defense and you need to secure some data immediately, or
…

Whatever valid reason you might have to need cryptography “now” instead of “later”, you will want to choose the fastest option possible. In that case, it makes sense to use the (immensely) faster FPGA (and/or ASIC) solutions instead of hoping your CPU(s) will manage to handle the job in such a short amount of time.

From a civilian point of view, I guess the most understandable motivation as to why cryptographic algorithms are implemented on FPGA would be the economic factor. It should be noted that you burn less energy when using an optimized FPGA or ASIC implementation. This practically means you can “produce more work” while investing the same (or less) amount power as you would have invested when using your CPU(s).

Now, related to your comment:

  Are there non cryptanalytical examples ?

Thinking about it, here’s a first, nice, practical, non-cryptanalytical example: cryptocurrencies. Just take a short look at the history of those folks… who evolved from “mining their coins” (read: creating their proof of work via cryptographically secure hashing algorithms) with CPUs, then switched over to GPUs because they were faster and more energy efficient, and ended up using specialized ASICs.

Besides that, there are – of course – other non-cryptanalytical examples. As a matter a fact, “An FPGA Implementation and Performance Evaluation of the. AES Block Cipher Candidate Algorithm Finalists” already hints at that, and a short search engine quest would have provided you with ample commercial product examples.

For your convenience, here are two randomly picked, non-cryptanalytical product ranges:

Helion : IP Core Products, based on ASIC or FPGA (Encryption, Authentication, Hashing, et al.)
Nallatech : 40Gbit AES Encryption Using OpenCL and FPGAs

I’m sure you’ll be able to find more examples using your favorite search engine…

EDIT (Lazy-Friday Bonus):

For the fun of it (and because I had a lazy friday afternoon), I whipped up two non-optimized C proggies just to show you something practical…

See that speed (and hash-count) difference?

Now imagine the increase that could be gained when using a field programmable gate array (FPGA). What might take years for one person, might just be a matter of hours for another.

Such speed differences are like a coin with two sides: benign users can enhance security in many areas, while malign users can attack faster (making some attacks feasable in the first place.)

That’s one of the reasons cryptographical FPGA solutions are of interest… no matter which side of the coin one prefers or chooses.


How is BCrypt secure when it uses a static dataset for blowfish hashing?

The BCrypt password hash algorithm is based on a modified version of the Blowfish encryption algorithm. The $P$ values are the round subkeys (used for XORing with the data), and the $S$ values are components for substitution boxes, both used in a Feistel network.

The initial values for $P$ and $S$ are the same as in the original Blowfish algorithm, and come from the hexadecimal digits of the circle constant $\pi$.

During the key schedule, these values $P$ and $S$ are used to create new (key-dependent) values, and then replaced by those. One critique point of Blowfish always was that it's key schedule is relatively slow (about as much as encrypting 4 KB of data - since we actually encrypt the zero string with the current $P$/$S$ values to create the new ones, and the size of $S$ and $P$ together is just 4 KB).

Bcrypt takes this slowness to a new level, using an expensive key schedule instead of the default blowfish key schedule, which takes a (configurable) much longer time.

This essentially (after a more complicated initial round which includes both salt and password) executes the normal key schedule $2^{\operatorname {cost}}$ times with each of salt and password as input, where $\operatorname{cost}$ is the cost parameter (the original bcrypt paper proposed $\operatorname{cost} = 6$ for normal user accounts, $\operatorname{cost} = 8$ for the administrator account). This is thus (time-)equivalent to encrypting $8·2^{\operatorname{cost}}+4$ KB of data with normal blowfish.

Then, a constant string (OrpheanBeholderScryDoubt) is (64 times) encrypted with the normal blowfish encryption using the thus created $P$ and $S$ boxes as state, producing an 192 bit string, which is then considered the bcrypt output (which is normally stored together with the salt and the cost parameter).

As we can see, the actually used values of $P$ and $S$ are very non-constant, depending strongly on the salt and password input. The initial values being fixed is not a vulnerability, but necessary to get identical output for identical input on each implementation.

Coming from the digits of $\pi$, they also quite likely don't contain a backdoor created by the designers of the algorithm (a nothing-up-my-sleeve-number).

Also, for a password hashing algorithm a collision attack is not the most important attack: An attacker finding two passwords which give (for a specific salt or pair of salts) the same hash, has about no advantage for finding the passwords to existing hashes (which also quite likely are using different salts).


Is it possible to crack AES 128 key if one can use the key to encrypt arbitrary data block?

Is there a term referring to this kind of crack which is 'crack key with the ability to encrypt arbitrary data block by the key'?

Yes. That's a Choosen Plaintext Attack. AES-128 is designed to resist that, and as far as we know does so very well. CPA is considered indispensable for any modern cipher or block cipher.

Beware however that in practice, an adversary might gather additional information (side channel attacks), like the power consumption during encryptions (Differential Power Analysis), the time it takes to make the encryption (timing attack), or the state of the data cache after that (cache as side channel), or the result of encryption when some of it is affected by errors (fault attack). An AES implementation could be vulnerable to these.


Can a raw ECDH shared secret be used directly for encryption?

If two parties calculate an ECDH shared secret can they (with no security weakness) use this raw value directly as an encryption key?

If the ECDH curve size is large enough, then yes, there is no immediate security weakness.  It would cause the theoreticians heartburn (as the symmetric key is supposed to be chosen uniformly,  and it isn't in this case), however there is no practical way for an attacker to exploit this.

To give an example: suppose the ECDH is done over P256, and you use the x-coordinate as the shared secret; and you use that shared secret to key AES-256.

Then, the attacker knows that (approximately) half the possible AES-256 keys are impossible (as they cannot be the x-coordinate of a P256 point); however there still are approximately $2^{255}$ possible values the key could be, and it would still be impractical to search over that large of a space.


Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)

Not if the attacker is given enough time to ask for the values $F(k,x)$ for all $2^n$ values of $x$.  We have

$\Sigma_x F(k,x) = 0$

which is distinguishable from random.


Explain same encryption time for two files of different sizes

Modern computers are quite fast, and modern cryptographic algorithms are quite efficient.

Most computers benchmark hardware accelerated AES in CTR mode well above 1GB/s, which would be a fraction of a millisecond for a 100KiB file. Since the standard system timer generally runs at 1ms intervals, the entire encryption operation ([file data] XOR [AES] XOR [Pad]) will take less than a single timer 'tick' to complete, and they will report the same completion time.

I would expect files up to 3 MiB will take less than 1ms to complete on computers made in the last 5 years, if the timer is started after the file data is read from disk, just prior to encryption.

Try using a much larger file, at least 1 GiB, in order to gauge the performance of the system. Also, Windows offers a high resolution timer through the kernel, if the hardware supports it, offering sub-microsecond accuracy. If you try to repeatedly measure very small time windows, they will vary greatly if there are other processes using the same CPU core.


why is index "a non-negative integer less than $2^{64}$" in the KDF for UMACs?

Because of this:

   T = uint2str(index, BLOCKLEN-8) || uint2str(i, 8)

uint2str obviously creates an encoding of an unsigned integer of at least 64 bits, given that the block size is at least 128 bits / 16 bytes. So for a 128 bit block size you can have a number between 0 (inclusive) and $2^{64}$ (exclusive) before you run out of bits.

It's a better question why numbytes is not below $2^{64} \cdot 8$ or $2^{67}$ as there is clearly some space left, how much depends on the block size. Of course, neither variable needs to go very high in practice, as this is a KDF, not a stream cipher. For the KDF to be secure, it is just important that $T$ is unique...

As I expected, I quickly found this quote to cement my suspicions:

  In any case, BLOCKLEN must be at least 16 and a power of two.

although AES - and therefore a block size of 16 bytes / 128 bits - is assumed. So there you are: the index must be less than $2^{64}$ because that's all there is space for within this scheme.

Note that "str" usually refers to an octet string - also known as a byte array or simply a span of bytes in memory - in specifications such as this one.


If you implemented it well, and there is no MITM (i.e. use authenticated comm channel), then it is difficult to forge the RSA signatures (meaning you can use them safely).
However, in your implementation there are 2 other major factors that you need to consider:

One is the use of Javascript as a coding medium: there are many who consider Javascript to be a bad languange to use for writing security code due to some notable exposure to adversaries. I personally am not in that camp - if you take good care of securing your environment where you run the JS code you will be OK.
Also, there are some advantages of letting the user's browser do the work (and Java has its own set of implementation / management problems), this may be a prudent choice.

The second point is a major one: you selected “cryptico” engine, and we don't know how well the guy who wrote and modified the code behaved.
Some critical security routines there were modified by him, and this should ring a big red alarm bell over its usage. If you plan to use it for anything important, you need to pass the published code through a critical security/cryptographic review before usage.