Is there a pseudo message that will encrypt and decrypt correctly if one of the primes is a pseudo prime in RSA

We expect that the encryption will fail since the incorrect $\varphi(n)$.

Not always; for example, consider the case $p=31$ (a Mersenne prime) and $\bar{p} = 561 = 3 \times 11 \times 17$.  We'll set $e = 13$ and $d = e^{-1} \bmod 30 \times 560 = 3877$.
Then, if we pick a random message $m=2$, then $2^e \bmod n = 8192$, and $8192^{3877} \bmod n = 2$; encryption and decryption works just fine.  Actually, it turns out that any value $m$ will encrypt and decrypt properly with this particular $n, e, d$ set.
Lets try it again with another random example; this time we'll pick a Fermat prime $p=17$ and an arbitrary $\bar{p} = 91 = 7 \times 13$, and so $n= 1547$.  This time, we'll use $\lambda(n) = (p-1)(\bar{p}-1) / \gcd( p-1, \bar{p}-1 )= 720$; we'll pick $e=7$ and so $d=e^{-1} \bmod \lambda(n) = 103$.  Again, if we pick a random message (we'll try $m=3$ this time, we have $3^e \bmod n = 640$ and $640^d \bmod n = 3$.  And, again, any $m$ will encrypt and decrypt properly with this particular $n, e, d$ set.
So, how did this work?  Did I just pick these examples at random?  Is this always true of Fermat and Mersenne primes?  Well, no, for this trick, I selected my $\hat{p}$ values carefully, and most everything else was arbitrary.
In the first case, I selected $\hat{p}$ to be a Carmichael number, that is, a composite number such that $\lambda(\hat{p})$ is a factor of $\hat{p}-1$.  It turns out that a Carmichael number acts just like a prime as far as RSA is concerned; any $p$ (relatively prime to $\hat{p}$ would make it work).
In the second case, I selected a $\hat{p}$ that wasn't a Carmichael number (561 happens to be the smallest), but instead it is something we may call a "semicarmichael number" (terminology I just made up, so don't bother googling it); it has the property that $\lambda(\hat{p})$ is a factor of $2(\hat{p}-1)$.  Now, these numbers won't always work within RSA, however it does work if either $p \equiv 1 \bmod 2^{k+1}$ (where $2^k$ is the largest power of 2 which is a divisor of $\hat{p}-1$), or alternatively you use the $\phi(n)$ relation of $e, d$ (rather than the $\lambda(n)$ relation - for primes and Carmichael numbers, it doesn't matter - for semicarmichael numbers, it does).
So, what does this stage magic trick relate to your question:

If, so, what is the probability of the pseudo messages?

Higher than you'd expect, if you did a number of rounds of Fermat or Miller-Rabin beforehand.  It turns out that Carmichael numbers will always fool Fermat (unless you happen to pick a generator that's not relatively prime to the Carmichael number), and semicarmichael numbers will fool Fermat half the time.  And, both these numbers have good probability of fooling Miller-Rabin (obviously $< 1/4$, however sometimes not much less).  Hence, while Carmichael and semicarmichael numbers are rare, if you have a composite number that fools several rounds of Fermat or MR, the probability you started with such a number is pretty good.


Given $g$, $b$, $g^{ab}$, is finding $g^a$ a hard problem?

Not at all. It's very trivial:
$$(g^{ab})^{b^{-1}}=g^a$$


Is the Java function AES/CBC/PKCS5Padding vulnerable to padding oracle?

The problem with CBC mode is the padding. When there is a padding error, the server must respond a message back to you so that you can send the message back again or encrypt the message from the beginning.
The padding oracle attack is solely based on this idea. The attacker changes the byte and looks at the response of the server to execute the attack.
As we can see the attacker needs an oracle to execute the padding oracle attack. Data on-rest or encrypted databases has no oracle. Therefore they are not vulnerable to padding oracle attacks.

CBC mode has no integrity and authentication and removed from TLS 1.3.
AES-GCM which is in TLS 1.3 has an authenticated encryption scheme which provides both integrity and authentication. In the internal GCM mode uses CTR mode for encryption that requires no padding. Therefore padding oracle is not applicable.
So in short, in GCM mode you will have

Integrity
Authentication, and
No padding which is vulnerable to padding oracles.

Since you are going to use AES/GCM your next issue will be the IV. Instead of random IV, you can use incremental IV so that you can mitigate IV Reuse catastrophe. For more information on IV recommendations see section 8 of NIST-800-38D
In Java, you can use AES/GCM/NoPadding from  javax.crypto.Cipher package.


Is AES-256 a post-quantum secure cipher or not?

Biclique cryptanalysis is the current best-known attack on AES. It reduces the security of AES-256 from $2^{256}$ to $2^{254.4}$. Related key attacks are not practical attacks, as they should never occur in the wild. They are symptomatic of poor implementation and contrary to the recommended use of AES.

The best known theoretical attack is Grover's quantum search algorithm. As you pointed out, this allows us to search an unsorted database of $n$ entries in $\sqrt{n}$ operations. As such, AES-256 is secure for a medium-term against a quantum attack, however, AES-128 can be broken, and AES-192 isn't looking that good.

With the advances in computational power (doubling every 18 months), and the development of quantum computers, no set keysize is safe indefinitely. The use of Grover is just one of the gigantic leaps.

I would still class AES as quantum resistant, so long as the best-known attack is still some form of an exhaustive search of the keyspace.

As for your question about using different attacks: Combining attacks rarely works as you need all of your attacks to reveal exclusive bits of the key. Given that the best attack on AES doesn't even reveal 2, you will be hard pushed to make a reasonable attack like this.


How can a collision attack using MD5 be used to break WOTS

I believe that, in the question you cited, the answer included:

BTW: this appears to be more about the proof technique used to prove W-OTS, rather than the actual security; we can create MD5 collisions (invalidating the proof), however we don't know how to use those collisions to actually attack W-OTS-MD5; hence it would appear to be secure (but we can't prove it).

That is, we don't know how a collision attack would break Winternitz; we just can't prove that it can't.


Why does "2xAES-256" provide "99.99%" security strength whereas "1xAES-128" provides "40%"?

It's meaningless nonsense. I would be inclined to avoid spending any money with these people. If you scroll down on this page, you'll find a table labelled key size vs. time to crack, according to which their $2 \times 256$ bit encryption takes $3.31 \times 10^{112}$ years to crack, making it (apparently) superior to ordinary $256$-bit encryption (which can be cracked after a paltry $3.31 \times 10^{56}$ years).

I think you'll find that the values you cited are based on the exponents of these numbers (hence $10^{112} \rightarrow 100\%$, but $10^{56} \rightarrow 50\%$).

However, they don't explain why you should be concerned about your data remaining secure after the heat death of the universe.

Seriously, don't give your money to these clowns.


Is there a string that's hash is equal to itself?

I restrict to hash functions $H$ with an output of some fixed size $n\ge1$ bit(s), accepting as input some strings, including all $n$-bit strings; MD5 (resp. SHA-1, SHA-256) is an example of such function for $n=128$ (resp. $n=160$, $n=256$).
Whether there exists a solution to $H(x)=x$ depends on the particular hash function. If $H$ is a random function (as MD5, SHA-1, and SHA-256 aim to be), the answer is YES with odds next to $63.2\%$ for practical values of $n$.
More precisely: $H(x)=x$ can hold only if $x$ has exactly $n$ bits. There are $2^n$ values of $x$ that satisfy the later condition, and restricting $H$ to such $x$ there are $(2^n)^{(2^n)}$ different $H$ functions, of which $(2^n-1)^{(2^n)}$ such that $H(x)=x$ has no solution. Therefore, if we choose one $H$ uniformly randomly, odds are exactly $1-{(2^n-1)^{(2^n)}\over(2^n)^{(2^n)}}=1-(1-2^{-n})^{(2^n)}$ that we picked $H$ such that $H(x)=x$ has a solution. As $n$ increases, this converges very fast to $1-1/e\approx0.632$ (where $e\approx2.718$ is the base of the natural logarithm).
This does not tell if MD5 has the property that there exists a solution to $\operatorname{MD5}(x)=x$ (which would be a 128-bit bitstring $x$). The best we can say is that it likely holds, with odds about to 63%, but determining if the assertion is true or false is beyond our current computing power (the best method we have is exhaustive search, and if the answer is no it would require $2^{128}$ hashes; otherwise it is still likely to require over $2^{126}$ hashes, which is beyond reach).
PHP specific: if md5($string) === $string had some solution, that would be a 32-character string of hexadecimal lowercase characters; we are not hashing the same $2^{128}$ candidates as above so the question is not equivalent, but the reasoning can be adapted, and again the best we can say is that it is likely there's a solution, with odds about 63%.
Further, the original question asked if there is a string such that md5($string) == $string. To answer this, we must take into account how the == operator works in PHP due to type juggling (it holds that "0042" == "42", and "20e2" == "   +002000"). It is overwhelmingly likely that there is a solution (just consider that among the $2^{200}$ strings consisting of 200 space or tab and an additional final 0, we expect about $31\cdot2^{72}$ hash to one of "00000000000000000000000000000000", "000000000000000000000000000000e0" .. "0e000000000000000000000000000000"); however we can't exhibit one.

It is easy to define a hash function $H$ such that $H(x)=x$ has no solution: for example, define
$$H(x)=\begin{cases}x\oplus1&\text{if }\operatorname{MD5}(x)=x\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$

It is also easy to define a hash function $H$ such that $H(x)=x$ has at least one solution: for example, choose some arbitrary 128-bit constant like $k=\text{af5d2bc6c9181f76f3161f43f41f6aeb}$, and define
$$H(x)=\begin{cases}k&\text{if }x=k\\\operatorname{MD5}(x)&\text{otherwise}\end{cases}$$

There can be no $x$ such that for all possible hash functions $H$, $H(x)=x$.
Proof by contraposition: assume there is such $x$, a function $H$ with $x$ having that property, and consider the function $\tilde H$ defined by $\tilde H(x)=H(x)\oplus1$.


How can disk encryption systems (like Truecrypt) resist frequency analysis when they allow random access?

Free space and used space look exactly the same to someone who only sees one version of the ciphertext.

First, the basic idea of a secure block cipher is that you learn nothing about the plaintext block simply by observing the ciphertext block. You may be able to learn something about the plaintext from the surrounding context, such as by collecting more ciphertext blocks, but nothing about the ciphertext block itself yields information about the plaintext block.

Truecrypt uses block ciphers in XTS mode. Popular modern block ciphers are just a deterministic mapping between an input 16 bytes and an output 16 bytes, but XTS mode allows a normal block cipher to work with an additional input "tweak" value that affects the encryption. The tweak input describes the position of that block within the volume, and each one is unique. Since this tweak value affects the final ciphertext, a plaintext $P$ will encrypt differently if it is at position $i$ (and is thus tweaked by value $i$) or position $j$ (and is thus tweaked by value $j$) within the volume. So all unused space on the volume would encrypt to a different ciphertext for every block, even if they are all the same plaintext block value, such as 0. So no pattern of unused space would emerge in the ciphertext since, for all effective purposes, you would be encrypting different plaintext at every single spot. You can perform random access on XTS, as each ciphertext block is stand-alone. (However, for performance reasons, ciphertext is probably always read and decrypted in full sectors. True random access is not very efficient at the block disk level.)

XTS isn't unique in this regard, but it's is the most popular mode of operation in this sort of context right now. Other modes of operation like CBC can also provide similar security. In CBC mode, the plaintext is divided into sectors (usually 512 bytes to 4K in size, about the size of a sector) and each block is encrypted using a unique IV as input that aids the chaining process that you are familiar with. The chaining ensures that each plaintext block is encrypted differently in different contexts, and the uniqueness of the IV starts each chaining sequence uniquely. CBC doesn't have true random access, on reads you must read the previous block of ciphertext in the sector for use in decryption, and on writes you must re-encrypt the entire sector after the modified block. But since the sector sizes are small, it's "close enough" to random access.

(That is all a gross simplification, designed primarily to give an intuitive notion as to how used and unused space is treated.)

Ciphertext corruption is a minimal concern. In XTS mode nothing is chained, so only corrupted blocks become unusable. In chaining modes, generally only one other block becomes corrupted. For example, in CBC any given ciphertext block is only used in at most one other plaintext block encryption, so a damaged ciphertext block only breaks it's own plaintext and the other plaintext block it was chained with. (Stare at the CBC Wikipedia diagram until that makes sense.)

That describes the cryptographic solution, but there is a semi-complimentary ad-hoc solution as well. It takes advantage of a details of the filesystem. All blocks of the plaintext are encrypted, regardless of whether or not the filesystem stores any data in that block, and the filesystem doesn't care about the contents of unused blocks. So if each unused block has random, uncorrelated plaintext in it, then their ciphertexts will be uncorrelated. The attacker wouldn't know if those blocks had legitimate plaintext in them or just random unused data. This method should not be required for security, but it does add a nice buffer layer of security to mitigate a potential weakness in the algorithm or failure in the implementation.

Truecrypt uses that technique too. When you create a volume they give you the option of performing a "full" format in the beginning. This full format writes random data to every single sector of the encrypted volume. As you use the volume the filesystem simply overwrites the random data as it needs to use new sectors and ignores the random data it doesn't need to overwrite.

However, things change when an attacker can take multiple looks at the volume at different points in time. If they can see the volume ciphertext and take a snapshot of it, then later come back and take another snapshot of the ciphertext, they could compare the two and might be able to estimate what changed and what space is used/unused, depending on the activity that had happened on the volume in that period of time. But that becomes highly dependent on what the attacker knows about the structure of the plaintext, how much of it changes, etc, and is not relevant to an attacker who only gets too see the ciphertext at one point in time.


Relation between the correlation coefficients $\widehat F(w) = C(f(a), w^ta)$ and $(-1)^{f(a)}$

Kodlu already gave a hint, but here are a bit more details (since I don't think this is homework). By definition (or equation 3 in your reference),

$$\widehat F(w)= C(f(a), w^t a) = 2^{-n} \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x) + w^t x}.$$

Hence

$$\sum_{w \in \mathbb{F}_2^n} \widehat F(w) (-1)^{w^t a} = 2^{-n} \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x)} \left(\sum_{w \in \mathbb{F}_2^n} (-1)^{w^t (x + a)}\right).$$

The inner sum is zero whenever $x \neq a$ and equal to $2^n$ otherwise. Hence

$$\sum_{w \in \mathbb{F}_2^n} \widehat F(w) (-1)^{w^t a} = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x)} \delta_{x, a} = (-1)^{f(a)} = \widehat f(a).$$

I've used the same notation as in your reference. If you want a more general understanding of this result, you should read about Fourier transformations on (locally compact) groups.


That is, why is the scheme insecure if we compute the output tag $t'$ using $F_{k_1}$?

Computing $F_{k_1}( \text{CBCMAC}_{k_1}(M))$ is precisely equivalent to taking the padded message $M$, appending an all-zero block to it, and then preforming the CBC-MAC on it (sans the padding operation).

Here's how an attacker can exploit that to break the MAC scheme, given the restriction that all messages presented to CBC-MAC has an all-0 block at the end:

First, ask for $a = \text{CBCMAC}_k(M_1 || 0)$, and $b = \text{CBCMAC}_k(M_2 || 0)$

Then, we know that $\text{CBCMAC}_k(M_1 || 0 || u || 0)$ and $\text{CBCMAC}_k(M_2 || 0 || u\oplus a \oplus b || 0)$ are the same (for any single block $u$); this happens because, when the two MACs xor in the $u$ or the $u \oplus a \oplus b$ blocks, then both set their internal states to $u \oplus a$, and all other processing is identical past that point.

So, the attacker asks for one, and he then knows the MAC of the other.


Both ent tests distinguish the files from random data with high confidence (99.84% for the bit test, >99.99% for the byte test). That follows from the "randomly would exceed this value.." reports.

It would only be an issue in actual use if the random data was directly used. Which would be bad practice in cryptography, where the rule is that the output of an unconditioned TRNG is, under operating conditions, fed exclusively to

a monitoring scheme which ensures that the unconditioned TRNG outputs some entropy;
and a PRNG processing the output of the unconditioned TRNG.

Note: if the PRNG is not cryptographically secure (which is often the case for hardware ones), its output is further processed with a CSPRNG.

With this structure the monitoring scheme's purpose should not be to try to determine that/if the TRNG is near-perfect. It should be to rule out that the TRNG is badly broken (like, insure that the entropy rate if at least 0.5).

The ent test is ill-suited to the purpose: it is not operating in real time, is not designed to ignore minor defects, and most importantly it fails to detect some huge, not-unlikely defects: if there was a triple-trigger for every Geiger event, making three identical or incremental values recorded for each Geiger event, that would not be detected by ent (except for very small input), when that's a disaster.

Still, from an engineering perspective, it is interesting to understand what makes the ent tests fail. Some ideas (before the question was updated with raw data and code):

The Geiger event determines when a free-running 16-bit timer clocked at about $2^{16}/10^{-3}$Hz (about 70 MHz) is sampled. It could be that there is some analog feedback from the counter, or from something derived from the same clock as the counter, to the sampling logic. For example, if when the Geiger event occurs near the active edge of the clock, the current state of the low-order bit of the counter influences (by e.g. capacitive coupling) the decision of the gate that determines if the event is going to be registered as having happened before or after the edge, then that low-order bit is going to be biased. It may be that ent's byte test will detect this bias more accurately than it's bit test (because the biased bit is always at the same position in a byte).
If the sampling is in software (e.g. an interrupt triggered by the Geiger event reads the 16-bit timer), then the latency in the processing of that interrupt can play a role. For example, if the 16-bit timer generates an interrupt of identical priority when it overflows, that makes it impossible that some 16-bit values (those right after the overflow) get sampled, creating a bias. I believe ent's byte test would detect that kind of issue more selectively than it's bit test.

Summary (before the question was updated with raw data and code):

The ent tests failed, and that's likely related to some minor imperfection. We can only make guesses at which.
It is no indication that this unconditioned TRNG is unsuitable to seed a (CS)PRNG, which is the Right Thing to do with an unconditioned TRNG.
The enttest is not adequate for an unconditioned TRNG source; not even in an exploratory phase, much less for the continuous surveillance of the unconditioned TRNG, as necessary in serious cryptographic uses.

Update: Mystery solved!

Summary frequency analysis of the raw data demonstrates beyond doubt that byte values 0x11 and 0x13 have been filtered out. That's what allows ent to raise alert. Certainly, XON/XOFF software flow control strikes again!

0x00 281  0x01 300  0x02 343  0x03 313  0x04 322  0x05 321  0x06 295  0x07 342  0x08 317  0x09 319  0x0A 337  0x0B 320  0x0C 328  0x0D 308  0x0E 324  0x0F 344
0x10 316  0x11   0  0x12 320  0x13   0  0x14 314  0x15 376  0x16 336  0x17 325  0x18 295  0x19 342  0x1A 325  0x1B 338  0x1C 326  0x1D 293  0x1E 324  0x1F 296
0x20 328  0x21 300  0x22 322  0x23 313  0x24 340  0x25 334  0x26 342  0x27 315  0x28 336  0x29 295  0x2A 313  0x2B 305  0x2C 322  0x2D 341  0x2E 303  0x2F 331
0x30 308  0x31 339  0x32 371  0x33 325  0x34 323  0x35 319  0x36 324  0x37 309  0x38 337  0x39 296  0x3A 323  0x3B 338  0x3C 335  0x3D 302  0x3E 335  0x3F 348
0x40 331  0x41 318  0x42 334  0x43 285  0x44 323  0x45 348  0x46 323  0x47 333  0x48 325  0x49 370  0x4A 345  0x4B 318  0x4C 338  0x4D 302  0x4E 330  0x4F 326
0x50 332  0x51 308  0x52 307  0x53 362  0x54 300  0x55 292  0x56 335  0x57 333  0x58 352  0x59 355  0x5A 317  0x5B 326  0x5C 329  0x5D 334  0x5E 316  0x5F 331
0x60 318  0x61 324  0x62 293  0x63 318  0x64 302  0x65 324  0x66 317  0x67 313  0x68 297  0x69 310  0x6A 330  0x6B 334  0x6C 300  0x6D 340  0x6E 310  0x6F 317
0x70 324  0x71 335  0x72 309  0x73 335  0x74 333  0x75 336  0x76 314  0x77 313  0x78 354  0x79 333  0x7A 294  0x7B 333  0x7C 324  0x7D 340  0x7E 343  0x7F 336
0x80 309  0x81 294  0x82 352  0x83 324  0x84 306  0x85 295  0x86 314  0x87 342  0x88 324  0x89 311  0x8A 331  0x8B 292  0x8C 305  0x8D 318  0x8E 324  0x8F 321
0x90 307  0x91 325  0x92 335  0x93 329  0x94 324  0x95 335  0x96 318  0x97 336  0x98 335  0x99 302  0x9A 310  0x9B 342  0x9C 315  0x9D 326  0x9E 290  0x9F 323
0xA0 308  0xA1 319  0xA2 347  0xA3 323  0xA4 305  0xA5 312  0xA6 336  0xA7 293  0xA8 323  0xA9 310  0xAA 352  0xAB 323  0xAC 305  0xAD 312  0xAE 340  0xAF 306
0xB0 305  0xB1 311  0xB2 334  0xB3 333  0xB4 303  0xB5 324  0xB6 343  0xB7 308  0xB8 305  0xB9 309  0xBA 331  0xBB 322  0xBC 332  0xBD 329  0xBE 311  0xBF 327
0xC0 350  0xC1 349  0xC2 352  0xC3 313  0xC4 319  0xC5 350  0xC6 282  0xC7 316  0xC8 305  0xC9 348  0xCA 316  0xCB 325  0xCC 335  0xCD 337  0xCE 295  0xCF 309
0xD0 305  0xD1 344  0xD2 325  0xD3 311  0xD4 296  0xD5 301  0xD6 349  0xD7 285  0xD8 328  0xD9 308  0xDA 323  0xDB 338  0xDC 276  0xDD 299  0xDE 323  0xDF 314
0xE0 286  0xE1 360  0xE2 315  0xE3 308  0xE4 329  0xE5 321  0xE6 302  0xE7 315  0xE8 346  0xE9 326  0xEA 315  0xEB 352  0xEC 346  0xED 319  0xEE 333  0xEF 289
0xF0 320  0xF1 309  0xF2 317  0xF3 325  0xF4 312  0xF5 366  0xF6 331  0xF7 316  0xF8 283  0xF9 344  0xFA 336  0xFB 302  0xFC 331  0xFD 310  0xFE 347  0xFF 335

Note 1: As a minor aside, the 16-bit counter is sampled by software in an interrupt, rather than in hardware by an input capture mechanism. It follows that any variation in interrupt latency influences what's sampled. In many CPUs, interrupt latency varies slightly according to foreground activity (like, a multi-cycle instruction or access to a peripheral requiring wait states increases latency). The ATMega328P has instructions lasting 1 to 4 cycles, thus this could have some minor influence, especially on the low-order bits. While I have seen the uncertainty in sampling by interrupt about halved by putting a CPU in wait/sleep mode rather than in a loop with a 2-cyles branch, that's a non-scalable kludge, and using the ATMega328P's Input Capture Unit would be best (depending on what pin the signal to sample is connected, that could be software-only change).

Note 2: putting a radioactive source nearby will have several effects:

The entropy rate (in bit/s) will increase.
The samples will get closer, and that will increase a currently minor issue: by design, the difference between a 16-bit sample and the next (modulo 65536) is biased.
Odds of upset in the nearby logic/CPU will increase, which could have dramatic negative side effects.

Note 3: Proper monitoring of the unconditioned source is best done with knowledge of which is high and low byte of 16-bit samples. This currently is possible only by timing considerations (especially with the disappearing bytes). We can solve that and make the output plain ASCII by sending a 16-bit sample as 4 characters, the first in PQRSTUVWHIJKLMNO and the others in pqrstuvwhijklmno, with the low-order 4 bits of each character equal to 4 bits of the 16-bit sample (I suggest, in big-endian order, which is the most common in crypto).

Note 4: In some cryptographic contexts, adding a proper CSPRNG somewhere will be essential. If this unconditionned generator was used as /dev/random directly, it would be easy to distinguish the output from good randomness, at least if it can be timed when the output becomes available! Proper monitoring is important too, and essential if an adversary can approach the device (sabotage is a thing; and forcing Geiger events to occur is not rocket science).


Suppose you have an asymmetric algorithm that creates a 48-bit signature. Then an attacker can simply test possible 48-bit signatures and find one that verifies in $2^{47}$ tries on average. Even with a relatively slow asymmetric algorithm that would be feasible, especially if the attacker can test the same signature for multiple tokens. And that is only a brute force attack, asymmetric systems usually allow much faster attacks.

If you can establish a symmetric secret, even a short MAC is much better, because while the attacker still has a $2^{-48}$ probability of success with a random guess, they can no longer verify those guesses offline.


When NIST disallows the use of 1024-bit keys, what effect will that have on SHA-3 (with max. 512 bits)?

That's not the same kind of key.
Symmetric keys are a bunch of bits, such that any sequence of bits of the right size is a possible key. Such keys are subject to brute force attacks, with a cost of $2^n$ for an $n$-bit key. 128 bits are way beyond that which is brute-forceable today (and tomorrow as well). If a block cipher is "perfect," then enumerating all possible keys is the most efficient attack (i.e., "no shortcut").
RSA keys are mathematical objects with a lot of internal structure. In a 1024-bit RSA key, there is a 1024-bit integer value, called the modulus: this is a big integer whose value lies between $2^{1023}$ and $2^{1024}$. To break an RSA key, you "just" have to factor this modulus into its prime factors. There are relatively efficient algorithms for that, to the extent that factoring a 1024-bit RSA modulus is on the verge of the feasible. It has been estimated that the "cost" of factoring a 1024-bit RSA modulus is similar to the "cost" of brute-forcing a 77-bit symmetric key. Note that this is not the same kind of cost (you need a lot of fast RAM for factoring big integers, whereas enumerating many AES keys requires no RAM at all).
DSA and Diffie-Hellman keys are also mathematical objects, with again a lot of internal structure. There is also a modulus, but a prime one, so it is not about factorization, but something else, called discrete logarithm. It so happens that breaking discrete logarithm modulo an $n$-bit prime has a cost that is roughly similar to the cost of factoring an $n$-bit RSA modulus (the DL cost is, in fact, a bit higher). So a 1024-bit DSA or DH key is also similar in strength to a 77-bit symmetric key (or maybe an 80-bit symmetric key).
Elliptic curve cryptography yet again uses mathematical objects as keys, but with another structure that fits in fewer bits for a given security level. Basically, you get "$n$-bit security" (resistance similar to that of an $n$-bit symmetric key) with a $2n$-bit curve.
Hash functions have no keys. Yet there is a concept of resistance to various attacks (collisions, preimages, second preimages...) with costs that can be estimated depending on the function output size (assuming that the function is "perfect"). For a hash function with an $n$-bit output size, resistance to collisions is in $2^{n/2}$, resistance to preimages (and second preimages) is in $2^n$. (There are ongoing discussions about making SHA-3 faster by relaxing this latter value, i.e., having "only" 128-bit security against preimages with a 256-bit output length.)

See this site for lots of data on comparative strength estimates. In particular, these NIST recommendations illustrate their point of view:

1024-bit RSA/DSA/DH and 160-bit ECC are "as good" as an 80-bit symmetric key.
2048-bit RSA/DSA/DH and 224-bit ECC are "as good" as a 112-bit symmetric key.
3072-bit RSA/DSA/DH and 256-bit ECC are "as good" as a 128-bit symmetric key.
7680-bit RSA/DSA/DH and 384-bit ECC are "as good" as a 192-bit symmetric key.
15360-bit RSA/DSA/DH and 512-bit ECC are "as good" as a 256-bit symmetric key.

NIST also says that the "80-bit" security level should be shunned except when mandated for interoperability with legacy systems.
These five formal "security levels" are the reason why AES was defined with three key sizes (128, 192 and 256 bits -- the two lower levels mapping to 2DES and 3DES), and SHA-2 with four output sizes (SHA-224, SHA-256, SHA-384 and SHA-512, the "80-bit" level being used for SHA-1); and, similarly, SHA-3 is (was) meant to offer the four output sizes 224, 256, 384 and 512 bits.


Create a time capsule using a Word processor

I know no feature like this built into any word processor. And, despite work on so-called time-capsule cryptography, we know no practical[*] way to implement one without relying on trusted hardware or trusted third party.

To achieve this, we can use the help of a trusted third party/server. It can generate and publish public keys for which it will publicly release the private keys at a set date. The sender enciphers the message with the public key selected per the desired release date. The receiver can't decipher until that date. To do so, s/he must get online, get the private key (now published) from the third party, then decipher.

[*] Problems with proposed time-capsule cryptography systems requiring no trusted external hardware/party are that their delay of release is too imprecise, and they would be prohibitively costly. They achieve timed release by requiring sequential iteration of a certain computation, assumed to require at least a certain time $T_0$. To obtain a delay $T$, the receiver is forced to perform $t=T/T_0$ operations, at full rate, during the whole timed release. But $T_0$ varies a lot with the technology, and the fasted high-speed logic is prohibitively expensive. That used to be GaAs, now perhaps InP, or is it unobtainium-on-diaphire immersed is liquid nitronium.


How to provide encryption of user's data that can be performed by multiple (specific) users?

First of all, reuse of keys for multiple purposes is severely frowned upon when it comes to key management. If you just derive a single secret from PBKDF2 for authentication then you can still split it further into multiple keys / password hashes using a KBKDF such as HKDF.

Furthermore, if you want to decrypt data with multiple keys then you can simply create a random "data key" and encrypt that with the keys required.

If the key is a symmetric key then that key may however not be available, especially for the administrators. In that case you could just encrypt with a public key of a key pair generated for that administrator. You can encrypt the private key of that key pair using the symmetric key derived using PBKDF2 and the KBKDF. That way you only need the admin to log in when decryption is required instead of for encryption and decryption.

That said, I'd strongly advice you to hire a data encryption expert if you've got these kind of questions. There may be a lot of other requirements to secure the system.


Is HKDF one-way, namely given `Ko` it's hard to guess `Ki`?

Very shortly, yes, this is the case.
A KDF is secure if an adversary cannot make a distinction between the output of the KDF and random output (with a larger probability of ${1 \over 2} + \epsilon$). The attacker gets to know the salt and is able to choose the $Info$ parameter and output size (i.e. all the other input parameters) as well as any previous output. This is basically a plaintext excerpt of chapter 3 of the original paper "Cryptographic Extraction and Key Derivation: The HKDF Scheme".
It is easy to see that the above definition fails if the input source keying material is known to the attacker. Hence it is of vital importance that the KDF is one-way with regards to the input keying material. Usually all the output of a KDF is generated by one-way functions in the first place, usually a hash based MAC. In the case of HKDF this is HMAC. In the paper they generally talk about a one-way function as primitive.
This is rather expected; the whole idea of key derivation is to decouple the output from the input to any adversary. Other methods of establishing a key may not carry this property though; there is a reason why HKDF has decided to include a security definition of KDF inside the paper instead of pointing to another document. The fact that the security of HKDF is formalized is one of the big strengths of HKDF and has probably helped it getting standardized by NIST.
HMAC is relatively complex because it requires protection against length extension. When e.g. SHA-3 is used you could use KMAC or a similar construction instead. KMAC already generates as many output bits as required, which makes a KDF-expand function easier to define as well.


are there more efficient ways to generate the authentication path without recomputing the xmss root?

Yes (and without using large amounts of memory to store the entire tree).
These are Merkle tree walking algorithms; these are algorithms which output the 'next' authentication path for a Merkle tree - they store some number of internal nodes, and recompute some small number of leaf nodes while generating an authentication path.
The best known (and best described, if not the simplest) would be the BDS algorithm, which generates the next authentication path in $O(h)$ time and storing $O(h)$ intermediate nodes (where $h$ is the height of the tree).
Another (simpler approach) would be the Fractal algorithm (which isn't well described in the paper); this uses more internal storage, but it requires fewer numbers of computations per authentication path generated (and hence may be a better trade-off, depending on which you are trying to minimize)
These are not the only two; google can point you to others...


What is significance of recovering the chaining value of a hash compression function?

This should be considered as a weakness of the compression function, which is not a preimage resistant anymore. Sometimes, but not always, this may imply an attack on a hash function or a larger construction using this compression function.

For instance, consider the prefix MAC scheme, which is constructed out of a hash function $H$ as follows:
$$
MAC_K(M) = H(K||M).
$$
The prefix scheme is secure for some hash functions, for example the SHA-3 (Keccak) hash function.

However, if the compression function used by $H$ is not preimage resistant, then an adversary given $MAC_K(M)$ may recover the chaining value
$$
CV=H(K),
$$
and construct a valid MAC for any other $M'$ even though he does not know $K$.


If there is an algorithm A can calculate the modular square root of input n, How to use it to get prime factors?

How many solutions are there for equation $x^2\equiv y\pmod N$?

That problem is easier when $N$ is odd and $\gcd(y,N)=1$ (notice that when either does not hold, we have a factor of $N$): there are either $0$ or $2^k$ solutions, where $k$ is the number of distinct primes $p_i$ dividing $N$. Proof starts with $N$ prime (see Legendre symbol), then a power of a prime, then the product of powers of distinct primes (using the Chinese Remainder Theorem).

  Why the algorithm $A$ would always return the same output?

The proof thought to answer the question should work including when the algorithm $A$ always return the same output $x$ for input $(y,N)$, because nothing in the question's assumption "Suppose.." says that $A$ will return all solutions, or would eventually return all solutions when invoked repeatedly. Many algorithms are deterministic, that is always perform the same operations for a given input, including producing the same result. Actually, in cryptography, we often implicitly restrict to such deterministic algorithms, considering that a random behavior must come from an explicit extra random input.

Hint: you want to have two solutions: one you know beforehand, and one that the algorithm will give you. The algorithm can't read your mind, thus there's a chance that it will return another solution, and perhaps that will be helpful.


Generate $J_0$ for GCM cipher when $\operatorname{len}(IV) \neq 96$ bits

Yes, the initial 128 is multiplication and it is performed before the subtraction.

OK, so if $\operatorname{len}(IV) = 1$ in bits then $$s= 128\big\lceil\operatorname{len}(IV)/128\big\rceil-\operatorname{len}(IV)$$ would be $$s= 128 \cdot 1 - 1 = 128 - 1 = 127$$

However, if you encode it as a single byte then $$s= 128 \cdot 1 - 8 = 128 - 8 = 120$$.

Note that any IV size between 0 exclusive and 128 inclusive will let $\big\lceil \operatorname{len}(IV)/128\big\rceil$ evaluate to 1, as the division result is in between 0 exclusive and 1 inclusive.

The IV is generally delivered as byte array as implementations generally do not operate on bits, even if the speficiation does specify the algorithm in bits. So generally delivering just one bit is not possible. This means that the most significant (leftmost bits) of the byte or bytes are included in the calculation even if they set to 0. The IV is handled as a string of bits, not as a number within the specification. So lets assume a single byte with value 00000001 in bits.

For the second part of the scheme to calculate $J_0$ we have $$J_0=\operatorname{GHASH}_H(IV||0^{s+64}||\big[\operatorname{len}(IV)\big]_{64})$$ which means the $\operatorname{GHASH}$ using $H$ over the one byte IV concatenated by $s + 64$ bits (184 bits or 23 bytes) set to zero and then the length of the IV created as static, big endian unsigned encoding of 8 bytes. If you combine the sizes of the fields you'll get a nice 32 bytes: $1 + 23 + 8 = 32$, which is handled perfectly well by GHASH that requires 128 bit / 16 byte block size.

The result will be, the GHASH over (in hexadecimals, two characers per byte):

01_000000_00000000 00000000_00000000 00000000_00000000 00000000_00000001


Extract private RSA key from USB cryptographic token using Bardou et al. attack (variant of "million message attack")

Their attack does not recover the private key.  Instead, it gives the attacker a way to decrypt an arbitrary ciphertext of the attacker's choosing.  (This is not the same thing.)

If the attacker has a ciphertext $c$, the attacker can query the hardware device tens of thousands of times and then based upon the responses, deduce what the decryption of $c$ is.  If the next day the attacker runs across another ciphertext $c'$ that he wants to decrypt, he needs to issue another tens of thousands of queries to the hardware device.  That's pretty bad -- but it's not as bad as revealing the private key.

So, the answer to your question is: no, their attack does not reveal the private key.

(I think all of this is already covered in the links you mentioned in the question, so I'm not sure whether I understood what you were asking.)


The HOTP standard describes the resynchronization algorithm (section 7.4). Basically, the server remembers the last value $C$ of the counter for which a correct password was presented. When a new password is to be verified, the server tries $C+1$, $C+2$... until one matches, or $C+w$ is reached for some $w$ called the "window size".

The intended scenario is the following: the client has a handheld device which outputs the successive passwords, one new password per button-press. The client may press the button a few times between two login attempts. The server "bets" that the client will not press the button more than, say, 100 times before attempting to log in again: so the server uses $w = 100$. If you let your 3-year-old nephew play with your HOTP device a whole afternoon, chances are that it will be too much desynchronized, and login will not work any longer.

The server wants to keep $w$ small, because:

The raw effect of $w$ is that, at any time, the server will accept $w$ possible passwords; the higher $w$ is, the higher is the risk that an attacker trying random passwords may log in.
The computational cost on the server in case of a wrong password is proportional to $w$.

but $w$ must not be too small, because a desynchronized device implies extra costs (more work for the help desk), which should not happen too often, even in the presence of hyperactive infants.

The RFC 4226 contains no instance whatsoever of the word "integrity" so I have no idea what your last question is about.


I only know permutation from mathematics, is it the same here? A permutation of "abc" is: abc, acb, cab, bac, bca, cba Is the same logic applied in Keccak?

It's a slightly different sense of the word permutation that's in play here.  The initial sentence of the Wikipedia entry touches on this:

  In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting.

In your example, the set is $\{a, b, c\}$, and it's already ordered as $abc$, so those other strings are permutations of the set and the string.

In cryptography when we talk about permutations, normally we're talking about sets of binary strings of some fixed length (notation: $\{0,1\}^n$) and a permutation is a bijective function with that set as both domain and codomain.  This is the same sense in which the term is used in abstract algebra:

  In algebra and particularly in group theory, a permutation of a set $S$ is defined as a bijection from $S$ to itself. That is, it is a function from $S$ to $S$ for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of $S$ in which each element $s$ is replaced by the corresponding $f(s)$.

Or, since the elements of a set $\{0,1\}^n$ can be read as numerals, you can read that as a providing an implicit, canonical ordering of the set, where the first element is the numeral for zero, the second element is the numeral for one, and so on.  And in that setting a permutation can be written as a nonrepeating sequence of all the numerals in the set, such that the $i$th element in the set's canonical ordering is substituted with the $i$th element of the sequence that denotes the permutation.

So the specification for Keccak defines certain permutations that are just some standardized functions over binary strings of a fixed length (which the specification defines for several lengths, but the most common is for 1600-bit strings).  These functions are designed to behave as much as possible like a permutation chosen at random from the set of all possible permutations of the same set, but to be efficiently computable.  But one way to reason about how Keccak works is to pretend like the permutation really is a randomly chosen one.  Again, if we think of the bit strings in the set that the Keccak permutation operates on as binary numerals, what the function does is, given any one of these as input, compute the position it would occupy in the randomly shuffled set.


Questions about a SHA3 cipher stream encryption scheme

TL;DR: The idea is good and the implementation should work securely (with a solid security margin), given that some tweaks are implemented.

How secure is it?

  A) If given a large enough password, does this system appear secure?

If you replace "password" with "key", then the answer should be yes.

For analysis purposes, let's define $E_K(M) = \operatorname{MAC}_K(\text{CTR} || \text{Nonce})\oplus M$, with $\operatorname{MAC}_K(M) = \operatorname{Keccak}(K||M)$. The nonce is message based and the counter is call-based, i.e. the counter increases by one every 512 bit. The MAC was already analyzed here.

Let's further define $E^A_K(M) = \text{Nonce}||E_{K1}(M)||MAC_K(E_{K2}(M))$ which is the full authenticated encryption mode. Note that I have used different keys here for authentication and for encryption. This removes potentially dangerous dependencies between the two components. Not furthar that the order of key and ciphertext was swapped for the authentication to obtain more consistency and don't do potentially dangerous things.

The encryption component of the above is basically CTR-Mode, with a split-up counter where one part is "static" and one part is "dynamic", like is done in GCM. As you properly randomize it using the nonce and the counter, this is a proper instance and therefore the standard security bound of $2^{n/2}$ (for non-permutations) holds, i.e. the encryption strength is 256-bit. This is is due to the fact that you expect collisions from the hash after roughly $2^{n/2}$ invocations with different values and thereby can derive information about the plaintext from this. As for the authentication, at least collision attacks are required to break the standard encrypt-then-mac, also giving (at least) 256-bit security.

If you truncate the output of the hash function, security will decrease accordingly. SHA-3-256 would only yield 128-bit strength, as you'd expect collisons after only $2^{128}$ calls instead of $2^{256}$.

Potential Improvements

Make the keys independent.
Make the order of arguments to the hash consistent (i.e. always the key first)
Take associcated data (AD) into account, especially the nonce should always be authenticated.

Real Life applications

If this wasn't for demonstrations purposes you should strongly avoid rolling your own crypto and rather use AES-GCM (which should be faster anyways), any standard AES authenticated encryption scheme, Keyak or the scheme linked by otus in the comments: "Duplexing the sponge: single-pass authenticated encryption and other applications" by Bertoni, Daemen et. al.


In cryptographic protocols, what protects against an attacker dropping messages?

Not much in the cryptographic protocols themselves. But you can do other things to get around such attacks:

Request signed read receipts, or received receipts. So, if I send a message from my phone to yours, it sends back a reply that your phone has received the message (or that you have opened it). If such a receipt is signed, your attacker might be able to drop the messages, but won't be able to hide that fact from you.
Have another mode of communication to verify. I'll send you a message over wifi, and if I can't verify whether or not you received it over wifi, I will send you a text message over my cellular network. I might even call you. Hopefully, your attacker doesn't have serious control over both networks.
Distribute the work of sending the message broadly. Send each message through multiple channels through a protocol that can handle such sending without displaying the same message multiple times. Perhaps this protocol is advanced enough to make sure that no one party sees all of its traffic... otherwise, you're living in a post-apocalyptic world much like the one we happen to be in. Whoops.

At the end of the day, this would probably only be an issue if you're a competitor of Verizon's or a merged TWC/Comcast, or something like that. Maybe Microsoft could build some such bullshit into Windows. But none of those corporations would, because they'd be hit with gigantic criminal sanctions and civil lawsuits and face legitimate market harms as well.

But... I don't think cryptography is meant to handle this problem.


why doesn't quadratic residue attack work with Elgamal encryption with decisional diffie Hellman assumption?

The difference is to which groups we think the assumption applies.

The discrete logarithm assumption is thought to apply to groups of the form $\mathbb{Z}_p^*$ with $p$ prime, amongst others. As explained in the linked lecture notes, there exist polynomial time algorithms that determine whether $m_b$ is a quadratic residue. This is sufficient to rule out half of the possible plaintexts, because in groups modulo a prime, exactly half of the elements are quadratic residues. Given this counterexample, the discrete logarithm assumption is consequently not sufficient to achieve semantic security.

The Decisional Diffie-Hellman assumption does not apply to groups $\mathbb{Z}_p^*$ with $p$ prime, but it is thought to apply to other groups -- the ones typically use for ElGamel. The DDH assumption is a stronger assumption that applies to some of the groups where the discrete logarithm assumption holds.

In particular, if the DDH assumption holds, we can prove that there cannot exist a polynomial time algorithm that determines whether an element is a quadratic residue. This necessarily disproves the DDH assumption for groups $\mathbb{Z}_p^*$ with $p$ prime.

So long story short, if the DDH assumption holds, then the attacker cannot perform the attack using quadratic residues in polynomial time, or in fact even distinguish chosen plaintexts in polynomial time. However, the DDH assumption does not hold for all groups where the discrete logarithm assumption holds, and for some of those groups where the DDH assumption does not hold, an attacker can perform the attack in polynomial time.


Efficiently show/prove knowledge of third party secret without leaking information

Public-key cryptography is not sufficiently computationally burdensome to where other approaches must be used for authentication protocols. Note though that what you describe is not actually public-key based. The verification of the MAC requires Dave and Bob to both have a shared key. Also, note that a random component must be included in some manner in all authentication protocols, else an attacker will be able to mount a man-in-the-middle attack and/or reuse the authentication string in the future. However, similar schemes that are based purely on public-key algorithms do exist, and are more commonly used. Either way, Alice is acting as a $TA$, verifying Bob's identity through some secondary channel and publishing a mechanism by which Dave can confirm that the owner of Bob's private signature algorithm (presumably Bob) is in fact Bob.

In this case, the computationally burdensome process, generating public-private key pairs, occurs not every time authentication takes place, but only when Bob asks Alice for a certificate. Also note that generating public-private key pairs is not particularly expensive, provided access to either an efficient cryptographically secure random number generator or a large pool of entropy, both of which are relatively easy to have.

Beyond that, public-key algorithms are designed so that the encryption and decryption processes can be computed efficiently. For instance, RSA and other Discrete Logarithm based problems have square-and-multiply or some variant. As such, the actual signing and verification step for Bob and Dave is quite simple and efficient, and there are a number of schemes which require only the limited computing power of say, smart cards.


Calculate a base point on the twist of secp192k1 with maximal order

Let $\beta$ a non-square element in $\mathbf{F}_p$, then the elliptic curve defined by $\beta y^2 = x^3 + 3$ is a quadratic twist of secp192k1 whose equation is $y^2 = x^3 + 3$.
It means that if $x_0^3 + 3$ is a square, there exists $y_0 \in \mathbf{F}_p$ that is a square root of $x_0^3 + 3$, so $(x_0, y_0)$ belongs to secp192k1, and on the other hand if $x_0^3 + 3$ is not a square, there exists $y_0$ such that $\beta y_0^2 = x_0^3 + 3$, so $(x_0, y_0)$ lies on the quadratic twist instead. Here, we can take $\beta = -1$ since it is not a square in the finite field $\mathbf{F}_p$.
There is a relation between the cardinality (number of points) with the quadratic twist. The cardinality of secp192k1 is a prime number $n$, that can be rewritten as
$$
n = p + 1 - t,
$$
where the value $t$ is called the trace of Frobenius. Then it is easy to compute the cardinality $n'$ of the quadratic twist:
$$
\begin{align}
n' & = p + 1 + t, \\
& = 3 \cdot 373 \cdot 56383 \cdot 619124299 \cdot 160695254510139039862526647837522958722153.
\end{align}
$$
Write $n'= h\cdot q$ where $q$ is the largest prime in the decomposition. The goal is to find a point of order $q$ on the twist. Let's use SageMath for the computation, but unfortunately it does not handle elliptic curves with an equation of the form $-y^2 = x^3 + 3$. That's not a problem, a simple change of variable will do the trick: let $x'=-x$, and the equation becomes $-y^2 = -x'^3 + 3$, and by multiplying each side by $-1$ we get $y^2 = x'^3 - 3$.
We can make some check that all is good:
p = 2**192 - 2**32 - 2**12 - 2**8 - 2**7 - 2**6 - 2**3 - 1
E = EllipticCurve(GF(p), [0, 3])
n = E.cardinality()
print(n.is_prime())
t = p + 1 - n
Et = EllipticCurve(GF(p), [0, -3])
nn = Et.cardinality()
print(nn == p + 1 + t)
print(Et.is_quadratic_twist(E))

The last command returns a nonzero value if the two curves are indeed a quadratic twist of each other.
To find a point whose order is the largest prime $q$, we can run something similar as in this post.

Generate a random point on the twist;
Compute $Q = [h]P$;
If $Q \neq \mathcal{O}$, then $Q$ is a point of order $q$.

h = 39062147507228523
q = 160695254510139039862526647837522958722153
while True:
    P = Et.random_element()
    Q = h*P
    if Q != Et(0):
        break
print(Q)
print(Q.order() == q)


Can I verify that digital object exists before a given date?

You can do all sorts of verification with a time stamped hash and signed hash, but it can't be a NYT headline. Just as MD5 hashing is now considered insecure and ineffective, the block width of a NYT headline is insufficient. Actually, the input entropy of the textual headline is only a few tens of bits.  "Trump Convicted" does not hold a lot of entropy, which means that another headline at another time might hash to exactly the same value.

You also can't do what all good kidnapper's do and take a photo of the paper's front page alongside your object. This isn't just for the obvious reason that it's digital, but noise and the avalanche effect will ensure that you'll never manage to exactly replicate the image for future verification.

The thing to do is to hash sufficient cohesive public data. Something like the FTSE 250 list of share prices (at the time of hashing and signing) contains enough entropy to make collisions impossible. There's over 8000 bits of pure entropy available there by my calculation. That's sufficient for any possible cryptographic use.  The Million Dollar elliptic curve purports to use public lottery results but that must be  very cumbersome to collate. The music industry uses almost imperceptible fluctuations in the mains frequency to watermark tracks. A frequency vs. time curve could be hashed and keyed alongside the object. Object dating could be achieved for the timespan of available records.

So for example, to check if your object existed at any particular time you'd simply hash and key against all the records you have available. A hash match at a particular time would prove the existence of that object at that time.  You might be able to check with a 15 minute granularity for FTSE250 share prices. Again the most important thing is to hash against sufficient entropy to preclude manufactured collisions. Clearly you can't use this technique if you don't have reliable digital entropy for the time period under consideration.


Security Strength of Double Substitution Ciphers

I am wondering why people are using RSA keys when some types of double substitution ciphers seem to be just as secure if not better off.

First of all, RSA is an asymmetric cipher while a substitution cipher is a symmetric cipher. Asymmetric ciphers are used to achieve different security needs, e.g. TLS authentication or non-repudiation of documents. Or, more closely related, the encryption for one specific person without that person having to hand you their private key.

So no matter how secure your cipher would be, it would still be a symmetric cipher and could therefore not replace RSA.

  This method would render any method I know for deciphering codes useless, and I was wondering if there is a method I am missing or if this is actually a very strong method of encryption.

Bruce Schneiers law: "Anyone can invent a security system that he himself cannot break"

As already indicated, a cipher requires a key because of Kerckhoffs principle. An algorithm that doesn't require a key will be broken as somebody will likely leak the algorithm itself in time.

Even if there was a key, I don't think your scheme would even survive the most basic of attacks such as frequency analysis. More advanced algorithms would require multiple rounds, transposition etc.

As you don't include a nonce or random input to your cipher, your cipher would already be considered broken because identical plaintext would lead to identical ciphertext. This means you are leaking information about the plaintext. This is why stream ciphers or block cipher modes of operations require either a different key for each encryption process (notably RC4) or a unique/unpredictable nonce or IV.

To get any idea of the complexity you could take a look at the book that describes The Design of Rijndael (by the authors of Rijndael, which became AES).


Assuming that . represents concatenation, no, except in the specific case that $arg1 is the empty string.  You're trying to perform a preimage attack, which is one of the things that SHA512 is designed to be resistant to.

Further, knowing $arg2 and $arg3 does not let you speed up a brute-force attack on $arg1, because for each candidate value for $arg1, $arg2 and $arg3 will modify the checksum differently.  (If you knew $arg1 and $arg2 and were looking for $arg3, you could precompute the partial checksum of the first two values as the starting point for each try at finding $arg3)


Boolean circuits and arithmetic circuits are two different ways of representing a computation. The main difference is with respect to their input types and their gate types: boolean circuits work on bit inputs, and the gates of the circuit correspond to boolean operations (such as XOR, AND). On the other hand, arithmetic circuits work on inputs that are elements of some field $\mathbb{F}$, and the gates of the circuit correspond to arithmetic operations, id est, field operations (such as additions and multiplications).

The class of functions that can be computed by Boolean circuits of polynomial size coincide with the class of functions computable by arithmetic circuits of polynomial size. Indeed, one can always use some representation of the field elements and translate the field operations to boolean operations (with a blow-up polynomial in the length of field elements). Conversely, one can always translate a boolean circuit to an arithmetic one, by interpreting $0$ as the neutral for addition over $\mathbb{F}$, $1$ as the neutral for multiplication over $\mathbb{F}$, and translating the boolean gates to arithmetic operations (e.g. $a\phantom{i}\mathsf{OR}\phantom{i}b$ becomes $a + b - a*b$).

Deciding whether a boolean circuit is better than an arithmetic circuit in a particular application depends on the type of computation you want to perform. In cryptography, it is quite common to rely on computation on-field elements, and we have cryptographic tools that allow us to manipulate field elements in an atomic way, id est, treating a given field element as a single input (and not as a string of bits). In this case, it makes sense to represent the computation with an arithmetic circuit. However, many applications of, say, secure computation involve non-arithmetic operations (for example, integer comparison, which is a basic procedure in many computations). In this case, implementing this non-arithmetic operation as an arithmetic one would be very inefficient, and boolean circuits are more natural representations.

Another way of seeing it is the following: arithmetic circuits are a generalization of boolean circuits to arbitrary fields; boolean circuits correspond to arithmetic circuits over the field $\mathbb{F}_2$. There have been many papers that worked on extending cryptographic methods that work well for computations represented as boolean circuit to the setting of computations which are best captured by arithmetic circuits, to get efficiency improvements for those circuits (e.g. Yao's garbled circuit method has been extended to garbled arithmetic circuits), or on bridging between methods adapted to boolean circuits and methods adapted to arithmetic circuits, to capture computation whose best representation is a mix between the two.

Answering a question in comments

  I am looking for a reference that establishes the result that "the class of functions that can be computed by Boolean circuits of polynomial size coincide with the class of functions computable by arithmetic circuits of polynomial size". Can you provide a reference to a book or a scientific paper? My search was without success...

As I mentioned in the comment, you will likely not find a reference because the result is folklore. Fix an arbitrary field $(\mathbb{F}, +, \cdot)$ and consider a function $f$ which can be computed by a boolean circuit of size polynomial in its input size, say, over the standard basis $\{\mathsf{XOR}, \mathsf{AND}, \mathsf{NOT}\}$. To emulate the computation over $\mathbb{F}$, encode the bit $0$ as $0_\mathbb{F}$ (the neutral for addition in $\mathbb{F}$) and the bit $1$ as $1_\mathbb{F}$ (the neutral for multiplication). The boolean gates can be emulated as follows:

To compute an $\mathsf{AND}$ gate on input $(x,y)$, return $x \cdot y$
To compute an $\mathsf{XOR}$ gate on input $(x,y)$, return $x + y - 2\cdot x\cdot y$
To compute a $\mathsf{NOT}$ gate on input $x$, return $1_\mathbb{F}-x$.

I'll let you check that this correctly emulates the boolean operations. Since emulating each boolean gate requires at most 4 arithmetic operations, the arithmetic circuit emulating the boolean circuit over $\mathbb{F}$ is of polynomial size as long as the boolean circuit is polynomial size. The converse direction is trivial since a boolean circuit is just an arithmetic circuit over $\mathbb{F}_2$.

For the sake of generality, I'll add that you can generally emulate field operations over an arbitrary field $\mathbb{F}$ using boolean circuit; indeed, this is what your computer is doing every day: fix a field $\mathbb{F}$, and consider the binary decomposition of any element $x$ of $\mathbb{F}$: $x = \sum_{i=0}^{\lceil \log |\mathbb{F}| \rceil-1} b_i \cdot 2^i$, with $b_i \in \{0_\mathbb{F}, 1_\mathbb{F}\}$.

To emulate addition over $\mathbb{F}$, use the schoolbook binary addition method, which only requires using $\mathsf{XOR}$ and $\mathsf{AND}$ gates, by observing that $\mathsf{XOR}$ gives you the $i$-th value, while $\mathsf{AND}$ gives you the $i$-th carry.
To emulate a multiplication over $\mathbb{F}$, use the textbook multiplication algorithm, which relies only on $\mathsf{AND}$ gates plus field additions, which we already showed can be emulated.

Overall, the size increase is dominated by the $O(\log^2 |\mathbb{F}|)$ cost for the schoolbook binary multiplication.


Calculation of the avalanche effect coefficient

I believe the only way you can do this is to assume you have fixed length inputs to the hash function $f$. Otherwise, it is problematic what probability distribution you'd want to impose on the input set $\{0,1\}^{\ast}$ which is the collection of all finite input strings. In practice, hash functions do have an upper limit on the input string, but that's astronomical, in terms of testing all input strings.

So, let's assume the hash function has security parameter of $k$ bits. This corresponds to the function acting like a random function with outputs of length $n=2k$ bits.

Your testing would generate a large number of random values from a uniform  distribution on $\{0,1\}^{m},$ thus treating the hash function as a random function $f:\{0,1\}^m\rightarrow \{0,1\}^n.$ Let this random set of inputs be denoted by $X$. Now define
$$
a_{ij}=\#\{x \in X:[f(x\oplus e_i)]_j \neq [f(x)]_j\}
$$
for $1\leq i\leq n,1\leq j\leq m,$
where $e_i$ is the vector with a one in the $i^{th}$ position and zeroes everywhere and $[u]_j$ denotes the $j^{th}$ component of vector $u$. $a_{ij}$ counts the number of inputs from $X$ which differ in the $j^{th}$ output bit when the $i^{th}$ input bit is flipped.

You can now define a degree of strict avalanche criterion $D_{SAC}(f)$ as
$$
D_{SAC}(f):=1-\frac{\sum_{i=1}^n \sum_{j=1}^n \left|\frac{2a_{ij}}{\#X}-1\right|}{nm},
$$
with the expectation that $D_{SAC}(f)$ should be approximately 1, i.e., the sum of the absolute differences $$\left|\frac{2a_{ij}}{\#X}-1\right|$$ over $i$ and $j$ should be small. One way of expressing this may be to say $E[A_{ij}] \approx (\#X/2)$ if $A_{ij}$ is a random variable representing the $a_{ij}$ with $A_{ij}$ distributed as the binomial variable $Bin(\#X,1/2).$ From here you can then model the overall experiment in terms of chi squared variables, by using the Gaussian approximation to the binomial. So take the properly scaled $nm$ variables as being from a chisquared distribution with $nm-1$ degrees of freedom.


Can homomorphic encryption offer program integrity and program obfuscation?

If the homomorphic evaluation procedure is deterministic, as is usually the case, the program integrity requirement is trivially fulfilled: given a function $f$, the input ciphertext $C$ and the output ciphertext $C'$, anyone can publicly evaluate $f$ on $C$ (homomorphically) and check that the result is indeed $C'$. However, this conflicts with a standard other requirement, where one wants the output $C'$ to be distributed as an encryption with uniformly random coins.

When the output ciphertext is randomized, to ensure program integrity, the usual strategy is to use a zero-knowledge proof system. Namely, given a function $f$, the input ciphertext $C$ and the output ciphertext $C'$, the homomorphic evaluator will prove in zero-knowledge that $C'$ was obtained as the result of homomorphically evaluating $f$ on $C$ (and randomizing the output). Many solutions exist to implement this, depending on the other constraints (e.g. if we want this verification to be less expensive than performing the entire homomorphic evaluation, on can use succinct zero-knowledge proofs).

Regarding your 'program obfuscation' requirement, this sounds like what is usually called circuit privacy (i.e., when evaluating $f$ on $C$ homomorphically and getting an output $C'$, seeing $(C,C')$ should leak nothing about $f$). Any 'partially homomorphic' encryption scheme we know of (Paillier, ElGamal, Goldwasser-Micali, and the like) is re-randomizable (given a ciphertext $C$, anyone can publicly construct a ciphertext $C'$ encrypting the same value with uniformly distributed random coins), hence can be trivially made circuit-private. For fully homomorphic encryption, it's a bit more complex, but there are also well-established techniques, such as using noise flooding, or some more advanced strategies such as this one.


Therefore, the cipher must be decrypted in order to verify its integrity?

No, there is no such requirement.  As you state, the authentication tag is calculated from the ciphertext blocks, however, the receiver does not have to decrypt anything to get the value of the ciphertext blocks - he gets those directly.
One of the things that appear to be confusing you is that the diagram is the processing that occurs during encryption, not decryption.
For GCM decryption, the authentication block is validated this way: he takes the ciphertext (and the AAD), and repeatedly does MULTH and ADD [1] operations, then he MULTH and ADDs the AAD/ciphertext len, and then a MULTH and ADD of the processed nonce.  No decryption of ciphertext need to be done.
[1]: I say "ADD" even though it is really XOR; we're working in $GF(2^{128})$, and so field addition is xor.


Why do we truncate the hash when using DSA?

During verification you perform $u_1 = H ( m ) w \bmod{q}$ would return the same $u_1$ for  multiple hash values. In general you only want one hash to succeed, even if it is unlikely that an adversary can generate a hash that equals $n q + H(m) w$.

Of course this means that any hash with the leftmost bits identical to the org. hash is also acceptable, but at least you don't have to perform $\bmod{q}$ over an extensively large number.

For modular arithmetic any input (base value for modular exponentiation) larger than the modulus contains spurious information.


Some of your conditions are already met by the definition of an encryption scheme:

Encryption has to be reversible, so that a ciphertext can be the encryption of (at most) one plaintext.
Your last point is basically just a ciphertext only attack. That is usually the weakest considered attack, and for todays security definitions not enough. So any scheme which is considered secure, it also includes this.

The only non-trivial part is your first point, because it is not that easy to find an encryption scheme, which has ciphertexts of 32 or 64 bit length. Of course you could use 3DES (64 bit), but that should not be recommended any more today. But there are other options:

Stream ciphers don't expand the ciphertext. When choosing a stream cipher, use a current one, and consider to use keystream btis beginning after some threshold. RC4 is popular but has quite a few security problems.
Using a block cipher in OFB, CTR (or KFB) mode of operation functions very similar to stream ciphers, and you can just drop the bits you don't need.
Format preserving encryption is a method which enables you to have that 32 bit to 32 bit relationship. But there are a lot of constructions, and quite a few build upon the other mentioned methods.


What key length has to be send to a recipient when using a stream cipher?

I think what you have here is a confusion about terminology. Here's standard terminology:

Keystream: The thing that's the length of the message that you XOR with the message. Must remain secret; should really not be sent to the other person (if you do, may as well just use a OTP). This is not the key, and is not referred to as such.
Key: That secret information that both parties must know before they can communicate. Must remain secret; does not, in general, suffice to determine the keystream. This is the only secret information that you generally should share before doing the encryption.
Initial state: I'm not sure if this is actually a formal term, but this refers to the initial state of the CSPRNG that makes up the stream cipher. Always depends on key; may or may not actually include the key (RC4's initial state is constructed using the key, but the key itself isn't part of it -- rather, there's an algorithm that starts with a fixed state and mixes in the key before starting the main CSPRNG). Also often depends on other parameters; RC4 just takes one input, but with Salsa20 you have key, nonce, and a fixed component in it (you also have a stream position component there, but that's because Salsa20 does 512 bits at a time, so the stream position is because you initialize the CSPRNG many times in a message). You generally don't send this; you don't care what the initial state is, that's an internal detail of the algorithm. All you send is the information the algorithm needs to construct it, some of which is secret.

Also, since I used the term:

Nonce: A number used only once; in this case, it's a stream-specific number that is never, ever, ever reused with the same key, and is used to allow multiple messages to be sent with the same key. Also called the IV in some cases. With RC4, it's just part of the "key" the cipher expects, and the secret key is the rest of the "key" the cipher expects; in other stream ciphers, this is explicitly part of the algorithm. However, when using RC4 with a nonce (e.g. in WEP), the key is different from the key fed into the RC4 algorithm itself; it's still just the secret part (i.e. if you have RC4-128, with a 32-bit nonce, you're feeding 128 bits into the RC4 algorithm but your key is just 96 bits). Nonces are not secret.

To communicate, you need to send the key in secret, and whatever nonce material you're using for that message (this can be in the clear). You don't send keystream, and don't send internal state.


How are the names of cryptographic algorithms (like RSA, AES, SHA-256, Curve25519, etc.) pronounced?

However you pronounce them, the important thing is to make sure that your listeners understand you.  In general, it's never wrong to pronounce acronyms letter by letter (and digit by digit), as in:

RSA → "arr ess ay"
AES → "ay ee ess"
SHA-1 → "ess aitch ay one"
SHA-256 → "ess aitch ay two five six" (or "ess aitch ay two fifty six" or even "ess aitch ay two hundred and fifty six")

If the acronym could also be pronounced as a word, and the resulting pronunciation is clear and distinct enough, you can also do that.  So "shuh two fifty-six" for SHA-256 is OK, too.  Certainly this is true for longer acronyms that "just happen to" spell out an English word; I'd much rather hear e.g. SHAKE256 pronounced "shake two fifty six" than "ess aitch ay kay ee two five six", even if the latter isn't strictly speaking wrong, either.

Curve25519 is a bit of a special case.  Obviously the word "curve" should be pronounced as the English word, and I would say that it's perfectly fine to just read out the numbers one by one, as in "curve two five five one nine", although "curve two five five nineteen" or "curve two fifty five nineteen" would also be OK.

As yyyyyyy notes in the comments, though, the number 25519 in the name is really made up of the two numbers 255 and 19, so you should not read it as e.g. "curve twenty-five thousand five hundred and nineteen".  You can thank D.J. Bernstein for this naming ambiguity; his Poly1305 MAC is arguably even worse named, since the two numbers concatenated into that name are 130 and 5, but pronouncing it e.g. as "poly one thirty five" would just invite naïve listeners into parsing it as "Poly135".  I don't know how DJB himself pronounces that name, but I'd probably just read it digit by digit as "poly one three oh five". Peter Schwabe pronounces it at "poly thirteen oh five".

Of course, where it gets really tricky are names like Rijndael or Grøstl which are not acronyms, and which even (or perhaps especially) native English speakers have trouble pronouncing.  In those cases, I'd suggest either looking up an audio sample of the "official" pronunciation and imitating it as well as you can, or just giving up and pronouncing the name according to the standard pronunciation in whatever language you're speaking.


Is AES solvable in this way? In other words, will the algorithm eventually complete, producing the correct key?

Almost yes. It will produce some correct key — there might be more than one.

(It should quite plausibly be unique given "enough" plaintext-ciphertext samples, but this need not be the case in general.)

Generally, computing the key in a known-plaintext scenario is in $\mathbf{NP}$, hence can by definition be reduced to any $\mathbf{NP}$-complete problem such as $\mathrm{SAT}$. If this is done correctly, solving the $\mathrm{SAT}$ instance is bound to produce a correct key — but fortunately, doing so is not at all practical to the best of our current knowledge.

(If it turned out that $\mathbf P=\mathbf{NP}$, this would potentially change that picture a bit, but in that case we are doomed anyway.)

Therefore the short answer is: Yes, but it doesn't help.


In CBC mode if 2 cipher blocks are same then is CBC still secure?

if there is a $P_i \oplus P_j= C_{i−1}\oplus C_{j−1}$ relationship, is CBC still secure?

As commented by SqueamishOssifrage standard collision of $2^{64}$ blocks for a 128-bit block cipher is not a hard limit. We want a negligible success for the adversaries. With $q$ queries ( encryptions) the advantage of the adversary must be negligible like $2^{-32}$ or $2^{-64}$.

To achieve this we need

$q^2/2^{128} = 1/2^{64}$ that is $q=2^{32}$, or
$q^2/2^{128} = 1/2^{32}$ that is $q=2^{48}$

Therefore you should not encrypt more than $2^{32}$ or $2^{48}$ block depending on the advantage settings of the adversary.

The CBC mode has more problems than this;

The IV must be unpredictable.
The padding oracle attacks on servers.
The BEAST and Lucky13 attacks on TLS only.

And, therefore CBC mode is removed from TLS 1.3. CBC mode is archaic. Today, you should use Authenticated Encryption as AES-GCM or ChaCha20-Poly1305.

  How does this equality lead to information leak?

You have a relation $P_{i}\oplus P_j=C_{i-1}\oplus C_{j-1}$ in which you know
$C_{i-1} \text{ and } C_{j-1}$ then you know the $\oplus$ difference of the two plaintext. In AES, you will have at most 128-bit to apply crib-dragging attack like in OPT. If you know one of the plaintext you know the other.


What are the differences Between “White-Box Cryptography” and “Code Obfuscation”?

As you suspected, there's a very close relationship between white-box cryptography and obfuscation.  (Good instincts!)  White-box cryptography is basically all about obfuscating an encryption implementation.

White-box cryptography is obfuscation of crypto code. Imagine that you took an AES implementation, picked a random AES key, and then hardcoded that AES key into the code.  Obviously, publishing this code would be insecure, because it would immediately reveal the AES secret key.  It might be nice if we could obfuscate the resulting code, hardcoded key and all, in a way that preserves its function but hides the encryption key.  In other words, the result should be obfuscated code, which still computes the same function, but no longer reveals the AES key.  This is exactly what "white-box cryptography" does -- or, at least, what it tries to achieve.

So you can view white-box cryptography as a special-purpose obfuscation method, designed for obfuscating a very specific kind of code.

More background. There's a lot more that can be said about white-box cryptography.  For instance, many published methods for white-box cryptography have been broken; both white-box AES and white-box DES have been cryptanalyzed and are now known to be insecure.  As far as I know, every published approach to white-box cryptography has subsequently been broken, so it is not known whether it is possible to achieve the goals of white-box cryptography securely.

Here is an outstanding overview and introduction to white-box cryptography:

Marc Joye, On White-Box Cryptography.  Security of Information and Networks, 2008.


EAX vs CTR vs XTS + cascade ciphers in disk encryption hell

This would allow my system to stay secure even if one of these ciphers has been broken, right?

Most likely, however one can construct situations where the cascade is only as strong as the first cipher.

  If so, EAX is arguably better than XTS, isn't it?

It is.

  Are there maturity issues?

No, it actually has a security proof for the strongest notion for a symmetric encrytion scheme, namely as an authenticated encryption scheme assuming the used block cipher is secure.

  Why is it so unpopular?

In general because AES-GCM / ChaCha-Poly1305 is faster with similar security properties. In this specific case of disk encryption because it incurs 16 bytes of overhead per authenticated message. These 16 bytes are really annoying in disk encryption. They mean that either the disk encryption software has to offer a smaller, non-standard sector size which may not be supported by the OS or it has to remove a linear amount of storage from your disk as well as completely break most performance assumptions by requiring two sector accesses by logical sector access.

Most people are not willing to sacrifice ~1% of their disk space and take the high performance stemming from the extra sector accesses for a defense against a rare attack scenario of manipulation attacks.

  Is it possible to use a more sophisticated hashing algorithm like bcrypt instead?

Theoretically? Absolutely. Practically? Your disk encryption software simply has to support it.


Can I use different initialization vectors (IV) for the same data in AES-CBC?

Yes, this is fine and you should always use a random IV, irregardless of the plaintext.

  The problem is: if I save the same data with the same key several times, I generate different encrypted data.

That's usually a good property to have.

When this property does not hold, it is possible to know when a pair of plaintexts is equal (without knowing the value of plaintexts). That can be a pretty important finding if the set of messages is small (example: something that encrypts "yes" or "no").


Is the statement true in the context of AES-256 encrypted data stored on a hacked server?

Important note: as long as the data on the server (name of platform) is encrypted and the decryption key safely stored elsewhere according to protocols established, it does not matter (from an access to the data perspective) if the account on the server is hacked. In that case the real protection for the data is the encryption, not the server itself, although it does act as an additional layer of security.

Yes and ... No.

Could you define what do you mean by access to the data perspective ? By whom ?

You need to have a clear definition of the properties you want to guarantee. In cryptography there are 3 essential properties.

confidentiality: only the authorized users can read the data (and understand it).

integrity: the users have the guarantee that the data have not been modified, or in other words only the authorized users can modify the data.

authenticity: the users have the guarantee that the data/entities are who they are (this is different from identification).

In the case you are talking about, you only implies that you are providing confidentiality but no integrity. In other word, an attacker could access the data, not be able to read it but could still modify it. Note also that the property access to the data perspective is not provided anymore to the authorized user in the case where the data have been modified.

Thus in my opinion, you should slightly improve the text to say that you don't provide the integrity in this case (or use an Authenticated Encryption Scheme). It might also be a good idea to use the vocabulary previously defined (confidentiality and integrity).


What is the best way to send two floating point numbers to a server on the internet from a small device such as an arduino?

You have to define precisely what Eve can and cannot do. For instance, has Eve occasional physical access to the Arduino-based device ? If yes, then she can (at least conceptually) grab the device, "open" it, extract the shared secret, and replace the device with one of here own which does the same job, except that it also sends a copy of the data to another server that Eve controls. Arguably, she could also add her own measuring device along yours, to achieve the same effect. This would be a quite hard security model.

If Eve does not have occasional physical access to the device, then the "shared secret" model is fine. You still want to be careful with the secret; e.g., if you deploy several Arduino-based devices, have each of them use its own secret key, uncorrelated with the secrets in the other devices.

As for the encryption part:

You do want an integrity check, i.e. a Message Authentication Code. Otherwise, Eve could, for instance, intercept messages and replace them with older messages. Eve would not directly learn the data, but that would probably be harmful to your system.
You need either some randomness to each message, or some memory on the device, to avoid problem. Without either, the same pair of temperature values would yield the same encrypted message, and this would be visible to Eve. Actually, if you use only randomness but no memory, Eve could reorder messages at will, which could also be a problem. By "memory" I mean that the device must be able to store a value and change it, and such that the storage resists reboots.

Here is a specific scheme which will ensure security: to encrypt a pair of temperature values, encode them into a 128-bit word containing, in that order: the first temperature (over 24 bits), the second temperature (24 bits), a field containing only zeroes (48 bits), and counter (32 bits). Then encrypt this as one block with AES (the key being the secret shared between the device and the server). This yields a 128-bit value which you can send to the server. The counter must be managed with some care:

The counter must start at 0. For every message, the counter must be incremented. It must not be possible to "reset" the counter to a previous value, even in case of temporary power loss.
The server must verify, upon decryption, that the field containing zeroes indeed contains only zeroes. That's what serves as a MAC.
The server must store the counter value from the last received message from the device. The new message is accepted only if it has a counter value which is greater than the stored counter value. (Potentially, the server could enforce stricter rules, e.g. refusing to increase the counter value by more than 100 as well.)

Under these conditions, the device will be good for four billions of messages or so. Even if it sends one message every second, this will still take 120 years before running out of counter values.

Security comes from the indistinguishability of AES from a random permutation over the space of 128-bit blocks. It would not work with a block cipher with smaller blocks, e.g. DES (or TripleDES). Also, the "zero-field" which serves as a MAC must not be too short; Eve could send messages with random junk, and a 48-bit field means that the risks of seeing one such message accepted by the server as genuine are around $2^{-48}$ -- since each message has length 16 bytes, it would take on average $2^{52}$ bytes (4000 terabytes) for Eve to succeed. 4000 terabytes, that's huge, but not impossibly huge. If you shorten this field to, say, 30 bytes, then these become 16 gigabytes, and that's highly doable.


Create big random number from 2 smaller numbers?

Raising to powers isn't how you'd want to go about it. For instance, lets say my true random number generator gave me x=3 and y=5, and lets say it usually generates numbers between 0 and 7. That's 3 bits of randomness per value. If I generate two of them, I will have 6 bits of randomness. If I output x^y as the result, then it has the potential to output anything from 1 to 823543 (7^7). This is around a 20 bit value coming from only 6 bits of entropy (the technical term for randomness). This will be very biased.

A better way, if your RNG (random number generator) outputs with a range of a power of 2 (1 to 8, 0 to 15, 20 to 23, etc), then you can get the random bits and simply concatenate to get a larger number. For example, from the earlier example, 3 can become "011" and 5 can become "101". The resulting number can then be "011101" or 29. This (assuming the RNG is uniform across 0 and 7) will be uniform across 0 and 63.

However, if your RNG is biased, or outputs with a range that's not a power of 2, then you can use a cryptographic hash function to "mix" the randomness. If your RNG outputs uniformly between 0 and 99 (a range of 100), then each value is 6.6439 ( $log_2(100)$ ) bits of entropy. You can collect enough values to have at least 256 bits (in this case, 39 values) and run them all through a 256 bit hash function (such as SHA256). The output of this will be 256 uniformly distributed bits.

In the last example, it's important to put a delimiter between the random values before hashing them. For instance, if you get the values 3, 6, 5, and 1, then hash "3,6,5,1" not "3651".

Of course, this all assumes you want the output to be truly random. If you're okay with pseudorandom, then you can use the output of your RNG as the seed of a PRNG at a much greater speed.


Difference between Multi-linear and Multi-Secret Sharing Schemes

As quoted by Yang's A (t,n) multi-secret sharing scheme line 76.

In fact, various secret sharing schemes have different approaches.

So by using the term Multi-secret sharing means to share multiple secret by any means. That makes Multi-Linear secret sharing is a subset of Multi-secret sharing.
I'm not 100% sure on this but it appears to me that for Linear secret sharing scheme, it involves solving matrix to find a linear recombination of each part of the secret and used it to reconstruct the hidden secret.
In this sense, Chien's A Practical (t,n) Multi-Secret Sharing Scheme is close to Multi-Linear secret sharing scheme in the sense that it has a matrix and you need to solve an equation to find the secret. The different between the two scheme is on how you construct the matrix.
On the other hand, Yang's work relies on Shamir's Secret Sharing as quoted in line 80.

In this article, we will propose a multi-secret sharing scheme based on Shamir's secret sharing


Where is the S-Box generated in Rijandel/AES?

The S-Box was generated when Rijndael was designed, not in any step.
It's used in every round in the SubBytes step.
The S-box is constant. You could see it as a function taking a byte and returning a byte. It is used to reduce algebraic properties of Rijndael.

In fact, this is it:

   | 0  1  2  3  4  5  6  7  8  9  a  b  c  d  e  f
---|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|--|
00 |63 7c 77 7b f2 6b 6f c5 30 01 67 2b fe d7 ab 76
10 |ca 82 c9 7d fa 59 47 f0 ad d4 a2 af 9c a4 72 c0
20 |b7 fd 93 26 36 3f f7 cc 34 a5 e5 f1 71 d8 31 15
30 |04 c7 23 c3 18 96 05 9a 07 12 80 e2 eb 27 b2 75
40 |09 83 2c 1a 1b 6e 5a a0 52 3b d6 b3 29 e3 2f 84
50 |53 d1 00 ed 20 fc b1 5b 6a cb be 39 4a 4c 58 cf
60 |d0 ef aa fb 43 4d 33 85 45 f9 02 7f 50 3c 9f a8
70 |51 a3 40 8f 92 9d 38 f5 bc b6 da 21 10 ff f3 d2
80 |cd 0c 13 ec 5f 97 44 17 c4 a7 7e 3d 64 5d 19 73
90 |60 81 4f dc 22 2a 90 88 46 ee b8 14 de 5e 0b db
a0 |e0 32 3a 0a 49 06 24 5c c2 d3 ac 62 91 95 e4 79
b0 |e7 c8 37 6d 8d d5 4e a9 6c 56 f4 ea 65 7a ae 08
c0 |ba 78 25 2e 1c a6 b4 c6 e8 dd 74 1f 4b bd 8b 8a
d0 |70 3e b5 66 48 03 f6 0e 61 35 57 b9 86 c1 1d 9e
e0 |e1 f8 98 11 69 d9 8e 94 9b 1e 87 e9 ce 55 28 df
f0 |8c a1 89 0d bf e6 42 68 41 99 2d 0f b0 54 bb 16

You can read it by choosing your column by the low nibble of a byte, and the row by the high nibble of a byte.


Is ChaCha20 safer than AES with respect to side-channel attacks?

It basically depends on what you consider side-channel attacks.

If you consider time/cache side channel attacks than chacha20 has been design with resistance to such attacks in mind while AES didn't.
In fact, AES is vulnerable to these kind of attacks (as they were invented after AES was designed). But, hardware implementations, such as AES-NI are protected because they don't use caches and execute in constant time.

If you consider also power/electromagnetic side-channels then both algorithms are vulnerable and in this sense the community has researched A LOT more on protections for AES then for Chacha20 which will be significantly harder to protected due to its ARX nature which require expensive masking conversions.
So it will be more easy to find protected , pure sw, AES implementations, even in open source. But you need a protected implementation, otherwise you will be vulnerable.

To summarize you have to check which side-channel attacks you want to protect against and the security claims of your implementation. It can't be simplified as "AES needs to use AES-NI" because we can have side-channel protected AES in pure software (see the link above).


Unlikely.
Although they could use the same set of cryptographic algorithms, SSL/TLS use ASN.1-encoded certificates, and recently raw keys (but still using ASN.1 OID algorithm identifiers), but SSH on the other side use its own application-specific format. So the biggest potential problem with your idea would be interoperability.


Is there a maximum number of encryptions I should make with the same RSA key?

No, at least, none that can be practically performed.

For RSA, we assume that the adversary has the public key, and hence is able to generate his own plaintext/ciphertext pairs, and in fact, can do that a huge number of times, should he find that helpful.

Hence, if RSA becomes insecure if you encrypt, say, $2^{80}$ messages, then a large adversary can go ahead and encrypt that many messages himself (and thus obtain whatever weakness that was posited.

The fact that we believe that, say, 3k RSA cannot be broken with less than $O(2^{128})$ operations would therefore say that it's safe to encrypt $2^{128}$ messages (and you'll never ever need to encrypt that many).


Brute force attack on RSA - success criteria?

Well, typically for RSA, we have the public key.  That makes the verification process easy:

If you're trying to guess the private key (factoring or equivilent), that's easy; you just verify the factorization; "does the two primes we get, multiplied together, give us the modulus in the public key?"
If you're trying to guess the padded plaintext that corresponds to a ciphertext, that's easy; you encrypt the padded plaintext with the public key, and if it results in the ciphertext, you guessed it correctly.  Note that, for nondetermanistic padding methods (which is what ought to be used for RSA encryption), you have to guess the nondetermanistic padding bytes as well as the message bytes.
If you're trying to forge an RSA signature, that's easy; you just verify the forgery with the public key.


Why is time-lapse cryptography not popular?

I suspect the main (only?) reason is that nobody's set up the necessary distributed key generation infrastructure.  That's not as easy to do as you might think, since, for the scheme to be practical and credible, the key generation network needs to meet a bunch of challenging requirements:

It needs to be composed of multiple unrelated parties located in separate regions, so that no plausible adversary can compromise a majority of the network (or more than the threshold number of nodes, if lower).  It would also be desirable for most of the parties to be considered generally trustworthy to begin with, but the whole point of the distributed key generation network is to avoid relying on this.
The hardware and software used by the nodes should be as secure and well reviewed as possible, to avoid it being compromised.  Yet, on the other hand, it would be desirable for the nodes to use many independent implementations of the protocol, so that a vulnerability in any single implementation cannot be used to compromise a majority of the network.  These requirements are, alas, even more difficult to realize together than they are separately.
The parties need to be committed to maintaining their nodes: if too many of the nodes participating in the original public key generation cease operating, the private key can never be reconstructed.  It's possible to mitigate this issue somewhat if new nodes enter the network, both by having existing nodes generate new shares for new nodes and by having closing nodes pass on their shares to others.  However, both of these mechanisms also increase the risk of early compromise, so they need to be considered carefully.

The first and second requirements are challenging enough, but not impossible to meet: both the Tor and Bitcoin networks demonstrate that.  However, I suspect that it's the last one that's the killer: all successful distributed crypto networks that I know of contain a large number of ephemeral nodes.  For time-lapse cryptography, most of the nodes need to stick around for however long you want the secrets to be kept.

Another, related problem with Rabin and Thorpe's proposal is that it doesn't really offer any obvious incentive for anyone to commit to maintaining a node.  Contrast that with e.g. Bitcoin, which provides direct financial incentives for keeping the network running, and Tor, which strongly encourages anyone using the network to also participate in it as a relay.

Both of these networks also deliberately keep the barrier of entry very low, something which I wouldn't see as practical with time-lapse cryptography for the reasons described above: if somebody's going to join the network, you want to be reasonably sure that they're going to stick around, and that they're not just the next one in a string of a million sockpuppets created by an attacker.


Why would an Initialization Vector be supplied externally?

It offers more flexibility in using that API. Having a separate IV parameter enables bigger plaintexts than would not be possible in a single invocation, because of for example memory restrictions.

I assume CBC is used. You generate the IV and invoke the encryption on the first part of the big plaintext with the generated IV. For every other part of the plaintext, you take the last block of the previous ciphertext and use it as an IV to get the ciphertext of the current plaintext part. You then concatenate every ciphertext part to get a ciphertext which is the same as you would have got in a single invocation on the complete plaintext.


Are there many permutation polynomials in a field?

For a field $F$ of order $q$, every function from $F$ to $F$ is expressable (uniquely) as a polynomial of order $q-1$.  $q!$ of these will represent permutation polynomials.

Is there anyway to pick uniformly at random permutation polynomial in a field of prime order?

Given a function from $f$ with $f(x_i) = y_i$, it's not difficult to write the polynomial that generates it.  It's just a sum of terms like $(x y_0/x_0)(x-x_1)(x-x_2)(x-x_3)... + (x - x_0)(xy_1/x_1)(x-x_2)(x-x_3)...$.  If you are generating the permutation on the fly, you can compose simpler permutation polynomials.  I don't know if there are more efficient methods.


openssl sha1 message digest not matching with NIST vector input?

You read the testvector incorrectly.

I assume you are referring to the following part of the file SHA1ShortMsg.rsp of the FIPS 180-4 vectors:

[L = 20]

Len = 0
Msg = 00
MD = da39a3ee5e6b4b0d3255bfef95601890afd80709

This test vector has length 0, so the specified hash is for an empty message and not for a single zero byte. This openssl command shows the correct result.

  $ echo -n ""|openssl dgst -sha1
  (stdin)= da39a3ee5e6b4b0d3255bfef95601890afd80709