Security of simple xor and s-box cipher?

Let a "block cipher" be defined with a fixed S-box $S$ (i.e. a permutation of some space) and a key $K$ (same size than a block), such that the encryption of a block $M$ is $C = S[P\oplus K]$. Everybody knows $S$ and can apply and invert it (that's a "S-box", not a "key" -- if the S-box is "key dependent" then the S-box is itself a block cipher in its own right, and that's another question). Since the key has the size of a block, blocks are supposed to be large enough to defeat exhaustive search on the key (say, we use 128-bit blocks).

Hence, given a single known plaintext block and the corresponding ciphertext, an attacker can trivially recover $K$: $K = S^{-1}[C] \oplus M$. This is weak unless you ever encrypt a single block with a given key, in which case this is just One-Time Pad. The S-box here is a red herring: as a generic rule, any fixed public permutation for which either the input or output is known can be "removed" at will, so it adds nothing to security. For instance, in DES, the "Initial Permutation" and the "Final Permutation" (which swap bits around in a 64-bit word) can be abstracted away from the security analysis, because anybody can apply and unapply them. Without the S-box, we get $C = M \oplus K$, the well-known equation for OTP.

Since a fixed permutation is as good as gone when it operates on known values, and since we usually consider that the attacker knows some plaintext/ciphertext pairs, this means that a S-box, to be useful, must be "isolated" from both plaintext and ciphertext. So we can imagine the following design:

$$ C = K \oplus S[M \oplus K] $$

This is what @Ethan suggests to study as an exercise (except the he talks about 16-bit blocks, hence a 16-bit key, which is trivially undone through exhaustive search; here, let's assume that $C$, $M$ and $K$ are sequences of 128 bits). If you look at the slides that Ethan points to, you will learn that this is a special case of a more generic construction from Even and Mansour, which goes like this:

$$ C = K_2 \oplus S[M \oplus K_1] $$

with two $n$-bit keys $K_1$ and $K_2$. John Daemen has then shown that although the total key material length is $2n$ bits, you get much less security, actually no more than $2^{n/2}$. With $n = 128$, that's "64-bit security", a rather low value against today's technology (64-bit exhaustive key search is expensive but has been done at least once with thousands of machine and 5 years of computation). With $n = 256$, we could hope for 128-bit security, albeit with 512 bits of key material.

However, there are two important points about that:

The subkeys $K_1$ and $K_2$ should be unrelated. Using the same key for both, or simply keys which admit simple algebraic relations, may allow for many additional attacks.
The $2^{n/2}$ bound is for a generic S-box, i.e. a permutation taken at random over all the permutations of $n$-bit blocks. But the S-box is computable. There exists a rather compact piece of code which can run it in both directions. Yet, there are $2^n!$ permutations of $n$-bit blocks, which implies that the minimal representation of a random permutation will need, on average, at least $2^{264}$ bits, if $n = 256$. This is ludicrously high (it will not fit in the known Universe). Conclusion: an actual implementation of that cipher will use a specific S-box out of the very limited set of S-boxes than can be computed by some code which fits in a few kilobytes of opcodes and constant arrays. The S-box necessarily has some structure. Structure might be exploitable, and often is. The $2^{n/2}$ theoretical strength may then be hard to reach in practice.

So the Even-Mansour scheme is not "secure enough". What do cryptographers do in such a situation ? They add more rounds ! So we are talking about something like:

$$ C = K_5 \oplus S[K_4 \oplus S[K_3 \oplus S[K_2 \oplus S[K_1 \oplus S[K_0 \oplus M]]]]] $$

for, say, 5 rounds. How many rounds do we need ? This depends on the specific unavoidable structure of $S$, and also on how "different" the $K_i$ are (we would, in practice, generate the $K_i$, dubbed "subkeys", from a master key $K$ through a deterministic process -- the "key schedule" -- which itself will have some potentially exploitable structure). We want the whole thing to be decently efficient, so we cannot add thousands of rounds, and we must cope with a relatively simple $S$.

Down that road lies... the AES itself. With 128-bit blocks and a 128-bit master key, the AES uses 10 rounds, hence 11 subkeys. Each round $S$ is a combination of a few operations, some linear (in a given vector space over $\mathbb{F}_{256}$), and an internal fixed permutation over 8-bit blocks (what the AES specification calls "the S-box", but not what we call $S$ in this text !). The AES is believed secure for what it is meant to be. It has raised a few concerns about "related keys": pairs of keys which induce the corresponding AES instances to behave in a related way, which can be detected; nothing serious for encryption, but something to watch for if you want to use the AES as part of, say, a hash function. This is due to the mathematical structure in the key schedule. The Whirlpool hash function is a hash function derived from the AES, and the first thing the Whirlpool designers do was to replace the AES key schedule with something with less exploitable structure (but also slower).

Summary: designing a block cipher as a sequence of XOR with (sub-)keys mixed with a fixed permutation of the whole block space is a valid block cipher design. But with a single "perfect" S-box and two sub-keys, you do not get your money worth of security (you get at most $2^{n/2}$ of a $n$-bit block). And since both the S-box and the key schedule cannot be "perfect", you have to add more rounds, and be very careful about the mathematical structures that you must necessarily employ. The current best-in-class design with that kind of structure is the AES, and it took many smart cryptographers and a lot of time to actually build some trust in its security.


Why aren't 4096-bit RSA PGP key blocks $\lceil\frac{4096}{6}\rceil=683$ base64 characters long?

Base64 uses $64=2^6$ characters, and hence can encode at most 6 bits per character.  Hence, the correct calculation would be at least $\frac{4096}{6} = 682 \frac{2}{3} $ characters (or 683, we really can't have fractional characters)

As far as why PGP keys are longer than that, well, that's because they're carrying around a lot more information than just the raw RSA key.


FIPS 202/SHAKE: insecure 3DES key derivation example

There may well be situations where Eve does not have to trick anybody; in the scenario in FIPS 202 the parties badly use the XOF so the mistake is not necessarily triggered by Eve.

The equations in your question are really not needed. My guess is that you're making it more complex than it needs to be.

Say that Alice and Bob use 3DES with 2 keys $f$ and $g$ then attacking that two-key 3DES key means overcoming a security strength of ~80 bits (given that the chosen plaintext attacks on 2 key 3DES are possible, but hey, we're not excluding any attack here).

Once key $f$ and $g$ are known the key $h$ can simply be brute forced, as single DES only has a strength of 56 bits - the strength of DES itself. However, that means a maximum number of operations of $2^{80} + 2^{56}$, not $2^{80} \times 2^{56}$. In other words, the resulting scheme has a strength of ~80 bits instead of the promised 112 bits offered by three-key 3DES. Removing 32 bits of security certainly counts as a break in any scheme.

The final conclusion that you've written down: that this would be mainly an issue with long-term (or at least often used) keys seems correct.

The point that the FIPS document tries to make is that you should not ever reuse output of the XOF, even if the output size differs - for example when used as underlying function of a Key Derivation Function (KDF).

This indeed has nothing to do with the security of the XOF itself.


Blind quantum computing and fully homomorphic encryption

Well, since I'm one of the authors on the paper, let me try to answer your question.

First I should explain that the paper you link to is not the original paper proposing that approach, but rather the first implementation of it (in this case using quantum optics). The original paper which introduced the Universal Blind Quantum Computing (UBQC) protocol which the experiments demonstrate was written by myself along with Anne Broadbent and Elham Kashefi, and appeared at FOCS in 2009, so at least some people in the CS community took us seriously. I should also point out that of the three of us, only I am a physicist. Elham and Anne are both computer scientists. Indeed Anne's PhD supervisor was Gilles Brassard, one of the Bs in BB84, and one of the discovers of quantum key distribution.

One might ask why our original paper doesn't reference fully homomorphic encryption, but that is easy to answer. It simply didn't exist when we wrote the paper in 2008.

As David Cash mentions in the comments above, UBQC is a quantum protocol, and hence requires quantum information processing, meaning at least some quantum computational abilities. It is certainly not something you can expect to deploy tomorrow, and any large scale version of this kind of thing is likely decades off. We worked with one of the top experimental groups to implement it, and still only managed 4 qubits (essentially hiding a 12 bit description of the circuit).

Now, we're certainly not the only ones to have written about the concept of blind quantum computation. The term is taken from a 2003 paper by Arrighi and Salvail which introduced a non-universal blind computation protocol, although there was earlier work by Childs. A few months after us, and apparently independently, Aharonov, Ben-Or and Eban came up with a similar idea in the context of interactive proofs.

There are some important differences between blind quantum computing and homomorphic encryption. First, blind computation and homomorphic encryption are fundamentally different in what they seek to achieve. In blind computation the aim is to have a remote computer perform a computation for you in such a way that it remains "blind" to the computation (i.e. the input, output, and the actual computation performed), and should only learn upper bounds on the resource requirements. In homomorphic encryption the situation is somewhat different, since while the intention is indeed to hide the input and output, the computation itself is known to the remote computer and not necessarily to the user. This is a fundamental difference in the goals of the various protocols. Secondly, protocols such as ours and the Aharonov-Ben-Or-Eban approach, take measures to ensure that the remote computer cannot interfere with the protocol without being detected, which is in completely the opposite direction to homomorphic encryption. Thirdly, there is a fundamental difference in security. Many of the blind quantum computation protocols are information theoretically secure, meaning that they are secure independent of the computational power of their adversary. This is not true of current schemes for fully homomorphic encryption. And, last, but certainly not least, blind quantum computing allows you to essentially boost the computational power of the user, in computational complexity terms, expanding the class of decision problems they can solve from P to BQP, which contains certain problems believed to be NP-intermediate problems such as factoring, which is not something fully homomorphic encryption currently allows for.

Let me close by saying why I think people should be interested in blind quantum computation. As I have said, as a tool for cloud computing, practical technologies would be decades off, and I certainly don't want to be guessing the future that far in advance. Rather, I would suggest, the main reason people currently find such protocols interesting is because of their possible consequences for the study of complexity classes, and as a practical means for verifying that purported quantum computing technologies do indeed function correctly (which is a non-trivial task since BQP is believed not to be contained in NP, and hence there exist no efficient means to verify the outcome of certain quantum computations after the fact).

I hope this helps answer your question.


In a TLS 1.3 connection, how do the client and server choose a mutual cipher suite?

The client doesn't - the server now chooses the ciphersuite. The client now sends the supported client suites and the server gets to choose. Fortunately there aren't that many ciphersuites for TLS 1.3 because the server is likely to have a somewhat shorter list (note that there are only two bytes required per cipher suite though).

Similarly, since there is only DHE and ECDHE for key agreement it is relatively easy to "guess" the key agreement protocol. It's pretty likely that a server supports both - and otherwise it just costs another round trip and key pair generation.

An even better explanation can be found here with clear indications of what gets send at what step in the communication between client / server.  Note that "key share" here is not an encrypted key, it's just the public key of the generated ephemeral key pair.


Is there a possibility to create a public key block cipher?

Let's make a list of reasons why public "block ciphers" are generally not used:

asymmetric ciphers expand the ciphertext compared to the plaintext, rather than being a permutation of a block of bits;
asymmetric ciphers require a lot more processing power;
asymmetric ciphers require a lot more state;
asymmetric ciphers are more vulnerable to side channel attacks (as they are based on big number arithmetic rather than binary operations on smaller words);
asymmetric ciphers are more vulnerable against attacks using quantum computers;
normal block cipher modes do generally not apply to asymmetric ciphers;
because of 2 & 3, (full) hardware acceleration is generally less common for asymmetric ciphers.

I've left the word "generally" out of above reasons, but that may have to be inserted in each reason. There may be asymmetric ciphers that violate one or more of the rules displayed above.

Hybrid cryptography - where asymmetric / public cryptography is combined with symmetric / secret key cryptography - is rather easy to implement. So there is simply not much need for modes of encryption that use an asymmetric cipher for larger messages.

Modes such as ECIES or RSA-KEM are easy to describe and implement. Their main drawback is that the symmetric cipher mode of operation is generally not standardized.


Does the backdoor in Dual_EC_DRBG work like that?

Not quite, but you're close.  I will write $[n]A$ for scalar multiplication of the point $A$ on the curve in question by the scalar $n$, as is more typical notation, and I will write $x(A)$ for the least nonnegative integer representative of the $x$ coordinate of $A$.

Let $E/k$ be an elliptic curve over the field $k$, and $P$ and $Q$ be two $k$-rational points of large prime order.

The initial state is a bit string interpreted as an integer $s_0$.  The $i^\mathit{th}$ state $s_i$ and output $r_i$ are given by
\begin{align*}
  s_i &= x([s_{i - 1}]P), \\
  r_i &= x([s_i]Q).
\end{align*}
If $P = [d]Q$ for some integer $d$, then $$s_{i + 1} = x([s_i]P) = x([s_i][d]Q) = x([d][s_i]Q) = x([d] x^{-1}(r_i)),$$ where $x^{-1}(r_i)$ is one of the two possible points with $x$ coordinate $r_i$.

Finding $d$ given $P$ and $Q$ is intractable in a curve for which the ECDLP is hard, but the nation-state adversary influencing cryptography standards could have picked $P$ and $d$ and then computed $Q$ from them.

You, too, can create your own Dual_EC_DRBG back door in the privacy of your own living room!  However, you probably can't get FIPS certification if you do that—and if anyone catches you at it outside your living room, you may fall afoul of US Patent 8,396,213 on how to design a key escrow euphemism for a back door.  And by design they can't distinguish whether you generated your own $P$ and $Q$ at random or picked $Q$ and $d$ first and then computed $P$ from them for a key escrow system, saving $d$ somewhere secure like a sticky note on your monitor.

So merely using base points other than the standard ones may be a violation of US patent law.  (Caveat: I may be a vulture, like many attorneys, but I have not passed the bar, and I am certainly not your patent vulture.)


https://tools.ietf.org/html/rfc6637#section-8

  Elliptic Curve Cryptography (ECC) in OpenPGP

  ...

  EC DH Algorithm (ECDH)

  The method is a combination of an ECC Diffie-Hellman method to
  establish a shared secret, a key derivation method to process the
  shared secret into a derived key, and a key wrapping method that uses
  the derived key to protect a session key used to encrypt a message.

  The One-Pass Diffie-Hellman method C(1, 1, ECC CDH) [NIST-SP800-56A]
  MUST be implemented with the following restrictions: the ECC CDH
  primitive employed by this method is modified to always assume the
  cofactor as 1, the KDF specified in Section 7 is used, and the KDF
  parameters specified below are used.

  ...

  The key wrapping method is described in [RFC3394].  KDF produces a
  symmetric key that is used as a key-encryption key (KEK) as specified
  in [RFC3394].  Refer to Section 13 for the details regarding the
  choice of the KEK algorithm, which SHOULD be one of three AES
  algorithms.  Key wrapping and unwrapping is performed with the
  default initial value of [RFC3394].

  ...


How different is SHA-512/224 when compared to SHA-512?

As stated by FIPS 186-4 (6.6) The only two differences between SHA-512 and SHA-512/224 are the eight 64-bit words used for initialization, given by FIPS 186-4 (5.3.6.1); and result truncation to the first 224 bits of the 512-bit result: $H_0^{(N)}$, $H_1^{(N)}$, $H_2^{(N)}$ each 64-bit, and the high-order 32 bits of $H_3^{(N)}$.

I suggest to start by checking the SHA-512 implementation pass test vectors; then implement the truncation, and test; then change the initialization value, and test.

[epilogue: that was the test vectors, see this]


At a purely technical level, having the two group elements and secret exponents enables a proof, in the random oracle model, that the scheme is CCA secure assuming that decision Diffie-Hellman is hard.  For regular (hashed) ElGamal, we only know how to prove CCA security in the random oracle model under a stronger assumption (in our paper we called it strong Diffie-Hellman, but gap Diffie-Hellman seems more common).

The intuition for why the two keys should help is more difficult.  At a very high level, by deriving the session encryption key as the hash of two Diffie-Hellman group elements, we are getting some "verifiable proof" that the ciphertext was either properly computed or is useless to the adversary, and allows the reduction to respond accordingly.  Looking back at regular ElGamal, the difference is that "proof" is not "verifiable".  The stronger assumption in the CCA proof of ElGamal is what technically allows this "proof" to become "verifiable".

The paper makes this argument formal.  In order to understand it better, I'd recommend starting with this paper, which gives the mentioned proof for hashed ElGamal under the stronger assumption.  Then one can contrast it with the twin construction and security analysis.


Asynchronous Ratcheting Tree and modern group key agreements: Why left balanced-tres used?

In the asynchronous ratchet tree construction, intermediate group keys are constructed at each leaf of the tree.  It's important that all parties agree on the exact structure of the tree so that they will all derive the same keys.  An array is the canonical representation of an ordered list of items, and that array can be viewed as a binary tree.  An array of length $2^n$ corresponds to a complete binary tree, while an array of any other length corresponds to a left-balanced binary tree.

You might find the Messaging Layer Security IETF working group of interest, as I believe at least one of the ART paper's authors is involved in the specification efforts.  The current MLS protocol Internet-Draft restates the ART protocol from a more concrete engineering perspective, so it's very helpful for understanding how everything fits together.


Why do some people believe that humans are "bad at" generating random numbers/characters like this?

In short, it is more than a belief: there is strong evidence that humans are not good entropy sources. There is a test for this

Man vs. Machine. Or, why Man is not a Particularly Good Source of Entropy.

Try to win!
So we don't rely on whether generating a random number from the mind or random keyboard typings and mouse movements that seem like a monkey playing on the computer from outsiders. We rely on good entropy sources like the /dev/urandom. That kind of sources comes from good research.
Some researches on supporting this;

1972, W. A. Wagenaar, Generation of random sequences by human subjects: a critical survey of the literature

1997, Brugger, P., Variables that influence the generation of random sequences: An update. Perceptual and Motor Skills

2005, Persaud, N, Humans can consciously generate random number sequences: A possible test for artificial intelligence. Medical hypotheses, 65(2), 211-21

2012, Schulz et. al, Analysing Humanly Generated Random Number Sequences: A Pattern-Based Approach

2012, Williams and  Griffiths Why Are People Bad at Detecting Randomness? A Statistical Argument

2014, Towse et. al, Not all numbers are equal: preferences and biases among children and adults when generating random sequences

Other online tests;

not so random with the collected results.


Multiplicative inverse in $\operatorname{GF}(2^8)$?

The standard method for doing multiplication (and multiplicative inverses) in $\operatorname{GF}(2^8)$ is using a log and antilog table.  Each table takes up only 255 bytes; hence it is much smaller than a full $256 \times 256$ multiplication table, and it is much faster than the multiplication procedure you give above.

To create such tables, we need to pick a generator $g$; that is a field element such that $g^i$ is all 255 nonzero elements for $0 \le i < 255$ (where $g^i$ is what you would expect; $g$ multiplied by itself $i$ time).  Such an element always exists, and (IIRC) $g=3$ happens to be a generator in the field representation you are using.

Now, the antilog table is defined as:

$${\rm antilog}(i) = g^i$$

This table has 255 elements, and can be easily built using your multiplication procedure.  You may want to extend it farther (as discussed below); it just continues in the obvious way (and it just repeats itself).

The log table is defined as its inverse, that is:

$$\log(\operatorname{antilog}(i)) = i$$

This table also has 255 elements (but is indexed from 1 to 255), and can be built using the antilog table we already have, or just initialized at the same time:

uint8_t log_table[256], antilog[255];
const uint8_t g = 3;

void init_log_table(void)
{
    log_table[0] = 0;  /* dummy value */
    for (int i = 0, x = 1; i < 255; x = gmul(x, g), i++) {
        log_table[x] = i;
        antilog[i] = x;
    }
}

Once we have those two, we can do multiplication by:

uint8_t gmul_table(uint8_t a, uint8_t b)
{
    if (a == 0 || b == 0) return 0;

    uint8_t x = log_table[a];
    uint8_t y = log_table[b];
    uint8_t log_mult = (x + y) % 255;

    return antilog[log_mult];
}

This works because, if $a = g^x$ and $b = g^y$, then $a \times b = g^x \times g^y = g^{x+y} = g^{(x+y) \bmod 255}$

As you can see, that should be considerably more efficient than your original algorithm; you can omit the % 255 operation by extending the antilog table for 255 more elements.

We can also use those tables to compute multiplicative inverses:

uint8_t ginv_table(uint8_t a)
{
    if (a == 0) return 0;       /* as needed in the context of AES */

    uint8_t x = log_table[a];   /* x       is in range [0..255] */
    uint8_t log_inv = 255 - x;  /* log_inv is in range [0..255] */

    return antilog[log_inv];
}

You can also compute inverses using the Extended Euclidean Algorithm (which can be adapted to work in $\operatorname{GF}(2^8)$; however it's considerably more work than two table lookups.

Here is how that algorithm would look like:

uint8_t ginv(uint8_t x)
{
    uint16_t u1 = 0, u3 = 0x11b, v1 = 1, v3 = x;

    while (v3 != 0) {
        uint16_t t1 = u1, t3 = u3;
        int8_t q = bitlength(u3) - bitlength(v3);

        if (q >= 0) {
            t1 ^= v1 << q;
            t3 ^= v3 << q;
        }
        u1 = v1; u3 = v3;
        v1 = t1; v3 = t3;
    }

    if (u1 >= 0x100) u1 ^= 0x11b;

    return u1;
}

where bitlength(x) returns the position of the most significant 1 bit of x (i.e. the smallest number y such that (1 << y) - 1 >= x).


Why does AES-GCM not require an auth key, but encrypt-then-mac does?

AES-GCM does require an authentication key. You don't need to pass it because it is generated from the encryption key by encrypting an all-zero "plaintext" block:

  The hash subkey, denoted $H$, is generated by applying the block cipher to the “zero” block. The
  resulting instance of this hash function, denoted $GHASH_H$, is used to compress an encoding of
  the AAD and the ciphertext into a single block, which is then encrypted to produce the
  authentication tag.

(source - in "5.3 Primitives for Confidentiality and Authentication")


Meaning of entropy of a bitstring in NIST SP 800 - 90A

"Entropy" is more accurately defined, in cryptography, as "that which the attacker does not know". For instance, suppose that every day you take all rates at the closure of the New York stock exchange, and hash them with SHA-256. The resulting value is very unpredictable (otherwise you could become very rich), so, from a "physics" point of view, there is a lot of entropy here. However, once the rates are published, everybody knows them: thus, from a cryptographic point of view, the entropy is nil.

To estimate the entropy, you have to analyze the process that generates the purportedly random value, and imagine an attacker trying to guess that value: the attacker has access to a validation box that returns "true" if the attacker found exactly the value, and "false" otherwise. You may say that the process yields "$n$ bits of entropy" if, on average, the attacker must invoke the validation box $2^{n-1}$ times before hitting the right value.

The important point here is that the estimate can come only from an analysis of the generation process. It cannot be tested with statistics, because statistics do not capture the level of knowledge of the attacker.


How to determine required number of rounds for RC6 cipher given custom W and B parameters?

In the case of AES, they had a lower bound on the highest probability differential (and the analogous linear hull), and they were able to use that information to determine at how many rounds would be required for a differential (and analogous linear) attack of a specific cost.

Ideally, that is how you would proceed.

However, Rijndael (later AES) has some specific properties that enable such a calculation to be made. All of the constituent operations are very cleanly and precisely defined, and they operate on sizes that are small enough to enable such analysis to take place.

With ciphers built from bitwise and arithmetic operations ad-hoc*, especially when those operations function on large words, finding the worst-case differential probability is more challenging, if/when it is possible.

You can find the sort of average worst-case probability (which is not really the worst-case) and make the calculation for rounds using that, but that does not prove that no attack costs less then the desired amount, because there could be some higher probability differentials you don't know about yet.

Still, that is probably the best strategy you have.

Note

You can only perform this type of process for attacks that you know of already. You could prove that no basic differential attack costs less than $\frac{1}{2^n}$, but that does not mean that no attack costs less than $\frac{1}{2^n}$.

* Technically the operations in Rijndael are built from bitwise and a certain type of arithmetic operations - but all circuits are powered by these, at the circuit level.


80-bit vs 128-bit security in today's world

80-bit
First, note that the Bitcoin miner's hash rate reached $> 2^{93}$ SHA-256 hashes per year in February 2021. This makes the 80-bit security absolute for known entities. They even passed that years ago (that is around 2012 per year). And even around 2011, it was absolute and NIST increased security strength from 80 to 122 for Federal Government in 2014. So there is no place for 80-bit in today's security.
128-bit
For 128-bit the question a bit more interesting, while yet there cannot be a group that can reach $2^{128}$ complexity ($2^{35}$-year is needed for a power like the Bitcoin Miners). There are

multi-target attack
In short; The expected cost of finding a key from $t$ targets is $2^{128}/t$. If you have a billion targets that you will be able to find the first key much lower than 128-bit security. The cost would be below $2^{100}$ and the time would be below $2^{70}$.

quantum-based attacks due to Grover's quadratic speed algorithm on symmetric ciphers. If ever build and if we omit other costs, 128-bit has 64-bit symmetric security on quantum computers.

Or see what can be done to AES-128
256-bit
To mitigate all just use AES-256 (or any 256-bit secure cipher like ChaCha20) and that is already the golden standard by the industry. Brute-force is impossible, multi-target has no meaning, and Grovers's algorithm can just reduce the security to 128-bit. Now we are safe as long as there no breakthrough either in breaking the algorithms or find a new scientific advancement.
112-bit
For lightweight cryptography NIST required at least 112-bit security from the 128-bit key size.


How is the block size of a block cipher related to how susceptible the block cipher is to a birthday attack?

If you encrypt (partially) random values then the likelyhood that you encrypt the same value is larger for block ciphers that operate of fewer bits. If you encrypt the same value with the block cipher (which is a PRP) it will result in the same ciphertext. Identical ciphertext can be used by an attacker to retrieve information about the plaintext, breaking the mode of encryption.

For example, say you'd use a 64 bit block cipher for CTR (counter) mode encryption and you'd use 32 bit for a random nonce and 32 bits for the counter. The counter will simply repeat after $2^{32}$ block encrypts. The random nonce however is succeptible to the birthday problem. This means that you'd have a relatively high chance of a collision (with one of the earlier values) after generating only a few nonces.

As you can see above, the issue with the birthday problem above isn't with the block cipher itself. The problem lies within the mode of operation in which the block cipher is used. It is wrong to say that DES or TDES are succeptible to birthday attacks. 64-bit block ciphers are just not good candidates for modes of operation where the birthday problem may occur, especially if large quantities of data are concerned.


RSA smaller number work-out-by-hand not working - I think I made a mistake

At the encryption step, you wrote:

Public Key:
n = 667
k = 3

Input:
p = 13

Encrypted Integer:
E = (p ^ k) % n

And then mistakenly calculated:

(13 ^ 7) % 667 = 492
______^_____________

If you calculate it right using k = 3, you will get E = 196 which correctly decrypts to 13.

(as expected)


learning with errors is hard even when given some information about the secret vector

There is on one hand a recent preprint Hardness of LWE on General Entropic Distributions by Zvika Brakerski and Nico Döttling, and on the other hand it's well known that you can assume that the secret is sampled from the error distribution (see for example the last paragraph on page 7 of Classical Hardness of Learning with Errors by Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev and Damien Stehle).


ECC How do the Curve, its number of bits of security and key size affect the maximum size of ciphertext?

The standard way to do public-key encryption with elliptic curves has no limit on ciphertexts.  It works roughly as follows, with many details omitted for practical instances:

  Parameters.

  Fix an elliptic curve $E/\mathbb F_p$ over a finite field $\mathbb F_p$, e.g. $p = 2^{255} - 19$ and $E\colon y^2 = x^3 + 486662 x^2 + x$ (Curve25519).
  Fix a standard base point $G \in E(\mathbb F_p)$ of large prime order $\ell$, e.g. $G = (9, \dots)$.
  Fix a hash function $H\colon \mathbb E(\mathbb F_p) \to \mathbb \{0,1\}^{256}$, e.g. SHA-256 on the little-endian encoding of the coordinates.
  Fix an authenticated (symmetric) cipher $E_k$, e.g. NaCl crypto_secretbox_xsalsa20poly1305.

  Public keys.  A public key is the encoding of a point $P$ on the curve with coordinates in $\mathbb F_p$.

  Encryption.  To encrypt a message $m$: Pick an integer $b$ with $0 \leq b < \ell$ uniformly at random.  Compute $k = H([b]P)$, the encapsulated symmetric key.  Compute $c = E_k(m)$, the authenticated ciphertext.  Compute $Q = [b]G$, the encapsulation of the symmetric key.  Transmit $Q$ and $c$.

  Private keys.  A private key is an integer $a$ with $0 \leq a < \ell$ chosen uniformly at random.  The corresponding public key is $P = [a]G$.

  Decryption.  To decrypt a message given $Q$ and $c$, knowing the private key $a$:  Compute $k = H([a]Q)$.  Compute $m = E_k^{-1}(c)$, or drop it on the floor if authentication fails.

This structure is sometimes called ECIES, or sealed box.  It works because $$H([a]Q) = H([a][b]G) = H([b][a]G) = H([b]P),$$ so the sender and receiver are guaranteed to use the same key $k$.  The size of the message is limited only by the authenticated cipher $E_k$, and most authenticated ciphers have very large limits on message size, measured either in gigabytes or so big I don't even remember the word for it (what's more than a zettabyte?).

The field size $p$ and the group order $\ell$ are related by Hasse's theorem—they can't differ by more than approximately $\sqrt p$, so they are of the same order of magnitude.  The security offered by the curve is at most about $\log_2 \sqrt \ell$ bits, e.g. for Curve25519 you get at most the gold standard ~128-bit security, because a generic attack costs approximately $\sqrt \ell$ curve operations.  Of course, if you use AES-128, you won't get 128-bit security because it is much cheaper to attack multiple AES targets than to attack multiple Curve25519 targets.

The ciphertext expansion is only the constant overhead of the encoding of a curve point, and whatever ciphertext expansion $E_k$ has (typically a 128-bit authentication tag).

Some people call it ‘hybrid encryption’ when you combine a public-key operation like this with a symmetric-key cipher.  This is a poor choice of terminology, because it suggests that the public-key operation without the symmetric-key is itself a form of public-key encryption.  That is not the case here, or in any scheme similarly based on ephemeral/static key agreement, and that is generally a poor design with bad security and usage limitations even when it can technically be done with RSA.

The only way RSA is used in practice for encryption has the same separation, whether with RSA-KEM or with essentially any use of RSAES-PKCS1-v1_5 or RSAES-OAEP: encapsulate a uniform random symmetric key $k$ in an $e^{\mathit{th}}$ root modulo $n$, and encrypt the message with $E_k$.  Unlike attempting to shoehorn the message $m$ into $m^e \bmod n$, this has no limits on the message size or on the structure or distribution of messages that can be concealed.


RSA Signature Verification Implementation on Cortex M0

As pointed by CodesInChaos, you'll need to know the padding used; depending on application that could be RSASSA-PKCS1-V1_5, or RSASSA-PSS, or some of the three schemes of ISO/IEC 9796-2, etc.. Hashing, and padding check, are a significant part of the code.

In any case, yes, it is possible to implement RSA-2048 signature verification on a Cortex-M0 based MCU, with much less than 15 kB code and 2 kB RAM. That's extremely ample even including hashing, and padding check.

With tight coding we are talking 2 to 5 kB code (depending on hash and padding, including code for RSA and SHA-1, SHA-256 or even SHA-512) and at most 1.4 kB RAM (temporarily used in stack or heap, not dedicated) including public key and signature (assumed already properly aligned bytes).

To give an order of magnitude of the speed achievable: for $e=65537$, a simple but good implementation of the RSA public function is dominated by a core loop executed about $17\cdot(2048/32)^2$ times, comprising 8 MULS, 3 memory reads, 1 memory write, and like 16 other single-cycle operations; thus, on a 40 MHz CPU running without code wait states, like 70 ms with single-cycle MULS (or 500 ms with the 32-cycle MULS of some Cortex-M0 variants).

Speed (and code density) will also depend on

using assembly in the critical loops, rather than C which typically generates sub-optimal code for RSA arithmetic (notably, because C only has a tortuous idiom for carry propagation);
not using Montgomery arithmetic, which introduces complexities hardly justifiable for RSA signature verification and common (low) public exponents $e$;
value of public exponent; $e=3$ can be like 8 times faster than $e=65537$ (for short messages);
size of what's signed (influencing hash time);
care of programming; this is not easy!

An archetypal implementation of modular exponentiation $Y\gets X^e\bmod N$, geared for RSA signature verification with typical parameters including moderate public exponent $e>0$, optimized for low RAM footprint, code simplicity, and speed, can uses left-to-right binary exponentiation at the top level:

$Y\gets X$
set $j$ to the number of bits in $e$, that is $\lceil\log_2(e+1)\rceil$
while $j>0$

$Y\gets Y\cdot Y\bmod N$
$j\gets j-1$
if bit $j$ in the binary representation of $e$ is set, that is if $\lfloor e/2^j\rfloor\bmod 2\ne0$

$Y\gets X\cdot Y\bmod N$

This requires 2 modular multiplications for $e=3$, and 17 for $e=65537$.

In an implementation optimized for size (and simplicity) we'll have a single piece of code to perform $Y\gets X\cdot Y\bmod N$, and we'll replace argument $x$ by $Y$ when performing $Y\gets Y\cdot Y\bmod N$. Our modular multiplication will use more or less clever variants of the ‘classical’ algorithms commonly used by hand in decimal, only using base $2^w$ instead of base 10, where $w$ is some convenient word width. We note $n$ the number of $w$-bit words in $N$. Execution time will be $\mathcal O(n^2)$. On Cortex-M0 we'll probably use $w=32$ (or $w=16$ which would give simpler and shorter code, with only moderate speed penalty for the Cortex-M0 variant with 32-cyle MULS, but much more in proportion for the variant with single-cycle MULS).

The simplest option for modular multiplication is algorithm 14.28 in the Handbook of Applied Cryptography, which performs multiplication (using multiplication per algorithm 14.12) followed by modular reduction (using Euclidean division per algorithm 14.20 ignoring the quotient, or Barrett reduction per algorithm 14.42). This is has some drawbacks, though:

each modular multiplication requires $\mathcal o(2n^2)$ memory reads, $\mathcal o(n^2)$ memory writes, and $\mathcal o(n^2)$ loops for the multiplication, and modular reduction requires as many; when other algorithms reduce that to a total of $\mathcal o(3n^2)$ memory reads, $\mathcal o(n^2)$ memory writes, and $\mathcal o(n^2)$ loops (the same asymptotic cost as a good implementation of the equivalent of modular multiplication in Montgomery arithmetic);
the intermediary result is twice as wide as $N$, which consumes some RAM;
the index in this intermediary result is not the same as the index in other operands, thus we have two indexes to maintain.

These three drawbacks can be avoided without using Montgomery arithmetic (which requires pre and post computations that increase code size, and have significant speed penalty for low $e$), as follows.

For any integer $Z$, we note $Z_j$ the $j$th digit of $Z$ in base $2^w$, that is
$$Z_j=\left\lfloor{Z\bmod 2^{(j+1)\cdot w}\over2^{j\cdot w}}\right\rfloor$$
so that
$$0\le Z<2^{k\cdot w}\implies Z=\sum_{0\le j<k}Z_j\cdot2^{j\cdot w}$$
$N_0$ is odd since $N$ is odd, and $N_{n-1}>0$ since $n$ words are required to write $N$. We define (and precompute early, e.g. as a preliminary of exponentiation) $M_j=2^w-N_j-1$ for $0<j<n$ and $M_0=2^w-N_0$, corresponding to $M=2^{n\cdot w}-N$; and
$$H=\min\left(\left\lfloor{2^{5\cdot w}\over N_{n-1}\cdot2^{2\cdot w}+N_{n-2}\cdot2^w+N_{n-3}}\right\rfloor,2^{3\cdot w}-1\right)$$
as the corresponding $H_2$, $H_1$, $H_0$, which will help in quotient estimation.

The general sketch of modular multiplication goes:

$T\gets Y_{n-1}\cdot X$ over $n+1$ digits, using a loop scanning the $X_j$ and $T_j$ by increasing index;
for $i=n-2$ downto $0$ (a loop invariant being that $T<N\cdot2^w$)

find an approximation $q$ of the next quotient chunk $\left\lfloor{T\cdot2^w+Y_i\cdot X\over N\cdot2^w}\right\rfloor$, erring up by at most $1$ by excess, and with $0\le q\le2^w$ (which it turns out is possible using a constant number of multiplications and additions involving $T_n$, $T_{n-1}$, $T_{n-2}$, $X_{n-1}$, $X_{n-2}$, $Y_i$, $H_2$, $H_1$, $H_0$);
$T\gets T\cdot2^w+Y_i\cdot X+q\cdot M\cdot2^w$, over $n+1$ digits and an extra one $t$ for what would have been $T_{n+1}$, using a loop scanning the $X_j$, $M_j$ and $T_j$ by increasing index; most of the time is spent in this single loop with $q\ne2^w$ (the special case $q=2^w$ must be detected and handled separately, but is faster than the general case);
if $t<q$ (which is rare and will thus consume negligible time), then $q$ was one higher than it should have been:

$T\gets T-M$, using a loop scanning the $M_j$ and $T_j$ by increasing index;

$Y\gets T\bmod N$ (one way to do this is as an extra iteration of the above, with a virtual $y_{-1}=0$, and mapping the $T_{j+1}$ of the result to $Y_j$).

The essential thing is that we manage to perform multiplication and modular reduction in the same loop doing $T\gets T\cdot2^w+Y_i\cdot X+q\cdot M\cdot2^w$, with the quotient digit $q$ on a single word, using operations with fair native support (word multiplications and additions with carry; that's even though each full $32\times32\to64$ multiplication will require four MULS). As often in crypto, and especially crypto implementation, the devil is in the details.

Doing signature generation with appropriate speed and security is much more difficult. That's going to be like 50 times slower than signature verification with $e=65537$, using the CRT and regular two-factors RSA (and otherwise comparable code for the two modular exponentiations). The code will be significantly larger (though still feasible within the code and RAM budget). For some padding schemes including RSASSA-PSS and ISO/IEC 9796-2 scheme 2, a TRNG with some strength will be required, making the code's interfaces much more complex. Most importantly, it will be practically impossible to hide the required secret key from a JTAG debugger or the like, and even quite hard to safeguard it from timing and other side-channel attacks.


Does Lamport's authentication scheme still work if the hash function is not collision-resistant?

Lamport's one-time authentication scheme requires a one-way function.  In terms of cryptographic hash functions, one-wayness is (practically, modulo some technical differences in the definitions) equivalent to first preimage resistance.  In particular, a function does not need to be collision resistant in order to be one-way.

(A practical way to construct a non-collision-resistant one-way function is to take any given one-way function, such as a secure hash function, and make it ignore one of the bits of its input.  This weakens the first preimage resistance of the function only slightly, but completely destroys both collision resistance and second preimage resistance.)

Indeed, the original description of the scheme (Lamport, 1981) does not mention hash functions at all, but rather suggests constructing a  by encrypting a fixed plaintext with any secure encryption algorithm, using the input as the key and the resulting ciphertext as the output (citing Diffie & Hellman, 1976).  Such a construction generally does not guarantee collision resistance and, in particular, will trivially lack it if the encryption scheme has equivalent keys.


I think you're encountering the difference between an academic paper and an implementable standard like an RFC or NIST Special Publication.

In an academic setting, details like encodings rarely matter. Using a uint8, uint16, or plain old int results in the same security in this case. So the counter can be encoded however you wish.

However, unless you foresee a true need to generate enormous outputs, I would use a single byte and ensure that you return an error if the requested output is larger than 255*(hash length). This prevents the user from mis-using your KDF in an application for which it was not designed.


Can two cipher letters per plaintext letter easily defeat character frequency analysis?

It is probably impossible to remove language characteristics completely with a substitution cipher. Your algorithm flattens out single character frequencies, but that's it kinda.

Language bigrams (your cipher-quadruples) might not be uniform distributed. The reason for this is simple: Bigram probability is not just the product of the probabilities of both letters - they are not independent variables.

Let's make an example (frequencies from http://www.cryptograms.org/letter-frequencies.php):

Letter t with frequency 0.09056 => 61 cipher-bigrams for t
Letter h with frequency 0.06094 => 41 cipher bigrams for h
Bigram th with frequency 0.03882
Now there are $61*41=2501$ cipher quadruples for the original bigram th, and all of them have the same probability. However, $2501$ of $26^4 = 456976$ possible qudruples is just a fraction of 0.005473. So now the number of ciphertext quadruples for *th does not match required number to enforce a uniform distribution.

An other way to attack might work with those bigrams which are very unlikely or even impossible in English language.


A fixed hash function can be computed by anyone.

A signature depends also on a public key, and can be computed only by someone who knows a secret related to the public key.  Anyone can verify a signature on a message under the public key, but only knowledge of the secret enables creating signatures.  Signatures practically always involve the use of a hash function internally, combining the hash output (and sometimes hash input) with the public key using obscure mathematical spells.

RSA is not itself an encryption algorithm; it is a family of trapdoor permutations, which are obscure mathematical spells not really useful in isolation.  There are encryption schemes and signature schemes both built out of the RSA trapdoor permutation family, such as RSAES-OAEP and RSASSA-PSS.


Secure Channel - Encryption and Decryption Keys For A Message

how do we obtain the original message if we XOR the ciphertext with some other key stream, different from the one that we used to encrypt the message in Secure Channel: Sending a Message?

Answer: we don't use different keystreams.  When Alice sends Bob a message, she uses the 'Enc Alice to Bob' keystream,  When Bob receives that message, he uses that same 'Enc Alice to Bob' keystream.  The 'Enc Bob to Alice' keystream is used for messages that Bob send to Alice (both by Bob to encrypt those messages, and by Alice to decrypt those messages).

The MACs work the same way; the 'auth Alice to Bob' MAC keys are used by both sides to do integrity checking on the messages that Alice sends to Bob, and the 'auth Bob to Alice' MAC keys are used by both sides for messages that Bob sends to Alice.


Why would my certificate's signature algorithm differ from its keys' signature algorithms?

I can't get my head around why the certificate itself has one signature algorithm, but the same certificate's public and private keys have a different signature algorithm.

A certificate is a document signed by an issuer (the certificate authority or "CA"), that contains a public key used to verify signatures by a subject (the "owner" of the certificate so to speak).  The issuer and subject's choices of signing algorithm are independent.  What's going on here is that the certificate contains a signing key with one algorithm, and the issuer signed it with a different algorithm.  A very silly analogy:

Issuer is a notary
Subject is notary's client
Keys are pens
Algorithms are ink colors
Notary and client can use pens with different ink colors

The x509Certificate.SignatureAlgorithm field in your question seems to correspond to section 4.1.1.2 ("signatureAlgorithm") of RFC 5280:

  The signatureAlgorithm field contains the identifier for the cryptographic algorithm used by the CA to sign this certificate.

The key word there is "CA"—the issuer of the certificate.

Certificates in the proper sense of the term don't include private keys, so the x509Certificate.PrivateKey property that you describe must be related to the software library that you're using.  The certificate proper however, under tbsCertificate.subjectPublicKeyInfo, contains SubjectPublicKeyInfo records that specify algorithms used by the subject keys, as explained in section 4.1.2.7 ("Subject Public Key Info"):

  This field is used to carry the public key and identify the algorithm with which the key is used (e.g., RSA, DSA, or Diffie-Hellman).  The algorithm is identified using the AlgorithmIdentifier structure specified in Section 4.1.1.2.

And this, again, is independent of the other field, because one is for the issuer and the other is for the subject.

  Does it matter that the former is sha256 and the latter are sha1?

It's not a problem that the algorithms are different, but it is one to have SHA-1 in the latter, since SHA-1 should no longer be used for public-key signatures.


The shared symmetric key is the same for all users?

The shared key is exactly the same for each user, assuming they are connected to the same WEP access point. Because the nonce is concatenated with the key and fed directly into RC4, each wireless frame is technically using a different key (at least until the small 24-bit nonce repeats).

This is unlike 802.11i (WPA2), where a symmetric key called the PTK is derived in the 4WHS (4-way handshake) that is specific to that user and their current session, although this does not prevent a user who knows the PSK (via the passphrase) and has captured the 4WHS from deriving the PTK. Each user does, however, share a secret key called the PSK, though it is not directly used for encryption.

  Also, how can a user get this key?

The user can obtain the key either by asking the AP owner for it, or by exploiting one of any numerous weaknesses in the WEP protocol to crack the key and use it for authentication or to decrypt/inject data.


How (in)secure is a signature based on DSA with DSS1 (SHA1) in reality?

While no SHA1 collisions have been found, there are some attacks:

~$2^{60}$ collision attack. Estimated to cost around \$1-2 million currently in the cloud. Possibly economical soon, especially with specialized hardware.
Intractable preimage attacks like $2^{151}$ against reduced round variant, $2^{159}$ against full hash. (Cf. $2^{160}$ brute force on any 160-bit hash.)

  How secure or insecure would you say is using DSA with DSS1 when signing a license file for a software?

Like poncho wrote in a comment, using a collision attack against a signature requires the attacker having control over what is hashed. If you only sign messages you've created yourself, e.g. random data, there is no way to mount a collision attack.

  Is it possible that someone can calculate the private key within a reasonable amount of time (having the public key, a message and its signature) or what’s a realistic risk?

Even if a collision would be found, that would not compromise your key. A single collision would typically create a single valid-looking license file.

(A collision against a key signature, like against CAs, is a different matter because that allows one to create an arbitrary, valid, authorized key they can use to make their own signatures. That's why Microsoft is deprecating SHA-1 certificates.)

  I’m aware of the fact that calculations are getting faster and faster (GPUs, cloud based services, etc.) so please include your estimation for the next couple of years.

Current attacks could allow collision attacks in the next few years if you sign user controlled data.

Preimage attacks would require a breakthrough to become viable. Always a possibility, but there is still enough security margin that I wouldn't worry about it.

A note on preimage vs. second preimage:

Whether a preimage or a second preimage attack would be needed depends on your setup. If the scenario is that the attacker wants to create another signed license file knowing one, he would need a second preimage, which is possibly harder. If the scenario is that the attacker knows a signature and needs to create a license file to match it, any preimage will do.


Need help understanding public key format of Barreto-Naehrig signature

It is common to define pairing-friendly curve such as  Barreto-Naehrig on sextic twists to implement efficient pairings (https://eprint.iacr.org/2012/232.pdf). for example, $E(\mathbb{F}_p): y^2 = x^3 + 2$ and sextic twist $E'(\mathbb{F}_{p^2}): x'^3 + \frac{2}{s} = x'^3 + 1 - u, where ,\mathbb{F}_{p^2} = \mathbb{F}_p [u]/(u^2 + 1), \mathbb{F}_{p^6} = \mathbb{F}_{p^2} [v]/(v^3 - (1+u)), \mathbb{F}_{p^{12}}=\mathbb{F}_{p^6} [w]/(w^2 - v), 1/s = 1/(1 + u)$
So the public key may be a point on a curve defined over an extended field and thus the coordinates will have multiple components. I didn't get into your screenshot in detail but I think it may be a point on the curve over $\mathbb{F}_p^2$ and thus the coordinates $(x,y)$ have 2 components each which explains why you have components of 32 bytes each.


HMAC-SHA256 for hashing of credit card PANs?

Under your assumptions, everything will be secure, as long as HKDF is secure and your key is secure (assuming attacker has only offline access to data, not be able to for example check if given credit card number was already entered). Currently even 2^128 is far out of our reach. But I wouldn't say that this will remain until end of universe. It is possible that in future we will find SHA-2 weaknesses and be able to use them to crack your solution.

Your scheme can however be easily broken if key was stolen. If this is consideration, you can reduce output size and increase risk of collision while making attacker struggle with same thing. However, I have no idea if this allowable in your scheme since you didn't give any details on how such thing would be used.

All in all, I would be most scared of flaw that would give attacker ability to do, what you can do: Check if number is on list, because of breach and access to HSM interface (which can also suppress any warnings of hash rate etc.).


Why this function isn't preimage resistant?

Let $O$ be an oracle that provides pre-images for $G$ that is given $y$ it produces a pre-image $z$ such that $G(z) = y$. Now expand this to $$y = H(z)||LSB(z).$$ Therefore, given the oracle $O$ one can find the pre-images of $H$ by asking $x||0$ and $x||1$ to the oracle and test the result. As a result, if $G$ is not pre-image resistant then $H$ is not. too. This implies that $H$ is pre-image resistant then $G$.
In the details; the $O$ will produce $x_0$ and $x_1$ such that $G(x_0) = H(x_0)||0 = x||0$ and $G(x_1) = H(x_1)||1 = x||1$. As we can see that this may also produce collisions for $H$.

$G$ fails only two-bit resistance by leaking the LSB. If a hash function is failing its pre-image resistance by leaking LSB, then it has some serious problems. Consider that, one provides you the LSB of the pre-image for SHA256, can you find the pre-image easily?
To see the loss bits of resistance; let $H(z):\{0,1\}^* \to \{0,1\}^n$ be a collision resistant hash function. Then is has $\mathcal{O}(2^n)$ pre-image and secondary pre-images resistances, and $\mathcal{O}(2^{n/2})$
If $G(z):\{0,1\}^* \to \{0,1\}^{n+1}$ with $G(z) = H(z) \mathbin\|\text{LSB}(z)$ then it has $\mathcal{O}(2^{n-1})$ pre-image and secondary pre-images resistances instead of $\mathcal{O}(2^{n+1})$


Why can an RSA signature be authenticated ONLY with the signer's public key?

The probability of such a "collision" occurring randomly, with honestly-generated RSA keys, is extremely low. Mathematically justifying that assertion can be tiresome, but the idea is the following:

Let $s$ be a RSA signature, i.e. an integer of size $k$ bits for some $k$ (e.g. $k = 2048$). We consider RSA keys $(n,e)$ where $n$ is the modulus (of size $k$ bits) and $e$ is the public exponent, of size $r$ bits (in practice most people use $e = 65537$, i.e. $r = 17$; Windows' CryptoAPI cannot tolerate public exponents longer than 32 bits anyway). We want to estimate the probability that $s^e = m \pmod n$.

If $s^e = m \pmod n$ then $n$ divides $s^e-m$. $s^e - m$, as an integer, has size roughly $k2^r$ bits. That integer cannot admit more than $2^{r+1}$ distinct prime divisors of size $k/2$ bits. Even if $s^e-m$ is indeed the product of $2^{r+1}$ distinct prime integers of size $k/2$ bits, then there are only about $2^{2r+1}$ distinct products of two such primes which divide $s^e-m$. In other words, with $k = 2048$ and a given 32-bit exponent $e$, then there can be at most about $2^{65}$ (and in practice much fewer) modulus values $n$ such that $s^e = m \pmod n$. However, there are roughly $2^{2048-20} = 2^{2028}$ possible 2048-bit RSA moduli (products of two 1024-bit primes), a vastly bigger value. Thus, probability of collision is very low.

If we allow the public exponent to be large ($r = 2048$) then the answer is not as simple, because the computation above will yield a maximum number of matching moduli of about $2^{4097}$, which is completely exaggerated and not actually possible. In fact, for a given $e$, the integer $s^e-m$ will be large and may be assumed to be "typical", in that its factorization in prime factors will use factors of various sizes. The Hardy-Ramanujan theorem tells us that an integer of size $k2^r$ bits will be the product of, on average, $\log r$ distinct primes, yielding $(\log r)^2$ possible matching moduli. This leads to the same conclusion as before, albeit with an assumption of $s^e-m$ to be "typical" as far as factorization is concerned.

The above is for a random collision. However, we can ask ourselves whether such an occurrence could be forced. It turns out that it can be done. That is, consider a message $m$ (padded hash value) and a signature $s$ produced with a key pair $(n,d,e)$. We have $s^e = m \pmod n$ and $s = m^d \pmod n$.

Now, take $m'$ (another message, or the same as $m$, it works in both cases). Then one can compute a new RSA key pair $(n',d',e')$ such that $s^{e'} = m' \pmod {n'}$, and this can be done with $s$ and $m'$ alone (without knowing anything about the original key pair). The idea is the following: select random small prime integers $p_i$; for each small prime, compute $e_i$ such that $s^{e_i} = m' \pmod {p_i}$. This is a discrete logarithm which is very easy if $p_i$ is small. Once you have enough $p_i$, compute $n'$ as their product. The public exponent $e'$ is then such that $e' = e_i \pmod {p_i-1}$ for all $i$, so $e'$ is easily recomputed with the Chinese remainder theorem. At that point, you have $n'$ and $e'$, and you know the prime factorization of $n'$, so computing the private key $d'$ is straightforward.

Of course, this yields a rather weird RSA key: $n'$ is the product of small primes (but this won't be seen until someone actually tries to factor $n'$), and $e'$ is large (much larger than 32 bits). Whether a similar construction can work while keeping $e'$ small is not known. The discussion on random collisions above tells us that, "morally speaking", targeting a small $e'$ ought to be hard. Indeed, if we target a fixed $e'$, then $n'$ will have to be one of the $(\log r)^2$ (at most) possible values; since we should end up with $(n',d',e')$, then this means that this reconstruction yields a partial factorization of $s^{e'}-m'$, and we know that integer factorization is hard (indeed, RSA relies on it).

One alternate way to see it is the following: when trying to build $(n',d',e')$, we are actually trying to find factors of $s^{e'}-m'$ such that their product has the right size for a RSA modulus; we can do that if we are allowed to alter $e'$ and/or $m'$ so that $s^{e'}-m'$ is easy to factor. The more $e'$ and $m'$ are constrained, the harder the problem becomes. If $e'$ and $m'$ are fixed, then the problem seems as hard as breaking RSA. At which point the problem reaches the "infeasibility threshold" is not known.

See this article for a longer treatment of this subject. Bottom-line: digital signatures yield guarantees about a message for a given public key, not the other way round.


Formal Proof of Shamir's Secret Sharing Scheme Security

Let's recall Shamir's Secret Sharing. We work in a finite field $\mathbb{F}_q$ of cardinal $q$. The secret to share is $s$; we want $n$ shares with a threshold $t$. We suppose that $n < q$ (otherwise, the scheme does not work). We conventionally name $n$ non-zero values of $\mathbb{F}_q$: $x_1$, $x_2$... $x_n$. Exactly how we choose them is unimportant, as long as they are all distinct from zero and from each other, and everybody knows which is which. If $q$ is prime (field $\mathbb{F}_q$ is $\mathbb{Z}_q$, i.e. the integers modulo the prime $q$), then we will traditionally choose $x_i = i \bmod q$ (since $n < q$, this works: none of the $x_i$ is zero, and they are all distinct from each other). By convention, I also define $x_0 = 0$ (this will help in my notations).

To share $s$, we generate a random polynomial $A = \sum_{i=0}^{t-1} a_i X^i$, where:

$a_0 = s$
For all $i = 1$ to $t-1$, $a_i$ is chosen randomly and uniformly in $\mathbb{F}_q$ (notably, each $a_i$ can be zero with probability $1/q$).

By construction, $A(0) = s$. The share of each user $i$ is $v_i = A(x_i)$. The polynomial $A$ has degree "at most $t-1$" (degree of $A$ may be lower than $t-1$ since it is possible that $a_{t-1} = 0$).

To rebuild the secret, $t$ share holders use their respective shares to recompute polynomial $A$, and thus compute $A(0)$, which is the secret Reconstruction uses the Lagrange polynomial. I now suppose that the shares used for reconstructions are $v_1$, $v_2$,... $v_t$ (this simplifies notations, but since the conventional naming of $x_1$, $x_2$... is arbitrary, this assumption that not reduce generality). We define the Lagrange polynomial $L_i$ as the polynomial of degree $t-1$ such that $L_i(x_i) = 1$, but $L_i(x_j) = 0$ for any $j \neq i$ (for $1\leq i,j\leq t$). The Lagrange polynomial is computed as:
$$ L_i = \frac{\prod_{1\leq j\leq t, j\neq i}(X - x_j)}{\prod_{1\leq j\leq t, j\neq i}(x_i - x_j)} $$
Since all the $x_j$ are distinct from each other, the denominator is necessarily non-zero, so the division works; and with $L_i(x_i)$, numerator and denominator end up being identical products, this $L_i(x_i) = 1$.

With Lagrange polynomials, one can find a matching $A$ has:
$$ A = \sum_{i=1}^{t} v_i L_i $$
Since then:
$$ A(x_j) = \sum_{i=1}^{t} v_i L_i(x_j) = v_j $$

That $A$ is the unique solution can be proven with a counting argument: there are exactly $q^t$ possible tuples $(v_1, v_2,\cdots v_t)$ ($t$ values in $\mathbb{F}_q$), and, for each of them, the reconstruction with Lagrange polynomials yields a matching polynomial $A$ of degree at most $t-1$. However, there are only $q^t$ polynomials of degree at most $t-1$. Thus, there cannot be more than one matching polynomial per tuple; otherwise, you'd run out of polynomials at some point.

(It is in fact a more general result that a polynomial of degree at most $t-1$ is uniquely defined by its values over $t$ distinct inputs; this also works in infinite fields. A special case is for $t = 2$, and this really means that by any two distinct points, there passes exactly one line. The general result is proven with more algebra; for finite fields, the counting argument above is a lot simpler.)

Note that secret reconstruction is interested only in the secret $s = A(0)$; having the complete polynomial is only a mean to that, and it is not fully necessary. Indeed, we have:
$$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$
The values $L_i(0)$ depend on which share holders are involved (i.e. the choice of $x_1$, $x_2$... $x_t$), but not the share values ($v_1$, $v_2$... $v_t$). Thus, the $L_i(0)$ can be precomputed. This is especially convenient when doing multiple reconstructions with the same share holders; one typical case is when working with $q = 256$ (the finite field with exactly 256 elements) and applying Shamir's Secret Sharing on byte-per-byte basis on a multi-byte secret value.

The security of the scheme hinges on the following result: for any set of $t$ values in $\mathbb{F}_q$, there is exactly one matching polynomial $A$.

To simplify notations, I now suppose that you have shares $v_1$, $v_2$... $v_{t-1}$. These are $t-1$ shares, i.e. less than the threshold. To prove the absolute security of the scheme, we need to show that these $t-1$ shares yield no information whatsoever on the secret $s$. To do that, we note that:
$$ s = A(0) = \sum_{i=1}^{t} v_i L_i(0) $$
Therefore:
$$ v_t L_t(0) = s - \sum_{i=1}^{t-1} v_i L_i(0) $$
Note also that $L_t(0) \neq 0$:
$$ L_t(0) = \frac{\prod_{1\leq j\leq t-1}(0 - x_j)}{\prod_{1\leq j\leq t-1}(x_i - x_j)} $$
(All the $x_j$ and all the $x_i-x_j$ are non-zero, so the products are non-zero.)

It follows that, given share values $v_1$ to $v_{t-1}$, for any possible value of $s$, there is exactly one value of the missing share $v_t$ that would yield that $s$. Thus, the $t-1$ shares $v_1$ to $v_{t-1}$ yield no information at all about the secret, since all possible values of the secret are still possible and equiprobable at that point.

Note the subtlety here about "equiprobability". The counting argument says that there are exactly $q^{t-1}$ polynomials $A$ of degree at most $t-1$ such that $A(0) = s$, for a given secret $s$. With $t-1$ shares, i.e. knowledge of $t-1$ values $v_i = A(x_i)$, you don't know enough to pinpoint a single polynomial $A$; in fact, you have exactly $q$ matching polynomials, one for every possible value of the secret $s$. This establishes a bijection between the possible values of the secret $s$, and the possible values of the missing share $v_t$ (the formula above makes that bijection explicit). The bijection transports the information: every piece of information, even statistical, that you may know on the secret $s$, can be transformed through the bijection into the same information on the missing share $v_t$, and back. This really means that the $t-1$ shares, by themselves, teach you nothing more. Real-life secret values $s$ are not completely random and uniform, but that's not the point; the point is that without the missing share $v_t$, you don't know more on $s$ than you already knew about it before. This is the sense in which Shamir's Secret Sharing is unconditionally secure.

Some extra notes:

All of this hinges on the idea that the initial sharing polynomial $A$ was chosen really randomly and uniformly. In practice, this is not easily achieved: "true" randomness is elusive. We customarily use pseudorandom generators that expand a given seed, assumed "random", into an arbitrarily long sequence of bytes that are indistinguishable from randomness... as long as attackers have finite computing resources that do not exceed a given value. Moreover, the "seed" itself is obtained from some physical process which is supposed to be unpredictable, but this also assumes limitations on the abilities of attackers at obtaining information from the physical world. Thus, the "unconditional" security of Shamir's scheme is actually conditional on a number of other things.

(Physicists tell us that there is a fundamental uncertainty about the state of any physical system, but not many alleged "random generators" really tap into that. Moreover, from an epistemological point of view, using a quantum-uncertainty-powered RNG is not "stronger" than a cryptographically secure PRNG; you are just putting more trust in Niels Bohr than in Alan Turing.)
The security of the scheme relies on the fact that the polynomial $A$ is single-use. If you use the scheme to do a byte-per-byte sharing of a multibyte secret value, then you MUST generate a new random polynomial $A$ for every byte that is to be split into shares. If you reuse the same $A$ for several bytes, then all the security goes to naught.
A practical implementation may leverage the bijection between share tuples and polynomials, by NOT generating the coefficients $a_i$ randomly; instead, it would generate the first $t-1$ shares randomly and uniformly, then compute shares $v_t$, $v_{t+1}$,... $v_n$ with formulas such as the one described above, where the $L_i(0)$ values can be precomputed (even hardcoded in the implementation source code). The bijection guarantees that this is safe.


Why would one choose DTLS-SRTP versus just RTP over DTLS?

It's all about encryption overhead; how much the extra data the encryption method extends the packet by.

DTLS has a noticeable amount of overhead; the DTLS header alone is 13 bytes, and then you have the IV/nonce, and the tag; this overhead can be more than the actual VoIP payload.  In contrast, SRTP was specifically designed to minimize this overhead; except for the tag (which is optional; IMHO, bad idea to omit it, but some people insisted), there is no overhead compared to RTP.

You might ask "what's the big deal about encryption overhead?  Doesn't the internet not care that much about packet sizes?"  Well, yes, if you're talking about wired internet connections, actually, this overhead might not be that significant.  However, for wireless, yes, people do worry about it, because:

Because of power; the more bytes you have, the more bytes need to be transmitted (and if you're on a battery, well, that's a concern)
Because wireless is a shared media, so the more bytes you broadcast, that's less bandwidth everyone else connecting to the same AP gets.


At what point does passphrase strength match the strength of the cipher?

If I'm not missing some important point here, that's rather trivial to calculate. As implicitly stated in your question, the attacker has two possible ways to brute-force the encryption key: either by brute-forcing the encryption key itself or by brute-forcing the user-entered password.

Given the numbers of iterations of the key derivation function n, the time per kdf iteration tkdf, the length of the encryption key b (in bits) and the time per invocation of the actual encryption algorithm tenc, the average time needed to crack the encryption key itself (by testing half of the available keyspace) is

1/2⋅2b⋅tenc.

The average time to crack the user-entered password is

1/2⋅K⋅(n⋅tkdf+tenc),

with K=cl being the entirety of all passwords available to the user (c: number of characters available, l: length of password).

In your scenario, tenc=tkdf=1, and n=327661. Assuming AES-256 is used (b=256), one has to solve the equation

1/2⋅2b⋅tenc = 2256 = K⋅327662 = 1/2⋅K⋅(n⋅tkdf+tenc),

which yields (approximately) K=5.9447⋅1035. Assuming an available keyspace of 90 characters (which most users aren't likely to even find on their keyboards), this translates to approximately l=36.

(Disclaimer: I'm neither a mathematician nor an crypto expert. In case of any mathematical or semantic error, please comment.)

Related: https://security.stackexchange.com/questions/74566/long-passwords-and-key-derivation-functions


Finding Vigenere's keys with part of decrypted text?

The key lengths are important, also if it's the Vigenère cipher is applied twice its the same as once with a different keyword. If the two keys are the same length then the new key is that length, if the two keys are different lengths then the new key is sometimes = k1 length * k2 length. If the key length is longer than the message there isn't much analysis you can do.


Testing if a password for an eCryptfs mount is valid

You can use the ecryptfs-add-passphrase command to add a passphrase to your kernel keyring, which will also print the signatures (hashes) to standard out.

Once you've added a passphrase to the keyring, you might want to clear it, using the keyctl command.

eCryptfs uses a PBKDF2-like, key strengthening algorithm of 65536 rounds of SHA512.

(Disclosure: I am one of the authors and maintainers of eCryptfs.)


Does a key exchange protocol with mutual authentication which does not provide forward secrecy can be proven secure in Bellare-Rogway model?

This depends on what you mean by the Bellare-Rogway model? Do you mean

BR93: the original AKE model by Bellare and Rogaway?
BR95: their follow-up AKE model which incorporates the three-party case (among other things)?
BPR00: their third AKE model (together with Pointcheval), which additionally deals with the case of password-based authentication?
Or any of the many derivative models which extends or updates the above models in various ways, but still are generally referred to as belonging to the family of "BR-like" models?

If the BR-model in your question is interpreted specifically as being about any of the first three models above, then the answer is:

BR93: forward-secrecy is not required. This is because the model does not give the adversary any means of obtaining long-term keys.
BR95: forward-secrecy is required. This is because BR95 provides a Corrupt-query which gives the adversary access to a user's internal state (including its long-term key).
BPR00: forward-secrecy is required. Again, in this model the adversary is provided with a query that allows it to obtain a user's long-term key.

However, if your question is more generally about the BR-model thought of as a family of models, all centered around some core modelling concepts, then the answer is: it depends. By this I mean that the BR-model can be modified to accommodate both forward secure and non-forward secure protocols. To model a forward secure protocol, include a Corrupt-query (or something similar), which allows the adversary to obtain long-term keys. To model a non-forward secure protocol, leave out this query (or at least restrict it for the Test-session).

Regarding your question about freshness, this is not really about the protocol per se, but rather a modeling artifact. I.e., by the queries and capabilities given to the adversary in the BR-model (whichever flavor you want), there will always be ways for the adversary to trivially break any protocol. This is independent of how secure the protocol actually is, because these trivial attacks are inherent to the model, and do not correspond to any real-life attacks. Thus, the concept of freshness is introduced to correct for these trivial attacks, by saying that the adversary is only "allowed" to do attacks which are not deemed trivial. I should note, however, that actually figuring out what the trivial attacks are, can sometimes be a bit tricky.


Why is Rabin encryption equivalent to factoring?

Since n = pq, then when an integer modulo n is a square, then it has (in general) four square roots. This can be seen by reasoning modulo p and modulo q: a square has two roots modulo p, and two roots modulo q, which makes for four combinations.

More precisely, modulo a prime p, if y has a square root x, it also has another square root which is -x. The same applies modulo q, and makes four combinations. What you look for is a pair of values (a,b) such that both are square roots of the same value (i.e. a2 = b2 mod n), a = b mod p, and a = -b mod q (or vice versa). If you have such a pair, then c = a-b mod n will be an integer that is equal to 0 modulo p but not modulo q; in other terms, c will be a multiple of p but not of q, so a simple GCD computation between c and n will reveal p.

Suppose that you have a box that can compute square roots modulo n. Then, the attack works thus: generate a random a modulo n; compute a2 mod n and send it to the box. The box will return a square root b (one of the four possible square roots). If the box returns a itself, or n-a, then this round fails, and the attacker must start again with another random a. This happens 50% of the time. But if the box returns one of the two other square roots of a2 then the GCD explained above reveals a factor of n.

There is no square root choosing strategy from the box that can prevent this attack from working, because the attacker chooses a completely at random.

The above does NOT show that "Rabin encryption is equivalent to factoring". What it shows is that the general ability to extract square roots modulo n is equivalent to knowing the factors of n. The term "general" here means that the ability works for a substantial proportion of values which are squares modulo n. Anybody can compute square roots for some values (e.g. if we work modulo n and you challenge me with the value "9" then I can answer that a square root of that value modulo n is "3", and I can do that even without knowing the factors of n); but if you can do that for a non-negligible fraction of all integers modulo n then you can factor n.

There is no actual standard that specifies Rabin encryption, but if there was, then that standard would probably entail some sort of padding, because, as explained above, a square has four square roots. The decryption engine must choose which one is the right one. A simple strategy for that is to add some redundant padding: when encrypting message m, convert it to an integer x by appending h(m) to m (for some hash function h) and then interpreting the whole as an integer. Then, upon decryption, recompute the hash to know whether you got the correct square root, and not one of the three others. (The padding would also have to include some randomness to avoid brute force on the plaintext.)

With such a padding, a box that can decrypt things may return the decrypted value, OR it could say "this does not decrypt to anything that is properly padded". Then the attack explained above no longer works; the attacker will have to find a value a such that another square root b (which is neither a or -a) ends with a proper padding, otherwise the decryption oracle won't return it. Depending on how the padding is exactly defined, then the probability to hit such a value could be too small to actually happen.

Therefore, while extracting square roots modulo n is equivalent to factoring n, it cannot be said, in all generality, that practical Rabin encryption is equivalent to factoring. This depends on the details of padding and usage, details which are not, currently, defined.


Note: you should also take into consideration the Expansion table, as it glues together with the Pbox.

The simplest thing you would like to want from a Pbox is to provide a good diffusion on the inter-sbox level. That is, a single sbox should have an effect on many sboxes in the next round. This is not sufficient, for example you could have some indepent groups of sboxes. So you need to see how many rounds are needed to prodive full diffusion, for each of the sboxes.

For example, PBoxes which make some independent groups of sboes, do not provide full diffusion at all and are considered unsecure. Also, consider Pbox which matches sboxes like $(2, 3, 4, 5, 6, 7, 1)$ (e.g. 1 shift left). You need at least 7 rounds to provide full diffusion.

For DES I think 2 rounds are enough for full diffusion, so that is at least acceptable.

Of course I described the very basic property of the PBoxes, which is not sufficient to say that a PBox is secure for a cipher. For another example, you can consider weak sboxes, for example if 2 sboxes are weak. Some PBoxes may resist it, some PBoxes may make the cipher much more weaker.


Does CCA security imply authenticated encryption?

No. RSA-OAEP is indistinguishable under adaptive chosen cipher text attacks (and even non malleable under adaptive chosen cipher text attacks), but it is not an instance of authenticated encryption. - The sender who encrypts the message might even be anonymous to the recipient who decrypts the message.

More generally, in a successful Chosen Cipher text Attack the adversary gets the honest decryptor to accept a forged cipher text, decrypt it, and accept the resulting plain text. It is not primarily a key recovery attack (although in some cases it might be extended into one). In fact, you can't turn a CCA against a secure block cipher in any standard mode, into a key recovery attack. You can however alter the decrypted plain text by altering the cipher text, unless the scheme is NM-CCA2. Often this is enough - most attacks against SSL/TLS don't actually recover any secret key, but only gets the recipient to accept plain text as authentic even though it is not.

In the case of asymmetric encryption, this gets more complicated. Plain unpadded RSA is not secure against CCA (which at the same time makes it possible to use it for homomorphic encryption). RSA-OAEP is secure against CCA, meaning you can't take a RSA-OAEP cipher text encrypted by someone else, alter it (in any other way than by replacing it with another message RSA-OAEP encrypted with the same public key), and get the owner of the private key to decrypt it.


Ways to make white-box cryptography AES implementation more difficult to be broken

Is the above way reasonable (if we cannot find a proper implementation)?

No, there are currently no such code-obfuscation algorithms that securely obfuscate code to a point where it's very hard to reverse engineer it.

  Please recommend any mature WBC implementations (not broken yet)

I'm not aware of any WBC implementations for AES.

Note, that a successful implementation of a WB-AES algorithm would mean that the "one-wayness" (very hard to invert) would turn this algorithm into a public-key-cryptosystem without a need for asymmetric cryptography (you would just publish the WBC-AES-implementation and the key wouldn't leak). So I'm pretty sure that there are no unbroken implementations.

It could be that there are some unbroken WBC implementations out there, but I don't think that they would remain unbroken for long if they would attract a lot of attention from the cryptographic community.

  Any other better idea? (other than re-design & evaluate a new WBC algorithm)

No. As Geoffroy Couteau and I commented, self-made code obfuscation is likely unsecure for many reasons, the main reason being that the security would rely on the fact that nobody ever would gain knowledge of your obfuscation algorithm.


Making a cipher non-malleable using a plaintext transform?

Is there any existing approach that does anything similar to this? Basically some sort of modern version of Russian copulation?

There is one existing idea which is currently used in some RSA implementations that could be tweaked slightly to fit the requirements of Russian copulation.  I will briefly describe below, and then mention a potential additional benefit of such a 'transform'.
OAEP
Optimal Asymmetric Encryption Padding (OAEP) is a padding scheme often used together with RSA encryption.
The algorithm takes the form of a Feistel network which uses a pair of random oracles $G$ and $H$ to process the plaintext prior to asymmetric encryption. When combined with any secure trapdoor one-way permutation $f$, this processing is proved in the random oracle model to result in a combined scheme which is semantically secure under chosen plaintext attack

As using OAEP as an all-or-nothing transform would require processing in blocks (with padding) and potentially some extra tweaking to design it for the purposes of non-malleability.

Finally, it is not necessarily be the case that using such a transform function would only provide the benefit of non-malleability.  As per the Ron Rivest's paper All-or-nothing encryption and the package transform

We present a new mode of encryption for block ciphers, which we call all-or-nothing encryption. This mode has the interesting defining property that one must decrypt the entire ciphertext before one can determine even one message block. This means that brute-force searches against all-or-nothing encryption are slowed down by a factor equal to the number of blocks in the ciphertext. We give a specific way of implementing all-or-nothing encryption using a “package transform≓ as a pre-processing step to an ordinary encryption mode. A package transform followed by ordinary codebook encryption also has the interesting property that it is very efficiently implemented in parallel. All-or-nothing encryption can also provide protection against chosen-plaintext and related-message attacks.

Below I will give an example of how we can use OAEP as inspiration.  It can obviously be improved upon (and I could probably use a variant of ChaCha QR).  My code is here and may well be easier to read than my explanation below.
This CAN be done in a single-pass, and it is significantly quicker than my previous function which looked up/sliced/rearranged arrays, and processed byte-by-byte.
First, I took an unbalanced Feistel cipher and set it up (with 10 double rounds). It is made up of 8 blocks of 32 bits.
The blocks are XORed with fixed circular rotations of other blocks, and shift position after each double round.  In each double round, most blocks are affected in some way by most other blocks.  For example, block0 (in one double-round) is affected by Blocks 1,2,4,5 & 7.  Odd blocks are affected by one less, eg. Block 1 is affected by Blocks 2,3,4 & 5.
After 10 double rounds, this achieves good (over 50%) diffusion in output blocks 0,3,5 & 6.  In the other "bad" blocks it is around 56%.
We will process input data in 128 bit chunks, using the "good" blocks of the Feistel and the "bad" blocks of the Feistel will be the state/capacity which is initialised with random data and saved with the final encoding.  Thus allowing us to decode (backwards), and the initial randomness providing a nonce.
Finally, we add a 128 bit "counter" into the Feistel.  This keeps a XOR of all the data blocks processed (and begins on 0).  This doesn't need to be saved, but does require slightly more computation for decoding as we need to "count" all the blocks before we begin the decoding process.
As we decode in reverse, it is obvious that the last data block affects any of the previous data blocks (due to the saved state).  And as the "count" of previous data blocks affects the last data block, we have all bits affecting all bits.
It would require padding the input, but it's incredibly quick. 1KB is processed in <0.003 seconds on my rubbish machine.  It's actually too quick for my rubbish testing and often registers 0 at lower amounts.
The problem I can see is that it generates differing diffusion levels depending on the size of input.  If the input is 128 bits, the average number of bits changed for any bit flipped is around 75%.  For 1024 it is around 57%.  For 3072 it is around 53%. For 4096 it is still around 52.5%. At 1KB it is around 52%
I have not found a single bit that could be flipped that didn't cause over 50% of bits to change for any input size.


Password cracking: What if attacker is lucky?

"lucky" is not a property of the attacker. There's no "lucky" attacker nor "normal" attacker. They both have the same probability (low, very low) to guess the key. You can decrease the probability at will by increasing the length of the key (i.e. the no. of bits). You cannot really argue "what if the attacker is lucky" because "being lucky" is a posteriori statement; you say that an attacker is lucky only when he/she was... lucky


The answer is almost definitely no for what I think you want (question is still unclear). I was hoping someone else could give a definite no, but since they haven't I figured I'd write this up.

Your exact secret sharing method probably needs to be fully described in the question. I'm going to assume that $a=a_1\oplus a_2\oplus\dots\oplus a_n$ and similarly for $b$. Party $p_i$ is given $a_i,b_i$ and you want the parties to be able to compute shares, say $c_i$ of $c=a+b$ without reconstructing $a$ or $b$. I'll assume we are working in some finite field $\mathbb{F}$ and that $a_1,\dots,a_{n-1}$ are chosen randomly from the field and $a_n=a\oplus a_1\oplus\dots\oplus a_{n-1}$. The shares of $b$ are chosen similarly.

Note that this is basically additive secret sharing in a field of characteristic two. But, when you say you want to compute shares of the sum of $a+b$, I'm assuming you don't mean field-of-characteristic-2 addition (which is just xor). If that is what you mean, then the answer is simple (each party $p_i$ simply computes $c_i=a_i\oplus b_i$). I'm assuming you want something like 32 bit addition (i.e., addition mod $2^{32}$ or something very similar like addition in $\mathbb{Z}_p$ where $p$ is possibly the next prime after $2^{32}$).

To see why I don't believe it is possible, lets use $n=2$.

So, $p_1$ gets $a_1,b_1$ and $p_2$ gets $a_2,b_2$ where $a=a_1\oplus a_2$ and $b=b_1\oplus b_2$.

Therefore, the problem reduces to the following, we need some operation, say $\boxplus$, such that $(a_1\boxplus b_1)\oplus(a_2\boxplus b_2) = a+b$

So, what are the possibilities for $\boxplus$. If we allow for communication to take place between $p_1$ and $p_2$, then the answer is yes, it can be done. In this case, we can do multiparty computation in the characteristic 2 field and construct a 32 bit adder circuit. This should be possible as far as I understand MPC.

Now, assuming you do not allow communication between the parties after the shares are distributed (which I'm guessing is what you wanted), I just don't see a way to do it (though I haven't been able to fully prove it, if nothing else hopefully my answer will bring some good discussion). If we take the approach of MPC, all we can do on the shares is compute the xor and multiply by a constant. Given those operations I don't see how you would construct an adder.

Another temptation might be to simply add $a_i,b_i$ using regular addition. In which case you get $(a_1+b_1)\oplus(a_2+b_2)$ which will not be $a+b$. Really we need an operation $\boxplus$ which is commutative and associative with $\oplus$ in which case you could do $(a_1\boxplus b_1)\oplus(a_2\boxplus b_2)=(a_1\boxplus b_1)\oplus(b_2\boxplus a_2)=a_1\boxplus (b_1\oplus b_2)\boxplus a_2=a_1\boxplus b\boxplus a_2$. It is unclear where to go from there. This is where I ended up and couldn't go any further and why I believe the answer  is no in the case of no communication.


Is it possible to permute a binary vector obliviously?

Using an encryption scheme that is rerandomizable (such as ElGamal for example), A can just send n ciphertexts encrypting her values, then B shuffles those ciphertexts and rerandomize them. B never learns anything and the rerandomization destroys information about the original ciphertexts so that A cannot trace back the permutation.


Quantum security risk to present encryption

Quantum computers will seal the fate of conventional encryption techniques

This is only somewhat true in regards to asymmetric cryptosystems. Algorithms such as AES256 and XSalsa20 will remain secure even in the face of full scale quantum computation.

  the hardest hit will be the RSA algorithm used by 99 percent of all applications the encryption standard for any secure transfer and storage of communication data or software updates.

Both RSA and discrete-logarithm based systems such as Diffie-Hellman (including the Elliptic Curve variants) are vulnerable to Shor's algorithm, and both are widely used. RSA is used more for signatures than for key exchange. RSA is far from a single point of failure and being the only mainstream public-key cryptosystem.

  What are some solutions to the inevitable?

It is arguable that Quantum Computing of scale that will impact cryptography is "inevitable". There are non-trivial engineering barriers that have to be overcome.

Solutions

NIST is currently hosting a contest of sorts to find and standardize quantum-resistant asymmetric calgorithms.

Candidate schemes include:

Hash-based signatures
Code based cryptography
Lattice based cryptography
Supersingular Isogeny Diffie-Hellman
Multivariate cryptography


What is the concrete communication complexity of Commitment schemes?

The simplest commitment scheme is a hash based commitment; to commit to a value $M$, the committer selects a fixed length value $R$ and publishes $\operatorname{Hash}(R \mathbin\Vert M)$; to decommit, he publishes the values $R$ and $M$.

If the Hash function is collision resistant, then the committer cannot commit to two different messages; if $R$ is long enough, then it is infeasible to recover $M$ from the commitment.

With this in mind, and assuming we're using a 256 bit hash (such as SHA256) as our hash function, and a 128 bit $R$:

Data sent by verifier: none
The commitment: 256 bits
The decommitment: 128+n bits

This is a total of 384+n bits.

I believe that it can be shown that you cannot do better without reducing the practical security of the system below the "128 bit" level


How can I prevent a message replay with RSA?

You could use some combination of:

an expiration timeout (i.e. if the message does not arrive until the timeout, we don't accept it)
storing previous values of a nonce.

You only have to store those nonce values whose timeout didn't yet expire.

If the messages arrive all in order, you can instead use a simple counter (which always goes up) and reject every message which has a counter value smaller or equal than the last received one.


1. Is it a reasonable solution?

That's hard to say; for a transport protocol - which is what you are designing - you have hardly described anything at all. Yes, a counter can be used to make messages unique as to avoid replay attacks and introduce randomness when combined with the AES key.

  2. Are there any possible security risks?

Plenty, but with the minimal description - without even a mode of operation or message description, use case, threat model etc. - it is hard to tell which ones would be applicable.

  3. Since the plain text will not repeat itself, should I still use an IV? or can I omit it?

That depends on the mode. If your messages are only one block then you could use ECB mode, which does not require an IV . Otherwise it depends on the mode of operation.

For instance, encrypting a counter in the plaintext message with e.g. AES-CTR will not result in randomizing your ciphertext; in that case you need to use an IV. For AES-CTR, every bit of ciphertext doesn't depend on any of the other bits, so you cannot rely on the message randomizing the ciphertext itself. This is also the case for most authenticated modes of operation (e.g. GCM) as they internally rely on AES-CTR mode for confidentiality.

However, if you put the counter / randomness in the first block of plaintext for AES-CBC then you would be fine, and you could use an all-zero IV.

  4. Should I use a MAC, or is the counter is a sufficient authentication?

No, a counter is not authentication. You need either a MAC or an authenticated mode of operation (assuming you require message authentication, which is commonly the case).

After the edit: sure you can use ECB mode (which is just the application of the block cipher for a single block) to encrypt a plaintext block that includes a counter.

It depends on the size of the counter if you could see the result as authenticated. If the counter is 64 bit then you get 64 bits of security, which could be enough given that you require a new counter each time. If the counter is smaller then I'd certainly make sure that you only allow one (or a few) ciphertext messages.

Furthermore, you should never ever repeat the counter for the same key. Not on restarts, for instance.

Looking at your level of questioning, you're not yet ready to create your own transport protocol. You could have a look at e.g. TLS. There is also a version for packet encryption called DTLS. Or any one of the lightweight transport protocols used for embedded applications.


What does “simulator” and “interactive” mean in a cryptographic credential system's definition of security?

"simulator":

That's a definition of security in a model that is related to but weaker than the universal composability framework (thanks to Yehuda Lindell for making that clear and you can look at the paper in his comment). You could also look up the wiki link and I think there are also several question on this site.

As @Yehuda Lindell mentions in a comment, if you are not familiar with the concept of a "simulator" at all so far it is better to look at definitions of secure (multiparty) computation or the zero-knowledge property of interactive proofs.

"interactive":

Think of two probabilistic polynomial time Turing machines (Turing machine with additional random tape) who have local input and output tapes (as usual), but also additional tapes to write input to the other machine and receive input from it. Both machines after interacting halt with local outputs.

For instance, a machine $A$ may run on local input a secret key and machine $B$ on the respective public key and a message. After interaction $B$ halts with a signature for the message and $A$ with no local output (that would be the signing procedure of a blind signature scheme, which you probably know or are familiar with when studying anonymous credentials).


Implementation of garbled circuits using RSA

The notation you are seeing is for symmetric crypto. Garbled circuits typically use symmetric crypto since it can and symmetric crypto is fast. You may be able to do garbled circuits with asymmetric crypto, but it is definitely non-standard and may have subtle issues.