Why is pqRSA in the NIST PQC submissions?

[source of information: my interpretation of multiple hallway chats I've had with DJB and Tanja Lange at conferences]

The actual NIST PQC submission was for two reasons:

A joke. Evidence1: DJB yelling from the back of the room "How much RAM does the NIST benchmarking machine have??" Dustin Moody replying "Dan, we're not benchmarking pqRSA!". Evidence2: DJB mercilessly mocking his paper's reviewers on stage: "Of course it's not practical! This guy clearly has a British stiff upper lip".
A template for other submissions. DJB's plan at least was to submit it several months early to iron out the kinks in the submission process, and to make the latex source public for other submitters to re-use the format and the legal boilerplate (I don't know whether he did or not).

The scientific work behind the submission made some very valuable contributions to the field of cryptographic science:

Answer the question:

Question: "Do the honest parties (keygen, encrypt, decrypt) have an asymptotic advantage over a Shor's adversary? If so, how big does the key need to be to get a comfortable amount of quantum security?"
Answer: Yes; 1 TB keys to force a quantum circuit with >= $2^{128}$ gates. This reduces to 1 GB keys if you take into account latency between quantum gates and make a "not before expiry of the universe" type argument.

Modification to the encrypt and decrypt operation to make them more efficient on multi-prime keys.
Batch-prime generation: to optimize keygen of several thousand (million?) 1024-bit primes, they came up with a way to more efficiently generate primes in batches.
Can we save ECC the same way? As part of the same research, effort was put into making a pqECC with a similarly massive key, but they could not find equivalent mathematical tricks that would give the honest parties an asymptotic advantage over a quantum adversary.

Even though the submission will not make it past Round1, it made valuable contributions both to the competition itself, and to cryptographic science as a whole. As @SqueamishOssifrage said in comments:

  The hard work was already done—the paper written, the code tested—so hey, why not submit it?


You can do the following:

The server generates a linear equation $y=ax+s$ where $a$ is chosen randomly from a finite field $F_p$ and $s\in F_p$ is the secret.
For the values from $A,B,C$, let’s call them $x_A,x_B,x_C$. Evaluate the linear equation at these $x$ values and the server gets $y_A,y_B,y_C$.
The server returns $y_A, y_B,y_C$ to $A,B,C$ respectively.

Each party now has a share which is a pair $(x_i,y_i)$. Any two shares can reconstruct the secret $s$.

This is essentially (2,3)-Shamir secret sharing.


What is the longest AES key that has been recovered in practice?

Are such competitions held, and is there a recognized progress meter that is kept?

No. It is generally believed that $2^{128}$ AES keyschedule and encryption operations are out of reach for just about anyone. If and when that changes and $2^{128}$ draws in to be a more realistic number perhaps people will do that.

However, I have been unable to find any documentation of the biggest AES key that anyone claims to have recovered in practice.

This is usually not an interesting publishable result unless you also have found some major optimization to some part of the computation and thus not very desirable to do for academics.

As for search speeds:

On a CPU - assuming you get lucky with instruction scheduling - one round of AES with a keyschedule computation (very optimistically) costs you about 3 CPU cycles on a single core. For each AES instance there are 10 such steps, so around 30 cycles overall for on-the-fly key scheduling and encryption of one block - using only throughput not latency numbers. This amounts to about 1-2 billion AES key tests per core per second on a modern CPU. Assuming it is one of the beefiest around it has 64 physical cores and two CPUs on a mainboard amounting to say 200 billion AES key tests per second per mainboard. Feasibly a determined attacker can acquire and operate say ten thousand such mainboards amounting to $2\times 10^{15}\approx 2^{50}$ key tests per second. Then a realistic upper bound for how long would want to have this hardware run non-stop would be say 10 years if determined which adds another factor of $\approx 2^{28}$ amounting in total to $2^{78}$ AES keys using 20,000 of the current beefiest CPUs run for 10 years with a highly optimized implementation.
As for GPUs: A top-end Nvidia Pascal GPU hits about 32GB/s of AES throughput. That is 2 billion AES instances per second without the keyschedule, with the keyschedule it will probably drop down to ~800 million AES instances per second. Even if we assume that later GPU generations give a 5x performance increase to this number we'd only be looking at the performance of 1-2 additional CPU cores for a lot more power draw, so this is likely not worth it.
As for FPGAs, this paper claims around 120Gb/s throughput from an FPGA that has ~150 thousand lookup tables. Nowadays there are FPGAs around that are 25x larger. Using the usual (optimistic) factor of 3 for the keyschedule we're looking at around 8 billion key tests per second and card. This might be worthwhile if you can cool it properly but chances are it's a better investment of power to use more CPUs (which draw comparably much).
As for ASICs, this paper claims $678\times 10^{-6}$ bits per clockcycle-gate as the best result (ish). Assuming a GPU-sized die running at say 1GHz this would amount to $2\times 10^{16}$ bits per second or $2^{47}$ AES instances per second. Dividing this by our usual factor yields about $2^{45}$ instances per second. Assuming then that you can in fact produce, power and cool such a large die and somehow stack say 8 into a server mainboard's PCIe slots it would give you $2^{48}$ tests per board or almost $2^{90}$ tests in 10 years using 10,000 boards with 8 GPU-sized dies each running at 1GHz for 10 years.


El Gamal existential forgery using Pointcheval–Stern signature algorithm

The scheme you consider is the original ElGamal signature.  This scheme is known to be existentially forgeable.

By definition, a valid original ElGamal signature on a message $m \in \{1, \dots, p-1\}$ is a pair $(r,s)$ satisfying $g^m \equiv y^r \cdot r^s \pmod p$.

With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$ for random integers $e$ and $v$ the pair $(r,s)$ is a valid signature on message $m = e \cdot s \bmod (p-1)$. To see it, you must check that $g^m \equiv y^r \cdot r^s \pmod p$:

For $m = e \cdot s \bmod (p-1)$, we have $g^m \equiv g^{e\cdot s} \pmod p$;
With $r = g^e \cdot y^v \bmod p$ and $s = -r\cdot v^{-1} \bmod (p-1)$, we have $y^r \cdot r^s \equiv y^r \cdot (g^e \cdot y^v)^s \equiv y^{r+v\cdot s}\cdot g^{e\cdot s} \equiv y^{r+v\cdot (-r\cdot v^{-1})}\cdot g^{e\cdot s} \equiv y^0 \cdot g^{e\cdot s} \equiv g^{e\cdot s} \pmod p$.

Since the two sides are equal modulo $p$, the signature is valid. Q.E.D.


What SALT value will be used in HKDF_EXTRACT in TLS1.3?

The relevant text at the end of section 7.1 that explains this is:

  If a [PSK or ECDHE] secret is not available, then the 0-value consisting of a string of Hash.length bytes set to zeros is used.  Note that this does not mean skipping rounds, so if PSK is not in use, Early Secret will still be HKDF-Extract(0, 0).

This means that when a PSK is not used, the first step in key derivation is to compute the Early Secret (which is a fixed value that depends only on the selected HKDF hash function).

Following the main flow chart in section 7.1, feed Early Secret through Derive-Secret once, and the result is the salt argument for HKDF-Expand for the Handshake Secret calculation.

early_secret_no_psk_sha256 = "33ad0a1c607ec03b09e6cd9893680ce210adf300aa1f2660e1b22e10f170f92a"

And finally the HKDF-Expand salt for Handshake Secret is obtained when you invoke Derive-Secret(., "derived", "") on the Early Secret. For SHA-256, you end up with:

handshake_secret_salt_no_psk_sha256 = "6f2615a108c702c5678f54fc9dbab69716c076189c48250cebeac3576c3611ba"

Since these values contain no entropy, you don't need to compute them every time (again, assuming a PSK is not used). These values can be derived by anyone from the RFC text and depend only on the selected HKDF hash function.


Why would using a random seed with other variables be bad for ecrypting if you can't guess the key?

Your option has the flaw of allowing either key recovery, or RNG state recovery, or both. Cryptographically strong constructions do not allow key recovery with less effort than brute force, even with millions or billions of known message pairs. In your case an attack will most likely succeed in a short period of time. It took me only a few hours to completely break something quite similar that at first glance appeared much stronger than this, but suffered from the same key recovery attack with modest computing power.

Since Python does not have native encryption, you kind of have to roll your own from the standard library, or use an addon library such as PyCrypto.

If you do not have the option of using an addon library, a stream cipher can be built from HMAC-SHA512, plus a nonce and a some counters. The high level overview is:

Generate salt and nonce (nonce can be 128-bit salt + 32-bit message counter).
The salt should be randomly generated, if a good RNG is not available in Python, use random.org
Salt needs to be stored, it is used to generate the encryption key for all messages.
Message counter is very important to keep current.

Generate key from password and salt using PBKFD2. If you are using a true random key and not a password you can skip this part.
key = hashlib.pbkdf2_hmac('sha512', 'Password', 'Salt', 32768)[:44]

I use truncated HMAC to generate 44-byte blocks, and a 32-bit message counter. The reason I truncate is to hide 160-bits of the hash state, which may provide additional security, but slows it down to around 2/3 of what is capable.
Find out how many blocks of keystream are required to encrypt the message. A 113-byte message would need 3 44-byte blocks

hm0 = hmac.new(key, 'Nonce', hashlib.sha512)
hm = hm0.copy()
hm.update('BlockCounter')
KSBlock = hm.digest()[:44]

Loop the last 3 lines for each block of keystream you need, XORing the plaintext with the keystream to generate the ciphertext with the same length as the plaintext. Once that is done, prepend (or include in some way) the message counter. Decryption and encryption are the same operation, with the difference being you are using a specific message counter instead of a new one. You can also decode blocks out of order, which can be useful for large messages. Text readable encoding such as Base64 can be applied after encryption.

This example ties the encryption key directly to the password, which I assume is what you are looking for. Other methods use the password to encrypt a random key, then the key encrypts the message. This would allow for the password to be changed without having to reencrypt the entire message. On the other hand it needs a good random number generator.

The 32-bit counters give you a max message size around 176GB, and over 4 billion messages before the nonce counter runs out. This should be more than enough for a single person using a web application. Note that I am not a Python programmer, and the code samples here may not be proper syntax, and are more of a pseudocode. I would still highly recommend a cryptographic library and use AES-CTR instead, but sometimes you have no option.


How to store keys for a cascading encryption?

The part of this answer that talks about key storage is at the end, the first part is about implementing a cascade.

There are 2 main methods for cascading block ciphers, inside of the mode and outside of the mode. Within the encryption you have your mode of operation, and you have your block cipher cascade. The first cipher in the cascade will be considered the primary cipher.

Inside the mode means replacing the block cipher inside the mode with the cascade. In this method there is the single mode of operation wrapped around the cascade. The non primary ciphers essentially act in ECB mode on the ciphertext of the primary cipher, and the ciphertext of the final cipher is the ciphertext of the mode's inner cipher.

Outside the mode means you encrypt the plaintext with each mode (and each cipher) in sequence. This allows use of multiple modes, which can either have a security or performance advantage (or both, or neither). For example, the output of AES_CFB can then be encrypted with Twofish_CBC.

Depending on the target platform and development language, either method may have an implementation advantage. Certain modes of operation such as CTR or ECB are parallelizable, whereas CBC and CFB are note. CTR also allows encryption of lengths that are not a multiple of the cipher block size without using padding or CTS. The method Truecrypt uses is optimized for filesystem encryption, and using that method may not meet your requirements (which are not specified). AES also allows high speed timing analysis/DPA resistant implementations on modern processors with AES_NI instructions.

Cascading has not officially been given anyone's seal of approval, but it does have an allure that a single cipher may be completely broken and your ciphertext remains secure. For the actual security of using it, see the answers here: Combining multiple symmetric encryption algorithms - implications? I tried not to talk about how to implement in my answer, as it was not part of the question like it is here, but the security implications are quite relevant.

As for the main point of the question, how to store keys, you would do it the same way as any other cryptosystem, you are just storing more key data in this case. Standard methods include a high entropy unguessable password hashed with a KDF to generate key data, or encrypting the keys using an asymmetric algorithm. The strength of the KDF and asymmetric key size should be at least as strong as the expected security of the cascade. (256 to 768 bits with up to 3 AES candidate algorithms). In your example a password known to both parties is used to generate the keys, so there is no storage of keys, it is generated from hashing that password in some method that generates enough bits.

My personal recommendation for balanced speed and security would be to use AES128_CTR first then encrypt with Twofish256_OCB3. This requires 384-bits of key data, which can be generated using a SHA384 or an appropriate key derivation function, but it is better to use a strong random source if possible. Getting the keys to the recipient securely is a whole different problem.


If you use CBC mode and your communication protocol looks like SSL, then you may have trouble. In SSL 3.0 and TLS 1.0, the IV for each record is the last block from the previous IV; this implies that an attacker who can both inject some data of his own in the stream, and observe the outcome, may know the IV for the next record and choose his data accordingly. This is the basis for the BEAST attack: that attack context turned out to be realistic when the client is a Web browser.

In all generality, a decent communication protocol should provide both confidentiality and integrity, which means that your data should use a MAC. Combining symmetric encryption and MAC properly is known to be tricky and a good method is to use an encryption mode such as GCM or EAX which does both jobs. A nice point here is that these two modes don't require a random IV, only a non-repeating IV.

This leads to a communication protocol where the initial key exchange (say, your Diffie-Hellman) produces an initial shared secret, which is expanded into two symmetric keys, for the two directions of communications (this "expansion" can be as simple as hashing the initial shared secret with SHA-256, and splitting the 256-bit result into two 128-bit halves). Then both client and server send a sequence of "messages" to each other, using as IV the sequence number of each message (first message from client to server uses as IV the value 1, second message uses the value 2, and so on).

Note that GCM and EAX rely on AES. You can adapt them to any 128-bit block cipher. Usage of block ciphers with 64-bit blocks, like 3DES or Blowfish, is not recommended nowadays, because security of many encryption modes tends to break down when encrypting $2^{n/2}$ blocks with the same key, when blocks have size $n$ bits. For 64-bit blocks, the threshold is around 30 gigabytes, which is not that much.

If your protocol is single-record (after the key exchange, each party sends a single message, which is encrypted in one go, avoiding any BEAST-like issue), then a fixed IV is acceptable, since the key will be used for a single encryption run. However, it would be equally acceptable to derive from the shared DH secret a symmetric key for encryption and the IV; this is what SSL/TLS does (or at least did prior to version TLS-1.1): see the standard, section 6.3.


Shamir Secret Sharing: Why cannot we recover polynomial's root if we have $t-1$ shares?

Shamir Secret Sharing (SSS) is based on constructing a polynomial of degree $t-1$, whose independent term is the secret $S$. Each share is actually a point of the polynomial.

The security of SSS is based on the fact that, when one wants to interpolate a polynomial of degree $t-1$, one needs at least $t$ points of the polynomial. It can be seen graphically that trying to interpolate with less points (e.g., with $t-1$ points) is impossible since infinite polynomials can be drawn through those points. The Wikipedia article for SSS illustrates this very well.

In cryptographic applications you will not have "infinite" polynomials, but all the possible polynomials of degree $t$ for the given field. That means that knowing $t-1$ points is useless as all possible polynomials are equally plausible. This is called "perfect secrecy".


Does input truncation using SHA-256 expose any potential weaknesses?

No, hashing the passphrase with SHA-256 will be no stronger or weaker than feeding it in directly.  If you go with Scrypt (which I would recommend you do), there are no restrictions on the size of the passphrase... and Scrypt consumes it internally with one round of PBKDF2-HMAC-SHA256 anyway.

  When generating the HMAC authentication and encryption keys, would I benefit at all from using SHA-512?

No, you wouldn't. In fact, this step is unnecessary.  Just use the output of Scrypt directly... randomBytes = Scrypt(passphrase); encKey = randomBytes[0, 31];  authKey = randomBytes[32, 63]


RSA encryption is based on modular exponentiation, where the plaintext $m$ is transformed into a ciphertext $c$ by the operation $c = m^e \pmod n$. For any moderately large value of $e$ (normally 65537), this works OK.

However, the numbers 0 and 1 are unaffected by this operation, because $0^e = 0$ and $1^e = 1$ for any encryption key $e$ and any modulus $n$. Thus in "textbook" RSA, if $m$ is equal to 0 or 1, then $c$ is equal to $m$ and the encryption has no effect.

In practice, this isn't a problem because in the real world, padding is used to ensure that there is no possibility of $m$ being equal to 0 or 1. Padding can also provide other benefits such as semantic security.


Is the member sum of a subset of $\mathbb{Z}/p\mathbb{Z}$ known (with $g^n \bmod p$)? Is it always $\mod P = 0$?

(I observe $S=c\cdot P$ for some integer $c$.) Is that always the case?

Yes. Proof follows.

If $g=P$ then $S=0$. We'll disregard this special case in the following.

The set $M$ has $k$ elements, with $k$ the lowest strictly positive integer with $g^k\equiv1\pmod P$. This $k$ is known as the order of $g$ modulo $P$. This $k$ divides $P-1$. $M$ also is $\{g^n\bmod P, \text{ with } 0 \le n <k \}$, and in this later definition the $g^n\bmod P$ are distinct.

It follows $\displaystyle S=\sum_{n=0}^{k-1}\left(g^n\bmod P\right)$.

Therefore $\displaystyle S\equiv\left(\sum_{n=0}^{k-1}g^n\right)\pmod P$.

$g\ne 1$. Therefore $\displaystyle S\equiv\frac{g^k-1}{g-1}\pmod P$.

It holds $g^k-1\equiv0\pmod P$. Since $P$ is prime and $g\in[2,P]$, $g-1\ne0\pmod P$.

Therefore $S\equiv0\pmod P$. That is $\exists c\in\Bbb Z, S=c\cdot P$

  Any way to calculate this factor $c$?

If $k$ is even, then $c=k/2$. Argument: if $k$ is even and $x\in M$, it can be shown that $x'=P-x\in M$. We can pair the elements of $M$ into $k/2$ pairs which each sum to $P$.

If $k$ is odd, $c\approx k/2$ still holds. An heuristic argument is that $S$ is the sum of $k$ terms about haphazardly distributed in $[1,P-1]$, thus about $P/2$ on average. That's the best I can tell.

Notes:

$c$ depend only on $k$ and $P$ (not $g$), per the fundamental theorem of cyclic groups.
We can efficiently tell the parity of $k$ from $P$ and $g$: write $P-1$ as $2^\lambda z$ for odd $z$; then $g^z\bmod P=1$ iff $k$ is even (as commented by poncho).
$k$ can be efficiently found from $P$, $g$, and the factorization of $P-1$.


Would it be possible to negotiate a key of 128 or 256 bits strength using Merkle puzzles?

The complexity required for the attacker to break the scheme is at maximum quadratic in the security parameter $n$. It is not enough for a secure cryptographic protocol where you want exponential complexity to break the scheme.

Say $n$ is the difficulty of solving the puzzles and $m$ is the number of puzzles. Alice needs to solve one puzzle in time $O(n)$ but Bob will need to look in his puzzles to find the correct key. He needs roughly $O(m)$ time. The scheme has then $O(n+m)$ time complexity.

For breaking the scheme, Eve can brute force all the puzzles, she then needs $O(nm)$ time complexity. If you want to have this complexity be around $2^{128}$ you need to send an incredible amount of puzzles and/or puzzles too hard.


How can prime factor of $q-1$ divide prime $q$?

For arbitrary positive integer $n$ we have:

  $$\gcd(n,n+1)=1$$

So $q-1$ and $q$ haven't any nontrivial common factor.


Securely testing the presence of an item in a list without exposing the list

You could use convergent encryption for this.

For each item to be inserted, compute its hash, then encrypt it by deriving a key from that hash. Insert the ciphertext (discarding the hash/key).
To test for the presence of an item, hash it, encrypt, look for matching ciphertext.

You would likely want to use something like a hash table or a search tree (dictionary or set), instead of a flat list, to avoid $O(n)$ scan when looking for an item.

Note that the user can brute force / dictionary attack the scheme by encrypting chosen items and checking them against the list.


Just so we are on the same page, I recall that the LWE problem assumes that for a secret (and usually small) vector s, it is hard to distinguish (A,b = As+e) from a random (A,b), where A is a random matrix of $\mathbb{Z}_q^{m\times n}$ and e is small. (Considerations about the required parameters and the error distribution are irrelevant for our argument, so I skip them for simplicity.)

With hypotheses for the polynomials $s,a_i,e_i$ that are similar to the ones we had for s, A, e, Ring-LWE assumes that it is hard to distinguish $(a_i,b_i = a_i\cdot s+e_i)$, which we call R-LWE samples, from random $(a_i,b_i)$.

Now, there are at least two (closely related) ways to answer your question :

The public key of Alice is $(a, b = a\cdot s+e)$, and Bob sends her an encrypted message
$$(u,v) = (a\cdot s_b + e_b, b \cdot s_b + e_b' + m \lfloor q/2 \rceil).$$ $(a,b)$ is a R-LWE sample for the secret $s$ so it is indistinguishable from random for Eve. Similarly, if Bob sent $m=0$ to Alice, then  $(a,u) = (a, a\cdot s_b + e_b)$ and $(b,v) = (b, b \cdot s_b + e_b')$ are R-LWE samples for the secret $s_b$ so everything looks completely random to Eve and she wouldn't be able to distinguish whether Bob sent $m=0$ or random stuff to Alice.  To send $m\neq 0$, Bob adds $m \lfloor q/2 \rceil$ to $v$ and it will still look random to Eve.
I also like this more "lattice" approach. This is my interpretation and abusive notations ensue, so feel free to disagree:
$$\binom{u}{v} = \binom{a}{b}s_b + \binom{e_b}{e_b'} + \binom{0}{m \lfloor q/2 \rceil}$$
So $(u,v)$ = [point of the lattice generated by $(a,b)$] + [a small error] + [the message]. The error is chosen big enough so that Eve is unable to decode [lattice point] + [error], let alone [lattice point] + [error] + [message].
However, Alice can perform a "dot product" of $(u,v)$ with the secret vector $(-s,1)$, which is small and almost orthogonal to $(a,b)$:
$$\binom{u}{v} \cdot \binom{-s}{1} = e\cdot s_b + (e_b'-s\cdot e_b) + m \lfloor q/2 \rceil$$
At which point Alice can easily remove the remaining errors and recover m.


Question regarding multiple SHA-256 rounds on a Bitcoin Brain Wallet passphrase…

This would hopefully eliminate the worry that somebody could reverse-engineer the process by which I generate the brain wallets.

By Kerckhoffs's principle, you should assume that the adversary already knows the algorithm, and the only thing unknown are the secret keys – in your case, the passphrases.

Therefore, the adversary by definition knows that you are generating the brain wallet passphrases by $w_i = h( h(k_1 || i) || k_2)$ (where $h(x)$ is something like $Hex(SHA2(ASCII(x)))$. So the only things your attacker has to "reverse-engineer" are the two passphrases $k_1$ and $k_2$.

For now, SHA-2 is assumed to be preimage-resistant, which means that the best way of finding $k_1$ and $k_2$ is to simply guess them and see if the result matches any captured output (or, if there is no captured output, see if the result helps unlocking any of your wallets).

Generating different $w_i$ with the same passphrases does not significantly help the attacker to break it, but if he breaks one, also all the others are broken. The encoding (hex, ascii, anything else) doesn't matter for the security, too.

If your two passphrases are good (i.e. having more than 100 bits of entropy together), an attacker has little chance of successing with this brute-force.

If your passphrase is bad (and this includes all passwords with less than 10 characters, or longer ones which can be found in dictionaries), your derivation can be brute-forced easily. Also, if other users are using your scheme too, and by chance have the same password, they'll have the same $w_i$s, which might be usable by an attacker.

Your scheme could be made better by using a slow password hash, and including a salt input which is unique to you, like your email address. The output of this slow hash you can then process with the counter to get the actual $w_i$.

If the attacker has a key-logger and captures your passwords, everything is already lost.


What are the actual anonymity features of ZCash?

As a short answer, yes you can have a transaction that does not allow others to trace who the money was paid.

Zcash supports four kinds of transactions that are categorized as follows,

Public-address to Public-address (like as the ones in Bitcoin)
Public-address to Private-address (they call it shielded transactions)
Private-address to Public-address (they call it deshielded transactions)
Private-address to Private-address (they call it shielded pool transactions)

For transactions in Shielded Pool, origin, amount and destination are anonymous, but in deshielded or shielded transactions only one side is hidden. Recently there was an empirical analysis of anonymity in Zcash that has some very interesting result. I highlight some of them here,

Only 0.3% of Zcash transactions are done in shielded pools (the transactions that are completely anonymous) and only 14.96% of transactions do interact with shielded pools.
73.5% of Zcash users only use public transactions that already exist in Bitcoin and are shown to be linkable.
Only 25% of visible addresses have a non-zero balance, and more surprisingly the top 1% hold 78% of all Zcash coins (ZEC).
Founders of Zcash behavior with quite obvious patterns that make easy to trace their transactions. e. g. analysis show that 14 addresses of founders had been used regularly  to deposit coins to the pools.

You may read more details on https://arxiv.org/abs/1805.03180


Why do one-time pads not provide message authentication?

But, if you and I have a one-time symmetric key, and I send you a message, and it is not complete gibberish, is that itself not message authentication?

The informal criterion of "not complete gibberish" that you are applying here has two problems:

Malleability: It is trivial to modify OTP-encrypted ciphertexts so that they will decrypt to something that's unlikely to be "complete gibberish";
Computers are dumb: It assumes that the decrypted message is read by a human being possessed of common sense instead of acted upon by a dumb computer;

Malleability

This is the property many ciphers have that an attacker that doesn't know the key can nevertheless modify a ciphertext in such a way as to cause a predictable change in the plaintext it will decrypt to.  One-time pads and stream ciphers (the computationally secure variant thereof) are subject to one particularly trivial form of this:

If you flip any bit of a ciphertext, that causes the corresponding bit of the plaintext to flip.

This means that if I flip a bit in a ciphertext, the resulting fake plaintext will be minimally different from the real one. I hope you agree this means it's unlikely to be "gibberish."

In comments you've expressed skepticism that an attacker could exploit that to fool a recipient, because they'd have to know or guess a fair amount about the plaintext that corresponds to a the ciphertext.  But that's a condition that is often met in real life—for example we routinely encrypt network protocols and file formats that are publicly specified and such that an attacker can effectively guess the protocolar "skeleton" of encrypted messages.  And we don't want them to be able to exploit this to modify that skeleton.

Computers are dumb

The other problem is that the scenario you're implicitly contemplating—a human being, possessed of common sense, reading a single decrypted message—is not the norm by any means.  Most decrypted messages are acted upon by computers, slavishly literal and poorly programmed machines that will happily repeat the same humanly-absurd mistake billions of time per second with unintended consequences that nobody predicted.  We can't rely on some common-sense human notion of "gibberish" to reject forgeries—we need a fool-proof mechanical way of rejecting forgeries, one that not even a computer can goof up.

Example: EFail attack

One recent real-life example that combines these two motifs is the EFail attack on encrypted email.  It exploits:

Malleability: The attacker is able to modify an HTML emails' ciphertext to craft a forgery that decrypts to an HTML image tag with the original plaintext inside its URL;
Computers are dumb: Many email clients will obliviously decrypt that forged message and automatically make the HTTP request for the forged image tag before showing the plaintext to the user.

EFail is an attack against CBC-mode encryption, not stream ciphers or one-time pads, but cryptographers' general attitude to malleability is that it should not be allowed in practical systems, period.


Why are protocols often proven secure under the random oracle model instead of a hash assumption?

A random oracle is an idealization of a hash function $H$: if hash functions were perfect they would be random oracles. This is why it is always easier to consider a hash function a random oracle when one proves something about a larger scheme. Those are "proofs in the random oracle model". [1]

That being said it is still possible to prove things using different, weaker, assumptions about the hash function or even the compression function in the case of a MD hash function (collision resistance for example). Those are "proofs in the standard model"

Is it possible to go from one to the other? Not always since there are separations: there exists schemes that can be proven secure in the RO model that will become insecure as soon as you instanciate the RO by a real world hash function. [2]

Is it the end of the world? Not really, since we also have strong results that use the notion of Indifferentiability from RO: simply put, if your hash function is indifferentiable from a RO then you can replace your RO by your hash function and the scheme will remain secure. [3]

There are (as always) subtleties and what I've just said is not always true but this is good enough to make us feel more comfortable with our assumptions. [4]

Is this RO-indifferentiability just theoretical crypto stuff? No! I haven't checked for all of them but I know that Skein and Keccak 2 of the SHA-3 finalist come with proofs regarding that very property. I believe all of the finalist do. [5] [6]

[1] Random Oracle
[2] Impossibility result
[3] Indifferentiability framework
[4] Indifferentiability revisited
[5] Skein Proofs
[6] Sponge Proofs (keccak)

If you want you can start by reading the following:

http://en.wikipedia.org/wiki/Standard_model_%28cryptography%29
http://en.wikipedia.org/wiki/Random_oracle
http://blog.cryptographyengineering.com/2011/09/what-is-random-oracle-model-and-why.html


Ciphertext indistinguishability (IND-CPA) for symmetric cryptography

First off, your definition is not IND-CPA: In the IND-CPA setting, the adversary has access to an encryption oracle. As you have already determined, no deterministic encryption scheme can be IND-CPA secure. I don't think IND-CPA is widely used for symmetric encryption though (although I might be wrong), semantic security might be a better option. For public key schemes, this is the same thing, but for symmetric schemes, it is not.

Semantic security informally says that you can't derive any information from a ciphertext about the underlying plaintext. Formally (from Katz and Lindell: Introduction to Modern Cryptography):

A private-key encryption scheme is semantically secure if for every PPT (= probabilitsitc polynomial-time) algorithm $\mathcal A$ there exists a PPT algorithm $\mathcal A'$ such that for all efficiently sampleable distributions $X = (X_1, \dots)$ and for all polynomial-time computeable functions $f$ and $h$, there exists a negligible function $negl$ such that $\vert Pr[\mathcal A (1^n, Enc(k, m), h(m)) = f(m)] - Pr[\mathcal A'(1^n, h(m)) = f(m)]\vert \leq negl(n)$,
where $m$ is chosen according to distribution $X_n$  and the probabilities are taken over the choice of $m$ and the key $k$, and any random coins used by $\mathcal A$, $\mathcal A'$ and the encryption process.

If you look closely, you see that $\mathcal A$ has access to an encryption of $m$ where $\mathcal A'$ does not. The requirement is that this gives $\mathcal A$ no advantage, because for any function $f(m)$, the two do just as well.

Unfortunately, proving this kind of security is rather ugly, which is why (in public key cryptography, where both are the same) the IND-CPA notion is usually used. How to prove security for your scheme depends on your scheme, without further details, it will be hard for anyone to help you with that. The approach is generally to show something along the lines of "If an adversary $\mathcal A$ can break my system, I can construct an algorithm $\mathcal B$ (which calls up $\mathcal A$) that breaks problem $X$, but problem $X$ is considered hard". For example, ElGamal reduces to the decisional Diffie-Hellman problem this way, which is related to (and a stronger assumption than) the Discrete Log problem.


Remove padding (CBC) from decrypted text

First, you have to know what padding you are using. In the padding, you will find the padding length.

Second, you should set the padding type in the library.

Third, removing and validating and using padding is tricky and can lead to some padding oracle attacks. In essential, the attacker modifies a block, which is likely to result in wrong padding and a wrong message, but it might also result in a correct message. Attacker then observes if the message was accepted or not and makes some deduction.

To mitigate the padding oracle attack, the easiest way is using encrypt-then-MAC. As a result, any modified message is rejected and attacker can't observe differences between two garbled messages. (Probability of accepting a garbled message is negligible.)

These padding oracle attacks aren't theoretical. For example, SSL3 was killed by one of padding oracle attacks, i.e. POODLE.


Is there a method/protocol to validate a self-signed certificate by comparing a shortened hash?

TL;DR: Using words instead of strings / images may be a good solution for short, easy-to-verify codes and using locality / time dependent verification codes strengthens short hashes as would using password-hashes.
Additionally to the improvements to comparability of the hash proposed by A. Toumantsev, I will propose three extra measures which I believe may be more unconventional than his solution but will adapt to your situation in a better way.
The challenge you're facing
You need to reduce the output size so much that a user won't get tired comparing two outputs, making the comparison short and / or interesting is the obvious solution.
At the same time you need to ensure that the output is not too short, or an attacker will be able to brute-force keys with the same output and thus will be able to fool the user and accept a man-in-the-middle attack.
Improvement 1: Don't use images or QR-codes, use words!
Images tend to be difficult to compare properly and chances are that the user screws up the comparing process as much he can do with long number strings, in fact if the image is high-resolution it may actually prove more difficult to do a proper comparison.
Randomly selecting a word in the user's native language for each byte (or maybe two bytes) and showing the user a "sentence" consisting of 16-32 such words may actually be feasible for full comparison. This would then benefit from the Stapled Horse batteries effect and be easier to remember / check, much like passphrases are easier to remember than passwords.
Of course this only a suggestion and actual tests are required in order to find the most effective solution.
Improvement 2: Buy yourself strength by imposing time limitations
You are in the lucky situation that the parties wanting to verify each other's public key can communicate. This way you can randomize the verification process, because if an attacker found a key that passes your 64-bit test, he will probably fail your randomized test, so just let both devices exchange a random nonce and display the properly encoded $\operatorname{HMAC-SHA256}_{\text{Nonce}}(\text{PublicKey})$ for verification to the user. If you let this HMAC expire after an hour or so, you effectively only give an attacker that time amount for finding an appropriate second-preimage.
This trick with a 128-bit nonce would allow you to reduce the shown value's size to somewhere around 64-128 bit (less would slowly become dangerous again) while still maintaining strong security.
You may also want to give the user an option to mark a certificate / key as "verified" for this method.
Improvement 3: Password hashes
You can combine the above three methods with a password-hash that takes a few hundred milliseconds on your devices (using the nonce as the salt and the key as the password). This way an attacker has to spend a considerable amount of effort for each key generation, slowing down any brute-force attack attempts. With this method you can probably gain 10-20 "bits" of security without any problems, allowing you to shorten the displayed value even more.


Calculating DES key knowing message before and after encryption

A single p3.16xlarge EC2 instance is capable of evaluating $369\times10^9 \approx 2^{38}$ DES calls per second using hashcat.

This puts the maximum time to recover a key at around $2^{56} / 369\times10^9 / 3600 \approx 54$ hours. This costs a little over $1300 at current pricings.


For random systems of multivariate polynomial equations, the assumption that it is regular or semi-regular is generally accepted. Here "random" means with every coefficient being sampled uniformly. An open question in this field is to determine the probability of a random system being regular or semi-regular as a function of the number of variables, equations, and of the degree. This assumption implies that this probability is cryptographically negligible, but until that is proven it is technically an assumption.

Unfortunately, for systems of multivariate polynomial equations that are not random, we don't even have such an assumption, much less a rigorous framework supporting it. The best you can do is instantiate the system of equations for various small parameters and observe to what degree, if any, the empirical degree of regularity deviates from that of random systems with the same dimensions.

Having said that, there might be a couple of interesting sources for you in this vein:

Faugère and Perret study the complexity of a direct algebraic attack on UOV, and observe that the degree of regularity of the resulting system of polynomial equations equals that of random ones. This result has since been used to justify the stronger assumption that attacking UOV in this way is the same as solving random systems of equations, which enables complexity estimation and hence parameter selection. IACR ePrint
Ding et al. study the first fall degree, which is similar to but subtly different from the degree of regularity, of Square systems which are $\mathbb{F}_q$-affine equivalent to the monomial $\mathcal{X}^2 \in \mathbb{F}_{q^n}[\mathcal{X}]$ for some odd $q$. They conclude that this degree is exactly $q$. This is surprising, because generally we observe that the degree of regularity is independent of the field over which the equations are defined. Unfortunately, Square systems are insecure due to structural attacks that have nothing to do with Gröbner bases. ScienceDirect
Ding and various co-authors study the same first fall degree in the context of HFE$_v^-$ systems. They achieve upper bounds on the first fall degree (which they confusingly call the degree of regularity) as a function of the degree of the hidden polynomial, the number of vinegar variables added, and the number of polynomials dropped. Unfortunately, this upper bound is not tight and so it cannot be used to argue that a HFE-like system is probably secure. Springer Journal page Author home page


Can root and intermediate CAs use different asymmetric ciphers and key sizes?

For example, could a root CA use RSA-4096, one intermediate CA use
  RSA-2048, and another use ECDSA-256 (DH19)?

If you use the standard certificate verification algorithm described in RFC 5280 (section 6) that is no problem. Using that algorithm you have a working_public_key_algorithm, working_public_key and working_public_key_parameters which get updated as the as the certificate path is being processed (always after the current certificate was processed) and they're initialized with the root algorithm / public key / parameters.

However, practically you will rarely find ECDSA certificates issued below RSA roots and RSA certificates issued below ECDSA roots. Apparently this is mostly for historical reasons as clients used to indicate what they support (RSA vs ECDSA) using their TLS cipher suite, ie when it contains *RSA_* they only support RSA-based certificates (which needs pure chains obviously) and analogously for ECDSA.


How to take SHA-1 safely for my particular case?

The main difference between your two algorithms is that the second one takes longer because of your additional hashing of the "public key". Also, by the truncation of this hash to 3 characters (are this bytes, hex digits, base64 digits?) could lead to collisions of different public keys to the same hash, which is much more unlikely to occur if you use the full hash.

The same kind of collision is possible after your "main" hash, don't do any truncation before the final one, please.

The general problem with such password hashing schemes is that, given the output and the "public key" (this is usually called "salt"), it is possible to brute-force the "secret key", if there are not many possible values for it. A five-character password is not enough by any measure.

But even with a "good" password, good practice is to not use a fast hash function like SHA-1 (or some small number of iterations of it), but a slow one. (Using some repetitions is a good start, but you normally want to input the secret again in each iteration, to avoid collisions of different secrets.)

Have a look at What makes a hash function good for password hashing? for details and some example functions.


Why perfectly secrecy needs the key space to be as large as the message space?

how does that violate the definition (1) ?

Let's assume $|K|<|M|$. Then there exist $c\in C$ and $m\in M$ such that for all $k\in K$, you cannot get $c=E_k(m)$ ($c$ encrypts $m$ under the key $k$).

Now expand the conditional probability of your definition (1):
$$\Pr[M=m|C=c]=\frac{\Pr[M=m\;\&\;C=c]}{\Pr[C=c]}$$
but since $|K|<|M|$, we already have a pair $(m,c)$ that you cannot get under any encryption key, therefore $\Pr[M=m\;\&\;C=c]=0$. Your definition is violated.

You could get to the same conclusion by using entropy -- to get perfect secrecy (i.e. no information about the plaintext is yielded from the ciphertext), entropy of the key space must be at least as big as the message space entropy.


I don't know of any scheme that provides this, and it sounds tricky to build one.

Here's the closest I can come up with.  Let $n=pq$ be a 2048-bit RSA modulus, $d$ be a random 2048-bit number that is relatively prime to $(p-1)(q-1)$, and $e = d^{-1} \bmod (p-1)(q-1)$.  The master secret is $d$; $n$ will be baked into the description of the encryption algorithm $E$.  Let $\text{truncate}(z)$ be the result of truncating $z$ to 128 bits: say, deleting the low 1920 bits and keeping the high 128 bits.  Then, define $$E_k(x) = AES(\text{truncate}(k^e \bmod n), x),$$
and similarly for $D_k(x)$.  In other words, the key $k$ is a 2048-bit string.  To encrypt under $k$, we raise the key $k$ to the power $e$ modulo $n$ (a textbook-RSA encryption of $k$), keep the first 128 bits, and use that as an AES key to encrypt the message $x$.

Given a key $k$ and knowledge of the master secret, it is easy to derive many other keys that will be equivalent (just tweak the low bits of $k^e \bmod n$ randomly, then raise that to the $d$th power modulo $n$, and you've got an equivalent key).

This satisfies your requirements 1-4, but not requirement 5.  Why do you need your requirement 5?  I wonder if we might be able to weaken the requirement somehow and still get something that is sufficient for your application.


How do digital certificates work, and why is it not possible to reverse engineer one from a signed file?

Such certificates are basically just an implementation of digital signatures. One certificate is used to sign the data using a private key, and a corresponding verification certificate is given to the user along with the signature and the data. The user uses the verification certificate to verify that the file matches its signature.

You can't reverse engineer the signing certificate from the verification certificate because of the cryptographic properties of public/private keys. Whatever signing algorithm they are using, the private key should be underivable from the public key. Exactly why this is difficult (or at least believed to be difficult) depends on the exact algorithm being used, but as a general rule they all have this property.

An example situation, for a made-up app store/market system:

Developer creates an account in a market place through the Market Owner and gives the Market Owner a copy of their public certificate.
Developer signs an app with their private certificate and gives the app, signature, and public certificate to Market Owner.
Market Owner verifies that the certificate matches the one for Developer on their records.
Market Owner verifies that the signature of the app is valid using the public certificate.
Market strips off the signature and certificate from the app.
Market signs the app using their own private certificate and puts the signature and public certificate in the app.
Anyone who downloads the app verifies that the public certificate matches their device's local copy (it may have a built-in copy of said certificate) and they verify the app's signature from the Market Owner's public certificate.

There are a lot of variations and complexities that arise. What happens when a certificate is compromised, how to you revoke it? What if the user loses his certificate? What if the Market Owner wants to use multiple certificates? What about certificate expiry dates? Etc. But that's a general model for how the this kind of system could work using certificates.


Triple-DES DUKPT CBC PIN variant vs Data variant

BDK and KSN are used to derive a transaction key which is unique for that session. The are unique because KSN is updated after each transaction. Once this key is derived you apply different variants to get PIN, Data or MAC key.

For the PIN and MAC key: these variants are simply XORed with derived key. One more encryption is performed to calculate the data encryption key after applying variant.

These variants are fixed; you can refer to X9.24 Retail Financial Services Symmetric Key Management for more information.


SHA-1:Is there any mathematical result that gives us the minimum number of 1's in a 160-bit SHA-1 hash output?

No, theoretically a SHA1 hash can be any 160-bit value, including the string of 160 zeroes.

As for your second question, if we fudge a little bit and consider SHA1 a truly random function this becomes the same question as the following:

If we flip 160 coins, what is the probability that at least 128 of them will be heads?

Solution is left as an exercise to the reader; I suspect this might be a homework question.


64 bit clock cipher with CFB mode. One-byte defected from ciphertext. What is the number of bits defected from plaintext

The decryption of CFB mode as follows;

$$ P_i = E_k(C_{i-1}) \oplus C_i$$
$$C_0= \operatorname{IV}$$

Bit flipping attack in CFB

If there is a Bit Flipping attack in the ciphertext then we have two cases.

$\color{red}{\textbf{Red case:}}$ The last ciphertext bit is flipped. This only affects the corresponding plaintext block. So the attacker can change a plaintext bit without affecting any other bits.

$\color{ForestGreen}{\textbf{Green case:}}$ Assuming that the $i$th ciphertext bit is changed, $ 0 \leq i < n$ where $n$ is the total number of blocks, then this time two plaintexts blocks are affected. We can also see from the equations, too;

$$ P_i = E_k(C_{i-1}) \oplus \color{blue}{C_i}$$
$$ P_{i+1} = E_k(\color{blue}{C_{i}}) \oplus C_{i+1}$$

Note: Bit flipping on IV of CFB mode has no good effect as in CBC mode.

Your question

Since you have 100 Bytes, and 64-bit block cipher has 8-byte block size, the 12th-byte number falls into the second ciphertext. If it falls into the last one then only one byte is effected, $\color{red}{\textbf{red case}}$.

Now, since we are in the $\color{ForestGreen}{\textbf{green case}}$, for a defected one-byte $C_i$, we will see two plaintexts are effected $P_i$ and $P_{i+1}$. $P_i$ has one byte defection and $P_{i+1}$ has full block defection.

Fgrieu gave the probabilities of the defection in the comments. As noted, the defection is not clear about how many bits are flipped. It may be 1 or 8. Also, the affected full block is not under control. For example, if we assume that the cipher has avalanche criteria we expect each of the ciphertext bits has 50% probability to have a flip. Therefore we can say it is between 1 and 64. So the total number of affected bits is between 2 to 72.

Let finish this with mitigations:

The attack/defection is possible since there is no integrity on the data. A MAC or an HMAC can be used to prevent, or better use authenticated encryption which provides confidentiality, integrity, and authenticity. In TLS 1.3., CCM and GCM are standardized authenticated encryption modes.


Advantages and disadvantages of hash-based signatures

This table—of Ed25519 vs. the lattice-based post-quantum candidate Dilithium vs. SPHINCS+ variants at a comparable post-quantum security level, with a tradeoff between signature size and signing time—may help explain:

\begin{equation*}
\begin{array}{r|rr|rr|rr}
\text{sig scheme} && \text{sig bytes} && \text{cycles to sign} \\
\hline
\text{ed25519}
  & \times1= & 64
  & \times1= & 45\,400 \\
\text{dilithium3}
  & \times42= & 2\,701
  & \times101= & 4\,600\,060 \\
\text{sphincss192sha256simple}
  & \times266= & 17\,064
  & \times46\,000= & 2\,105\,269\,820 \\
\text{sphincsf192sha256simple}
  & \times557= & 35\,664
  & \times1\,850= & 84\,025\,740
\end{array}
\end{equation*}

Median cycle counts taken from SUPERCOP measurements on a 2019 AMD EPYC 7702 with 64 x 2000MHz cores; see the full results https://bench.cr.yp.to/results-sign.html for more details, comparisons on different machines, and additional signature schemes.

Although hash-based signatures are reasonably well-understood and based on conservative design principles, they are thousands of times costlier than the modern standard for signatures secure against a classical adversary, the elliptic-curve signature scheme Ed25519, and hundreds of times larger.  (That said, the verification costs of SPHINCS+ aren't quite so bad.)

The stateful signature scheme XMSS has been deployed in OpenSSH, which is a little silly because (a) stateful signatures are a serious foot-gun for operators, and (b) there's no need to deploy post-quantum online authentication mechanisms for a long time—it is only important to deploy them once quantum computers are becoming a serious threat so that future sessions cannot be forged by a quantum adversary.

(In contrast, post-quantum encryption and post-quantum key agreement are important to deploy as soon as possible—and OpenSSH is experimenting with that too—to prevent a future quantum computer from retroactively decrypting past sessions.)


What happens when a RC4 stream gets corrupted?

If a large file enciphered using RC4 is partially corrupted, the uncorrupted portions remains fully decipherable, including what's after a corrupted portion if the corruption modifies this data's value, but not its length (a length corruption could occur e.g. for serial communication, but is unlikely on a hard disk). This is a property of all stream ciphers.

An exception is when there's an IV somewhat combined with the key to form the full key input of RC4, and this IV is corrupted; then the whole file is undecipherable, essentially as if the key was lost.

Another practical exception is if the deciphering program somewhat stops when encountering a corrupted disk block, or gets the keystream out of sync with the ciphertext in this situation (which is not unseen!); to recover from this without fixing the program, the corrupted file can first be copied to a good media, with the corrupted blocks replaced by arbitrary data (rather then removed).

Finally, the deciphering program could include a provision to check file integrity, and refuse to output the plaintext if it is corrupted; in that case, this deciphering program needs a change to skip this check.


Is there a reason to use multiple hashing algorithms in a single system?

A protocol might rely on using some string $x$ as an index into a set of uniform random bit strings $H(x)$.  The security of the protocol may rely on the $H(x)$ being uniform random and independent for different $x$.

A complex protocol may rely on having multiple independent uniform random bit strings for any particular string $x$, used for different purposes in the protocol.  If you use the same $H(x)$ for both purposes, the security may evaporate.

Here's an example: A deduplicating encrypted storage scheme like Tahoe-LAFS needs to derive an encryption key for each file it stores, and needs to choose a storage index that depends only on the content.  Using a single hash function for both—$H(x)$ as the encryption key, and $H(x)$ as the storage index—is a fatal mistake: a malicious storage server can now decrypt every file you store on it.  But using two different hash functions prevents this: knowledge of the storage index $H_1(x)$ doesn't help to find the encryption key $H_0(x)$.

In practical terms, we implement $H_0$ and $H_1$ in terms of a single hash function with a specially formatted input for ‘domain separation’: $H_n(x) := H(n \mathbin\| x)$, where $n$ is some prefix-free encoding of an integer as a bit string—say the 32-bit little-endian encoding.


Using hash functions for Key Check Values (KCV)

To answer this question, the first thing is consider is "why do we have a key check value at all?  What benefit do we hope to gain from it?"

From my perspective, it would appear that the main use of a KCV is to quickly catch it when we attempt to decrypt a message with the wrong key.  This implies:

It makes sense only if attempting to decrypt the message with the wrong key is a plausible occurance.  The main case where this makes sense is if you are assuming the user will manually enter the key or the seed to generate the key (and might typo it).
It makes sense only if it is necessary for you to quickly detect an incorrect key.  Normally, we strongly suggest that when you encrypt, you include some sort of integrity check (as there are a number of clever methods known where an attacker modifies the ciphertext, and learns something from how the decryptor reacts when it decrypts it); if you enter the wrong key, presumably the integrity check would fail, and you'd notice that the key is wrong.  So, the only real value a KCV would bring is that you can determine whether the key is correct quickly (before decrypting the potentially large file).

Now, if the key is low entropy (which a manually entered key or key seed would be), a KCV would make it easier on the attacker to do a brute force search; instead of decrypting the entire file and seeing if it works, he could just check the KCV, and reject most of the incorrect entries in the database.  You could try to slow him down by using, say, Argon2 to generate the KCV, however that'd void the entire reason you have a KCV in the first place.

With that background in mind, lets go over your questions:

  Would it be relevant to compute a hash over the key and to consider the $n$th first bytes

If you actually need a KCV (see above for why it is only occasionally appropriate), then this would work (assuming, of course, that you don't use the hash of the key for anything else; if you do, you'll run into exactly the same issues that Maarten warned you about).  So, yes, this could introduce a weakness, if (for example) you are using $SHA-2(password)$ to encrypt the first several bytes of your file.

And, for a block cipher, encrypting a block of all 0's, and using a few bytes from that, would work as long as the cipher block mode you use doesn't rely on the encryption of the all 0's block; for example, counter mode standard at a random nonzero counter would work; also CBC mode with a random IV would also work.

General rule: if you use the password in multiple ways, you need to consider that those multiple ways play nicely together, and the one usage doesn't leak information that the other usage needs to keep secret.

  there is no equivalence for private keys used for asymmetric cryptography

Actually, if you don't mind leaking who you're encrypting the message to (in my experience, you usually don't; if I email an encrypted message with Alice with Alice's public key, well, Alice's email address will appear in the SMTP header), then it's easy; just hash the public key and that's the KCV.  Alice knows her own public key, and so should be able to recognize the hash of it (and reject any encrypted message with a different hash).


How can I share a number with an opponent?

Throw away the key lists and generate a fresh key every time you want to transmit a message. Use a key exchange algorithm like for example Diffie-Hellman.

If an enemy can steal your keys they are pretty much useless. You would have to notice the theft and replace all your keys with new ones. Asymmetric encryption like RSA won't help you here because as with symmetric keys the private key could be stolen. There's not much left you can do now, except for a key exchange algorithm. With that you create a new key every time you want to send a message to your friend. Beware that this won't help you against active attackers which can intercept and replace the communication between you two. It also needs direct responses from the other person to create a key, so you can't send him a new message when he's offline.


Here it helps to understand the history, internals and rationale for HMAC and Merkle-Damgård hash functions in a bit more depth.  In the M-D construction, the IV is used as the chaining argument to the compression function when processing the first block of the message.  What you are proposing to do is to put that IV value under user control, so that users may plug in a secret key instead.

The point of the HMAC construction is to achieve the functional equivalent of that indirectly, by prepending a block with the key (XOR'ed with a pad) before processing the message.  The hash function's fixed IV and the secret key block will be fed to the compression function, producing a new state that, from your point of view, you can think of as a derived secret key that then serves as the chaining value to hash the rest of the message.  When HMAC starts processing the actual message, the state of the hash function is the same as if you'd fed that derived secret key to the hash function as a user-selected IV.

In fact, if you look at the original HMAC papers, you'll notice that HMAC's security is analyzed in terms of something called NMAC, which is a construction using hash functions with user-controlled IVs.  HMAC is a practical improvement over NMAC with these advantages:

When HMAC was invented (and still today!), there were lots of legacy code bases and libraries that did not allow user control of the hash functions' IVs.  Therefore, HMAC can be implemented without modifying legacy libraries.
Allowing the user of the hash function to control the IV would, more likely than not, lead to people abusing it by supplying a secret key as IV and expecting it to behave like a secure MAC, leaving them vulnerable to even more length extension vulnerabilities.  A cryptographic API really should guard against misuse, and offer a secret-key MACs and public hash functions as different interfaces that accept different arguments.
NMAC requires two separate keys, one for the inner hash function and one for the outer.  HMAC uses just one user-supplied key to internally derive the two NMAC keys (that's what the ipad and opad values are used for).


How to use Real-Ideal model in a specific scenario (two party with cloud)

In this protocol, how should I use the real / ideal model paradigm to prove the protocol's security?

This question is too vague. Security in the real-ideal paradigm is defined as "for every adversary, there exists a simulator, such that the views are indistinguishable." So you have to do that.

  Should I consider the cloud as a party who does not have any input and output?

It receives/sends messages in the protocol, so you must do this.

  Can I consider the following cases for the security proof of this protocol like this?

Yes, but if these are the only cases you consider, then you are only proving security against a single corruption. In an $n$-party protocol, generally you would want to consider all cases of $n-1$ corrupt parties.

Your protocol is probably not secure against an adversary who corrupts both Alice & the cloud. I am inferring from your description that Alice has the decryption key to the encryption scheme, so when colluding with the cloud she can get Bob's input in the clear.

  For case c in quesetion 3, how should the simulator simulate? The cloud will only see the encrypted data?

The view of the cloud consists of the ciphertexts from the parties. You have to construct a simulator which generates something indistinguishable, given only the party's output from the functionality (this is the requirement for semi-honest security). In this case, I guess the cloud party gets no output from the functionality. So, given no information about the honest party's inputs, can you generate something that looks like encryptions of their inputs? Sure, just encrypt dummy stuff and use CPA security to argue that this simulation is indistinguishable.


Why use a timestamp and how can someone know it's the correct one?

Actually, I guess that you are talking about digital signatures and not about public key encryption (since you want to have message authenticity and not confidentiality).

Whether using time-stamps or not makes sense depends on your application. Basically, the idea is that the verifier can determine when the signature has been issued and in particular that the message existed before some particular point in time.

However, with your above mentioned approach, a verifier can not really be sure, since the signer ($A$) may include an arbitrary time-stamp (this does not necessarily be the correct one and could be "back dated"). Whether this is really a problem, again, depends on your application.

In order to tackle the above mentioned problem with "back dating" and thus to ensure that the message is correctly dated there are so called trusted time-stamping approaches.

If $A$ uses trusted time-stamping based on digital signatures then basically $A$ lets a trusted third party (TSA - time-stamping authority) sign the message along with a time-stamp ($A$ only needs to send the hash value of the message not the message itself, if $A$ does not want to reveal the message) and then $A$ signs the time-stamp+signature from TTP+message with $A$'s own private signing key. Now, everyone in possession of $A$'s authentic public key and trusts the TSA can be sure that the message existed before the time-stamp.

You may also look here for a more detailed discussion on time-stamping.


Would possessing a string with the SHA-256 hash of all zeros lead to an attack on SHA-256?

Would possessing a string with the sha-256 hash of all zero bits lead to an attack on sha-256?

No, it would not lead to any useful attack on SHA-256. You’ld only have an input string that hashes to 256 zero-bit output. It may be nice to know and look at, but it doesn’t buy you anything useful to attack SHA-256. All in all, it’s no different from any other hash value produced by hashing some value to another specific SHA-256 output. Just because your input renders an SHA-256 output of 256 zero-bits doesn’t mean, nor indicate that SHA-256 is broken and it certainly doesn’t open an attack vector on SHA-256.

  I could easily imagine that a specialized attack leaked knowledge of how to do it,

At the time of writing this, no such attack is known. Remember that SHA-256 has been around for a few years. The algorithm has been tested, analysed, attacked, and verified by governmental agencies as well as independant people worldwide. If there would be any weakness/shortcut in the algorithm which would enable someone to produce a 256 zero-bit hash, it would have been found. But no such findings have been made… which is why we all SHA-256 a “well vetted, cryptographically secure hash”.

Besides, being able to say “I have this set of bytes that, when I feed it to SHA-256, outputs an all-zero hash” doesn’t open any door to a cryptographical attack. It’s no different from knowing that “hello world” hashes to “b94d27b9934d3e08a52e52d7da7dabfac484efe37a5380ee9088f7ace2efcde9”.

Having knowledge of something like that doesn’t point at a weakness or attack vector. It’s what SHA-256 does: hash a specific input into a specific output. If that output happens to be 000…000 then so be it. It may be nice for some people to know how to produce a 256 zero-bit output, but it doesn‘t have any impact whatsoever on the security claims of SHA-256.

Things would be different if some weakness in the algorithm was found which would enable us to produce any specific, chosen output we like… eg: 256 one-bits (FFF…FFF) or another series of 256 output bits (123…321). Even more interesting would be finding a way to produce collisions for SHA-256 (where two different inputs produce the same output), which would be disasterous. But all that isn’t the case. No such weaknesses have been found over the years.

  but I could equally imagine that a bitcoin miner randomed onto one.

I honestly doubt that any bitcoin miner will produce anything that has any influence on SHA-256 just by hunting down the next Bitcoin block. Even if a Bitcoin miner would happen to find a 256 zero-bit output, it wouldn’t gain you anything as it’s still like the “hello world” hash example I mentioned above. Knowing which input bytes produce an SHA-256 output of 256 zero-bit hash doesn’t buy you anything which could be used as an attack… not even a coffee.

Some distantly related Q&As which might (or might not) be interesting for further reading:

What are the time considerations with regard to security against birthday attack?
Computational requirements for breaking SHA-256?
Are there any well-known examples of SHA-256 collisions?
Cryptocurrency serving as hash breaking?


When doing an implementation based on tables, yes, it is customary to hardcode the table. Some extra notes:

Usual table-based implementations of AES merge the S-box application step ("SubBytes") with the subsequent linear operation ("MixColumns"). In that case, the hardcoded table has 256 entries of 32 bits each (and some implementations use four distinct tables to merge "ShiftRows" as well, in order to avoid computing rotations).
In some languages where there is an explicit initialization step, such as Java or C#, it is customary to use it to recompute the tables instead of hardcoding them; this makes the source code clearer and the binary size smaller, at the expense of some extra CPU cost when first using the code in the application. You can find an example of that in BoarSSL, a C# SSL library (used to serve as test system for BearSSL, which is written in C); the table building is done in the static class initialization code (lines 326 to 430).

Not all AES implementations are based on tables, though. In fact, using lookup tables is problematic because of cache attacks (memory accesses at addresses that depend on secret data may leak information based on how memory caches in the CPU are impacted). "Constant-time" implementations avoid making such accesses, and instead will evaluate the S-box with non-table operations. For these, the algebraic structure of the S-box definition is very convenient, because it helps making a more efficient circuit. In 2009, Boyar and Peralta have worked out a nice circuit of boolean gates that evaluates the AES S-box in 115 boolean operations; it has been used in a bitslice context by Käsper and Schwabe to make a very efficient and constant-time implementation of AES (in CTR mode): their code is not only robust against cache attacks, but it is also about twice faster than classic AES implementations that use tables.

For more information on constant-time cryptographic implementations, see this page.


How does gpg know what cipher algorithm is needed for decryption?

how does gpg know which cipher is needed (in this case AES256 instead of the default CAST5?

The OpenPGP Symmetric-Key Encrypted Session Key Packet (RFC 4880, §5.3) says which algorithm.

  wouldn't it be "better" to not tell anyone what encryption type was used?

Not really.  This is a basic premise of essentially all serious cryptography for more than a century starting with Auguste Kerckhoffs in the 1880s: a cryptosystem should remain secure as long as the key is secret, even if everything about the method is known to the adversary.

The standard security goal for an unauthenticated cipher is IND-CPA, short for ciphertext indistinguishability under chosen-plaintext attack, meaning essentially that an adversary can't tell the ciphertexts of two distinct messages apart—even if they can choose the two messages, and even after studying the ciphertexts of any other messages of their choice.

Consequently, e.g., an adversary can't learn anything about the content of an email you've exchanged.  But they can still look at the email header, which tends to have a lot more information about your conversation (including who you were corresponding with, which can be extremely juicy information!) anyway than which algorithm GnuPG chose to encrypt it with.

If you wanted to conceal whether there is a message at all in some other stream, as in steganography, then you might want to avoid identifying information like this.  But that's not the setting that OpenPGP was designed for, and that's much costlier to implement.


All communications between the authentication service and the client, as well as between the client and the application service are done over HTTPS.

So at least the servers are authenticated to the client, and the communication channels are private.

This is not really an authentication problem. What you have is a capability-based access control while the license (and the token) serves as a capability list to authorise the user's operations. Your goal (I guess) is that only users who possess a valid license can access the application. The server's token is MAC protected so integrity should hold (assuming good a MAC scheme is used and good key management). The application server can be sure the token was generated by the authentication server, and not long ago (timestamp).

The first problem is whether the client needs to prove it possesses the license. Presenting the license number is not enough for this, because the number is a string which can be stolen or even simply enumerated. If you need a proof of possessing, need the license needs to be linked to some verifiable secret only known to the owner e.g. a secret key, a password. This is similar to when spending bitcoin you need a private key for the account. In bitcoin, the account number is equivalent to license number in your case, and a signature verifiable using the public key associated with the account number is the proof of possession. If you don't care and anyone who has the license number can use your service, then this is not a problem and you have the next problem.

The next problem is to prevent multiple users from sharing one license. This is similar to the double spending problem in e-cash, and in your case it can be solved easily since you have a centralised system. For example, when issuing a token, the authentication server can keep a record of the license number and the token expiration time. If a user comes with a license number that already has a token issued and the token hasn't expired, then the server can reject issuing a new token. The application server can also link tokens to sessions to ensure each token can initialise only one session. Of course, there are practical issues like the user may lose his token because the computer is shut down unexpectedly etc., and the full solution needs to cover those.


Clifford Cocks Interview: "Raising numbers to a power with the product as modulus"

I'll give a brief and simple example of what is described in the quote, which is now known as RSA for which there are plenty of descriptions and tutorials for all levels of understanding as pointed out by yyyyyyy.

  ... so I thought of the product of two primes ...

So, for our example this will be $p=21$ and $q=23$ of which the product is $n=21\times 23=483$. Note that you'll find it easy to multiply the two numbers to find $483$, but will have a rather hard time to find the factors of $483$, only given a calculator or pen and paper, for real-world encryption the primes will be around $10^{300}$.

  ... raising numbers to a power with the product as modulus...

For our example let's pick the exponent $e=17$, which is also sometimes used in the real-world. As our example message, let's pick $m=131$. You'd now raise $m$ to the power $e$ modulo $n$ ($=m^e\bmod n$). In our example this would mean calculating $131^{17}=985398793384554108247251712700460611$ (using a calculator or a math program may be useful here). Next, you'd apply the modulo operation which is taking the remainder of division with remainder. In our example this would mean calculating $985398793384554108247251712700460611\bmod 483$ which is $395$ -- your result -- as $395 + 483 \times 2040163133301354261381473525259752=985398793384554108247251712700460611$.

That's it what he actually described in his quote, I'll add the decryption procedure below.

For decryption you must find an integer $d$ such that $(e\times d) \bmod{((p-1)\times(q-1))} = 1$ (also commonly notated as $ed\equiv 1\pmod{\varphi(n)}$). Normally you use the extended euclidean algorithm to find this value efficiently. In our example $d=233$, which you can use as the exponent to which you need to raise the ciphertext in order to retrieve the original message. So you'd calculate $c^d\bmod n=395^{233}\bmod n=131$ (don't bother calculating $395^{233}$, it's over 500 digits long) and get $131$ as expected.


How would I encode RSA private key, given that I know the decimal representation of all of its components?

A commonly used way to encode RSA keys is DER which derives semantic meaning via ASN.1. You can find more detail in RFC3447. The ASN.1 syntax for a DER-encoded string looks as follows:

  Version ::= INTEGER { two-prime(0), multi(1) }
      (CONSTRAINED BY
      {-- version must be multi if otherPrimeInfos present --})

  RSAPrivateKey ::= SEQUENCE {
      version           Version,
      modulus           INTEGER,  -- n
      publicExponent    INTEGER,  -- e
      privateExponent   INTEGER,  -- d
      prime1            INTEGER,  -- p
      prime2            INTEGER,  -- q
      exponent1         INTEGER,  -- d mod (p-1)
      exponent2         INTEGER,  -- d mod (q-1)
      coefficient       INTEGER,  -- (inverse of q) mod p
      otherPrimeInfos   OtherPrimeInfos OPTIONAL
  }

A sample private-key using the encoding and syntax above would look as follows:

-----BEGIN RSA PRIVATE KEY-----
MIGGAgEAAhkAr6M0MwwZb+PmNOex7pFe5IDLe+eKEhazAgMBAAECGBpkc9uX3dqq
bFVW224yqOR0m8LyV+x2wQINANs9bxnc7ZdljRmlHwINAM0WMid0p2sbmMOn7QIN
AMocs4yTOFFG5DJNHwIMOLmt76ndcMu2Sk/VAgwpTp5DBMk2FLZKfaY=
-----END RSA PRIVATE KEY-----

Final note: You've posted your private key online ... which means that you shouldn't use it anymore.


Is it possible to multiplex TLS connections by SNI metadata without knowing any keys?

is it possible with TLS, if the P does not know any of the keys?

Sure. SNI is part of the ClientHello message extensions, which is the first TLS message the client sends. At this point you do not yet have key material on the client side to encrypt this in all cases and even for session resumption, SNI is usually included to tell the server which old key material to use.
Though it may be that this setup breaks in the future if and when encrypted SNI (currently only a draft standard) is enforced.
A (rather minimal) example implementation of such a multiplexer is the dedicated slt package, but this functionality should be achievable with most standard reverse proxy setups, e.g. Apache.


Why does a Hashing Function produce good Random Numbers if Input is random?

I mostly agree with your statements.
To answer your questions:

Obviously the entropy reduces if the entropy of $s$ is greater than $2^n$. Using a good hash will however result in that maximum amount of entropy.
Indeed, SHA-1 is not a random oracle. It is a common assumption that a hash function acts like one. Since collisions for SHA-1 have now been practically found that assumption is clearly wrong. The practically used primitives, like compression functions and block ciphers, are thoroughly cryptanalyzed but not proven secure.


privacy enhancing techniques on image data

I think what you are looking for is "Perceptual Hashing".

What I understand from your question is that you need a way for programmatically identifying images even when they have been manipulated beyond human recognition.

Their is a Microsoft project called PhotoDNA. I believe the have a cloud API.

You may also want to look at this Python example


Generating child keys for a hill climb algorithm

My experience is that hill climbing is very efficient for solving substitution ciphers. As I understand there are two topics now.

How to generate the child keysSwapping characters of the key randomly (stochastic hill climbing) as well as trying all possible swap combinations is reasonable.  But for solving a substitution cipher I believe trying all possible character swaps per parent is more efficient. First, trying the same key more than once is avoided (at least for one parent), secondly it provides a clear condition when to stop the hill climbing: If none of the childs provide a better result than the parent.  Using the stochastic hill climbing and keeping track of the tried keys would be overkill, and I think effectively it turns this into trying all possible key swaps.
How to avoid a local maximumOne option is to use the Random-restart hill climbing (or Shotgun hill climbing, see http://en.wikipedia.org/wiki/Hill_climbing#Variants). It simply repeats the hill climbing using different random initial conditions and it works very well for breaking substitution ciphers.

Resources:

http://www.guballa.de/crypto/substitution.html
A substitution cipher solver, using the Random-restart hill climbing algorithm choosing always the first better key (called "simple hill climbing"). It uses Javascript Webworkers, so it will not run on some older browsers.
http://www.guballa.de/crypto/substitution_breaker.js
The related Javascript implementation


How can you tell the type of encoding being used?

That looks like bcrypt.

There are four parts:

$2y - identifier that this is bcrypt in modular crypt format.
$05 - number of key expansion rounds: in this case, it is 25
68LWs...X/e - this is the salt. A total of 128 bits encoded in base64.
lfa1z...MwW - this is the hash. A total of 184 bits encoded in base64.

Since base64 encodes three bytes to four base64 characters, you get 6 bits for each base64 character.


How does BLAKE2 ensure that hash(A) != hash(B) when B = A||0 and both A & B have the same number of blocks?

You are right that the padded message by itself is ambiguous.

But the Blake2 compression function does not just take the message block and the chaining value as input. It also takes a finalization flag (to mark the last block and prevent length extensions) and the message size in bytes.

Passing the size to the non final blocks mainly serves to prevent certain multi target attacks. For these blocks the size is always a multiple of the block size. For the final block it's different: Here the size parameter is the total size of the message in bytes and it disambiguates messages which map to the same zero padded message and only differ in size. The flag ensures that compressing a message which ends at the end of the current block, and a message which continues (and thus has the same size argument) have different inputs.

Beyond the specification, which Nova already quoted, it might also be interesting to read:

The Skein specification, which uses a similar approach where the tweak contains the length of the message and which inspired the Blake2 padding.
My blog post Alternative Blake Padding where I propose a simplified padding, which with some minor tweaks turned into the Blake2 padding.


How does Google's “authenticator number generator” work?

I found the accepted answer above a bit unhelpful -- it basically just says: "read these two RFCs".  So, on the theory that the quickest way to get the right answer to a question on the Internet is to provide a wrong one, and wait a few New York Minutes until someone corrects you, here's my attempt at a summary overview answer, based on a laughably cursory examination of the Wikipedia entry and the two RFCs.

basically your phone and the server app start by agreeing on a secret key, which they both know.  that happens just once, when you set up the app on authenticator.

From there on in, the number that's generated every 30 seconds is based on SHA-1 hashing the secret key with the current time (in the form of a unix timestamp, rounded down to 30 seconds).

So, tl;dr: it's a hash of a shared secret with the current unix timestamp.

Or is it? Corrections welcomed...


Extractor for Oblivious Transfer Protocol

The paper is about garbled-circuit-based ZK protocol, in which the verifier generates the garbled circuit, and the prover obtains the wire labels corresponding to his private input $x_0$ through COT (committed OT).

The simulation in your problem works by letting the simulator simulate the ideal functionality of COT, which is defined in Fig. 1 on page 4. Here the receiver is the prover. Now the prover needs to invoke the COT ideal functionality by sending $(choose,b_i)$ to the ideal functionality where $b_i\in \{0,1\}$ is the $i$-th bit in the prover's input $x_0$. Since this ideal functionality is simulated by the simulator, the simulator gets all $b_i$ thus "extracts" the prover's input $x_0$.


Why is the server's public key always used in SSL encryption and never the client's public key?

Why is the server's public key always used in SSL encryption ...
  ... why do we not use the client's public key in SSL encryption instead of using the server's public key?

Neither the servers nor the clients public key is used for encrypting application data.

The servers public key is only used for encrypting the premaster secret during the obsolete RSA key exchange. And this is done since this way the server gets implicitly authenticated because only the server can decrypt the encrypted premaster secret using its (the servers) private key. And proper authentication of the server is essential to protect against active man in the middle attacks.

Apart from that there usually isn't even a client key involved in TLS. A client key is only involved when mutual authentication is done, i.e. when the client is required to authenticate against the server using a client certificate. Thus, in most cases the client does not even have a key.


Rolling Hash function over untrusted data: how to preserve statistical splitting properties?

There are absolutely functions like this but no such function, regardless of its properties, can solve your problem. They depend on the adversary not knowing the secret value used for deciding where to mark the stream. For efficient rolling HMACs, the attacker has almost full control of the output if they know the key.
how to build a secure rolling HMAC
Performance is 1/16th that of AES encryption because one full block is encrypted for every input byte. The universal hash is trivial in comparison and not a bottleneck.
An attacker with the key can produce streams with arbitrary function outputs limited by the number of bits they are putting into the window. Putting in 16 bytes gives them (almost) full control of the output of the universal function and resulting AES encrypted output value.
This is true regardless of the function you use. If the attacker has the keys they can set the splitting properties of the stream arbitrarily. It's only a question of computing cost.
That's why most systems for chunking or otherwise marking locations in streams as interesting just use buzhash and friends with a secret tweak. The moment the attacker learns that F(x)<threshold they can construct a stream x|x|x|x full of marked locations. Constructing a stream that contains no marks is similarly trivial. It becomes possible to construct streams with arbitrary marks from a library of strings with known mark properties.
There's no point in paying the computing cost to prevent key recovery if the adversary can break the system anyway which is why secure rolling hashes aren't in wider use.


What is the meaning of weight in cryptography and how is it related to branch number?

In cryptography, "weight" of a vector of bits is most often the Hamming weight, that is the number of non-zero bits in the vector. But in this AES context, that's most probably the "bundle weight" of a vector of bundles of bits (e.g. a vector of bytes), defined as the number of non-zero bundles.

In the AES context, the "(differential) (bundle) branch number" of a Boolean transformation with respect to a bundle partition, as defined by Joan Daemen and Vincent Rijmen in The Design of Rijndael (2002), section 9.3, is a measure of diffusion. It is defined as the minimum bundle weight of the XOR of two distinct input/output combinations of said transformation. For MixColumns, that's the minimum number of bytes that can change between two distinct input/output combinations (of a total of 32 bytes), or equivalently the minimum number of bytes in a non-zero input/output combination; which is 5.

This is consistent with the general definition of Hamming weight in coding theory, where, for a given symbol alphabet, the weight of a nonzero symbol is $1$ while the weight of the zero symbol is $0.$ The designers of AES used MDS codes over the finite field $GF(2^8)$ (which can be represented by binary vectors of length 8, i.e., the vector space $GF(2)^8$). This is a $[length=8,dimension=4,min.~distance=5]$ code and the minimum weight (same as minimum distance since the code is linear) is $5$. This minimum weight corresponds to the guarantee that there are at least 5 total nonzero bytes amongst the 4 input and 4 output bytes (the number of input bytes is the dimension of the code and the number of input+output bytes is the length) of the $\textsf{MixCols}$ mapping.

This answer further discusses the branch number.

Thanks for the many useful contributions in comments!


How does the frequency work with Vigenère Cipher?

So in your cipher text, the characters $c_1, c_7, c_{13}, \ldots, c_{1+6i}, \ldots$
should roughly obey the frequency statistics of a permuted or shifted standard English frequency. In the most standard Viginère, if you know E corresponds to cipher letter F (e.g. because it is (one of) the most frequent letters, the key letter is B and the alphabet has been shifted by $1$, allowing for immediate decryption of all letters in this subtext. The same holds for the characters
for encrypted by second key letter $c_2, c_8, c_{14}, \ldots c_{2+6i}, \ldots$: check the histogram, to see if it looks like a shifted standard alphabet etc. In general, the cipher alphabets per key letter could be totally independent and then it can take quite a bit of hand work (guessing words and extrapolating from that) to completely solve the text, but if the standard alphabets are merely shifted, it's rather easy to determine the key letter.


For a typical n-bit symmetric key, how many keys would be considered too weak to use?

I understand that all zeros or all ones would be weak for any cipher.

This isn't actually true. For good cipher there are no weak keys.

  And certain ciphers, e.g. DES, have a list of weak keys. But I assume that there would many 'patterns' that would be detected (if that is the correct term) as weak. For example, 0x0505 ...05, 0x1010...01 and 0x0A0A...0A. Or other patterns such as half the key being 0s and the other half being 1s or half the keys being 3s and the other half being Cs (i.e. the compliment of 3.

This isn't true for most algorithms.

More specifically you fall into thinking that number can either be random or not. Is 3 random? On a 1-10 scale? We humans easily assume that "1234" or "1111" isn't random. But what if it's just what came our of good RNG? Is RNG broken?

No, instead we are broken. We easily consider some things "too simple", while computers can just draw random number in range that is always random (if proper algorithm is used). It doesn't really matter if the number is 1, 5 or 283921. Algorithm design decides if numbers generated are good, not the number itself. Algorithm doesn't have to check for only 0bit keys, because chance that it generates this key is just as high as all other keys.

Now, why DES has "weak keys" then? Because those are keys that make algorithm perform poorly (encrypting again can undo effect for example). This shouldn't be case with good ciphers. We hope that Enc(K1,text) can only be undone with Dec(K1,text), not Dec(K2,text), nor Enc(K3,text) and especially not with Enc(K1,text) again!

  A key must have a large number of patterns, so is there a way to calculate this number?

Yes, random key in 128-256bit range is good. Any attempt at excluding keys like only zeros just limit how random your algorithm is.

  Are the patterns I mentioned above (and similar) weak keys?

No, DES weak keys come from how DES performs with those keys, not from how they look. If we found AES weak key of 0x28357129912581823923, this would be weak key because of how it works in algorithm, not because it looks non-random.

If we speak of "weak key" as in keys that aren't random enough, then it only comes down to how you generate those keys, not what those keys are! (Any key you get is not random then).


Point-at-infinity in the scalar multiplication

Yes, it is possible.

The smallest scalar $k$ for which $[k]P = \infty$ is called the order of $P$.

For every non-zero point $P$ on the curve there is such a $k$.

This is simply due to the fact that there is only a finite amount of points so if you keep increasing $k$ at some point you must get a repetition $[k]P = [k-i]P$ for some $i$. Now $[k]P - [k-i]P = \infty \iff [i]P = \infty$.

No, $k$ does not have to be bigger than the group order $n$.

In fact for any prime $p$ dividing $n$ there is a point $Q$ such that $[p]Q = \infty$. This is Cauchy's theorem.

On the other hand Lagrange's theorem tells us that the order of every point divides the group order: $[k]P = \infty \Rightarrow k|n$. Therefore, if the group order $n$ is picked to be prime it follows that the order of every non-zero element is $n$.


Calculate the security of a cascade cipher

It seems the result is specifically for multiple encryption with a single cipher (like in 3DES). It probably applies for different ciphers as well, but key and block sizes would need to be equal. You might get a lower bound by using the minimum key size, but don't quote me on that.

However, I don't think this is really relevant for a practical implementation. AES alone has a large enough key space that brute force attacks on the key are impossible. (Assume AES-256 if you care about quantum computers or are very optimistic about Moore's law.)

The formula tells you nothing about what the security is if some of the ciphers in your cascade are broken, which is the only reason you would use different ciphers in the first place. Therefore, it tells you nothing very important about the security of the cascade in practice, unless all the ciphers you used would be insecure on their own (again, 3DES). The brute force resistance is simply "enough".


After some thought, I think the answer is in fact NO, even for IND-1-CCA* and even for Shoup's OAEP+.

RSA-OAEP/OAEP+ work by taking a message $m$, producing a padding $p(m,r)$ and then encrypting this, so $c = f(p(m,r))$ where $f$ is RSA encryption, and $f(u) = u^e \pmod{N}$ is deterministic. In fact, the whole point of OAEP(+) is to inject some entropy into ciphertexts which is required for IND-CPA and higher security.

ElGamal encryption is already randomised. If we try ElGamal-OAEP(+) we get $c = (g^r, y^r \cdot p(m, r'))$ where $y$ is the public key. Since ElGamal is homomorphic, this is obviously not even CCA1: consider an adversary who picks $m_0, m_1$, asks for a challenge ciphertext $c = (u, v)$ and then sets $c' = (u \cdot g^s, v \cdot y^s)$ for randomly chosen $s$. This is still a valid OAEP(+) ciphertext whatever the padding $p$ is (since we're only changing the "outer" randomness $r \mapsto r + s$) so the IND-1-CCA game will happily decrypt this and return $m_0$ or $m_1$ as desired.

This is assuming of course that you can map your padding function's range into the group over which you're doing ElGamal --- for ECC, this should be fine, for $\mathbb Z^\times_p$ groups it's harder. As an alternative one could consider hashed ElGamal-OAEP+ with $c = (g^r, H(y^r) \oplus p(m, r'))$ where $H$ is independent of the hash functions used in the OAEP+ padding $p$. My intuition is that this is still not CCA1, even though it doesn't have the homomorphic property anymore. Certainly if $H$ has some homomorphic properties itself then one should be able to do something like the above counterexample.

IND-1-CCA: Is standard IND-CCA2 where you only get 1 decryption query after seeing the challenge ciphertext instead of polynomially many.


Secret sharing scheme WITHOUT Shamir Secrete Sharing

XOR secret sharing used directly is unconditionally secure, if the randomly generated first share $S_1$ is a uniformly distributed vector in $\{0,1\}^{128}$. Let the secret be $X \in \{0,1\}^{128}$ and the shares be $S_2=X+S_1,$ and $S_1,$ where $+$ denotes bitwise XOR.

For a third party to learn the secret, they need to brute force $O(2^{128})$ guesses in the worst case.

Now you've "hidden" the secret $X$ by your $S_1'=TRUNC_{128}(SHA_{512}(X)).$

As stated in the comments I was wrong, thebirthday paradox does not directly apply.

An attacker brute forcing the share $S_2’=X+X_1$ at the same complexity will not learn your secret but its hash, so you’ve gained something.

However in the absence of side information, the original XOR scheme is as secure, unless the guesses for the secret can be tested by using it, say, as a password to unlock some system. In that use case, your modification is an improvement since it prevents this way of testing if the guess is correct.