Cryptographic algorithm for knowing who has more money?

You are looking for Yao's Millionaire Problem:

Yao's Millionaires' problem is a secure multi-party computation problem which was introduced in 1982 by Andrew Yao, a prominent computer scientist and computational theorist. The problem discusses two millionaires, Alice and Bob, who are interested in knowing which of them is richer without revealing their actual wealth.
This problem is analogous to a more general problem where there are two numbers ${\displaystyle a}$ and ${\displaystyle b}$ and the goal is to solve the inequality ${\displaystyle a\geq b}$ without revealing the actual values of ${\displaystyle a}$ and ${\displaystyle b}$.


Is multiple encryption using NaCL and TLS better?

Two things to consider: encryption and authentication.

In general you can only say that a cascade of ciphers is as secure as its weakest link. If the encryption in NaCL had a side-channel attack, it might leak information about the plaintext, whether or not the ciphertext is sent through TLS.
Authentication, on the other hand, is additive. If you can authenticate the message in both TLS and NaCL, breaking one will not allow an attacker to make forgeries.

However, getting any benefit requires that you have set up long term keys in both. Simply sending a NaCL key over a TLS channel allows a man-in-the-middle attack in case TLS is broken. Also, you have to use independent keys or a key recovery attack on any part of the stack may reveal them all.

In practice, a cascade may not help. If the implementations were perfect, it would likely be stronger, but with more things to implement there is also more potential for bugs and they may affect both. For example, Heartbleed would likely have leaked plaintext and keys even if you used an inner encryption layer (because it allowed random memory dumps).

When considering TLS and NaCL, specifically, you should note that some algorithms are used in both:

AES (used in Poly1305 and some TLS suites)
SHA-2 (Curve25519 and at least some TLS suites)

That doesn't matter if you are only concerned about implementation or protocol weaknesses, but means you couldn't claim resistance to one of those being fundamentally broken.


I'm assuming you're referring only to static image manipulation, as that's the common fear these days (terrorists are hiding data in eBay images!)  But it's a mistake to think that images are the only potential carriers of hidden data.  Data can hide wherever information moves, including audio files, DNS requests, TCP port knocking, error codes, URLs, Unicode, spam, anywhere.

LSB is often used in stego demonstrations because it's a simple and understandable example of the idea, but it has a lot of weaknesses that make it less than perfect for real world use.  For one thing, it works directly on bitmaps, but not compressed images.  If the message is short and modifies only the first half of the picture, the top of the image will have a "static" appearance that magically cleans up in the bottom half.  Also, BMPs may themselves be suspicious, as most people use compressed formats such as JPG or PNG.

Using LSB on an ordinary GIF would give you crazy incorrect colors, but you could use a modified palette with 128 duplicated colors to hide the data invisibly.

Both of these are easy experiments to perform and demonstrate to an audience.  You can show them a before and after picture.  You can show them a photo of a clear blue sky over the ocean, then mar the top third with an LSB stego message.  Then show them how a photo of a forest of autumn leaves or a field of wheat makes the effects of LSB stego almost invisible.  Show them how LSB messes with GIF images, then show them a reduced palette image followed by the same image with an LSB stego message.

Messing with JPEG and TIFF formats is technically much more difficult, but in the real world would probably do a better job of remaining hidden.  But they're still detectable to someone looking for them.  Each camera and image manipulation software package uses a custom "quantization table" that says how a block of pixels will be encoded.  Canon's are distinct from Nikon's.  Both are distinct from Adobe's, GIMP's, ImageMagick's, etc.  If your image has some quantized blocks that match those from Canon, but others that aren't recognizable, an eavesdropper might determine it was tampered with.  For a start to more information, see http://www.imagemagick.org/Usage/quantize/

A long time ago, the program OutGuess did a good job at spotting steganographically altered images encoded in many different image formats, but as far as I know the author never released the source.


With randomized encryption, ciphertexts must be slightly longer than plaintexts in order to allow for more than one possible ciphertext per plaintext

Think about it in the other direction; there are $2^{64}$ ciphertexts which will all decrypt to the same plaintext, and this holds for every plaintext.  There are a total of $2^n$ plaintexts of length $n$; hence, there must be $2^{64} \cdot 2^n = 2^{n+64}$ distinct ciphertexts which all decrypt to plaintexts of length $n$.  If we assume that all those ciphertexts are the same length, they must be at least $n+64$ bits long (because there aren't enough ciphertexts of shorter length).

Of course, if we don't require all the ciphertext lengths to be the same length, then it is possible that some of the ciphertexts may be shorter than $n+64$ bits (but only at the cost of having other ciphertexts be more than 64 bits longer than the corresponding plaintext).


Adding the same noise to all element of a vector is Differential privacy

This cannot possibly be differentially private.
Recall than a randomized algorithm $\mathcal{A}$ is $\epsilon$-differentially private if, for all datasets $D_1$ and $D_2$ that differ in a single entry, and all subsets $S\subseteq\mathsf{im}(\mathcal{A})$, that:
$$\Pr[\mathcal{A}(D_1)\in S] \leq \exp(\epsilon)\Pr[\mathcal{A}(D_2)]$$

Let $\mathcal{A}$ be your proposed mechanism, which samples $e\sim \mathcal{D}$ for some distribution $\mathcal{D}$, then maps $v \mapsto v + e(1,1,\dots,1)$.
Let $S = \{v\in\mathbb{R}^n \mid v_1 = v_2\}$ be the set of all vectors such that their first two coordinates are equal (any pair of coordinates suffices).

Identify datasets with vectors in $\mathbb{R}^n$, as this seems to be your use case. Let $D_2 = (v_1, v_2,\dots, v_n)$, and let $D_1 = (v_1, v_1, v_3,\dots, v_n)$.
Note that these differ in a single entry (their second entry).

We have that $\Pr[\mathcal{A}(D_1)\in S] = 1$, but $\Pr[\mathcal{A}(D_2)\in S] = 0$, so the inequality cannot hold.

Note that the above makes no restrictions on the entries of your datasets (a prior answer had them in $\{0,1\}^n$), nor does it make any restrictions on the error distribution $\mathcal{D}$.
So your optimization cannot ever be differentially private.


Testing speed of symmetric vs asymmetric encryption and decryption using gpg

100 MiB is nothing nowadays. Still, it is likely that most time is spend because of I/O operations, rather than encryption /  decryption. Once the file is buffered in RAM, the operations will proceed much more quickly. Worse than that, during encryption most of the time is spend during compression of the input - not encrypting it. Try -z 0 so compression of random data doesn't cost that much time:

maartenb@maartens-ryzen:~/Test$ time gpg --symmetric --batch --passphrase 123 --output blob.gpg -z 0 blob
gpg: AES256 encrypted data
gpg: encrypted with 1 passphrase
gpg: handle plaintext failed: General error

real    0m0.686s
user    0m0.670s
sys     0m0.016s
maartenb@maartens-ryzen:~/Test$ rm blob
maartenb@maartens-ryzen:~/Test$ time gpg --decrypt --batch --passphrase 123 --output blob blob.gpg
gpg: AES256 encrypted data
gpg: encrypted with 1 passphrase

real    0m1.056s
user    0m0.965s
sys     0m0.088s

It seems that you are using password based encryption for "symmetric encryption" while you are using encryption / decryption with an unprotected private key (because the passphrase is cached).

For password based encryption you'd use a password based key derivation function or PBKDF, which has an explicit work factor (or iteration count) to slow down password guessing. More information here.

Now, if you look at the encrypted packet, you get this:

maartenb@maartens-ryzen:~/Test$ gpg --list-packets blob.gpg
gpg: AES256 encrypted data
gpg: encrypted with 1 passphrase
gpg: decryption failed: Bad session key
# off=0 ctb=8c tag=3 hlen=2 plen=13
:symkey enc packet: version 4, cipher 9, s2k 3, hash 2
    salt 4D975A3A5174CD4F, count 65011712 (255)
# off=15 ctb=d2 tag=18 hlen=6 plen=104857656 new-ctb
:encrypted data packet:
    length: 104857656
    mdc_method: 2

Note the s2k 3 and the pretty high value of count in there. Note that I'm using gpg (GnuPG) 2.2.12.

The public / private key operations do not have such a deliberate slow down - unless the private key is still protected by a password.

This is another advantage of public key encryption: during encryption you won't have any slow down to protect pass phrases sampled from a source with low entropy output (i.e. you).


Common modulus attack with not coprime exponents

No, it's not possible (or so we hope).  If you could, you could break RSA.

Suppose you had an Oracle that, given $n, e_1, e_2, m^{e_1}, m^{e_2}$ with $\gcd(e_1, e_2) = d$, and which is able to output $m$.  We can assume that the Oracle only works for a specific $e_1, e_2$ pair.

Then, suppose you were given $c = m^d$, and wanted to recover $m$.  Here is what you could do:

Compute $c_1 = c^{e_1/d}$, and $c_2 = c^{e_2/d}$

We note that $c_1 = m^{e_1}$ and $c_2 = m^{e_2}$.

We give $n, e_1, e_2, c_1, c_2$ to our Oracle; our inputs matches the Oracle requirements and so it produces $m$, thus solving the original RSA problem.


Is there a way to prove equality of plaintext that was encrypted using different public keys?

Here is an answer to your question using a zero knowledge proof in the case of Elgamal encryption. The biggest difference between this solution and your own is that Alice does not need to tell Bob the value of $r_1$ anymore. This makes the zero knowledge proof more complicated.

Setting the scene:

Let $\mathbf{G}$ be the group of prime order $p$ in which the Elgamal encryption is taking place. Let $(g_1,h_1)$ be Bob's public key, and $s_1$ be Bob's private key, so that $g_1 = h_1^{s_1}$. Let $(g_2,h_2)$ be Carol's public key.

Let $(c_1,d_1) = (mg_1^{r_1},h_1^{r_1})$ be the ciphertext that Bob receives from Alice. Bob doesn't know $r_1$, but he does know that the decrypted message is $m = c_1 d_1^{-s_1}$.

Let $(c_2,d_2) = (mg_2^{r_2},h_2^{r_2})$ be the ciphertext that Bob sends to Carol.

Bob will use a zero knowledge proof to prove the following without leaking any information about $s_1$ and $r_2$:

-$s_1$ is the secret key corresponding to $g_1,h_1$

-$d_2 = h_2^{r_2}$, meaning that $r_2$ is the randomness used for $(c_2,d_2)$

-$c_2 = c_1 d_1^{-s_1} g_2^{r_2}$, meaning that the message obtained by decrypting $(c_1,d_1)$ with $s_1$ is the same as that encrypted in $(c_2,d_2)$

The Zero Knowledge Proof

Proof Statement: $(c_1,d_1),(c_2,d_2),g_1,h_1,g_2,h_2$

Bob picks $b_1,b_2$ uniformly at random from $\mathbb{Z}_p$. Bob computes $G_1 = h_1^{b_1}$, $G_2 = h_2^{b_2}$, $G_3 = d_1^{b_1} g_2^{-b_2}$

Bob computes a hash $x = h(proof statement || G_1 || G_2 || G_3)$ (I think it is necessary to include the statement in your original example too, but need to check).

Bob computes $\bar{s}_1 = s_1 x + b_1$ and $\bar{r}_2 = r_2 x + b_2$.

Bob publishes $(G_1,G_2,G_3,\bar{s}_1,\bar{r}_2)$.

Verification:

To verify, first compute $x = h(proof statement || G_1 || G_2 || G_3)$.

Check that $h_1^{\bar{s}_1} = g_1^x G_1$ (shows $\bar{s}_1$ is a randomised version of Bob's public key)

Check that $h_2^{\bar{r}_2}=d_2^x G_2$ (shows $\bar{r}_2$ is the randomness used in $(c_2,d_2)$)

Check that $c_2^x c_1^{-x} d_1^{\bar{s}_1} g_2^{-\bar{r}_2} = G_3$ (shows that the messages in both ciphertexts are the same)

Security Proof Sketch:

I'll sketch a proof that the underlying interactive ZKP where the verifier picks random $x$ from $\mathbb{Z}_p$ is secure, and then rely on the well-known fact that replacing this with the hash to get the above gives a secure NIZK protocol will full zero knowledge.

(Completeness) It's easy to see that an honest prover will always convince the verifier by substituting the honestly computed values of $\bar{s}_1,\bar{r}_2,G_1,G_2,G_3,x$ into the verification equations.

(Special Soundness) For the same $G_1,G_2,G_3$, if the prover could produce acceptable proofs with $\bar{s}_1,\bar{r}_2$ and $\bar{s}'_1,\bar{r}'_2$, for two different values $x,x'$, then we could extract Bob's secret key (and hence the message), and the randomness used in the second ciphertext. From the first verification equation, we can compute $s_1,b_1$, the discrete logs of $g_1,G_1$ with respect to $h_1$, such that $\bar{s}_1 = s_1 x + b_1$ and similarly for $\bar{s}'_1$. From the second equation, we can compute $r_2,b_2$, the discrete logs of $d_2,G_2$ with respect to $h_2$, such that $\bar{r}_2 = r_2 x + b_2$, and similarly for $\bar{r}'_2$. Substituting into the third verification equation, we have $\left( c_2 c_1^{-1} d_1^{s_1} g_2^{-r_2} \right)^x d_1^{b_1} g_2^{-b_2} = G_3$. This is a polynomial (in group elements) which is satisfied for two different values $x$ and $x'$, so all coefficients must be equal to the group identity. Taking the coefficient of $x$, we have that $c_2 = c_1 d_1^{-s_1} g_2^{r_2}$. In other words, the decryption of the first ciphertext, when encrypted, gives the second ciphertext.

(Special Honest Verifier Zero Knowledge) Given $x$, the simulator can pick $\bar{s}_1,\bar{r}_2$ uniformly at random from $\mathbb{Z}_p$, and then compute $G_1,G_2,G_3$ using the verification equations.


Access control is a broader concept that includes authentication, authorisation, accounting and possibly other components contributing to the control of access. Authorisation only concerns granting or denying permissions according to a security model and policies.


Toy one-way hash function for six digit number

A six digit integer gives you a possible one million possible IDs. Consider this python code that hashes every possible ID using a properly vetted, secure, cryptographic hash function:

import hashlib
import time

t0 = time.time()

for i in range(1000000):
    hashlib.blake2b(bin(i).encode("utf-8"))

t1 = time.time()

print(t1-t0)

It runs in around 400ms on my laptop. An attacker could generate a look-up table in less than a second that would map these output hashes back to the original employee numbers that they derive from.

In order to combat this, you'd have to use some kind of "hard" cryptographic hash like Argon2 or PBKDF2 in order to ramp up the computational complexity of generating a rainbow table.

But really this is just pushing the problem down the road and making it more difficult for yourself as well.

The better solution is to generate your own random lookup table and use that as a substitution in your spreadsheet. Consider:

import secrets

lookup = {}

for i in range(1000000):
        lookup[i] = secrets.randbelow(1000000)

# employee id "662893" is mapped to which masked value?
print(lookup[662893])

The code is not quite what you want as there's no padding to six digits and the reverse lookup is likely the more useful one, and it does not check for collisions, but it serves to make the point.

Tackling collisions can be done by selecting IDs from the set of unused IDs, or just increasing the length of the random values so that the probability of collisions becomes negligible.

In this scheme where each employee is mapped to a unique ID, an attacker has no way of computing the original employee ID from the masked value without the lookup table, as they were generated randomly.

If the small (2x) memory overhead of this solution is unacceptable, Maarten's solution of using a keyed hash function is also viable. Simply use a HMAC construction with a secure hash function and a 32 byte key, and the attacker would have no way of bruteforcing the inputs without knowing the key.


Privacy of vote from tallying authority in El Gamal Voting Schemes

The random $b,e$ values would seem to allow the uniform randomisation of the message between $G$ and $G^{-1}$.

Also, while reading a technical article at this level, one can note the citing of sources [SK94,CFSY96] where the technique seems to have been first used and follow up those.


Proving equality of two Schnorr Signatures

I don't think that works with keeping the message private - unless you break the signature scheme by reusing the nonce.
Your variables $c_1$ and $c_2$ are the results of the hash function. And those can not be the same by the definition of $r$ being a nonce. Moreover: the hash function does not retain any algebraic structure. By the definition of hash functions, the resulting hash only shows if two inputs wre the same or not. No partial matching or any type of relation between two inputs.
But they are also the only variables, that depend on the private message $x$. And  from that, I don't see any way to distinguish $c$-values , where $x$ is the same or $x$ is different. Unless you allow $r_1=r_2$, which breaks the security of the signature.
The main misconception with using Chaum-Pedersen: They don't use signature schemes. They use commitments. From the statement, that you want to keep $x$ private, maybe you should use commitments instead of digital signatures. They give the privacy requirement, and you can use Chaum-Pedersen directly.


Correcting Improperly Formatted EC Private Keys

Yes, it seems related: the private key just misses a 00 value (not a 01 value) in front. The problem that the I2OS primitive seems to round down instead of up if the value is smaller than 520 bits (65 bytes).

Fortunately the public key seems to be OK. The next byte boundary from 521 is 528 (512 + 16 bits). 2 x 528 = 1056 bits. However, the first 8 bits of the bit string indicate the number of bits that are not used out of the next bits. They are always present, and always set to 00 whenever the bit string is used to represent bytes. So they always need to be skipped (check the bits themselves on the site you link to - you'll see they start with 00000100 which is 04 not 00!).

So basically you get to the following simple scheme: get the private key and add as many 00 bytes to the left until you get 528 bits (66 bytes). For the public key just use it straight away, starting at the 04 (uncompressed point). If it doesn't work then maybe iOS expects the X and Y coordinates directly so strip the 04 away.


How to choose parameters for Argon2 for password vault

The parallelism was probably one reason why Argon2 won the Password Hashing Competition.
The use of processor cores allows for greater memory hardness (security)
without increasing the execution time accordingly.
The drawback is that developers have since then been wondering what value they take for their application.
Paralellisms depends on the number of available cores.
If you want your application to run on different devices,
the execution time will vary greatly with higher parallelism factor.
As of that time, about 50 percent have quad-core processors in their computer.
This would suggest to increase the parallelism factor to 8 (twice the number of cores),
but for smartphones with a single core this would roughly quadruple the execution time.
There is no clear solution for this.
I personally find the choice of libsodium too extreme, even though it is most likely to be cross-device.
But you are thus missing out on a major advantage of Argon2.
If you assume that the vast majority of your users have at least two processor cores,
you can set the parallelism factor to 4, if you are more careful, to 2.
Then you can set the assumed available memory (there is no clear solution for this too, at least 64 MiB?)
and at the end set the time-factor that the execution time is maybe one second.


ORAM  can be built on a multi-party scenario, where the data belongs to various parties using Secure Multiparty Computation. Recent research calls this approach ORAM for Secure Computation (SC-ORAM).

Given that writing and reading are required, it is my believe this would be the best approach.

In the typical SC-ORAM setting, several parties store information on remote server that holds the ORAM, and use SFE and general 2PC to execute ORAM tasks.

There are ways you can get rid of the Server however, Keller and Scholes propose the adaptation of Path ORAM, among other methods under a setting where the DB is secretly shared among the participants. Their results could be adapted to any method using ORAM and MPC.

What may be the most relevant of all, are the results by Faber et al, show how to build such setting under an MPC framework that allow for a secret shared database between 3 distrustful parties.

A short post about their results including a nice video with detailed explanations can be found here.


Design flaws when designing a MAC-function

Collision resistance is usually a property of hash-functions, would that also be a proper term to describe block-ciphers?

Well, kind of.
The message space of a hash function is huge. It contains about 2 ^ 2 ^ 129 separate messages for SHA-512, for instance. So it will have collisions as the output size is limited to 512 bits.
On the other hand a keyed block cipher is a permutation, a mapping from all input elements to a specific output element each. As all the input is mapped to a unique value in the output, there cannot be any collisions on the block cipher itself.
You haven't specified any method of using the block cipher for messages with a different size than that of the block size. If the block cipher is used in a specific way then you may well have a possible collision and therefore collision resistance when those are hard to find. Many hash functions are build on top of block ciphers after all, but it depends on the block cipher specifics and the way that it is used if that's secure.


Why can't you decrypt an encrypted message with just the public key?

I stumbled onto this great write up by Cloudflare a while ago as I was trying to understand Elliptic Curve Crypto better. It however starts of with some background on Public Key Cryptography followed by a detailed explanation and example of RSA key pair genaration AND how those keys (smallish primes) are used to encrypt a basic message. I suspect you will find that example answers some of your questions.

Specifically refer to the sections titled "The dawn of public key cryptography" and "A toy RSA algorithm".

All subsequent sections deal with ECC and go into a fair amount of detail (a great article on the whole).

Edit: If you tinker with the values in the example it should illustrate why the mathematics would not allow you to decrypt a message using the public key.


Is There any Risk to Using Meaningful Text as One Time Pad Key?

There are two major risks, one of which is very difficult to quantify. So let's start with that.

Kerckhoffs' principle states that you have to assume that only a key is secret, not the means of communication.   There's you and your friend, lover or co-conspirator and you communicate. The state knows this, and a search of your properties reveals a OTP was used, generated from some magazine. Assume you read a lot so you have many mags, say 10,000 as you have a rather large bookshelf.  Guessing the correct one is only equivalent to guessing a ~13 bit key. That's not a lot.  Granted you then have to work out which parts of the magazine were used, but you can see that the state is closing in on you.  There are other pragmatic issues to quantifying this like eating the magazine afterwards, but still... Compare that to an electro-mechanically generated key of the length of a Twitter message.  That's 1280 bits, which is oodles better.

Another risk is that the entropy rate of the key material must >= entropy rate of the plain text.  This is the fundamental requirement for a OTP to preserve perfect secrecy.  If your magazine is about fishing or football, the entropy rate of the text will be quite low, say just ~2-3 bits/character. An article by Umberto Eco will fare better, but not by much.  Your secret message will have to have a correspondingly low entropy rate.  So if you were to try and encrypt binary data approaching 8 bits/byte, perfect secrecy is impossible.  Your message would be capable of being easily brute forced. You can mitigate this by using randomness extraction on the magazine text to condense the entropy to 8 bits/character. That still leaves my first and main risk though.

This is one of the fallacies about using such key material, and it's perfectly understandable given human senses.  You think that finding the exact magazine is so hard it borders on impossible.  It's only 13 bits improbable, whilst to us 10,000 magazines seems a lot. Compared to truly random keys, it's no security at all.


Why is it allowed to Generate Keys inside the game?

The adversary is permitted to generate the keys

because we're not restricting the adversary's internals.

(For example, the adversary is also permitted to compute the parity of y,

and to generate a random element of {45,56,62,68}.)


I am going to assume that you're a regular Joe (no offence), and not a rocket scientist or millionaire philanthropist with a huge research budget, as this determines the answer.

No.

There is no true random number generator available to you that can meet all of your three tests.  By your mention of atmospheric noise, I'm further assuming that you're meaning a true random number generator based on physicalities, rather than a pseudo random number generator like the Mersenne Twister.

Specifically:

Yes.  True randomness and entropy are all around you.  I mean  sources of unpredictability.  The noise on your camera phone party pics, the jitter in your PC's system clock or noise on a voltage regulator valve.  These will not though produce uniformly random numbers without some randomness extraction.
Yes.  Any of the above will achieve this.  There is no interaction between the examples I've given.  (Even photon entanglement can be mitigated over a metre's distance but you won't be building one of those).
No.  Another assumption is you want a rate of 5 TB in 5 minutes.  That's >100 Mbits /s.  You cannot achieve this as Joe.  Unless you spend a great deal and are pretty clever building stuff.  I'm not aware of any simple devices like ring oscillators that can easily output this rate at the hobby level of construction.  (I exclude Intel CPUs as those are highly suspect undefined generators probably crippled by the NSA.)

3 1/2.  Be very careful with atmospheric noise.  I don't believe that it's possible for typical hobbyists to generate more than a few bits /s from this as the safety margin for true randomness will be enormous. The EM spectrum is full so your only course is to build a very broadband receiver and rely on the central limit theorem to achieve randomness. You can't use a tranny radio.  You will just end up sampling thermal noise on your receiving circuitry, oscillations of the phase locked loop FM detector or Lady Gaga's latest hit.  That probably happens at random.org and they just side step it with technobabble so don't be encouraged by their example.  Tip:  Use a 24V Zener diode. Enough true randomness for Joes.

Can I suggest that you see this question regarding your property 3?


Can iterated hashing be used to mitigate collision and preimage weaknesses?

With respect to collisions, hashing twice can not increase security, because if $x$ and $x'\ne x$ collide for $H$, that is $H(x)=H(x')$, then  $H(H(x))=H(H(x'))$. Otherwise said, any collision for $H$ is a collision for the double hash $H\circ H$. It is therefore trivial to exhibit collisions for $\operatorname{MD5}\circ\operatorname{MD5}$. Hence the answer to the question as worded in its title is NO.

With respect to preimage, hashing twice demonstrably does not harm security (from a preimage for $H\circ H$ one can make a preimage for $H$, simply by applying $H$), and tends to improve it for practical functions. In particular, one hypothetically able to build preimages for $\operatorname{MD5}$ only for 512-bit messages would likely have a hard time extending that to $\operatorname{MD5}\circ\operatorname{MD5}$.
Handwaving argument: if for some 128-bit $v$ one could find a 512-bit $\operatorname{MD5}\circ\operatorname{MD5}$ premiage $m$, then the easilly computed $m'=\operatorname{MD5}(m)$ would be a 128-bit $\operatorname{MD5}$ preimage of $v$, which arguably is harder to find than a 512-bit $\operatorname{MD5}$ preimage of $v$, since for a given $v$ it is expected that there are about $1$ premimage of the former kind, and about $2^{384}$ of the later.

One area where double-hashing increases security is length extension attack. $\operatorname{SHA-256}$ is trivially vulnerable to that, $\operatorname{SHA-256}\circ\operatorname{SHA-256}$ is not.

In some use cases, hashing twice can destroy security, including for common hashes; an example is given here; in summary: some proof-of-work protocol safe when using $H$ is entirely unsafe using $H\circ H$.

With usual hash functions (or ideal ones), hashing twice does not dramatically reduce the output space (it is reduced by a factor about $1-1/e\approx0.63212$); that makes accidental collision slightly less unlikely, and it is mostly immaterial in practice. It does not make collisions easier to exhibit, since the amount of invocations of $H$ expected necessary to exhibit a collision by whatever brute force method can not decrease (if it did, that would be trivially usable to exhibit collisions for $H$ at reduced cost).


Better than diceware? And sha512 related question

I don't really see the problem with just hashing the modified text. Even when the original text is public information, you've already shown that introducing $n$ independent changes gives you $\approx27n$ bits of entropy. Hence given an output hash, finding the modified text should be as difficult as exhaustive search if the hash function has pre-image resistance (and collision resistance, to ensure that the hashes of your modified text “look random“ conditioned on your original text).

Anyway, your line-by-line construction looks to me equivalent to some other hash function which combines multiple SHA512 invocations, so I can't imagine it'd be any more secure. Why don't you simply make a diff (e.g. insert a at position 12381, change position 812931 to f) and hash the result?


This is precisely the domain of secret sharing, of which there are various popular schemes like Shamir's secret-sharing scheme, and there are many widely available implementations of it in various forms which you can find with exactly those keywords.


is there any specific definition or feature for the problem, and could all problems, which can be verified, be converted into circuits and use zk-snark to generate proofs?

Problem should be in NP class. NP problems are problems that there exists an (efficient) algorithm that can decide or prove in polynomial time that is w a witness for the statement s (their statements) or it isn't. Many of zkSNARKs are based on circuit satisfiability problem. Circuit satisfiability is a NP-complete problem. There are two types of circuits: boolean and arithmetic circuits that can be converted to each other. Roughly speaking, we can design circuits for all algorithms (ex. SHA-256) that we can run on our computer. The below picture is a simple boolean circuit consist of wires and logic gates (AND, OR and NOT). In a zkSNARK system based on this simple circuit, prover want to convince the verifier that he knows the inputs ($x_1$ = 1, $x_2$ = 1, $x_3$= 0) that for this inputs the output of circuit is true, in another words, he knows the inputs that satisfy this circuit.

how to flatten a problem into a circuit, by programming or using mathematical methods?

After converting a NP problem to a (boolean or arithmetic) circuit, you should convert this circuit to a SNARK-friendly format like R1CS. There are some compilers that you can write your problem in a high-level programming language in them and compile the problem to R1CS format, for example, you can use ZoKrates, a toolbox for zkSNARKs on Ethereum or you can use libsnark's gadget libraries.


Are the Common modulus attack, Common Factor Attack, and Wiener's attack different?

Wiener's attack;

In Wiener's attack, an attacker may efficiently find $d$ when $d < (1/3) N^{1/4}$
Coppersmith's attack

The Wiener attack works on low $d$, but Coppersmith attack works on small $e$. In general case, the Håstad's broadcast attack uses The Coppersmith method. In the simplest form, it uses CRT when the sender sent the same messages to different parties.
Common modulus attack

In Common modulus attack, the modulus is the same but the public exponents are different.

As a result, they are different attacks with different names.

And, here a nice paper from Dan Boneh; Twenty Years of Attacks on the RSA Cryptosystem


How does the Signature Scheme in Picnic Works

There are a few steps involved in the design:
1. design a sigma protocol with special soundness.
2. transform the above sigma protocol to a nizkpok.
3. use the above nizkpok to prove the possession of x, such that F(0) = y, where y is the public key, x is the private key, F is an OWF.

The encryption is a PRF used to sample an OWF.

When talking about H(r,m), H is a (quantum) random oracle used in step 2 to obtain a nizkpok based on FS-transformation (Uhruh transformation).

The feature of Picnic is the use of MPC-in-the-head to obtain a sigma protocol with special soundness. This is done in few steps:
1. prover emulate a number of semi-honest execution of MPC where each party has input as a secret share of the witness.
2. prover commits to all views and states of all parties in all executions.
3. verifier open a selected subset of parties from each execution and check that the parties are behaving honestly.

Intuitively, is the prover misbehave for some parties, it will be caught with some probability; on the other hand, the semi-honest security of the MPC protocol ensures that even if some parties are opened, no information on other parties inputs (and thus the witness) is revealed.

Given the above, one can see that the challenge is the set of parties to open, and the response are the decommitments to open the views of these parties.


They do md5(random_string + password), and send this and the random string along with their data.

What would happen if the attacker recorded the above data, and then sent 'md5(random_string + password)', 'random string' (both from the recorded data), and then included their preferred data.  The system would check that the random string checks out, and so trust the data.

What I would recommend is something like:

HMAC( random_string, data ), data

(where data would include something that would identify the client, if necessary)

That way, the attacker can't just cut/paste the authentication information; it is a function of the data being authenticated.

BTW: there is no reason to use MD5.  The weaknesses known in MD5 do not apply in your case, however that's not a good enough reason to use it; I'd suggest using SHA-256 instead (possibly truncating it if 256 bits is too long)


Designing Secure Multi-Party Computation Sub-Protocols Based on Homomorphic Encryption

Since the keys are fixed from beginning (the sub-protocols input are ciphertexts), isn't it possible to give the secret key to the (non-uniform) distinguisher as an extra advice (the only restrictions for the advice is that its bitlength is polynomial in the security parameter), and thus allowing the distinguisher to decrypt?

This is up to your security model. For example in a protocol that is designed to provide forward secrecy, yes, you would need a method in the proof that allows the adversary to get the private key. After that, they would be able to distinguish between encryptions of 0 and the real encryptions, so something else must be done in the proof to handle this situation. Look around for examples of composability proofs in the forward secrecy model for guidance on how to do this.

If, on the other hand, your security model is not designed to handle key leakage, then you don't really have to handle it in the proof since that is impossible in both the simulation and the "real" protocol execution.


What does "constant rate" mean in universal composable commitment scheme?

Constant rate in general means that the overhead from a non-secure method is constant. So, in a simple way, if I am committing to an $\ell$-bit message, then the size of the commitment is $O(\ell)$. In some cases, however, one also allows an additive factor that is independent of the message size. Thus, for example, it could be that to commit to a message of size $\ell$ the amount is $O(\ell)+{\rm poly}(n)$, where $n$ is the security parameter.

Note that typically these are measured in an amortized manner. So, you have to send many commitments (or a long message) for it to be true. But, again, this depends on the exact scheme, so you'll have to read the details.


Using the encryption matrix from AES, how do you compute the decryption matrix?

First of all, this is not "AES", but something else.  Someone might claim that it's somewhat similar to AES, but it's still not AES.

However, to answer your question:

  please let me if I am on the right track or I'm not even close to the start of it all

Actually, you already got your answer:

  Compute the decryption matrix $D = E^{-1}$

That is, compute the matrix $D$ such that $D$ and $E$, multiplied together using standard matrix multiplication, gives:

$$\begin{bmatrix}d_{00}&d_{01}\\d_{10}&d_{11}\end{bmatrix}\begin{bmatrix}1&x^2 \\x^2&1\end{bmatrix}= \begin{bmatrix}1&0\\0&1\end{bmatrix}$$

This is a standard matrix inversion problem, and all the standard tools used to invert matrices over $\mathbb{R}$ work (and as a bonus, you don't have to worry about numeric stability).  Now, you do have to do your internal computations in $\mathbb{F}_{16}$, but that's pretty easy.


How does Truecrypt change password without the need for a complete re-encryption of volume

What Richie Frame describes above is correct. This is how most FDE solutions work.

A new random encryption key is created whenever new container is created or disk is encrypted. That encryption key (often called Master Key) is then protected by users' password. In case of Truecrypt, master key is stored in volume header (link) and volume header is encrypted with a key derived from a user password (another link).

Such scheme provides (at least) two major benefits:

Password changes are quick and do not require re-encryption
Multi-user setup is straightforward: just store master key encrypted with every user's password.

Major disadvantage is that if master key is compromised (e.g. by dumping memory while volume is mounted), adversary can maintain access to the data even if users change their passwords. To mitigate this some FDE solutions provide "re-encrypt" option which will create new key and re-encrypt all data.


Intuitively what makes indistinguishability obfuscation useful?

Bottomline: it is more appropriate to think in terms of indistinguishability rather than (black-box) simulation as indistinguishability obfuscation (IO) guarantees the former.

To see how IO can be useful, think of IO as a mechanism that "encrypts" the circuit (with the "encrypted" circuit being functionally equivalent to the original circuit), and its security requirement to be that for any two circuits that are functionally equivalent, the corresponding encrypted ciruits are indistinguishable.

In most applications of IO, the security argument involves showing that the adversary cannot tell the case where it is given the encryption of the actual circuit from the case where it is given the encryption of a "bogus" circuit.  As certain crucial parts have been removed from the bogus circuit, an adversary cannot have a significant advantage in breaking the bogus circuit. (And since the encryption of the actual circuit is indistinguishable (by IO) from that of the bogus circuit, security ensues.)

The above uses two ingredients: punctured programs and hidden sparse triggers.$^*$
The bogus circuit is usually constructed from the original circuit by "puncturing" the underlying PRF at the challenge. As a result, the bogus circuit behaves "randomly" at the punctured point. This modification could, inadvertently, lead to the bogus circuit behaving differently from the original circuit (and the security guarantee of IO goes out of the window). The way-around is to ensure that the point at which the puncturing takes place is hard to find using, for example, a PRG (i.e., sparse hidden triggers).

The construction of public-key encryption (PKE) from secret-key encryption (SKE) given in [SW14,§1,§5.1] is an excellent example which encapsulates the usefulness of this approach, and which I'd reccommend for further reading.$^{**}$

$^*$To quote [SW14], "the idea of the technique is to alter a program (which is to be obfuscated) by surgically removing a key element of the program, without which the adversary cannot win the security game it must play, but in a way that does not alter the functionality of the program."

$^{**}$ This highlights another point of why IO is so powerful: it is known that PKE cannot be constructed from SKE in a black-box manner, but since IO uses the circuit of the underlying SKE, the constrcution is non-black-box and helps bypass the separation.


How to plot the distribution of a ciphertext?

What you are looking for is a histogram plot.

For example, the distribution of letters in the english language looks like this:

The plot of a ciphertext from a strong cipher should have all bars about the same height (a fairly uniform distribution).


Looking at the MSDN link given by Tangurena, they use the word salt in this paragraph (and the following ones):

  To prevent discovery of plain text content by comparing encrypted values (the second
  attack), most encryption algorithms include a salt value. Specifying a different salt
  value generates a very different encrypted output. When using the .NET cryptography
  classes, you can specify the salt as the initialization vector argument.
  In SQL Server, a random salt value is always applied to the encryption.

A block cipher (given the same key) always maps the same plaintext to the same ciphertext.

When constructing a stream cipher from a block cipher, we usually use one of the secure cipher modes to avoid that same input blocks give the same output, which would be a point of attack. (See the ECB example image mentioned there.)

A database encryption works a bit different than a stream encryption: you normally want to have access on each record individually without having to decrypt the whole table/database.
But we still want to avoid same records/fields giving the same ciphertext.

To do this, we use the same trick as for the stream ciphers: for each block of data to encrypt, we generate some random initialization vector. But here it is saved together with the data instead of derived from the previous block(s) like in a stream cipher. This is input into the block cipher, as well as the key and the plaintext, for both encryption and decryption.


Mathematical formula for switching the key for OTP?

Instead of generating the random key for the one time pad cipher over and over again, is there a mathematical formula that allows you to switch the key to a new key?

No.
(Please keep reading…)

A single mathematical formula won’t cut it. That’s where cryptographic algorithms come in. There are more than a hand full of cryptographically secure pseudo-random number generators, stream ciphers, et al which could be used to create a cryptographically secure key… but when having to fall back on those, you might as well simply use them in the first place and drop your one-time-pad idea.

In fact, I’m wondering a bit: What research have you done? I’m asking because you seem to have skipped some of the important parts of what defines OTP.

Per definition, OTP requires the “key“ to be…

a truly random one-time pad value,
generated and exchanged in a secure way.
at least as long as the message, and
only to be used once.

Related to Point 1: Please note that it says “truly random” and not “pseudorandom”. Fact is that no mathematical function by itself can be truly random. Meaning: if you would use a math function (for example: a multiply-with-carry construction) it would definitely not satisfy the definition of OTP.

In a best case scenario, you would be dealing with a CSPRNG or a stream-cipher alike solution. As you probably know, those do exist and indeed provide cryptographically secure randomness (to some extend), but when thinking along that path you really have to ask yourself if you really want to use a car to ride a horse.

Instead of trying to make a square wheel round, it would be more constructive to revalidate your idea and check on already existing stream ciphers and/or cryptographically secure pseudo-number generators. A simple “it looks random so it must be secure” thing definitely won’t be able to handle the job! In case of doubt, look at the numerous PRNGs which have been cryptographically broken (and practically destroyed by cryptanalysis within the blink of an eye).

Related to Point 2 up to Point 4: That “exchanged in a secure way” is important because OTP can only be as secure as the key exchange procedure, which tends to be a problem when messages or data packages size up to a few megabyte or even gigabytes*.

Surely that’s where your question rooted. Yet, trying to find a way around the problem via a math function is neither OTP. nor cryptographically secure.

Last but not least…

  The new key must be as random and secure as the original key.

I wonder how you are planning to compare that. See, a truly random source is unpredicable. Same goes for things like cryptographically secure random number generators (assuming they’re not flawed or broken in some way).

Wrapping it up:

If you really want to stick with OTP, you’ll have no other choice (thanks to its definition) than to use a truly random, cryptographically secure source.

If that’s not available, you could fall back on something like a CSPRNG, or a stream-cipher alike construction (for example: HMAC-based). As said: a simple “mathematical formula” won’t do it. Only a cryptographic algorithm would come near the term “truly random”.

As an alternative: if you want something that’s both cryptographically secure and practical to use (which you indicate to be your main issue), you should definitely look beyond OTP. For example: stream ciphers like Salsa/Chacha. In the broadest sense, stream ciphers ”simulate” the one-time-pad idea. Using them you wouldn’t need to think about working around OTP annoyances.

Also, I think it is worth noting that there’s nothing wrong using good, well-vetted block cipher like AES/Rijndael.

(Funny enough, you could even use a block cipher like AES to create a CSPRNG construction which you could then abuse to create your one-time pad values. But that’ld be overkill since AES does a good job when it comes to encrypting data – which makes considdering OTP pretty superfluous.)


Differences between DSA and RSA Algorithms

If you're the user of some software using cryptography under the hood, knowing the mathematics of how RSA and DSA work won't help you. What you need to know is what configurations of your software are good for the way you use it, and the choice of algorithm is often not the most important factor, although between RSA and DSA the choice today is usually ECDSA, or failing that RSA over plain DSA.

RSA and DSA are both families of digital signature algorithms. A digital signature algorithm is a way to authenticate a message. When a message has a valid digital signature, it must have been signed by the holder of the private key that was used to sign. They are both instances of public-key cryptography: only the signer knows the private key, but the public key which is used to verify a signature can be known to everyone.

Today there are four families of digital signature algorithms in common use for computer users: RSA, DSA, ECDSA and EdDSA. The TLS protocol which powers most secure channels on the Internet can use RSA, DSA or ECDSA. SSH (specifically its most common implementation OpenSSH) can use RSA, ECDSA or EdDSA (older versions could use DSA). DSA has fallen into disuse; it isn't broken, but its performance is very poor compared to ECDSA for the same security level. EdDSA is still very new and not widely supported. RSA is on a slow path to obsolescence because it struggles to cope with the required increases of key sizes as computing power for cracking keys increases, but it still has a very broad installed base, and while it is much slower than ECDSA for signature generation, it is faster for verification.

Quantum cryptanalysis may come and force all these algorithms out, but for the time being it's still a research topic and nobody knows what post-quantum cryptography might end up looking like. There's an ongoing competition to find good algorithms that resist quantum cryptanalysis as it's currently thought to work.

If you're still using DSA, consider migrating to ECDSA. You're paying extra CPU power and using code that is probably not getting as much scrutiny these days. Don't migrate to any of the post-quantum algorithms because they haven't been studied much yet, and for all we know they'll be broken as soon as a cryptographer who isn't their author looks at them.

The security of RSA relies on the difficulty of the factoring problem, i.e. given only a product of two integers $p q$ the difficulty of finding $p$ and $q$ (with $p$ and $q$ chosen to make the problem difficult, i.e. being primes or at least probable primes). The security of DSA relies on the difficulty of the discrete logarithm problem, i.e. given $n$, $g$ and $y$ finding $x$ such that $g^x = y \bmod n$ (with $n$ and $g$ chosen to make the problem difficult). ECDSA and EdDSA also rely on the discrete logarithm problem, but on elliptic curves instead of $\mathbb{Z}/n\mathbb{Z}$.

There is also a family of public-key encryption algorithms called RSA. It uses the same mathematical problem under the hood, with different constructions on top. DSA does not have a corresponding encryption scheme in widespread use. ECIES is a standard for encryption using elliptic curve cryptography which can be thought of as a parallel to ECDSA, but it's markedly less common. The Edwards curves that power EdDSA can also be used for public-key encryption but I'm not aware of a standard for that.


Can a secret message be securely transmitted within a MAC tag?

There are two parts to this proposal: the use of a code book and a scheme to send short confidential and authenticated messages utilising an existing shared symmetric key.

A code book can be used alone to provide a degree of confidentiality, or can be used to ascribe specific pre-agreed meanings to short messages, in combination with any scheme for sending those short messages. The rest of this answer focuses on the use of a MAC for sending such short messages.

Short answer: yes, this scheme preserves confidentiality and integrity of messages.

Pre-image resistance of the secure hash function ensures confidentiality of the message (in conjunction with an appropriately strong key).

The use of a nonce ensures that an eavesdropper can't tell whether a genuine message is the same as any previous messages.

The properties of a MAC prevent forgeries or manipulated messages being accepted.

Note that this system does not protect against replay attacks or message re-ordering attacks, i.e. it can't be used as a generic secure channel. Once an attacker has observed a message, they can replay the message and the recipient cannot differentiate between a replayed message and a fresh message. If the recipient were to record all valid nonce-message pairs they could detect replays, but not out-of-order messages.

This use of a MAC isn't a standard way to build a secure messaging system, so shouldn't be used for production systems. Practically, it has very large message expansion (256 bit ciphertext + 256 bit nonce per ~10 bit data transferred = ~500bit overhead per 10 bit message). An example of a standardised alternative is GCM, which is more size-efficient (96bit nonce + up to 128bit tag = up to 224bit fixed overhead per any length of message) as well as supporting very long messages.


You cannot prove that this is difference unpredictable since it is not. Take $\delta=0$ and set $m_0=(a_0,a_1)$ and $m_1=(a_1,a_0)$.


Are there any known weaknesses with ElGamal algorithm?

A Diffie-Hellman exchange needs not be synchronous. In DH, each party has a private key (x) and a public key (gx mod p). If the sender knows the recipient's public key ga, then he can build his own key pair (b and gb), compute the shared secret (gab), and send both his public key (gb) and the encrypted message (symmetric key derived from gab) to the recipient. This works for asynchronous messages: the recipient needs not do anything at message sending time. This kind of processing is used in, for instance, S/MIME for encrypted emails, and it works.

The difference between DH and asymmetric encryption (like ElGamal or RSA) is only that in the case of DH, the sender does not get to choose the exact value of the shared secret, but that's fine as long as that secret is only used for symmetric encryption.

In fact, even if you use asymmetric encryption (ElGamal, RSA...), you still want to use it to encrypt a randomly generated symmetric key, and use that key with a symmetric encryption algorithm to process the actual data. Indeed, asymmetric encryption algorithms are quite limited in the size and format of what they could send.

That being said, ElGamal, as an asymmetric encryption algorithm, is fine as long as it is used properly. Notably, ElGamal is homomorphic (given the encryption of x and the encryption of y, one can from the outside compute the encryption of the product xy), which is a nice property in some cases, but can be bothersome in other conditions. A safe method to do ElGamal encryption is to, indeed, use it only to encrypt a random symmetric key, at which point there really is no advantage over a simple Diffie-Hellman.

"Proper usage" really means that you should not just slap together a few cryptographic algorithms; such an assembly is a delicate matter, and should be done only as part of a fully specified and analysed protocol. For instance, OpenPGP, which is implemented by GnuPG (an opensource library from which libgcrypt was derived). Indeed, OpenPGP supports ElGamal encryption, and does it "properly" (it uses ElGamal because that protocol was defined at a time when RSA was still patented, but ElGamal was not -- this no longer applies nowadays).

So that would be the "guidelines": follow OpenPGP; even better, save time and use the GnuPG implementation directly. Code which is easiest to design and implement is code which has already been designed and implemented by somebody else.


GCM mode of operation and IV size less 96 bits

If you want to use 64 bit deterministic IV's then you can. The NIST specifications  call this the "deterministic construction" listed in section 8.2.1 of Special Publication 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC.
The "deterministic IV" is then called the "invocation field" of the IV. That leaves you with 32 bits for the "fixed field", for which it is specified that:

Similarly, the entire fixed field may consist of arbitrary bits when there is only one context to identify, such as when a fresh key is limited to a single session of a communications protocol. In this case, if different participants in the session share a common fixed field, then the protocol shall ensure that the invocation fields are distinct for distinct data inputs.
...
The lengths and positions of the fixed field and the invocation field shall be fixed for each supported IV length for the life of the key. In order to promote interoperability for the default IV length of 96 bits, this Recommendation suggests, but does not require, that the leading (i.e., leftmost) 32 bits of the IV hold the fixed field; and that the trailing (i.e., rightmost) 64 bits hold the invocation field.

So as long as you are sure that your deterministic IV is unique, i.e. is a nonce, then you can do with the fixed field whatever you want - as long as both the encrypting party and decryption party use the same value, of course. So you can simply generate an IV consisting of a fixed field consisting of all zero's (a constant of 4 bytes set to zero) and use the nonce for the remaining part.
This way you don't need to use $\mathit{GHASH}$ for calculating $Y_0$ at all, which is more secure and more interoperable as not all GCM implementations may allow IV sizes other than 96 bit.
You would of course end up with $$Y_0=0^{32}\|nonce\|0^{31}1$$ instead of $$Y_0=nonce\|0^{63}1$$ for $Y_0$ but that doesn't matter much. In the resulting scheme, $0^{32}\|nonce$ would be called the IV and the postfixed $0^{31}1$ is generated by the GCM implementation. Of course, if you use $nonce\|0^{32}$ as IV then you would get your construction - and as you can see it is allowed but not recommended by NIST.
If your IV is smaller than 96 bits, you can always simply pad until you've got 96 bits; as long as the IV is unique, there is no problem.


Can AES-GCM be broken if initialisation vector is known?

However, we are using the same nonce/IV to encrypt different data.

No, don't do that

  if someone indeed gets hold of the plain-text nonce/IV and a number of different encrypted messages (which are encrypted using the same key) can they be able to decrypt the messages successfully?

Actually, it doesn't matter if they know the nonce; if they get two messages encrypted with the same nonce, then they can compute the xor of the two plaintexts.  Depending on the nature of the plaintexts, that is often enough for an attacker to deduce the contents of the original plaintexts.  Given the attacker more than two messages from the same nonce, well, that just makes it easier for him.

In addition, knowing two messages with the same nonce, then can deduce the internal value $H$ to GCM; that'll allow him to generate encrypted messages of his own that would pass validation (hence the authentication piece of GCM goes away).

  We have proposed to make this better by using a different nonce for encrypting each message. However, I am not sure if this will still prevent someone from decrypting the message when they can get hold of the plain-text nonce, even when there is only one message that is encrypted with that nonce.

That is absolutely better.  It doesn't matter in the slightest if the attacker knows the nonce; that knowledge doesn't allow him to deduce anything about the plaintext.  In practice, we often just prepend the nonce to the ciphertext, as that's the easiest way to get the nonce to the decryptor.  What matters greatly is that you never use the same nonce twice.


RSA 1024 bit forge a new matching signature from a chosen message

We assume an RSA signature scheme with appendix where the signature of message $M$ is $S=\left(\operatorname{MD5}(M)\right)^d\bmod N$, and the verification procedure checks that $0\le S<N$ and $\left(S^e\bmod N\right)=\operatorname{MD5}(M)$, with $e=3$ (or other relatively small odd $e\ge3$). Eve somewhat got $k$ rightful signatures $S_i$ and perhaps the corresponding messages $M_i$ (which Eve could not influence). Eve wants to construct another $M$, and matching signature $S$.

Eve will make a multiplicative forgery: she'll find a message $M$ and a matching set of $k$ non-negative integers $e_i$, such that $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$ is an $e$th power, then compute the signature of $M$ as
$$S=\left(\sqrt[e]{\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}}\right)\cdot\left(\prod S_i^{e_i}\right)^{-1}\bmod N$$
which verifies $\left(S^e\bmod N\right)=\operatorname{MD5}(M)$.

Define $m_{i,j}$ as the multiplicity of prime $p_j$ in the factorization of $\operatorname{MD5}(M_i)$, and define $m_j$ as the multiplicity of prime $p_j$ in the factorization of $\operatorname{MD5}(M)$. The goal of Alice is that $\forall j,\; m_j+\sum_i m_{i,j}\cdot e_i\equiv0\pmod e$. That linear system of equation with unknowns $e_i$ is equivalent to $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$ being an $e$th power.

Eve computes the hashes $H_i=\operatorname{MD5}(M_i)$, directly or as $S_i^e\bmod N$. She factors the $H_i$ at least partially (with $H_i<2^{128}$, even complete factorization is feasible). She can ignore any $H_i$ with a prime factor $p_j$ not appearing in the other $H_i$ [and $m_{i,j}\not\equiv0\pmod e$, but that is likely for $k$ large enough to carry the attack]; in particular she can without loosing much ignore those $H_i$ with a prime factor larger than about $k^3/\log(k)$, which are unlikely to be of any help.

Outline of the rest: Eve repeatedly

selects a message $M$ of her choice [that she did not previously select, and distinct from the $M_i$ if these are given]
computes $\operatorname{MD5}(M)$ and factors it at least partially
if that factorization consists entirely of primes occurring in the factorization of at least one of the $H_i$ kept [in that screening Eve could exclude primes with multiplicity $m_j\equiv0\pmod e$ in the factorization of $\operatorname{MD5}(M)$, and occurrences with multiplicity $m_{i,j}\equiv0\pmod e$ in the $H_i$, but that won't make much of a difference for $k$ large enough to carry the attack]

attempts to solve the linear system, and if that works

computes $S$, noting that the $e$th root extraction reduces to dividing the exponents by $e$ in the known factorization of $\operatorname{MD5}(M)\cdot\prod\left(\operatorname{MD5}(M_i)\right)^{e_i}$
outputs $M$ and $S$.

It will help to have preprocessed the system of linear equations. For larger $k$, solving the linear system will succeed for a large proportion of $M$ having passed the screening; or/and it will be possible to put an upper bound of the $p_j$ early on, making the factorization easier and the linear system smaller, thus easier to manage.

A small $e$ helps the attack, but with a large-enough $k$ it can be carried for any $e$. The size of the public modulus $N$ of the RSA key is essentially immaterial; what matters most is the width of the hash, which at 128-bit is grossly insufficient.

A slightly simpler variant of the problem (where all the messages are chosen, which is moot for a hash without collision resistance as $\operatorname{MD5}$ is nowadays) is discussed by Jean-Sébastien Coron, David Naccache and Julien P. Stern in section 2 of: On the Security of RSA Padding (in proceedings of Crypto 1999); or, when we set $\mu$ to $\operatorname{MD5}$, by Don Coppersmith, Jean-Sébastien Coron, François Grieu, Shai Halevi, Charanjit Jutla, David Naccache, and Julien P. Stern in section 3 of: Cryptanalysis of ISO/IEC 9796-1 (in Journal of Cryptology, 2008). The idea of a building coefficients by solving a linear system based on prime multiplicity was introduced by Yvo Desmedt and Andrew M. Odlyzko in A chosen text attack on the RSA cryptosystem and some discrete logarithm schemes (in proceedings of Crypto 1985).


Secure logical AND using Ishai-Sahai-Wagner Scheme

"Splitting into $d + 1$ shares" is mentioned in the Introduction, right after a reference to secret sharing schemes and mentioning threshold property. So, this particular IACR preprint is not the best source on secret sharing. I'd suggest to start from Shamir secret sharing algorithm.


Does authenticated encryption add any protection to a signed digital envelope?

I suggest that you look at Signcryption; a short survey appears here, and efficient schemes appear here. Just signing then encrypting or vice versa in a naive way is not secure (especially in the multi-user setting). So you have to do this right. Once you have a concrete scheme, you then have to see what level of security the encryption scheme needs to be. Typically it does need to be CCA secure, and the way to build CCA-secure symmetric encryption is the same as authenticated encryption. (Note that doing hybrid encryption or KEM/DEM, you need both the asymmetric and symmetric parts to be CCA secure.)  However, it really depends on exactly what you are doing. Look at the cited references as a starting point.


To quote from the paper you linked:

  The above particular values of $\mathrm{opad}$ and $\mathrm{ipad}$ were chosen to have a very simple representation (to simplify the function’s specification and minimize the potential of implementation errors), and to provide a high Hamming distance between the pads. The latter is intended to exploit the mixing properties attributed to the compression function underlying the hash schemes in use. These properties are important in order to provide computational independence between the two derived keys.

Note that a "high" Hamming distance is not exactly the right term: In fact, $4$ is the mean Hamming distance, i.e., half of the bits are flipped.

For lower distances, we have $\mathrm{opad}\approx\mathrm{ipad}$, thus the keys fed into the compression function are very similar: Those seem more likely to trigger some vulnerability of the underlying compression function than keys without such a simple relation.

Similarly, high Hamming distances imply that $\mathrm{opad}\approx\overline{\mathrm{ipad}}$ (and in the extreme case $8$ we have equality), so there is again a nice relation between the two pads, falling under the same reasoning.
(For example, even though not a hash function, DES has the complement property $E_k(x)=\overline{E_{\bar k}(\bar x)}$, showing that such things can indeed happen in cryptographic primitives.)

Thus, it seems like a reasonable choice to select pads that have the most "non-regular" Hamming distance: This means flipping not too few and not too many bits.

And indeed, it turned out later that those values do matter in some situations: The 2012 paper Generic related-key attacks for HMAC presents a related-key attack on HMAC that depends on the values of $\mathrm{opad}$ and $\mathrm{ipad}$.
The authors state:

  In the case of HMAC this is possible only when $k=m$ or $k=m-1$ since the last bit of ipad and opad are equal (otherwise, for a smaller key the attacker can not build a proper related-key). This shows that the choice of ipad and opad is not anecdotal. For example, if ipad and opad were very similar, then our attacks would work for basically any key length.


Trial division + Miller-Rabin complexity

Well, the probability that a random number circa $N$ happens to be prime is approximately $1 / \log_e N$ (for $e=2.718281828...$), this is also known as $1 / \ln N$.

Now, if $n$ is the number of bits of the number we're searching for, that is, we are generating random numbers circa $2^n$, then this probability is approximately $1 / \ln 2^n = 1 / (n \ln 2)$.  Hence, if we try random $n$ bit numbers, we would expect to need to try about the inverse of this number, namely $n \ln 2$, before we stumble onto a prime.  Now, obviously, we might get lucky early, or we might happen to need to do several times this number before we find a prime - this is just an average.

Now, one thing that you don't mention that they do is, when they select a random number, they set the lsbit.  This means that we'll never select an even number (which are hardly ever prime), effectively doubling the probability that a guess happens to give us a prime.  This doubling of the probability halves the number of expected trials, hence giving us an expected $n \ln 2 / 2$ trials.

Now, one thing about the equation you listed; it includes the term $N T_{mr}$.  This may be accurate if, independent of whether the trial division finds a factor or not, you perform the Miller-Rabin test anyways.  However, it is more likely that, if the trial division shows that the number is composite, you don't perform the Miller-Rabin test, but instead try again with another random number.  This implies that you perform fewer Miller-Rabin tests than the number of random numbers you picked (and how much fewer would depend on how thorough you are with your trial division; checking the factors 3, 5, 7 will be less effective (but cheaper) than checking all potential prime factors less than, say, a million).


This is true.

A conciser statement is: If an adversary can find a message $m$ for which $H(m) = 0$, then the adversary can forge the signature $(r, s)$ on $m$, where $r = x([k] Q)$ for some arbitrary ‘nonce’ $k$ (e.g., 1), and $s \equiv r k^{-1} \pmod n$, because $$x\bigl([H(m)\,s^{-1}] G + [r s^{-1}] Q\bigr) \equiv x\bigl([rr^{-1}k] Q\bigr) \equiv x([k] Q) \equiv r \pmod n,$$ satisfying the verification equation.

The obvious solution is to pick a hash function for which an adversary has no hope of finding preimages of 0, of which the streets of cryptography are littered with examples.  Here's one: SHA-256.

Suppose an adversary can cause a signer to accidentally compute 0 for $H(m)$ via some fault attack and learns a ‘signature’ $(r, s)$ on a hypothetical message $m_0$ with $H(m_0) = 0$.  Now what, supposing the adversary knows no such message $m_0$?  From this the adversary learns a uniform random curve point's $x$ coordinate $r = x([k] G)$, and a uniform random scalar $s \equiv r k^{-1} d \pmod n$, where $d$ is the signer's secret scalar and $k$ is the signer's secret nonce.

These are not independent, but they are related by a discrete log: if the adversary can compute $d$ from $(r, s)$, then the adversary can also compute $k$, the discrete log of $R = \pm x^{-1}(r)$ from the base point $G$.  And if the adversary can compute discrete logs, they might as well just compute $d$ offline from $Q = [d] G$ without bothering to apply a fault attack in the first place.

In other words, this does not really seem worse than a fault attack revealing an unintended signature on any other message with a nonzero hash.  And the signer can always thwart fault attacks by verifying the signatures it computes before revealing them.


How can I implement the elliptic curve MOV attack myself?

It is all pairings... this is a rather complex matter. I recommend reading Ben Lynn's PhD dissertation; it is about as nice an introductory text on pairings as you can get.

The definition is rather mind-twisting:

You first define divisors, which are rather formal objects. It is the free group of the curve points: for each curve point $P$, you define a divisor $(P)$, and then you add divisors together, so the complete form of a divisor is a linear combination: $\sum_{P\in E} a_P (P)$. This is a formal sum: all the linear combinations are deemed distinct from each other. In particular, $(P+Q)$ (the divisor associated with the point $P+Q$) is not the same as $(P)+(Q)$ (which is the sum of two elementary divisor, and is thus a divisor in its own right, but not associated with a curve point). Each $a_P$ is an integer (possibly negative).
Then you consider rational functions over the curve (these are functions $f = R_1(x,y)/R_2(x,y)$ where $R_1$ and $R_2$ are polynomials, and $(x,y)$ are the coordinates of curve points).
Then you establish a kind of bijection between divisors and rational functions. The function $f$ has zeros (roots of polynomial $R_1$) and poles (roots of polynomial $R_2$): you map $f$ to a divisor $\sum_{P\in E} a_P (P)$ such that:

if $P$ is a zero of multiplicity $n$ then $a_P = n$;
if $P$ is a pole of multiplicity $n'$ then $a_P = -n'$;
otherwise $a_P = 0$.

It so happens that to a given divisor corresponds a unique rational function $f$, up to a multiplicative constant. This is not completely surprising: we know that a polynomial can be rebuilt (up to a multiplicative constant) from knowledge of its roots: if polynomial $T$ has root $t_1$ with multiplicity $2$ and root $t_2$ with multiplicity $3$, then $T = \alpha (X-t_1)^2(X-t_2)^3$ for some constant $\alpha$. Here, this is extended to rational functions, which contain two polynomials, hence the zeros and the poles (our $f$ functions are over two variables $x$ and $y$ instead of one, but the same principle is at work here). We denote the divisor corresponding to function $f$ by $\operatorname{div}(f)$.
Then the really confusing part: for some reason, we begin to apply rational functions to divisors. It took me some time to understand this step. We define a new operation which takes a rational function $f$ and a divisor $D$, and computes $f(D)$. Then magic occurs: for two functions $f$ and $g$, we have $f(\operatorname{div}(g)) = g(\operatorname{div}(f))$ (the "Weil reciprocity").
Then we define the Weil pairing as a quotient of two such applications of functions on divisors. The quotient makes the multiplicative constants disappear, and the result is well-defined.

Then you want to compute the pairing. Mathematically, you would need to build two huge rational functions (the polynomials would have $2^{160}$ or so coefficients, so that's not feasible) and then apply these functions to some divisors (which are equally humongous). However, since we are just interested in the final application result, we can remove a lot of needless complexity, and that's Miller's algorithm.

All of this suppose that you start with a finite field $\mathbb{F}_q$ for some $q$ (a prime or a prime power), then do all computations in some extension field $\mathbb{F}_{q^k}$ for some $k$ called the embedding degree. Theory shows that if your points of interest have order $r$ (a prime number)(points of order $r$ are called $r$-torsion points), then the pairing remains trivial (you get $1$ at the end), until $k$ is "large enough": precisely, the $k$ value at which things get interesting is the smallest $k \geq 2$ such that $r$ divides $q^k-1$ (that the Balasubramanian-Koblitz theorem).

For normal curves, the embedding degree $k$ is ludicrously high (the same order of magnitude as $q$), so you would have to do computations with numbers too large to fit in your computer, or, for that matter, in the Universe taken as a whole. However, if the curve is so that $k$ is small, then the pairing can be computed, and the MOV attack reduces the problem of discrete logarithm on the curve to the problem of discrete logarithm in $\mathbb{F}_{q^k}$, which can be substantially simpler.

In particular, when $q$ is prime and equal to $3$ modulo $4$ and the curve is $Y^2 = X^3+aX$, then $k = 2$. If $q$ is a 256-bit integer, then the MOV attack turns discrete logarithm over a 256-bit curve (infeasible) into discrete logarithm in a 512-bit field (hard but feasible).

Implementing pairings is a deep exploration into non-trivial mathematics. It is enlightening, but daunting. For practical purposes it may be simpler to rely on some existing code, e.g. Ben Lynn's PBC library).

(I am writing all of this from memory, there could be some mistakes. Feel free to fix them.)


How secure is a hash based signature scheme after signing assuming quantum computers?

Two things:

The question "how hard is the oracle-based collision-finding problem be for a Quantum Computer" is an open question; we know that it is somewhere between $O(\sqrt[3]{n})$ and $O(\sqrt{n})$ effort (I recall a paper showing that $O(\sqrt[3]{n})$ Oracle queries is the lower bound, but I forget what paper that was) - we don't know where in the range it actually is.  Brassard et al showed an algorithm that found collisions with $O(\sqrt[3]{n})$ Oracle queries; however Dan pointed out that the other costs associated with the algorithm made it actually more expensive than just running a large number of second-preimage finders in parallel [1].  What is currently unknown whether there exists another algorithm that uses $o(\sqrt{n})$ Oracle queries [2], and doesn't have the other expenses that the Brassard algorithm has...

The three current 'hash based signature standards', namely, LMS, XMSS and Sphincs+ don't actually rely on collision resistance, even when doing the initial hash of the message.  What all three do is, when the signer is given a message $M$, the signer selects an unpredictable $R$ and then computes $\text{Hash}(R + M)$ (and then uses that hash for the rest of the signature operation).  If the adversary submits a message to be signed, he doesn't know what the value $R$ that the signer will select; instead, to perform a collision attack, he would need to select two distinct messages $M, M'$ for which $\text{Hash}(R + M) = \text{Hash}(R + M')$ with nontrivial probability (given the probability distribution of $R$), and that would appear to be far more difficult than finding a collision.

[1] The Brassard algorithm is essentially a large multi-target second preimage attack, and Dan's complaint is that the quantum logic to do a recognization over a large sparse unstructured space is quite expensive. In an unpublished work, I looked at the Brassard algorithm, and searched for the 'sweet spot' between 'number of targets per searcher' and 'number of searchers' - based on the published SHA-256 Quantum circuit, and a sketched out target recognizer circuit I drew, I came to the conclusion that this made the problem circa a factor of 1000 cheaper to attack than a single preimage problem (and the sweet spot was circa a million targets per searcher).
[2] For those who are unfamiliar with little-oh notation, $o(\sqrt{n})$ means 'fewer than $c\sqrt{n}$ queries, for any $c > 0$ (as long as $n$ is large enough, and the meaning of "large enough" depends on $c$).  More colloquially, $o(\sqrt{n})$ means 'grows slower than $\sqrt{n}$'


The system described in the quoted article depends on the security of AES with random keys (not only on the theoretical unbreakability of the OTP) for at least two things:

the encryption of large files, as apparent in the quotes of the question;
the initial establishment of the OTP, as shown by this other quote

  The first step is always optical, and that is an exchange of an AES 256bit key, plus an authentication key, and so those are the keys to encrypt the One-time pad as it’s being transferred wirelessly via Multipeer [or Wi-Fi Direct]… with a symmetrical AES key that was exchanged optically.

Claims that a practical system base its security directly on the OTP are typically misleading, on purpose as a marketing point or by incompetence, often both.

Addition per comment: the technique used for photos seems to be using 256 bits from the pad as an AES key enciphering the photo. This is not as secure as the OTP from an information-theoretic standpoint, yet this is believed practically secure when done properly.


Encryption that could have multiple decryption key

What you ask is very well possible.

Let's assume you have a document DATA you want to encrypt. You first randomly generate a symmetric key K and authenticate and encrypt DATA using this one.

In the next step you asymmetrically encrypt K with the end user's public key and store the resulting cipher text along with the encrypted data.
For allowing your administrators to access the file only when at least two collaborate you have two options:

Secretely share a private key among the administrators using a threshold of $k=2$ and encrypt K using the corresponding public key. The drawback of this one is, that the admins actually learn the private key and nothing can stop them from decrypting all files without per-file collaboration of two admins.
Give each administrator a private key and secretely share a symmetric key (with a threshold $k=2$) that can recover K (on a per-file basis). Encrypt the shares using the admins' keys and store them with the encrypted DATA and when they need to access a file, they first have to recover the symmetric key using secret sharing and then they recover K. The advantage here is that for each file two administrators have to collaborate but the drawback is that you now need to store $n$ ($n$ being the number of admins) asymmetrically encrypted cipher texts instead of $1$.


As CodesInChaos mentioned in the comments, you could simply set the size of the digested block to one byte (or bit, if that is your preference). Also as mentioned in the comments, this will not necessarily work nicely with any given hashing construction.

Is it required to always split the message into blocks instead of processing bytes?

I am not sure how you would process any input without breaking it into some kind of blocks. Considering that a block can be an arbitrary size that is usually defined by the algorithm in question, a block could range from 1 bit to however many bits constitute a complete input message. One bit is a valid blocksize, one byte is a valid blocksize, and X-Y bit words for any X and Y is a valid blocksize.

So I would say yes, it is unavoidable to split the message up into blocks for processing. Input of any length that you feed into the compression function constitutes a block. This seems unavoidable, unless you simply don't compress any input. Even if you compress the entire message at once, you are still working on one block.

Is this just an artifact of the functions used internally by the hash

The blocksize influences the performance of the compression function. If you digest 512 bits at a time using X instructions, clearly this will digest data much more quickly then digesting 1 bit at a time using the same X instructions. This assumes the CPU has appropriately sized registers and instructions for operating on the desired word size - which may not necessarily be the case.


Is there a way to prove knowledge of a limited resource like a phone number just to the people who already know about it?

As you mention, phone numbers have low entropy. Someone who "doesn't know" a phone number at the time of the proof can easily obtain the phone number later. You won't be able to find a non-interactive solution to this problem -- an attacker can always run a dictionary attack and use your "proof" as a test for whether they've found the right number.
For an interactive solution, this problem is often known as the socialist millionaire's problem. Two parties each have a private string, and they want to simply test whether their strings are equal while revealing nothing in the case that the strings are different. The secret strings do not have to have high entropy. You can also achieve this functionality by a symmetric password-authenticated key agreement (PAKE) with explicit mutual authentication / key confirmation. With PAKE, the two participants agree on a random key only if they hold the same secret (low-entropy) "password". Mutual authentication means that the parties are notified if their passwords don't match (instead of simply walking away from the conversation with unrelated keys).
Since these protocols are interactive, it only matters what password (phone number in your case) they use during the interaction. Someone who doesn't know the password only gets one shot to guess it. Using some password $pw$ in the protocol does not leave a way to later test whether a different password $pw'$ was the correct one.


Creating certificate: Where is my private key stored?

Typically you send a Certificate Signing Request (CSR) to the CA. The CSR contains everything you want to be inside your certificate, including your public key. The CA takes a look, and if it likes it, creates a certificate and signs it and sends it back to you. The CA never has to see your private key.


RSA attack with continued fractions (Wieners attack)

Let $n=pq$ be an RSA modulus.  Let also $e$ be the public exponent and $d = e^{-1} \bmod (p-1)(q-1)$ the matching private exponent.

From $ed \equiv 1 \pmod{(p-1)(q-1)}$, there exists some integer $k$ such that $$ed = 1 + k(p-1)(q-1) = 1 + k(n-p-q+1) \iff kn-ed=k(p+q-1)-1$$  Dividing through by $dn$ yields
$$\frac{k}{d}-\frac{e}{n} = \frac{k}{d}\Bigl(\frac1{q}+\frac1{p}-\frac1{n}\Bigr) - \frac1{dn}$$

Furthermore, we have the following theorem.

Theorem   If $|\frac{a}{b}-x| < \frac1{2b^2}$ then $\frac{a}{b}$ is a continued fraction approximant for $x$.

So, if the condition of the previous theorem is fulfilled then $k/d$
is a continued approximant for $e/n$. Since $e/n$ is public and since continued fractions can easily be computed, it is possible to find the secret
exponent $d$ (again provided that the condition of the theorem is satisfied).

In particular, assuming $p \sim q \sim \sqrt{n}$ and $e \sim n$, the condition of the theorem is satisfied for a private exponent $d$ of order up to $n^{1/4}$.

Proof. First, we note that if $e \sim n$ then $k \sim d$.  Moreover, we have
$$\Bigl|\frac{k}{d}-\frac{e}{n}\Bigr| \le \frac{k+1}{dn}+\frac{k}{d}\Bigl(\frac1{p}+\frac1{q}\Bigr) \sim \frac1{n} + \frac1{\sqrt{n}} \sim \frac1{\sqrt{n}}$$

Therefore $|\frac{k}{d}-\frac{e}{n}| < \frac1{2d^2}$ if $d$ is of order at most $n^{1/4}$.

Back to your example, the continued fraction development of $e/n$ is $[0,2,1,9,6,54, 5911, \dots]$. Hence, the successive convergents for $e/n$ are
$$\frac{0}{1}, \frac{1}{2}, \frac{1}{3}, \frac{10}{29}, \frac{61}{177}, \frac{3304}{9587}, \frac{19530005}{56668934}, \dots$$

Provided that the conditions of Wiener's attack are met (i.e., $d$ of order up to $n^{1/4}$), we know that $k/d$ is among them.  Actually, you can check that $d = 9587$ is the corresponding private exponent.

In this example, we also have $n^{1/4} \approx 674144$ and $56668934 \gg 674144$.


TL;DR

Don't look for a primitive that provides the best communication efficiency. Instead, look for ones that are rich with desirable features.

Asker's confession

As the OP, I've always had a compulsive frustration that we don't get to enjoy the `perfection' and elegance that elliptic curve primitives used to provide in pre-quantum public-key cryptography. ECC operations are efficient compared to RSA; have actual exponential keysize-security relation; and quite a few other nice properties.

However, ECC isn't always a silver bullet. It requires generating system parameters in complicated ways; and certain parameters must be verifiably secure and sound - which isn't easy to achieve.

Symmetric-key analogy

It should be noted, that constructing secure and efficient primitives in symmetric-key cryptography, is no less noble an art than that in public-key cryptography.

Some blockciphers may require larger and more complex key schedule; some hash functions may require larger internal states, or more pre-computed constants, or both; some AEAD construct may run fast on some systems, but very slow on others.

Why answer my own question

The way the question requests an answer can't be say isn't "too broad" - it really is a bit too broad because I think it's quite deep.

I'd like to answer myself in a way that can inspire thinking instead of pointing people to a mis-predicted future.

What we really should look for

Communication / object size efficiency.
Computation efficiency / performance.
Interoperability.
Ability to be implemented correctly.
Ability to be implemented cost-efficient.

etc.

All these factors must be balanced.


How to use `openssl asn1parse` or equivalent on output files from `ssh-keygen -t rsa -b 4096`?

The private key is like a PKCS#8 encrypted private key. However, it misses the wrapper that indicates the type of encryption used. Instead, this information is present in the PEM header.

-----BEGIN RSA PRIVATE KEY-----
Proc-Type: 4,ENCRYPTED
DEK-Info: AES-128-CBC,12FF93A74CD3E34DFEF8B1CF04FFEFA6

bsUb0TiyTU9RML8PteBhjd1vwdDv/MB8kR6+J1506dkS3+t1b6mEYNKDkZeQYPPt
...
mnLNzPODtVFrEeinQcfzQCCIS+VOrtTE3dJ3bklN8he3qQmnDC9+nyQsX2Q8EuUw
-----END RSA PRIVATE KEY-----

So the base 64 encoded contents of the PEM encoded private key is just the ciphertext that makes up the wrapped private key. As the ciphertext is indistinguishable from random you won't find much structure in there. To parse it you will first have to decrypt it.

As for the SSH public key, the key is in OpenSSH compatible format, which isn't specified using ASN.1 and doesn't use BER/DER encoding.

ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAACAQDTYu/U8i2a+AVe0GnZJbpJCRFwPa4yN0S77x0ZTKUudzx9OXf20reuiaDarH6x+r1XMvh/9EwarRw3CquXAdEIZ4O2AZHmgvkQCJK1Q7ZRN3rpfIrMMPqjf7NLAEmUNoI/oS977jSynRtBK001NGD4YqY9uuFLyMHPqEwR9Ii
...
/yE8pvaO6qJIIzNbTQ== maartenb@Lenovo-PC

So trying to parse it using the asn1parse will obviously not work. You would need to use SSH itself for that. One way of doing that (the long way) can be found here.


Using variable length CBC-MAC, can some block cipher with a fixed k be used as a cryptographic hash function?

No, it cannot; you can find a preimage attack on it.

CBC-MAC on a two-block message $(M_0, M_1)$ (after padding) is defined as $E_k( M_1 \oplus E_k( M_0 ))$.  To find a preimage for a value $S$, you select $M_1$ with a valid padding pattern (because of the padding, we cannot select this block arbitrarily), and compute $M_0 = D_k(M_1 \oplus D_k(S))$; it is easy to see that the padding message $(M_0, M_1)$ hashes to the value $S$.

And, even if you cannot easily compute $D_k$, it is still easy to find second preimages...


Why does Apple use One-Pass Diffie-Hellman for file encryption?

If you have a look in the introductory paragraph of Section 6.2.2 of the NIST SP 800-56A document, you will find an explanation of how the one-pass key-agreement protocol is supposed to work.

If I understand the description you are quoting correctly, some public ECDH key corresponding to a static ECDH key pair is used to encrypt files while the device is locked, because the actual symmetric encryption key is only available when the device is unlocked. Furthermore, each file gets encrypted with a separate per-file key. This is where the one-pass key-agreement comes into play. In particular, one uses it to derive a per-file key, which is in turn used to encrypt the actual file (one has different keys per file since the ephemeral keys are freshly chosen for each file). Then, as soon as the device gets unlocked one can use the static secret key corresponding to the ECDH key pair to obtain the per-file key using the key agreement protocol and then store/encrypt the file as it would have been stored/encrypted if the device would have been unlocked in the first place.


Non adjacent form of an integer is unique

Non-Adjacent Form (NAF), also called Balanced Binary Representation (BBR), is a representation of integers reminiscent of binary, but with an extra $-1$ value for digits, and such that at least one of two adjacent digits is $0$. Because the resulting representation has at least half of its digits at zero (typically about $2/3$), it can be used to speed-up modular exponentiation, or point multiplication on an arbitrary group (e.g. Elliptic Curve).

We define a NAF of $a\in\mathbb N$ as any tuple of $j\in\mathbb N$ integers $a_i\in\{-1,0,+1\}$ with $0\le i<j$, such that:

$a=\sum_{i=0}^{i=j-1}a_j\;2^j\;\;$ (same formula as for binary)
$j>0\implies a_{j-1}\ne0\;\;$ (the highest-rank digit, if any, is non-zero)
$0<i<j\implies a_i\;a_{i-1}=0\;\;$ (at least one of two adjacent digits is $0$)

Each $a$ has a unique NAF (we'll prove this in detail). These defining properties of NAF need no change for an extension to $a\in\mathbb Z$. There is either $0$ or $1$ more digit in the NAF for $a$ than in the binary representation of $|a|$; more precisely, for $a\ne0$, $j=\lceil\log_2(3|a|)\rceil-1$.

Counting from $0$ in NAF goes (showing the big-endian form, then the little-endian tuple):
 $\;a=0:\;$             $\;\;\;j=0\;\;()$
 $\;a=1:\;$          +1 $\;\;\;j=1\;\;(a_0=+1)$
 $\;a=2:\;$       +1  0 $\;\;\;j=2\;\;(a_0=\;\;\;0,\;a_1=+1)$
 $\;a=3:\;$    +1  0 -1 $\;\;\;j=3\;\;(a_0=-1,\;a_1=\;\;\;0,\;a_2=+1)$
 $\;a=4:\;$    +1  0  0 $\;\;\;j=3\;\;(a_0=\;\;\;0,\;a_1=\;\;\;0,\;a_2=+1)$
 $\;a=5:\;$    +1  0 +1 $\;\;\;j=3\;\;(a_0=+1,\;a_1=\;\;\;0,\;a_2=+1)$
 $\;a=6:\;$ +1  0 -1  0 $\;\;\;j=4\;\;(a_0=\;\;\;0,\;a_1=-1,\;a_2=\;\;\;0,\;a_3=+1)$
 $\;a=7:\;$ +1  0  0 -1 $\;\;\;j=4\;\;(a_0=-1,\;a_1=\;\;\;0,\;a_2=\;\;\;0,\;a_3=+1)$
 $\;a=8:\;$ +1  0  0  0 $\;\;\;j=4\;\;(a_0=\;\;\;0,\;a_1=\;\;\;0,\;a_2=\;\;\;0,\;a_3=+1)$
 $\;a=9:\;$ +1  0  0 +1 $\;\;\;j=4\;\;(a_0=+1,\;a_1=\;\;\;0,\;a_2=\;\;\;0,\;a_3=+1)$

To establish that an integer $a$ can't have two different NAFs, we use an argument of infinite descent, a special case of proof by contradiction. We hypothesize there exists integer(s) with at least two distinct NAFs, and define $a$ as the smallest such integer. We'll construct an integer $b$ less than $a$ with two distinct NAFs (leading to contradiction).

We note one of the two distinct NAFs for $a$ using $j$ and $a_i$, and another using $\tilde j$ and $\tilde a_i$, swapping theses if necessary so that $\tilde j\le j$. The only case with $j=0$ gives both NAF empty, thus identical, hence $j\ge1$.

If we had $a=0$, we would have $a=0=\sum_{i=0}^{i=j-1}a_j\;2^j$ with $a_{j-1}\ne0$, and by explicitly computing the minimum and maximum of the other terms as a sum-of-powers, we show this can't hold. Hence $a>0$, and hence $\tilde j\ge1$.

We consider three cases each leading to contradiction:

If $a\equiv0\pmod2$, then by reducing modulo $2$ the equation $a=\sum a_i\;2^i$, it comes that $a_0=0$.
$b=a/2$ is an integer less than $a$ (since $2b=a$ with $a>0$), and it's easily verified that the $j-1$ integers $b_i=a_{i+1}$ for $0\le i<j-1$ obey each condition for a NAF for that $b$. Similarly, a NAF for that $b$ is the $\tilde j-1$ integers $\tilde b_i=\tilde a_{i+1}$ for $0\le i<\tilde j-1$, and that's another NAF (since $a_0=0=\tilde a_0$ and the two NAFs for $a$ are distinct).
If $a\equiv1\pmod4$, then by reducing modulo $4$ the equation $a=\sum a_i\;2^i$, it comes that $2a_1+a_0\equiv1\pmod4$, thus $a_1=0$ and $a_0=+1$ (notice that $a_1=+1$ and $a_0=-1$ is ruled out by $a_1\;a_0=0$).
$b=a-1$ is an integer less than $a$, and a NAF for that $b$ is the $j$ integers $b_0=0$, and $b_i=a_i$ for $1\le i<j$. Similarly, another NAF for that $b$ is the $\tilde j$ integers $\tilde b_0=0$, and $\tilde b_i=\tilde a_i$ for $1\le i<\tilde j$.
If $a\equiv3\pmod4$, then by reducing modulo $4$ the equation $a=\sum a_i\;2^i$, it comes that $2a_1+a_0\equiv3\pmod4$, thus $a_1=0$ and $a_0=-1$ (notice that $a_1=-1$ and $a_0=+1$ is ruled out by $a_1\;a_0=0$).
$b=(a+1)/2$ is an integer less than $a$, and a NAF for that $b$ is the $j-1$ integers $b_i=a_{i+1}$ for $0\le i<j-1$. Similarly, another NAF for that $b$ is the $\tilde j-1$ integers $\tilde b_i=\tilde a_{i+1}$ for $0\le i<\tilde j-1$.

There are several ways to explicitly construct the NAF of an arbitrary integer $a>0$ from that of a smaller integer $b$, recursively, until reaching $b=0$ that has a trivial NAF. For example:

If $a\equiv0\pmod2$, we build the NAF for $a$ as a tuple with one more element than the NAF of $b=a/2$, with $a_0=0$, $a_{i+1}=b_i$.
If $a\equiv1\pmod4$, we build the NAF for $a$ as a tuple with two more elements than the NAF of $b=(a-1)/4$, with $a_0=+1$, $a_1=0$, $a_{i+2}=b_i$.
If $a\equiv3\pmod4$, we build the NAF for $a$ as a tuple with two more elements than the NAF of $b=(a+1)/4$, with $a_0=-1$, $a_1=0$, $a_{i+2}=b_i$.

In all three case, it is easy to derive the properties required from the NAF of $a$ from these for the NAF of $b$.

Various sources credit the idea, proof of uniqueness of NAF representation, and proof of optimality of the non-adjacency criteria from the standpoint of maximizing the number of zeros, toGeorge W. Reitwiesner, Binary arithmetic (paywalled), Advances in Computers, vol. 1, pp. 231-308, 1960.

I recommend Jeffrey Shallit: A Primer on Balanced Binary Representations (1992-1993, Department of Computer Science, University of Waterloo). I'm not the only one to find it late!

Marc Joye and Christophe Tymen: Compact Encoding of Non-Adjacent Forms with Applications to Elliptic Curve Cryptography (in proceedings of Public Key Cryptography 2001) notice that we can re-encode NAF as bits using a simple Hamming code, storing integers as NAF essentially as compactly as in binary, while keeping them directly usable for fast point multiplication.


Actually it seems to me that you are using the wrong basis and got the key for the other way around:

Suppose you have the plain text $x_1 = \pmatrix{5\\17}$ and $x_2= \pmatrix{8\\3 \\}$ and the corresponding ciphertexts $y_1=\pmatrix{15 \\16}$ and $y_2=\pmatrix{2\\5}$ and please note how I represent those as vectors and not line matrices, then everything seems to work fine with your method:

Hill's cipher translates into:
$$\pmatrix{k_{11}&k_{12}\\k_{21}&k_{22}}\times x_1 \equiv y_1 \mod 26$$
$$\pmatrix{k_{11}&k_{12}\\k_{21}&k_{22}}\times x_2 \equiv y_2 \mod 26$$

This leads to the system you are solving (but you may also represent it using 4 equations) and you get:
$$\begin{cases}5k_{11}+17k_{12} &= 15\\
5k_{21}+17k_{22} &= 16\\
8k_{11}+3k_{12} &= 2\\
8k_{21}+3k_{22} &= 5\end{cases}$$
Which correspond, once represented using matrices, to solving:
$$\pmatrix{5&17 \\ 8&3} \times \pmatrix{k_{11}\\k_{12}} \equiv \pmatrix{15\\2} \mod 26$$
$$\pmatrix{5&17 \\ 8&3} \times \pmatrix{k_{21}\\k_{22}} \equiv \pmatrix{16\\5} \mod 26$$
Since you have computed it, you know that
$$X^{-1} \equiv \pmatrix{9&1 \\2&15 \\} \mod 26$$
for $X=\pmatrix{5&17 \\8&3 \\} $.

But now, this is where it seems to me that you are doing something wrong: to get the key, you can simply solve the above equations by left-multiplying by $X^{-1}$ so that:
$$ \pmatrix{k_{11}\\k_{12}} \equiv X^{-1}\times X\times \pmatrix{k_{11}\\k_{12}} \equiv X^{-1}\times y_1\equiv \pmatrix{9&1 \\ 2&15} \times \pmatrix{15\\2}\mod 26$$
and the same holds for $X^{-1}\times y_2$:
$$ \pmatrix{k_{21}\\k_{22}} \equiv X^{-1}\times X\times \pmatrix{k_{21}\\k_{22}} \equiv X^{-1}\times y_2\equiv \pmatrix{9&1 \\ 2&15} \times \pmatrix{16\\5}\mod 26$$
 and you end up with the key which seems to be, after computing the latest results:
$$\begin{cases}k_{11}=7\\ k_{12}=8 \\k_{21}=19\\k_{22}=3\end{cases}$$
And which translates into $$K=\pmatrix{7&8\\19&3}$$
And you can check that $ay$ get encrypted into $ku$
$$ K \times \pmatrix{0\\24}\equiv \pmatrix{10\\20} \mod 26$$
But to decrypt anything, you'll need to invert the key to get:
$$K^{-1}=\frac{1}{det(K)}\pmatrix{3&-8\\-19&7}\equiv 25 \pmatrix{3&-8\\-19&7} \equiv \pmatrix{23&8\\19&19} \mod 26$$
And so you can decode the $fr$ from the $pq$ by:
$K^{-1}\times \pmatrix{15\\16} \equiv \pmatrix{5\\17} \mod 26$
which checks out.

This is because decoding Hill's cipher necessitate to left-multiply the cipher by the inverse of the key.