Is Using Digital Signatures to prove identity a zero knowledge proof?

This is not zero knowledge. In particular, you give away information in the form of signatures on challenges. This is something that the verifier doesn't have and so it is something that is "learned".

This can be meaningful for two reasons. Let's say that I want to prove to YOU that I wrote the book, but I don't want you to be able to convince anyone else that you interacted with the person who wrote the book. With this protocol, it's possible to prove that you interacted with the book author, but this isn't possible with real ZK. Another issue is that the challenge may actually be generated maliciously so that it provides a meaningful signature.


Hashing based on the discrete logarithm problem

A secure hash function based on the discrete log problem is $H(x\|y)=x\cdot G+y\cdot P$, where $P$ is a random point for which the discrete log is not known and "$\|$" denotes concatenation; this was shown by Damgård. This can be proven collision resistant under the discrete log assumption (if you can find a collision then this can be used to find the discrete log of $P$). Note that in order for it to be of interest, the output has to be shorter than the input. However, this is easily achieved for most curves by using point compression. Once you have this function, you can get a general collision-resistant hash function by applying the Merkle-Damgård transform.

Of course, this would be extremely inefficient, but it is a collision resistant hash function from the discrete log problem.

The paper presenting this is Collision Free Hash Functions and Public Key Signature Schemes by Ivan Damgård. It is also described in Section 8.4.2 of the Katz-Lindell textbook (second edition).


Secret Key Exchange and FIPS or Industry Standard Compliance

Suppose you are a device manufacturer. Suppose further you know to which companies you are selling your devices. Suppose further that all that really matters for the device-to-device communication is a) that they are legitimate devices made by you and b) that they are operated by a specific company. Now if your customers trust you (which they kinda have to given that you sell them devices), these devices can be made to communicate securely.

I'll make the assumption that the static private keys are non-extractable because if you can extract one, you can impersonate this device. This can be achieved using TPMs, HSMs or other security-chip based key-stores.

The idea here is that you pre-provision all devices you ship and you essentially act as the CA in this ecosystem.

The setup is really quite simple:

Manufactur the device right up to the point where you would normally ship it (that is all hardware and software is complete)
Generate an asymmetric signature key-pair on the device. Also generate a CSR on the device, given that you create the CSRs in a trusted environment, you can include the designed customer in it.
Transport this CSR to your internal CA and issue the requested certificate. Given that the CSR is from a trusted environment, you can "blindly" copy the owner information into the certificate.
Transport and install the certificate into the secure-chip's keystore. Also install the certificate / public key of your internal CA into your platform's root CA store (and make sure it's the only root CA) on the device. Make sure that your preferred SSL/TLS library actually uses this key-store.

This is the whole setup, which needs to be executed per-device.

Now for the connection establishment which is really standard.

Suppose Device A wants to securely talk to Device B. Suppose further both devices are listening for incoming connections.
Now A ("the client") initiates a TLS handshake with B ("the server").
You run a standard TLS-connection between the two devices with the following caveats:

You make sure only secure parameters and cipher suites are used.
You only accept B's certificate if it passes standard certificate validation and your custom company-based validation and it is issued by your root CA.
B needs to request client-authentication during the handshake. B needs to only accept A's certificate if standard validation succeeds and it passes the custom company-based validation and it is issued by your root CA.

And that's it. Your devices now have a secure connection and they know (and only that!), that their communication partner was manufactured by you and that their communication partner is a device that was sold to the given (other?) company.

The use of the device-manufacturer CA is industry-standard, as well as the use of TLS here. For high confidence you may want to your customers to use their own CA, their own sub-CA (and filtering for that one then if requested) and you want to apply standard CA security practices to your device-authentication CA.


Think about 2 special cases when using AEAD:

Some confidential data but blank associated data
Some associated data, but blank confidential data

In first case what you get when using AEAD cipher (e.g. AES-GCM) is just Authenticated Encryption, as there is no associated data.
In second case what you get when using AEAD cipher (again, e.g. AES-GCM) is essentially a MAC - there was nothing to encrypt, and what you actually did was calculation of authentication tag over associated data.
BTW, "What are the benefits of using AEAD algorithms as MAC" and "What is (or was) NIST thinking when they acknowledge(d) using AEAD as MAC?" are actually two different questions. I hope I answered the latter.
EDIT:
If you look at MAC algorithms like Poly1305, Poly1305-AES or CBC-MAC, they also use nonce/iv.


How to recover a message with shared modulus for textbook RSA

what I am doing wrong?

Accepting as fact a recipe with an equation, rather than deriving it.
Illustration: « Then we obtain $m$ as ${c_1}^a + {c_2}^b \bmod n$ » is stated rather than derived. And wrong.
As an aside the question reverses $a$ and $b$ (or is it $c_1$ and $c_2$, or $e_1$ and $e_2$): they are correct per the official solution which asks $a\,e_1 + b\,e_2 = 1$, but the calculation then made assumes and states $a\,e_2 + b\,e_1 = 1$.
Hint to derive the correct equation:

Prove that $m^1\bmod n=m$, by combining the definition¹ of raising to an integer exponent, the assumed range of $m$ in textbook RSA, and the definition² of the $\bmod$ operator.
In this equation, substitute $1$ with $a\,e_1 + b\,e_2$ where $a$ and $b$ are the Bezout coefficients such that $a\,e_1 + b\,e_2=1$.
Properly use properties³ of modular exponentiation. In cryptanalysis it's OK to assume plausible preconditions when that's necessary, but it remains good to verify them (or the result derived) in the end.

Suggestion: apply this technique with a slightly larger $n=14835196795348830319$, $(e_1,e_2)=(3,5)$, and $(c_1,c_2)=(14562201346830272020,1832973312396331965)$. As a bonus find the menu by expressing $m$ in hex. The point of these larger numbers is that guessing the Bezout coefficients and inverse is harder, and slightly more computer skills are needed.
More mathematically interesting, for a different method is needed, which would still work if $n$ was too large to factor directly from its value: with the same $(n,e_1,e_2)$ find $m$ for $(c_1,c_2)=(11810011337245959646,2207245693327700143)$.

Note: in actual use, RSA encryption

Does not reuse the same $n$ among several public keys, making this particular attack fail.
Does not directly encode the message as $m$, but rather adds randomness to the message in order to form $m$. That makes it extremely unlikely that $m$ is reused (it would be enough to allow some other attacks including with different $n$).
Uses $n$ with several hundred decimal digits in order to resist factorization. $n=143$ can be factored mentally, and the larger $n$ is factored in a small fraction of a second using a computer, which allows to find $m$ by using the normal RSA decryption equation, without needing $c_2$ or $e_2$.

Appreciation: taking at face value the statement that the extended Euclidean algorithm was used, the question shows fair skills to apply equations and algorithms, despite the inversion of $a$ and $b$. Be assured that the goal of such exercises is not learning the equations used. It's to learn to derive the necessary equations. That's easier when one gets the hang of it, and more fun. It's more reliable, and thus gets higher marks (which is a valid sub-goal) even when the reasoning is not considered in the notation. As a skill it's more useful, more adaptable, less likely to go obsolete, or unused and forgotten.

¹ ² ³ : See this definition of $x^u\bmod k$ and related typographical conventions, or refer to a previous version of the present answer.


trapdoor commitment from lattice-based assumptions?

If you have a (standard) commitment scheme $C$ and zero-knowledge proofs of knowledge (both exist from LWE -- in fact, both exist from one-way functions), then you necessarily have equivocal commitments. Here is a straightforward equivocal commitment $C_e$: committing with $C_e$ is just committing with $C$, and opening a commitment is done by revealing the committed value $m$, together with a proof of knowledge of an opening to $C$ such that the commitment opens to $m$. It is easy to see that the proof of knowledge property implies that $C_e$ is binding, and the zero-knowledge property implies the existence of a simulator which can fake proofs of opening to any $m$, hence the commitment is equivocal.

That being said, I'm pretty sure there are many direct and relatively efficient constructions of equivocal commitments. For example, the LWE-based fully homomorphic trapdoor functions from this paper are in particular equivocal commitments (see page 5 of the paper).


Is webkey a reasonably secure authentication system?

First of all, you should make a more formal definition of the protocol. Security cannot be assessed without a proper definition.

Second you don't specify an key sizes. RSA-512 is such a low key size that it may be considered broken. On the other hand, you may run into performance issues if you choose a higher key size (Elliptic Curve crypto would make more sense). This is not theoretical security, I know, but it kind-of makes sure that this will never run for any practical key sizes.

The same for the challenge. 3 characters is way to low and almost begs for replay attacks if the same challenge is ever send. A 16 byte challenge should be the minimum.

You seem to be using a Node.js include for your RSA key pair code. That's strange if the key generation is offered within the browser as you suggest.

The biggest usability issue is the fact that you may loose your private key if the browser storage is destroyed. The RSA key seems to be local to the browser, so sharing different devices isn't specified.

It doesn't seem to be specified what happens if you loose your key.

I haven't seen any requirements for TLS (with server authentication). You'd need that otherwise an attacker may steal your key by simply injecting Java Script code.

All in all, there's too much missing from the description of your protocol to make a full security review. But it seems there is a lot that may need improvement before it can be used for any serious purposes.


If WhatsApp cannot read our message, how can the media forwarding happen in an instant?

Leaving aside the WhatsApp aspect fo the question: the effect described can be achieved with hybrid encryption, where the bulk of the data is encrypted under a random secret symmetric key, and the result uploaded once; revealing that data to a recipient is performed by encrypting that symmetric key towards the recipient (e.g. using his/her public key), and thus requires very little data transfer from the sender for each additional recipient.


My intuition suggests that there would be no security impact if this output were truncated to 128 bits. Is this correct? My reasoning here is that salting prevents multi-target attacks, and that collisions are unimportant in the context of password verification.

Correct, there is no practical security impact. The preimage security of the hash function is what matters for password hashing, and 128 bits is long enough to prevent brute force preimage search. You could probably even go shorter than that, but database space is usually cheap which is why using the full 256 bits is common.

In principle, with a 129+ bit entropy password you would lose some security, as a brute force attack to find some password with the same hash would become faster. Such passwords are very uncommon, however, and the brute force would remain infeasible even if theoretically faster.

(If SHA-256 is found to be very weak after some new attack all bets are off. The attack could allow a faster preimage attack on truncated output or it could not. The opposite could even be the case.)


modfied man in the middle attack diffie hellman

Why are there exactly $m$ values for $k$?

Well, assuming $k$ is the value of the shared secret that either Alice and Bob derive, well, that's not true; there are at most $m$ possible values, however it may be fewer.  There will be exactly $m$ values if $g$ is a primitive root modulo $p$; however when we use Diffie-Hellman in practice, we generally avoid using a primitive root.

To understand why there are at most $m$ possible values, we need to look at Fermat's Little Theorem; one way of expressing it is:

$g^x \equiv g^{x \ \bmod\ p-1} (\bmod\ p)$

(This isn't the standard way of writing it; this formulation works out fairly well for this purpose).

The other thing to look at the Diffie-Hellman operation with the modified messages, where Alice computes:

$k = g^{aq} (\bmod\ p)$

And we ask ourselves "how many distinct values can $aq \bmod\ p-1$ take on?"  (Hint: consider the Chinese Remainder Theorem).

You're supposed to be learning, hence I'm not giving you the full answer; I hope these hints are enough for you to fill in the missing pieces.

  Why is this attack any better than the attacker simply raising $g$ to their own value $e$?

Well, in practice, it won't be any better; any secure protocol that uses Diffie-Hellman must have a story why an attacker who modifies the messages cannot gain an advantage; such protection will foil both attacks.

However, I believe the answer they're looking for starts with "if the attacker replaces both values with his own value $g^e$, then both sides will always derive different shared secrets (and hence different session keys); to continue the attack, the attacker must decrypt each sides messages, and reencrypt them with the keys shared with the other side.  However, if the attacker replaces both values with $g^q$, then with probability $\ge 1/m$, [fill in details here]


How much does using the same $H$ for all messages weaken GCM?

Under the ideal cipher model, security is not diminished by any choice of value $H = E_K(d)$ for a known value $d$, as long as none of the counter values that get encrypted to generate the encryption stream is equal to $d$. This is what "ideal cipher" means: you have no information on $E_K(x)$ for any $x$ that you have not already tried to encrypt with the same key, and that goes for all such $x$; none is beter or worse than any other. Using $d = N||0_{32}$ instead of $d = 0_{128}$ would thus not make GCM any weaker. It would not make it stronger either, for all we know, because making it "stronger" would require that we know of some weakness in GCM as it is defined nowadays; and we know of no such weakness.

Now, using $H = E_K(0_{128})$ has some implementation benefits. Namely, suppose that you want a constant-time implementation of GCM, thus without any memory access whose address depends on the data or the key (this is to avoid side-channel attacks through cache misses). On a modern PC, you will want to use specialized opcodes, but on a slightly less modern x86 CPU, or on a non-x86 architecture (e.g. ARM), you do not not necessarily have access to such facilities. Classical implementations of multiplications in $GF(2^{128})$ are either very slow, or use data-dependent table lookups, which are not constant-time. A constant-time multiplication by $H$ can be implemented relatively efficiently (at about 14 cpb) with the help of tables whose contents depend on $H$ -- but that's counting without the cost of generating these tables. If $H$ depends only on the key, not the IV, then the tables can be produced as part of the key schedule, for a much lower overhead if many messages are processed with the same key.

Thus, having an IV-dependent $H$ is not known to increase (or decrease) security, but may imply larger CPU costs in some situations. This is a good reason to have a fixed $H$, that depends on the key but not the IV.

Constant-time multiplications in $GF(2^{128})$ can also be done in other ways, but that's another story. One is to use additive Fourier transforms, which yields remarkable performance in generalized bitslicing, but only in situations where many blocks can be processed in parallel, and with a large fixed overhead. Another method is to use integer multiplications on the operands, with most bits cleared to make room for carries; this can be worthwhile if the architecture at hand offers constant-time efficient multiplications. An example of such an architecture is the very-low-power ARM Cortex M0+, where additions and multiplications have the same cost (1 cycle each).

Even then, having an IV-dependent $H$ still implies some extra work for each message, since that processing cannot be shared.


Repeatable encryption for pseudonymisation

AES with $\text{IV}$ created from the data $d$ by $\text{IV}=\operatorname{hash}(d)\bmod m$, where $m$ is the max value for $\text{IV}$

That seriously compromises confidentiality, and does does not provide authentication:

The $\text{IV}$ is typically in clear at the beginning of the cryptogram, and that allows someone without the key to test a guess of $d$, which is a total disaster for a login!
Someone without the key can prepare a cryptogram that will decipher (at least, to garbage, but that can still be damaging, causing denial of service or worse, see below).
If there is a test of acceptability of what's deciphered (e.g. a syntax check), that's ideal grounds for a padding oracle attack that might very well allow decryption without a guess (depending on details of the encryption, availability of a decryption oracle/server, test of acceptability and insight on its result an adversary gets thru side channels like error codes, network states, or timing).
Depending on AES mode and availability of valid cryptograms with known plaintext, someone without the key may be able to prepare cryptograms that will decipher to something under control of the attacker.

Making symmetric encryption deterministic (the academic name for "repeatable") is bound to allow a test that two messages are identical by comparing the ciphertexts, but all other drawbacks can and should be avoided.

A good option would be a Nonce-Misuse-Resistant Authenticated Encryption with a public fixed nounce, e.g. the key index (symmetric keys should be rotatable, and identified by key index for this purpose).

A modern such scheme is AEAD_AES_256_GCM_SIV of RFC 8452. We are straight in the designed-in usage: "encrypting two messages with the same nonce only discloses whether the messages were equal or not". The theory behind the scheme is described in Shay Gueron and Yehuda Lindell's GCM-SIV: Full Nonce Misuse-Resistant Authenticated Encryption at Under One Cycle per Byte, in proceedings of CCS 2015.

If performance is not an issue, there are ways to obtain similar functionality from more available primitives, such as a hash and/or an encryption-only mode of operation. Edit the question stating available primitives if that's needed.


No, in general, knowing the key $k$ allowing efficient computation of a keyed permutation $P_k$ does not allow to efficiently compute the inverse permutation.

Here is a concrete example where the inversion is (conjecturally) computationally infeasible:

Let $D$ be the set of 4096-bit bitstrings, assimilated to integers per big-endian conventions.
Let $p=2^{4097}+3^{2579}+863880\;$. This is such that $p$ and $(p-1)/2$ are prime, and $2^{(p-1)/2}\equiv-1\pmod p$. The function $x\to(2^x\bmod p)$ is an efficiently computable public permutation of the set $\{1,2,3\dots p-3,p-2,p-1\}$, but the reverse permutation is hard to compute for arbitrary input (that's a Discrete Logarithm problem).
For $k\in D$, let $P_k$ be the permutation over $D$ defined for input $x$ by

$x\gets (x\oplus k)+8192$
note: here $8192\le x<2^{4096}+8192<(p−1)/2$
repeat

$x\gets(2^x\bmod p)$

until $8192\le x<2^{4096}+8192$
output $(x-8192)\oplus k$

The repeat/until loop (known as the cycling trick) creates a public (conjecturaly) hard to invert (that is, trapdoor) permutation of the set $\{8192,8193,\dots,2^{4096}+8190,2^{4096}+8191\}\;$. Combined to XOR with $k$, that forms $P_k$, which is keyed, and (conjecturaly) hard to invert and computationally indistinguishable from a random permutation without knowledge of $k$.

The above $P_k$ is an example of a PRP which members are trapdoors even to one choosing the key $k$. That's not the case of all PRPs: we also have block ciphers, which are PRPs invertible by anyone able to compute the function; and textbook RSA encryption, which is computable by anyone knowing the public key, but invertible only by one knowing the private key (textbook RSA encryption alone is not quite a PRP on a fixed set, but it is possible to build such PRP from textbook RSA encryption, e.g. using a cycling trick as above).


Here are some recent papers that explicitly study optimizing PSI for the case of unequal set sizes.

Private Set Intersection for Unequal Set Sizes with Mobile Applications; Ágnes Kiss, Jian Liu, Thomas Schneider, N. Asokan, Benny Pinkas
Fast Private Set Intersection from Homomorphic Encryption; Hao Chen, Kim Laine, Peter Rindal
Unbalanced Approximate Private Set Intersection; Amanda Cristina Davi Resende, Diego F. Aranha

Update:

PIR-PSI: Scaling Private Contact Discovery; Daniel Demmler, Peter Rindal, Mike Rosulek, Ni Trieu


Are there practical upper limits of RSA key lengths?

Computational cost of RSA with keys of length $n$ bits is roughly $O(n^2)$ for public key operations (encryption, signature verification), and $O(n^3)$ for private key operations (decryption, signature generation). So RSA with a million-bit key will be roughly one billion times slower than RSA with 1024-bit keys (for the private key operations); the latter takes about 1ms on a common PC, so you're in for a fortnight of computation with your million-bit key.
Memory space is not a hard constraint, because RSA computations require only to keep a few values of the size of the key; a one-million-bit integer is 128 kB; you can have thousands of those in RAM. You will, however, exceed level 1 cache (that's 32 or 64 kB on a common PC) so you can expect some slowdown (with Montgomery's multiplication, data access is sequential, so this effect should be limited).
Of course, security is not only about resisting attacks; it is also about having confidence in being able to resist attacks. My confidence in a system which uses RSA with one-million-bit keys would be near zero... because it makes no sense. RSA is secure because big integers are hard to factor. The best known algorithms with the best available hardware fail at about 1024 bits; 2048 bits are more than enough. Going beyond is making a wild and totally unsubstantiated guess about what not-yet-discovered algorithms may look like, which is speculation on rumours of legends about mythical glimpses of the future. When someone talks to me about having an oversized RSA key, like a 8192-bit key "just to be safe", I see it as if he was talking about buying a SUV to demonstrate his manhood (in your case, you are advocating buying an aircraft carrier).


Why does Fortuna (RNG) require entropy sources to specify accumulator pool?

I see essentially three ways to design this API:

Take a pool
Take a counter and have the accumulator calculate the pool as pool = counter mod poolCount
Take a sourceId

Of these 2) seems clearly superior to 1) since the caller doesn't need to care how many pools there are, or how to distribute among the pools.

Comparing 1), 2) with 3) is more difficult, but I think for most situations 1) or 2) is preferable over 3).

If you look at a practical implementation, there will be three kinds of component, which don't trust each other: a) the pool b) some kind of service/daemon reading from the entropy source and feeding into the pool c) the actual entropy source.

Implementing method 1) is pretty easy for both pool and daemon:

The pool just needs to take care of thread safety, and feeds the entropy into the pool it's told.
The daemon just needs to take care of one counter per entropy source

Implementing method 3) is much harder in most circumstances:

You need some kind of sourceId which is different for each entropy source. Using simple integers is already annoying, since you now need a protocol by which a daemon can request a new sourceID. Then you need a process to deallocate them when the daemon terminates, which is problematic if it crashes.

But your biggest problem is that one malicious daemon could try to guess the sourceIDs of another daemon, possibly allowing it to feed that other daemon's data into specific (probably high-index) pools. This means that you need some kind of unforgeable sourceId, such as a random 128 bit value. But now keeping that counter becomes annoying for the pool, since it needs a hash table, not a simple index into an array. No biggy for high level languages, but annoying in c.

For an in process pool in .net or python seems seems OK, since you can use new object() to create an unforgeable ID and weak hashtables are available.

For a multi process setup, this seems like a bad idea. For example on a unixoid system you could have some deamon processes that gather entropy and feed it to the /dev/urandom device via a AddEntropy(counter, data) syscall. This would be much more complicated with a sourceId based design.


Is there an algorithm that gives a reasonable chance of decoding the entire ciphertext of this encryption scheme?

For a frequency-style solution, we can guess the least significant bytes of $k_1, k_2$, decrypt the least significant byte of each block, and check the frequency (e.g. space should be the most often). Then repeat with the previous byte, etc.
The scheme is bad in that it reduces to schemes mod $2^N$ for any $N < n$.


How to find the co-efficients of a function within Zp[x]?

One thing you can always do in situations like this is "defer the reductions to the end".
By this, I mean do all of your calculations in $\mathbb{Z}[x]$, and then at the end "perform reductions until you no longer can", where the two kinds of reductions you do in $\mathbb{Z}/p\mathbb{Z}[x]$ are:

Modular reductions (of coefficients): $a\mapsto a\bmod p$
Reductions (of variables) according to Fermat's little theorem (if working mod $n$ for a composite number, instead use Euler's theorem): $x^k\mapsto x^{k\bmod \varphi(p)}\bmod p = x^{k\bmod (p-1)}$

As kelalaka points out, you can first expand $f(x)$ as a degree 6 polynomial. As $p$ is large compared to the degree (unless by "large" you mean something like 5), you will need no reductions of the second type, so can solely reduce the coefficients of $f(x)$ mod $p$.
If you have to do these computations on the fly this is not the most efficient thing to do (as the initial computation of $f(x)$ can potentially have a very large representation compared to the reduced version, and you may have to do arithmetic with very large numbers in computing this), but it can be useful both conceptually, and fine when you need to pre-process a polynomial (as you do now).
Essentially, arithmetic with polynomials $\bmod n$ can be split into (familiar) integer polynomial arithmetic, followed by applications of the above two reduction rules.


How are old encrypted messages recovered for the sender?

Here is a way you can do it: use a key derived from the password to encrypt your long-term private key.

When you want to register an account with password $\mathit{pw}_0$:

Generate a key pair $(\mathit{sk}, \mathit{pk})$.
Generate a salt $s_0$.
Derive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Compute the ciphertext $c_0 = \operatorname{AES-GCM}_{k_0}(\mathit{sk})$.  (Set nonce = 0.)
Store $(\mathit{pk}, s_0, c_0)$.

When you want to read your mail:

Rederive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Decrypt $\mathit{sk} = \operatorname{AES-GCM}_{k_0}^{-1}(c_0)$ (or report authentication failure).
Use $\mathit{sk}$ to decrypt mail.

When you want to change your password to $\mathit{pw}_1$:

Rederive $k_0 = \operatorname{Argon2id}(\mathit{pw}_0, s_0)$.
Decrypt $\mathit{sk} = \operatorname{AES-GCM}_{k_0}^{-1}(c_0)$.
Generate a fresh salt $s_1$.
Derive $k_1 = \operatorname{Argon2id}(\mathit{pw}_1, s_1)$.
Compute the ciphertext $c_1 = \operatorname{AES-GCM}_{k_1}(\mathit{sk})$.
Replace $(\mathit{pk}, s_0, c_0)$ by $(\mathit{pk}, s_1, c_1)$ and erase all copies of $c_0$.

(This is presumably close to what ProtonMail does.)


Is length extension attack considered as collision?

No, the length extension attack/property is not considered a collision. It does not allow to build a collision.

The length extension property is that given the hash of a bitstring $M$ of given length $l$ (but arbitrary and unknown content), it is possible to compute the hash of $M\mathbin\|F(l)\mathbin\|E$ with $F(l)$ a short bitstring deduced from the length of $l$, and any known bitstring $E$.

It follows that if messages $M$ and $M'$ of the same length collide (have the same hash even though $M\ne M'$), then $M\mathbin\|F(l)\mathbin\|E$ and $M'\mathbin\|F(l)\mathbin\|E$ also collide. Therefore, the length extension property eases building more collisions from an existing collision among messages of the same length.

MD5, SHA-1, SHA-256, SHA-512 have the length extension property (and correspondingly, it is used to extend MD5 and SHA-1 collisions). SHA-3 and SHA-512/256 do not have the length extension property, because enough of the internal state does not make it to the output. The situation is not clear cut for other SHA-2 hashes truncated to more than half their internal state size (e.g. SHA-224 has only 32 bits of resistance to length extension).


TL;DR: It is a bad one.

Proof:

Consider a message $m$ such that $m = M_1 || M_2 || \ldots || M_n$ where $||$ is the concatenation and $M_{1..n}$ are of the same size (typically here 128 bits) and let your MAC be
$$
\begin{align}
MAC(M) &= AES( M_1 \oplus M_2 \oplus \ldots \oplus M_n)\\&=
AES(\bigoplus_{i=1}^n M_i)
\end{align}$$.

We have a forgery if we can find $M$ and $M'$ such that $MAC(M) = MAC(M')$.

Consider:
$$M \;= M_1 || M_2 || \ldots || M_n$$
and
$$M' = M'_1 || M'_2 || \ldots || M_n$$
where $M'_1 = M_1 \oplus 1$ and $M'_2 = M_2 \oplus 1$

Thus:
$$
\begin{align}
MAC(M') &= AES( M_1 \oplus 1  \oplus M_2  \oplus 1 \oplus \ldots \oplus M_n)\\
&= AES( M_1 \oplus M_2 \oplus \ldots \oplus M_n)\\
&= MAC(M)
\end{align}$$

With this I created a forgery $M'$ of $M$ which would still have the same MAC. $\square$

Remark:

You don't even need the key used for the AES encryption to create the forgery.


What's the difference between DH and DHE?

Using DHE means even the $g$ and $p$ parameters are randomly generated

No, that's not what DHE means.
They may be randomly generated, but as this is a very expensive process (because you need to find a safe prime), computationally seen, you usually don't do this.
What you do in DHE is that both parties pick random values for $x$ and $y$ at run-time (e.g. protocol execution).

However, when you're doing a DH (without the "E") key exchange, the server has a certificate, which embeds a static, public Diffie-Hellman key, i.e. $g^x\bmod p$ as well as $g$ and $p$ allowing you to save an additional signature (e.g. using RSA or ECDSA) to verify the authenticity of the DH parameter. So while the server's DH value is static, the client still usually chooses a random value for security and storage-reduction reasons. Obviously fixing the parameters in the certificate implies they can't be changed at run-time.

Please note: Static-Ephemeral DH is very rarely used these days (especially with TLS).

Please note: this answer uses the TLS terminology for DH and DHE, in many other applications static DH isn't a thing and DHE is always used and just labeled as "DH".


Is RSA key size the size of private key exponent?

No, the RSA key size is not the size of the private key exponent. It is customarily the number of bits in the public modulus (which is known as $N$). In other words, the key size is the integer $k$ such that $2^{k-1}\le N<2^k$.

In most implementations (and all implementations conforming to PKCS#1), a private exponent $d$ has size in bits at most the key size $k$, and typically is few bits smaller. Notice that the private exponent is not uniquely defined.

The smallest private exponent is $d=e^{-1}\bmod\lambda(N)$. It is always less than $\lambda(N)$, where $\lambda()$ is Carmichael's function, with $\lambda(N)=\operatorname{lcm}(p-1,q-1)$ when $N=p\cdot q$ with $p$ and $q$ distinct primes. The smallest private exponent always has size in bits strictly less than the key size $k$, and typically is a few bits smaller.

Sometime, a private exponent is computed as $d=e^{-1}\bmod\varphi(N)$, where $\varphi()$ is Euler's function, with $\varphi(N)=(p-1)\cdot(q-1)$ when $N=p\cdot q$ with $p$ and $q$ distinct primes. That particular $d$ has size in bits at most the key size $k$, often is a few bits smaller, and often is a few bits larger than the smallest private exponent.

Yet other methods to define a private exponent give no maximum for $d$, and only require that $d\equiv e^{-1}\pmod{\lambda(N)}$ (which is the necessary and sufficient condition for $d$ to work), or $d\equiv e^{-1}\pmod{\varphi(N)}$.


I  also know that the curve order is $q$, with $q<p$. That means there exist $q$ valid points on the curve,

True

  which is less than all the values that $x$ could have in $\mathbb{Z}_p$

Actually, that's less relevant than you think.

For every $x$ value in $\mathbb{Z}_p$ that has a valid solution, there are two values of $y$ that satisfy the equation (and hence correspond to two points).  It's easy to see, if $(x, y)$ is a solution, then so is $(x, -y)$ (aka $(x, p-y)$)

Note: some elliptic curve have 1 or 3 $x$ values that correspond to a single $y$ value (which is the $y$ value 0) - secp256k1 is not one of those curves.

In addition, there is a single 'point of infinity' which doesn't correspond to a solution to the equation, but is thrown in as an additional group element.

Hence, there are exactly $(q-1)/2$ $x$ values that correspond to (at least one) valid point.  Since $p \approx. q$, this if you pick an $x$ value at random, you have almost exactly a 50% probability of picking one with a solution.


Is it Ok to reverse the usage of public key and private key

No, this doesn't generally work:

encryption / decryption could use another padding scheme if it switches depending on what kind of key is used;
if the private key is leaked / made public then the public key can usually be guessed or calculated - this works at least for RSA and IES encryption using DH keys;
the crypto library may not be able to switch around the public key and private key, for instance for RSA may require the CRT parameters and ECC keys are different altogether.

A wild guess: in 60% it would not be feasible, 35 percent it would be completely insecure, 4 percent just less secure and in 1 percent of the time hey, you could be lucky and have something that approaches secure, all depending on the protocol, algorithm and implementation.


Can I derive an IV as a segment counter for AES256-GCM?

To conserve space for saving an IV for AES-GCM encryption/decryption, I was thinking to use each of my segments' sequential number as an IV. Would that pose an issue (in cryptographic sense)?

No, it will not pose an issue because the (twelve byte) IV for GCM encryption is really a nonce; it is not directly used as counter for the underlying CTR encryption.

  I decided to go with a 16-byte TAG (that is used by AES-GCM for authentication.) Is that an overkill for an encrypted 4096 byte segment?

The security of GCM is rather dependent on the size of the authentication tag. If you can spare the few bytes I would strongly recommend keeping it set to 128 bits. You have overhead anyway and 16 / 4096 (1 / 256 if I'm not mistaken) is less than half of a percent of overhead.

And it seems like you will be handling large amounts of data, which increases the attack surface to an attacker. Better safe than sorry.


How difficult is it to find the "pre-image" of a block cipher?

Take $C_2$ and pick any $k_2$. Then decrypt using $k_2$ so that $M_2 = AES_{k_2}^{-1}(C_2)$. Now obviously we have $AES_{k_2}(M_2) = C_2 = C_1$.

This extends to any blockcipher, because blockciphers are specifically designed to be reversible.

In the comments you asked about the scenario where $M_2$ is also fixed. This is as hard as breaking AES. Consider this problem:

Find $k_2$ given $k_1, M_1, M_2$ such that:

$$AES_{k_1}(M_1) = AES_{k_2}(M_2)$$

Giving $k_1$ (and thereby $M_1$) does not add information for the solver to this problem, because there is no relation between $k_1$ and $k_2$ other than that there exists a ciphertext that was created using both keys - which is non-information because all keys can create such ciphertext given the correct plaintext. Thus the problem with irrelevant information removed becomes:

Find $k_2$ given $M_2$ such that:

$$C_2 = AES_{k_2}(M_2)$$

This is obviously the problem of breaking AES itself.


Is the output of AES-CBC + MAC the same size as the input?

AES CBC usually requires padding, such as PKCS#7 padding. This padding is 1 to 16 bytes, 16 being the block size of AES. The HMAC will add 256 / 8 = 32 bytes to the total. Usually you will need to store the randomized IV as well with ciphertext, to allow for reuse of the key, adding another 16 bytes (the block size again). So the total overhead will be about 16 + 16 + 32 = 64 bytes.

You can shave some bytes off of this by using a smaller tag, but don't go below 8 bytes, the more bytes the more security the tag will provide. You can also use a different scheme and calculate the IV instead of sending all of the IV bytes, as long as the IV is unpredictable to an attacker. You may also be able to deploy ciphertext stealing (CTS) to avoid the padding overhead, but not many libraries contain ciphertext stealing in their implementations of AES-CBC.

With an authentication tag provided by the HMAC you will increase the size, and this will of course enhance your security; it adds integrity and authenticity and may even protect confidentiality if (padding) oracle attacks are feasible.

Don't forget to include the IV information in the authentication tag, and perform the HMAC over the ciphertext instead of the plaintext.


I see three options for you, each with strengths and weaknesses.

Use a PKI with some sort of trusted signing authority and validate that the certificate is signed by a trusted signing authority and that it has some identifier in it that should be present for your app to trust. For example, the certificate could have a Subject field embedded within it that has a value of my-really-cool-app.com. If presented with a certificate signed by the trusted authority with the correct Subject field, you trust the certificate and continue with the connection. This would happen every time you connect.
Use trust on first use. This means, the first time you connect, you accept whatever certificate you are given. On subsequent connections, you only accept connections that present the same certificate. If a new cert is given, you error out or something. This is similar to how SSH is used most often. In SSH the user is presented with the server's public key certificate fingerprint, but my guess is no one checks that and just trusts it the first time. If it ever changes SSH complains.
You ship your app with the desired public key certificate (or fingerprint) within it. On making a connection, if the certificate has changed, don't continue the connection. This is pinning.


Mathematically does there exists efficient algorithm $\mathcal{A}$

Yes; the Extended Euclidean algorithm can be used to efficiently compute multiplicative inverses modulo $N$, without knowledge of the factorization of $N$.


For the sake of this answer I shall suppose that the domain of "somesite.com" is used as the salt to some password-based key derivation function.

Now this has the usual problems of deterministic password managers: As soon as one site is breached, you need a different password for that site meaning either the site needs to change their URL (unlikely) or you need to remember an additional piece of information to derive the password for this particular site or you need to change your master password which will also force you to change passwords on all other sites you use, including those you no longer remember you actively use but still do from time to time where you're locked out with the new master password.

If you want more information why deterministic password management might not be a smart idea, have a look at this blog post.


GCM mode GHASH sensitivity to timing attacks

If the timing varies with public information, then it's not a problem.  If the timing varies with secret information like the key in GCM, it is a problem.  (While GCM feeds only AAD and ciphertext to GHASH, other AEAD schemes like GCM-SIV feed the plaintext to GHASH/POLYVAL; timing dependent on any secret information is a problem.)

It's hard to make a fast software implementation of GCM that does not vary with the key, since you're evaluating a polynomial in $\operatorname{GF}(2^{128})$ at the GHASH key.  (t is tempting to make a much faster software implementation that does vary with the key by using variable-time table lookups.)  Worse, each block of the message (AAD or ciphertext) figures into the GHASH formula exactly once, but the key, and its square, and its cube, etc., figures in many times.

And CPU instruction sets and programming languages are historically designed to support integer arithmetic, not Galois field arithmetic, so even on a CPU that does support Galois field arithmetic natively, reliably taking advantage of it requires nontrivial engineering effort.


Decode RSA given e,p and q_inv ( with respect to p)

In RSA $p$ and $q$ are chosen such that they are both prime numbers. I suspect that by $q_{inv}$ you mean the CRT coefficient, which is actually defined as $q_{inv} = q^{-1} \bmod{p}$. Thus, to find $q$ we need to calculate $q_{inv}^{-1} \bmod{p}$, and since $p$ is prime we can use Euler's Theorem to compute it as $q = q_{inv}^{p-2} \bmod{p}$. Note that this only works under the assumption that $p > q$, which is a standard assumption for RSA CRT. Knowing $p$ and $q$, we can now compute $N = p*q$.


Can MGF1 within OAEP and PSS be replaced by a XOF?

It seems that the authors of Keccak sponge (the algorithm chosen to be SHA-3) do think their SHAKE functions can directly be used for simplifying OAEP and PSS:

  The introduction of extendable-output functions (or XOFs, pronounced zoff) is a particularly nice feature of the standard. A XOF like SHAKE128 or SHAKE256 can be seen as a generalization of hash functions where the output length is not fixed but is potentially infinite. Concretely, XOFs can be used instead of complex constructions involving hash functions and counters such as MGF1. With RSA, this is of immediate benefit to full domain hashing (edit: also known as FDH), to RSA OAEP (Optimal Asymmetric Encryption Padding) and to RSA PSS (Probabilistic Signature Scheme). Other use cases are key derivation functions and stream ciphers.


What is wrong if you use a key in a Caesar cipher that is greater than 26?

Basically the Caesar and Vigenére ciphers perform operations on groups. In this case the group consists of the values $\{0, 1, 2 ... 25\}$ in that particular order and the modular addition $+$. Now within a group it doesn't make sense to add a number outside of the group domain - in this case 0 to 25 - to the value.

So as we are using modular addition we can see that $12 + 30 \equiv 12 + 4 \mod 26$ as $42 \bmod 26 = 16$ and $16 \bmod 26 = 16$.

We can use this fact to call the values $0$ to $25$ representants because they actually just represent an infinite amount of integers: all integers which are the representant plus some multiple of $26$. So with this in mind $30$ and $4$ have the same representant $4$ (in theory you could use special notation to make the difference between numbers and representants for infinite amounts of numbers more clear but we will not do so for the sake of alignment with established standards).

So adding 30 only makes sense if we extend the group to at least 31 values. Within these ciphers that basically means extending the alphabet: the letters that get encrypted (or duplicating characters, to make it more difficult to analyze the resulting ciphertext).

You could accept $30$ as key, but it would not really extend the key space because $30$ would be fully equivalent (that's the $\equiv$ symbol) to the key value $4$. So the final key strength would still consist of 26 possible keys (about 4-something bits) as well.


Does there exist a two-pass AKE protocol that is secure in eCK model and also has PFS?

It is possible to achieve PFS against active adversaries in two messages.
The "as we know" that you mention is incorrect; this misconception seems to stem from over-interpreting Krawczyk's result in his HMQV paper from 2005. At best, the argument seems to hold from protocols that exchange messages of the form g^x, g^y, where x and y are random values: for those protocols it seems you cannot achieve PFS against active adversaries by Krawczyk's example attack. However, his argument does not work against two-message protocols in general (e.g., that exchange messages of a different form).

This misconception is explained in detail in, e.g., the introduction of this paper by Cremers and Feltz, which also includes a full security model and detailed proof of a (construction of a) two-message protocol that achieves a form of security that implies eCK-security and PFS against active adversaries.

There is an earlier protocol (by Gennaro, Krawczyk and Rabin) that achieves PFS against active adversaries in two messages and is also implicitly authenticated, but that does not achieve e-CK security: it is the PKI-based variant described at the end of this paper.

The first description of an eCK-secure variant is found here.

So yes, it is possible to achieve this.


Is there a problem in a PK cryptosystem if the plaintexts are very small compared to the ciphertexts?

No.     Also, note that by hybrid encryption, ciphertext overhead will always be

at most   + poly(security_parameter) ,   no matter how long the message is.

For IND-CPA of any

public-key encryption scheme, or even

symmetric encryption scheme with stateless encryption

, ciphertexts for non-empty messages must be

overwhelmingly likely to be longer than plaintexts.

Your most recent comment suggests it was broken even in the following context, but otherwise you might have had a secure trapdoor permutation family whose domains are exactly the binary strings whose length equals the length chosen during key generation.


Converting NewHope/LWE key exchange to a Diffe-Hellman-like algorithm

It has been folklore (since at least 2010) that you can do what you propose, but less efficiently than the "key transport" method of any Ring-LWE based encryption scheme or KEM.

So here is what you can do: there is a public polynomial $a\in Z_q[X]/(X^n+1)$ that is shared by everyone.  It needs to be uniformly random, so it can be set to XOF(1), where XOF is something like SHAKE.  This way, it's "random" and we're pretty sure there are no planted trap-doors in $a$.

Then person $i$ selects two polynomials $s_i,e_i\in Z_q[X]/(X^n+1)$ with small coefficients and publishes his key $b_i=as_i+e_i$.  Now if party $i$ and $j$ want to share a key, party $i$ computes $s_ib_j = as_is_j+s_ie_j$ and party $j$ computes $s_jb_i= as_is_j+s_je_i$.  Since $s_ie_j$ and $s_je_i$ are products of polynomials with small coefficients, the coefficients of the products themselves are bounded (say by $\beta$).

So what we would really like is that the coefficients of $s_ie_j$ do not affect the higher order bits of $as_is_j$.   This could happen if $q$ is much larger than $\beta$.  Basically, if $q=2^k \beta$, then the probability of the higher order bit not being affected is around $1-2^{-k}$.  So by setting $q$ large enough, the way to retrieve a shared key would be to compute HighOrderBits$(s_ib_j)$.

So why isn't this done?  Because you would need to set $q$ quite large and the underlying hard lattice problem becomes easier the larger the gap between $q$ and the coefficients of $s_i,e_i$ are.  So you would have to increase the dimension of your ring to compensate.  It is possible to set such parameters, but I would estimate that achieving similar security as regular Ring-LWE encryption / key exchange schemes would result in keys that are around 20 - 40 times larger than in Ring-LWE based schemes.  So something around 20KB - 40KB could be expected.


Is there a library-less implementation of DSA available to read?

Not great answers but something:

If you just want the mathematical computations, indepedent of implementation, Wikipedia has a good explanation, and the standard is definitive.

Java JCE source is open. The repository is git (which I don't have set up); Oracle(Sun) JDK distribution has src.zip but exclude the JCE part; JRE distribution has no source at all. openjdk-src package for CentOS/RedHat does include JCE, and I'd assume/expect at least some other Unixes but maybe not Windows the same. The JCE facade/provider/engine framework somewhat complicates the code for all providers, including DSA.

Java BouncyCastle (http://www.bouncycastle.org) source is open. Their build recipe is too complicated for me, but can be avoided by downloading the jar(s) and the source and telling your debugger to link them; I use Eclipse and just set the source property for the library. BC includes both a provider implementation, with the same complication as the Oracle one, but also a "lightweight" API, where you just call an implementation directly; org.bouncycastle.crypto.signers.DSASigner is the one you want here. That's what I'd use if I wanted to debug something in Java.

OpenSSL C (http://www.openssl.org) source is open. Beyond a standard C toolchain (compiler, preprocessor if separate, assembler if separate, linker, lib/archive, etc, and debugger) build requires only perl (builtin to nearly all Unix, and easily available for Windows); a separate assembler can be needed for an optimized build, but for pedagogical you don't need optimized. Although linked enough you need to build the whole thing, for execution the code is quite well modularized and you can easily write a small program that just calls the DSA_* and BN_* (bignum) modules to do a few DSA operations. However, C code must explicitly deal with error handling and memory management that is (mostly) implicit in Java, and OpenSSL C code for older modules is not exactly the clearest possible. OpenSSL also makes it easy to add file handling when and only when you want.

Note that the numbers involved in DSA, even using the long-obsolete 512-bit minimum of original FIPS186, will be much too large to deal with or check or recognize manually, so you can step through code and see that it does something that works, but won't actually learn any more about what it does than the formulas in the spec told you to start with.


What are unified addition and differential addition in elliptic curve point arithmetic?

Unified addition means that the formula you use for adding two points doesn't depend on whether they are equal. Simplifying point addition in the Weierstrass form somewhat $s=(y_A-y_b)/(x_A-x_b)$ when $A\neq B$ - this is "Adding". Otherwise $s=(3x_A^2-p)/{2y_A}$ when doubling a point.

The implementation of these steps would normally involve different code paths and this can lead to problems as information about the private key is leaked if you can monitor the power consumption or timing to work out which path was taken even if you can't see the numbers involved. See section one of Barbosa & Page. Also, Bernstein ,on page 3 talks about a stronger but related property called "completeness".

Page 15 of the same Bernstein paper explains "differential additions". Another Bernstein quote is

  Differential addition chains (also known as strong addition chains, Lucas chains, and Chebyshev chains) are addition chains in which every sum is already accompanied by a difference.

They are used to support fast addition on elliptic curves in the Edwards form.


Ensuring integrity and confidentiality together with symmetric encryption

Do not invent your own authenticated encryption mode. Use a standardized one, and use a well-supported library to implement it in your code.

AES-GCM, AES-CCM, AES-OCB, and AES-CBC with HMAC-SHA256 over the ciphertext are all common options.

Some great direction from Matt Green here: How to choose an Authenticated Encryption mode


Cryptographic agility is the capacity for an IT system to easily evolve and adopt alternatives to the cryptographic primitives it was originally designed to use.

An example (and building block) for cryptographic agility is the X.509 certificate format, which is defined with various signature algorithms, hash algorithms, and key sizes, in a manner allowing in principle future growth.

Another is crypto provider APIs, such as Java's com.sun.crypto.provider.

A huge drawback of cryptographic agile systems is their complexity, leading to implementation and usage errors, incompatibilities and hasty workarounds for these, all conspiring to create security issues; examples abound. Also, the supposed agility often fails as soon as it is needed.

As an example of the later that recently hit me, consider code using Java's com.sun.crypto.provider made some time ago, invoking a cipher with

  Cipher cipher = Cipher.getInstance("RSA/ECB/OAEPWithSHA-1AndMGF1Padding");

and having made the string parameterizable. Now, because SHA-1 collision resistance is broken, some authority says that it must be replaced with SHA-256 everywhere including in that application (notwithstanding the fact that SHA-1 remains perfectly safe in that application, as far as we know). So, we change the parameterizable string to "RSA/ECB/OAEPWithSHA-256AndMGF1Padding" and are flying, right? Er, no. It turns out that MGF1 stands for a mask generating function that uses a hash, which remains SHA-1 by default, and there is no such thing as "RSA/ECB/OAEPWithSHA-256AndMGF1WithSHA-256Padding", or hope that it will be added soon to com.sun.crypto.provider (see this answer for details); so you have to change the code anyway, plus add a lot of new messy non-standard things all around to have the hash parameterizable as a single string, as the IT system requires.

And there are other more subtle issues, including this (potential) security one: by using SHA-256, all things being equal, we reduce the message capacity for a single RSA block, and it is likely hard to rule out that com.sun.crypto.provider, or some other, will happily and transparently add a second block oblivious to us; thus we might end up with two RSA blocks, and that could well create a vulnerability that did not previously exist.

Proponents of cryptographic agility could understandably object to this line of thought that if com.sun.crypto.provider was more crypto-agile, the argument would fall apart.


Byzantine agreement implies Broadcast channel [Consesus]

Note that if the dealer in broadcast is corrupted, then we don't need to guarantee anything except that all honest parties agree on the output. In contrast, if the dealer is honest, then all honest parties must output the dealer's input. Now, think about what happens if the dealer is instructed to send its input first to all parties over the point-to-point channel. What can the parties do after receiving this message (note that a corrupted dealer can send different values to different parties)? How can they ensure the properties... Of course, you should use agreement. I think that this is more than enough of a hint.


How much information do I leak if I upload multiple ciphertexts with cleartext overlaps?

The question has opposite answers, depending on if we consider adversaries computationally bounded, or not.

Actual adversaries are computationally bounded, that is have limited computational resources. Against these, any cipher that is secure against Chosen Plaintext Attack has the property that similarities between plaintexts are undetectable and unexploitable¹: the adversary gains no useful information (about the key or the plaintexts) from such similarities. With a properly chosen key, and a correct implementation (no side channel leakage, secure Random Number Generator for Initialization Vector, salt, …), that's believed² to be the case for all modern ciphers, including the ciphers in the question:

AES in any of the standard modes of operation except Electronic Code Book.
RSA encryption per one of the PKCS#1 mode (RSAES-OAEP and the legacy RSAES-PKCS1-v1_5), or using an otherwise secure hybrid encryption. Textbook RSA $c_i\gets {t_i}^e\bmod n$ is not CPA-secure.
The scrypt tool, which really uses AES in counter mode³. For this tool, "properly chosen key" means that the entropy in the password, combined with the workfactor parameters used, must make brute force password search far exceed the computational capabilities of adversaries.

Against computationally unbounded adversaries (theoretical all-powerful things), practical cryptographic schemes including those in the question become insecure no later than when what's known about plaintext exceeds the key entropy. In that case, learning that $k$ original plaintexts are mostly identical in a certain location reveals $k-1$ times the length of the common plaintext, and when that exceeds the key size it becomes theoretically possible to find the key, by enumeration of all keys, decrypting the ciphertexts, and keeping the (probably, single) key that makes all the tentatively decrypted plaintexts match in the stated location.
The situation is even worse for RSA and public-key encryption in general: knowledge of the public key, which is assumed, allows a computationally unbounded adversary to decipher any ciphertext.

¹ Including with any amount of known plaintext.
² Moderns ciphers are believed (without mathematical proof) to be resistant against mathematical attacks; that is, when the key is random and unknown, it is believed there is no attacks much more computationally efficient than trying all keys (brute force), absent side channels. AES is among such modern ciphers, despite two decades of intense analysis.
³ According to this description of the format, the bulk of the ciphertext is data xor AES256-CTR key stream generated with nonce == 0. The later means that a multi-targets attack applies (assuming redundancy in plaintext, it is possible to test if a 256-bit AES key matches any of the ones used in multiple ciphertexts using a single block encryption), but that's unlikely to be a practical weakness.


How to prove that work is done without actually knowing the payload

The answers to these questions depend heavily on the threat model.  Starting from the most pathological, and working our way back:

If the software has to be run on the remote machine, and $A$ cannot know anything about the data, and $B$ is willing to take full advantage of physical access to the remote machine, there's really nothing you can do.  Physical access is really hard to beat.
If $A$ can know a little of what $B$ needs, $A$ might be able to provide the algorithm encrypted in pieces, such that $B$ only gets enough of the algorithm to solve that one problem, but has to go back to $A$ to solve the next.  However, this requires knowing a little about $B$'s data and is very algorithm specific.
If the algorithm doesn't have to be run remotely, there's the relatively new field of homomorphic encryption.  This would let $A$ run the algorithm locally on an encrypted copy of $B$'s data without konwing anything about it.  However, this field is in its infancy, and practical examples are hard to find.
If we can reasonably trust $B$ to not reverse engineer the code, new options form.  At some point this trust becomes a legal question, which can get complicated.

In the last case, there is actually a solvable answer.  $B$ runs the program, which takes the inputs and outputs an encrypted form of the outputs (typically with asymmetric encryption).  This key is derived from the hash of all of the inputs.  This hash is then provided to $A$, who looks at that hash, and provides the correct decryption key.

It can also be done in the reverse order: $B$ hashes the inputs, $A$ looks at the hash, and signs them.  $B$ takes that signature and the inputs, and passes it into the algorithm, which confirms that the inputs are signed.


What can eve see when I go to https//paypal.com

Eve can see the size of the HTTPS request and response, as well as the domain and subdomain you connect to (via rDNS lookup or via SNI sniffing). TLS only protects the precise content of the data being transmitted, not where it is going. In particular, it works like this:

https://foo.example.com/some/page.html#some-fragment
| proto |    domain    |     path     |  fragment  |

proto - There are only two protocols in common use, HTTP and HTTPS.
domain - The domain is example.com and *.example.com, detectable with rDNS or SNI.
path - The path is completely encrypted and can only be read by the target server.
fragment - The fragment is visible only to the web browser and is not transmitted.

The attacker can see the protocol and domain, but not the path or the fragment. I wrote a more detailed answer about this on Information Security.


Is RC4 secure with a single-use 32-byte random key prefix and 3072 prefix bytes discarded?

Yes, there are reasons to avoid RC4 and to consider it hopelessly insecure.

The single-byte biases—the biases that were so obvious that Bob Jenkins found them empirically on his 1994-era laptop within days of RC4's publication—may decay as you go down the keystream.  But these are the tip of the iceberg.  Many other detectable multi-byte biases have been identified that continue long into the keystream, notably in Fluhrer–McGrew 2000 and Fluhrer–Mantin–Shamir 2001, and applied in practice on TLS and WPA year after year after year.

The only reason academics chose to spend precious grant money on designing and implementing public attacks on RC4 is that people kept using it in important protocols against the advice of cryptographers for twenty years after it was broken.

That nobody has broken your protocol with RC4 probably just means your protocol isn't as important as TLS and WPA.

Just Say No to RC4, kids!


Either is safe, but I would prefer encryption for two reasons:

As noted in the comments, you can change the key without needing to know the original password.
Encryption doesn't add to collisions, while HMAC can. The probability is tiny, but it adds to the probability that the password hash caused a collision. Not worth worrying about, but since it's avoidable...

On the other hand, HMAC does have one advantage: no IV, so no extra space. (GCM even adds an authentication tag.) If you can use something like a user ID as a counter, even that advantage could be lost. If not, that could be important in some cases.


Which bitlevel operations must a fully homorphic crypto system support?

Any set of functionally complete operations should be sufficient. As SEJPM says in his comment this could be simply the NAND operation as it is complete on its own. Thus a good test to see if the supported set of operations is complete is to check if you can use them to evaluate the NAND operation.

AFAIK many FHE schemes supporting Boolean operations are built to support the AND and XOR operations. These are actually not complete on their own as you also need an operation that outputs the constant 1 (in order to implement the NOT operation together with XOR). This, however, is easily achieved in FHE as you can simply use the public key to encrypt the value 1.


In the Smart Card industry, it is often used a technique called diversification: individual Smart Cards get a serial number $S$, and a device-unique secret key $K_S$ computed from a Master Key $K$, and $S$, using a (typically: non-entropy-stretching) Key Derivation Function. For example, $K_S=\operatorname{AES-ENC}(K,S)$ where the first parameter of $\operatorname{AES-ENC}$ is the key; or perhaps, $K_S=\operatorname{HMAC-SHA-256}(K,S)$. Injection of $K_S$ in Smart Cards, and injection of $K$ in SAMs, is done in secure conditions (production line of a card manufacturer).

A SAM contains $K$, thus is able to internally recompute $K_S$ of any Smart Card that it must interact with, from its (alleged) serial number $S$, which is usually freely readable from the Smart Card. The SAM and the Smart Card (if it is genuine) will thus share the secret key $K_S$, and then there are plethora of protocols to perform mutual authentication and establish a secure link.


I cannot access the linked document, but I think that $G$ is a generator point of the elliptic curve, so you will have points on both sides.


You are essentially asserting that if $k \equiv 1 \pmod N$, then $a^k \equiv a \pmod N$. This is false in general. The correct assertion is the following: $a^k \equiv a^\ell \pmod N$ if $k\equiv \ell \pmod{\phi(N)}$.

In more general group-theoretic terms, if $a$ is an element of order $n$ in a group $G$, then $a^k = a^\ell$ if and only if $k \equiv \ell \pmod n$. Note that in the statement of the previous paragraph, $\phi(N)$ is not necessarily the order of $a$, hence it did not have the "only if" part.

EDITED to add: This is actually an important issue which bears emphasis because it occurs often in cryptographic contexts. When working with powers of an element in a group, it is important to remember that the exponents should be viewed as integers modulo the order of the element. In an abstract group this is not a problem, but when the group is integers modulo some $N$, it is easy to "think modulo $N$" also for the exponents, but it leads to this sort of errors.


Shuffling: Purpose and formal definition

In side channel, shuffling makes correlation attacks harder. For example, if you shuffle the 16 AES S-Boxes in the first round each execution, and you target say first S-Box' output in the attack, at any single point in the trace you will see information related directly to that output only on 1/16th of all traces, and in the other 15/16th traces there will be something else, which qualifies as "noise" for the attack.
Note that this countermeasure is rather weak and is mostly considered complimentary to more sound masking countermeasure. Indeed, after taking 16 times more traces (maybe a bit more), the correlation would become noticeable again. While this adds up to the practical attack complexity, it is impossible to achieve exponential complexity increase, as masking allows.


There are the differences (whether they're con's vs pro's depends somewhat on what you're using it for):

Performance; the NIST key wrap is much slower than anything else on your list (and can't be parallized; some algorithms on your list can be).  On one hand, if you're using it for key wrap, well, we typically don't wrap/unwrap keys so frequently that it really matters.  On the other hand, you probably don't want to try to use it to encrypt packets on your 10Gbps link...
Integrity; if the attacker modifies a key wrapped ciphertext, there is a probability circa $2^{-64}$ that, on unwrap, it would be a valid (and effectively random) key; this probability is considerably higher than an authenticated encryption mode (but better than CBC or CTR without any integrity protection whatsoever).
Determinism; the key wrap algorithm is deterministic (based on the wrapping key and the plaintext); hence, if you wrap the same key twice with the same wrapping key, an attacker can detect that; the other modes you have listed are randomized.  On the plus side, this means that the key wrap mechanism is not subject to 'algorithm substition attacks' (where the attacker doesn't use a truly random randomizer, but instead selects values that leak some information).  In addition, you can make the key wrap randomized by the simple expedient of including some random data along with the key (and which is discarded after the unwrap).
Ciphertext overhead; the key wrap adds 64 bits to the plaintext length (assuming that the key you're wrapping is a multiple of 64 bits in length); this is less overhead than the other algorithms.

You might be wondering about differences in cryptographic strength.  There is effectively no difference; as long as the wrapping key is secure, and everything is done properly, any of these methods listed is essentially immune to cryptanalysis.


Storing Encrypted data in a mobile client

Salt and IV are public data (just like the ciphertext) and don't reveal any data about the plaintext. They are necessary to decrypt. Therefore, they don't defeat the purpose.


How to glean info from a message that simply has the letters shuffled?

What you are describing is called a transposition cipher.

First of all, it would be easy to detect which method you are using since the frequency distribution of your cipher text will be the same as the language of the plain text.

I think the biggest problem with using only transposition as opposed to a combination of both substitution and transposition is that you do not need to manipulate the whole message in order to find the key (i.e the order in which you shuffled it) finding how one word was shuffled reveals how the whole plain text was shuffled.

Another weakness is that even if you do not have the correct key, being close to it already reveals a lot of information.

A way to break this cipher would be to take a small chunk of cipher text and shuffle it around until you find some anagram to a known word, then solve the anagram.

Edit :

After rereading the question, if you were to shuffle your text randomly as you said in your example it is similar to using a one time pad for the exception that the key to the pad would be draw from a different distribution since you probably will not have equal amounts of each letter of the alphabet in your book.

Let $m$ be the book and $c$ be the shuffled book you can derive a key $k$ such that $|k| = |m|$ and $m\oplus k = c$.

$k = m\oplus c$.


The inversive congruential generator is not commonly used in cryptography. Its basic description, in fact, makes it entirely unsuitable for it—once you know a single value of $x$, you can predict the remainder of the sequence, which is something a secure pseudorandom generator should not allow.

To avoid the above trivial attack, you could truncate the output to, say, half of the bits of $x$. But the truncated inversive generator is also predictable by more elaborate means, as long as you truncate fewer than half the bits.

To top it off, inversion modulo $p$ is a very slow operation, which makes this generator very inefficient. So even for non-cryptographic purposes this is not a good generator to use.


If one source remains uncompromised plus statistically random on all bits, and both sources remain independent, then a xor of both sources together can also be  considered uncompromised plus statistically random for all bits.

Basic proof:

Label the the results two RNGs $X$ and $Y$, consider bits $X_n$, $Y_n$ and $Z_n = X_n \oplus Y_n$

Assume each value of $X$ remains uncompromised, such that $p(X_n=1) = 0.5$, and that each value of $Y$ is compromised so that $p(Y_n=1) = w$, the following holds assuming $X$ and $Y$ are independent:

$p(Z_n=1) = p(X_n=1) * p(Y_n=0) + p(X_n=0) * p(Y_n=1)$

$ = 0.5 * (1.0-w) + 0.5 * w$

$ = 0.5$

In other words, each bit of $Z$ retains the same probabilities and qualities of $X$, if $X$ is from a good RNG, then $Y$ can then be anything at all (provided it is independent of X). This holds even if $p(Y_n=1)$ is not independent of $p(Y_m=1)$, because whatever distribution you provide for $Y$, it just cancels out as above.

Knowing the exact value of $Y$ is just a special case of the above where $p(Y_n=1)$ is either 0 or 1 for each $n$. It doesn't grant any knowledge about $Z$, because each bit of $Z$ remains independent from each other bit of $Z$ and an attacker still only knows $p(Z_n=1) = 0.5$

Using a secure hash-based mixing method might allow you to relax the requirement for independence between the RNGs.

Entropy mixing with secure hashes can also be used to flatten distributions from sources which are not flat e.g. event timing data. You generally don't have that problem when the sources you are considering are well-written RNGs in the first place.


Can compressed data be made to look like random data?

TL;DR: yes it can look more random than the plaintext message itself, but it won't help you against crypt-analysis and in the worst case it may introduce vulnerabilities.

I guess the most boring but most effective way is simply to look for meta data within the compressed message. E.g. the precise compression mechanism and compression level may well be within the decrypted message.

Generally you assume that the protocol is known (Kerckhoff's principle). Note that finding out the compression used is usually not hard, and you only have to do so for a single message.

Once you know the compression method checking the correctness of decryption is as easy if not easier; you can always first decompress before checking the correctness of the decrypted message.

Decompressing a message may well be faster than decrypting it. Performing the compression is usually slower as it needs to look for patterns. Compression will only add a single additional step to the crypt-analyst; it's not something you do to make your protocol more secure against brute force attacks. Basically you could compare it to adding a single bit to the security level at most.

An attacker may always use compression on a (set of possible) known plaintext and compare against that, resulting in a meet-in-the middle attack.

Compression in cryptography is a very dangerous thing. Some plaintext compress better than others and smaller plaintext generally lead to smaller ciphertext. So even if the plaintext is the same size, compression may confer details about the plaintext to an attacker. Take for instance a look at the CRIME attack against TLS for an example of this.

Compressed or inflated data usually does not look like random data, and it is a very dangerous to see it as a security feature. It is much more likely to add insecurity than security when trying to encrypt messages.

Important note: this answer is only valid for modern ciphers where frequency analysis of the ciphertext is not an attack vector.


How do client and server agree on the values of p and g during DHE exchange?

Are their values fixed for each DHE group ?

Yes, by convention a named group includes at least $(g,\mathbb G,q)$ with $\mathbb G$ being a description of the group parameters (i.e. $(p,a,b)$ for prime elliptic curves or $p$ for FFDH), $g$ being the generator and $q$ being the generator's order.

How do the communicating parties using Finite Field DHE agree on the values of the g and p variables ?

The flow in TLS 1.3 currently is:

Client sends (in supported_groups) a list of 'names' (really code numbers) of the groups it is able and willing to use, which may be any combination of FFDHE and ECDHE, and optionally (in key_share) newly-generated public keys for some or all of these groups; it may send empty key_share if it wants to see the server's choice first, or if it is (also) offering and would prefer PSK-based session resumption.
If xxDHE is selected (i.e. except when the client proposes and the server agrees PSK-only resumption) the server checks in key_share for a group it also is able and willing to use, and if found sends a generated public key in that group. If not, but the server finds an acceptable group in the client's supported_groups, it sends HelloRetryRequest specifying that group (but not yet any public key). If neither,  the server aborts the handshake.
If requested, the client sends a new ClientHello with a public key for the group specified by the server (but other changes strictly limited as per 4.1.2) and the server responds with its public key in that group (no change permitted).

In TLS 1.2 and below the flow depends on whether both systems implement RFC 7919, which was published many years after most TLS 1.2 implementations were written, much less lower versions:

With RFC 7919, the client indicates in supported_groups, which originally was called elliptic_curves, the named groups it supports, either FF or ECC. There is no indication of support for other (arbitrary) FF groups, because that was the default long before this extension was created. For ECC groups/curves, previously (in RFC 4492) there were code values to indicate arbitrary/unnamed curves over Fp or F2^m in the Weierstrass form defined by X9.62 and 63, but this was rarely if ever implemented or used and RFC 8422 deletes this option.
The server for FFDHE always sends the p,g values, plus its public key (and a signature), in ServerKeyExchange in a format defined long before even RFC 4492, whether those values correspond to a named group or another, arbitrary group. An arbitrary group could be generated by the server or its admin, or imported from almost any source. For example, the Logjam researchers found a large number of public servers using one FFDHE group that was coded into some versions of Apache httpd.
The client either accepts the server's choice of group and generates and sends their public key in that group, or aborts the handshake. For example, especially in recent years, some client implementations abort if the server sends a group with p too small to provide the desired security level. (Java makes this a runtime-configurable option: jdk.tls.disabledAlgorithms contains "DH keySize < $number".) But even an FF group that is large enough numerically may be weak for less-obvious reasons; there are existing Qs about that.


These scheme doesn't really make sense in its current form:

The key depends on the message. That means, it can not be chosen before the message is chosen. And it is't independent of other parts.
How does the recipient receive that key? Or does he learn that from a separate communication channel, after the message (and thus the key) has been chosen? In that case: Why was not the message transmitted instead of the key?

A usual statement is "the key is drawn at random" - and implicitly you can add there " statistically independent from anything else". The reason for this is simple: If a value is calculated based on some other value, then it can be quite difficult to prove that this calculated value does not reveal anything about the original one. Therefore, we just chose a new random value without any dependencies on anything else.

Then, the security of cryptsystems is mostly analyzed with the assumption of a random key. Based on that assumption, statements about security can only be applied if the assumption holds. Having a message-dependent key is far from being random, especially with a deterministic function like a common hash function: If you assume that there are only a very limited amount of possible messages, then there are only a limited amount of possible keys. This makes the assumption invalid. So even if the scheme was known to be secure for random keys, this might not be secure at all.

  How would this compare with using an encryption key unrelated to T ? Since H(T) shouldn't be reversible how much more does an unrelated key add to the security ?

Well, no security statement can't be made about your scheme in general. You did not describe what kind of messages you have, how easy they are to guess or just in general, how much entropy you actually got. At worst, this could be completely insecure (example: there are only messages "yes" and "no", everyone can just go through the "encryption" and detect which ciphertext matches which plaintext). At best, you are lucky that the attacker didn't guess your plaintext.

So what is the advantage from a random key? It is huge, because you actually get something where security has been analyzed by lots of people over many years. In cryptography, it is really easy to get things wrong and not even notice it. Also, there is usually no leeway in the definitions unless explicltly stated. If something requires a uniform random key, then both parts are necessary - if you use a key which isn't random (including independence of other things) or isn't chosen uniformly, none of the previous security analysis might apply any more.


Are oracles needed in security proofs to prove that one problem is equivalent to the other?

As Squeamish Ossifrage pointed out in the comments, if you define "B is at least as hard as A" by "there is an algorithm that solves A given an oracle that solves B", which is a relatively standard way of defining "as hard as", then the oracles show up naturally in the reduction.

Yet, it should be pointed out that this is not always the definition. What Squeamish Ossifrage discussed corresponds to black-box reductions between primitives A and B. Put otherwise, saying "A and B are black-box equivalent" is exactly the same as saying that one can solve A with an oracle for solving B, and the other way around. Intuitively, a black-box reduction is a reduction that looks only at the input/output behavior of the primitive/attack, and does not use any specific details of its concrete implementation. In this case, it makes perfect sense to represent it by an oracle, since we do not care about how it's concretely implemented.

There are, however, many non-black-box reductions in cryptography. Black-box reductions are still by far the most common; they are much easier to find (non black-box techniques are often very advanced), often more efficient, and allow for proving separations (for example, we know that one-way functions and public-key encryption are provably not black-box equivalent: we can demonstrate that there is no black-box construction of PKE from OWF). A non-black-box reduction would not involve any oracle. It would be of the following form:

If there exists an algorithm $\mathsf{Alg}_A$ that breaks the primitive $A$, then there exists an algorithm $\mathsf{Alg}_B$ which, given the code of $\mathsf{Alg}_A$ as input, can break the primitive $B$.

(or, equivalently, you can also talk about a provably secure construction of a primitive using the code of a secure construction of another primitive)

Example of non-black-box reductions in cryptography include the construction of PKE from iO and OWF; the construction of maliciously secure computation from semi-honest secure computation and zero-knowledge proofs; a bunch of specific zero-knowledge proofs by Barak; the construction of IBE from CDH; the construction of iO from functional encryption; the construction of IND-CCA-secure encryption via IND-CPA secure encryption and NIZKs (the Naor-Yung paradigm); and many others. Some of these actually achieve constructions which are provably impossible to obtain via black-box reduction (see e.g. the paper of Barak).


What cryptographic paradigm is appropriate for this use case?

At least you understand that by embedding a key in the software that someone will be able to reverse engineer the binary, extract the key, and decrypt the file. Or they will find the decryption code, put a break-point after it, and dump the decrypted memory.

Since that does not concern you at the moment, you have a few options.

Generate a random AES key, encrypt the file with that key, embed that key into the source code, decrypt the file in your code and store the decrypted information in memory.
Generate a single private key and an AES key. Encrypt the AES key with the public key. In your code you can decrypt the AES key with the private key then decrypt the file with the AES key.

Of those two, 1 seems simpler. Of course in either case, you run the risk of a single user finding the decryption key and writing a simple script that will work on all of your customer's machines.

To "fix" that issue, you could generate a new key (be it AES or private+AES) for each binary you ship. There are still ways to develop a script that would read the binary, extract the machine specific key, and do the decrypt. It will be harder though, but doing this also means you need to track more keys.

Since it sounds like you are not worried about sophisticated attacks, only want to raise the bar slightly to prevent casual users from getting your configuration files, I'd go with #1. Just make sure you understand all the risks.


Do all PAKE assume that all parties already have a password?

Do PAKE assumes that involved parties already have a shared message?

Some do, some don't.  In general, there are two flavors of PAKEs; balanced (where both sides do know the password), and augmented (where only one side knows the password; the other side knows enough to recognize it).

J-PAKE is a balanced PAKE.

  in J-PAKE, they used an extension of Diffie-Hellman Key agreement to establish the shared message. However, I don't understand how they prevent Man-in-the-Middle attacks.

Going through it thoroughly would require going through a set of cases; however here's a nutshell: each side expects to receive (in successive messages) proof of knowledge of $x_2$ and $x_2 \cdot S$ (or $x_4$ and $x_4 \cdot S$); the MITM cannot fake both of those (without knowing $S$), and so those have to be forwarded untampered.  The adversary is them limited with tampering with $x_1$ and $x_3$; we can show that that doesn't give him an advantage either.

  In general, how does PAKE prevent Man-in-the-Middle attacks?

Well, with all PAKEs, if the attacker has a correct guess to the password, they can do MITM attacks or impersonation attacks (and because the password really is the only way the protocol has to perform authentication, we can't do better).  What a PAKE does try to do is make sure that the attacker is forced to test only one password per attempt (either MITM or impersonation); if he wants to test ten passwords, he needs to interact with a legitimate party ten times (for example, MITM ten separate exchanges).

How they to that varies, of course.  J-PAKE relies heavily on its proofs of knowledge; EKE encrypts the Diffie-Hellman keyshares (so that a MITM would need to guess a specific password for an attempt to work); CPACE uses a password-dependent DH base value (again, so you need to guess a specific password for an attempt to work); OPAQUE has the client and server do a multiparty computation on secrets that the client and the server has for the client to rederive the key needed to recover the private signature values (and the multiparty computation messages look completely random to a MITM).

It's fine that you're studying J-PAKE; just realize that other PAKEs work rather differently...


Very easy, you just use the Extended Euclidean Algorithm to compute $a^{-1} \pmod p$. Then you have $b \equiv ca^{-1} \pmod p$.

Note that, because the EEA has polynomial complexity, this remains easy even if $p$ is very large (e.g., tens of thousands of bits).


Bellovin 96' attack on IPsec ESP protocol on encryption only option

Actually, the attack is on CBC mode (which IPSec uses).  In the attack, it modifies the encrypted packets, and uses the IPSec decryptor as a decryption Oracle.

How it works is based on how CBC-mode decryption works:

Note that any particular plaintext block depends only on the corresponding ciphertext block, and the one immediately before it (and the key); as long as those two ciphertext blocks are correct, the corresponding plaintext block will result.

What the attacker does is take the encrypted packet, and replace its payload contents with the message he wants to decrypt (aligned about the cipherblock boundaries).

He then forwards the modified message to the decryptor, which will proceed to decrypt the message.  Now, consider how this decryption will happen for the parts of the message that he has replaced; if we ignore the very first block he replaced, then both the current ciphertext block and the previous one corresponds to the message he is attacking; hence the resulting plaintext will be the plaintext he is attacker.

That is, the resulting decrypted packet will have the plaintext of the message he is attacking embedded in it.

Then, if the security gateway forwards the message, it'll be forwarding a message containing the information the attacker is interested in.

As for your questions:

  Why does the attacker need to firstly send some arbitrary UDP packet?

He needs to send a message that:

Contains an IP header that will eventually get somewhere where he can look at it.  That's why we assume the attacker can't modify a random IP packet; the attacker can't assume he'll see that modified packet.  Instead, he sends a message that's targeted at a confederate; as long as he's careful not to overwrite the inner IP header, that packet will get to somewhere he (actually, his confederate) can see.
Won't be checked to see if any checksums are correct.  UDP can have checksums disabled; that's why Bellovin suggested it.  Actually, it doesn't have to be UDP; any protocol that doesn't checksum its payload would work.

  How can the attacker break the privacy between A and B?

Suppose the attacker sees a message going between A and B that he wants to read.  What he does is generate a packet that'll go through the tunnel between A and B, and is targetted at his confederate.  Once the packet has been encrypted and is traversing between A and B, he grabs the packet, and replaces the payload contents with the message he wants to decrypt (being careful not to disturb the inner IP header and the trailing ESP padding); he lets the modified packet go to B, which decrypts it, and forwards the decrypted packet to the confederate.  The confederate then looks at the internal payload data and see the decryption of the original packet; he wins.


If two hosts are using a transparent IP level authentication and encryption, is their communication subject to both MITM or replay attacks?

1) Are replay attacks possible?
Yes. For example, if Alice wants to tell Bob "Pay Eve \$100", then P = "Pay Eve $100"
C = RC4(P, KEY)
Packet = IP(C | MD5(C|KEY) )
By capturing and replaying Packet, Eve can make Bob pay her \$100 over and over again.

2) Are Man-In-The-Middle attacks possible?
More specifically, "Is there a possibility to intercept messages and impersonate at-least one of the parties? Is it possible for the attacker to put himself between the sender and receiver by breaking the encryption?"

This question is more complicated. In short, it depends.

If the attacker gets hold of plaintext / ciphertext pairs for the RC4 (either through encryption oracle or decryption oracle), he simply takes P xor C to find the keystream. RC4 key reconstruction attacks can be used to find the MD5 key. The attacker may then act as a full MITM, intercepting and viewing messages and optionally modifying them before passing them on.

I am also uncomfortable with that MAC construction, so I'll get back to you on that one.


Coding of unsigned int to prevent guessing next ID

swap-or-not seems perfect for your use case.


Difficulty of finding collisions for two different CRHF

To expand my comment into an answer. The answer to the question is: No, in general this not true. We will formally show the following:

  If a family of collision resistant hash functions $\mathcal{H}$
   exists, then there exists a family of collision resistant hash
   functions $\mathcal{H}'$ such that for any $h'_i,h'_j \in
 \mathcal{H}'$ it is trivial to find $x_i,x_j$ such that
   $h'_i(x_i)=h'_j(x_j)$.

As mentioned in my comment, what we will do is construct $\mathcal{H}'$ in such a way that $h'_i(i)=0^n$ (where $n$ is the output length of functions in $\mathcal{H}$).
However, we need to be careful in how we do that. A naïve construction of $\mathcal{H}'$ could define for each $h_i \in \mathcal{H}$ a function
$$h_i'(x) := \begin{cases} 0^n & \text{if } x=i\\h_i(x)&\text{otherwise} \end{cases} $$
However, this new family would not necessarily be collision resistant. If for example $\mathcal{H}$ was a family of functions where each function already mapped $0^n$ to $0^n$ we would have introduced a new easily found collision.

So we need to be careful to ensure that any collision in our new function corresponds to a collision in the original function. To do that we define $\mathcal{H}'$ as follows. For each index $i$ we define
$$h'_i(x) := h_i(x)\oplus h_i(i).$$

It is actually easy to see that collision resistance is preserved under this modification.

Let $\mathcal{A}$ be an arbitrary PPT adversary against the collision resistance of $\mathcal{H}'$. We observe that for any $x_1,x_2$ that $\mathcal{A}$ outputs in response to input $i$, it holds that
\begin{align}
&h'_i(x_1) = h'_i(x_2)\\
\iff& h_i(x_1)\oplus h_i(i) = h_i(x_2)\oplus h_i(i)\\
\iff& h_i(x_1) = h_i(x_2)
\end{align}

Therefore it holds that
$$\Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h'_i(x_1) = h'_i(x_2)] = \Pr_i[(x_1,x_2)\gets\mathcal{A}(i):h_i(x_1) = h_i(x_2)]$$
the latter of which is known to be negligible by our premise that $\mathcal{H}$ is collision resistant.

However, it is also easy to see that for any $i,j$ it is trivial to find $x_i,x_j$ such that $h'_i(x_i)=h'_j(x_j)$. An attacker given indices $i,j$ would simply output $i,j$ and since by definition of $\mathcal{H}'$ it holds that

$$h'_i(i) = h_i(i) \oplus h_i(i) = 0^n$$
and
$$h'_j(j) = h_j(j) \oplus h_j(j) = 0^n$$
$\mathcal{A}$ would be succesfull with probability $1$.


the parameters define which curve is used, which has consequences on security and efficiency.

To decide which curve type you need, go to section 8 of the PBC manual and read the paper "pairings for cryptographers"

then PBC provides functions to create your curve (i.e. param files):
https://crypto.stanford.edu/pbc/manual/ch05s01.html

But you can skip this step by directly using one of the curves already provided in the param directory.


Block ciphers are usually used in modes of operation. The security of a mode of operation depends on two things: the security of the underlying block cipher, and the security of the mode itself when you replace the block cipher with an "ideal" permutation.

Say you're using a block cipher with block size $n$ bits, so with AES-256, $n = 128$ (the 256 refers to the key size). A good block cipher should be a pseudorandom permutation, meaning when you give it a uniformly distributed key, it should be difficult to distinguish it from an ideal permutation. An ideal permutation is a uniformly randomly generated permutation over all permutations from $n$ bits to $n$ bits, basically a mathematical object.

Determining whether a given block cipher is secure means cryptanalyzing it to make sure there are no obvious attacks. Such attacks make use of the structure of the block cipher, so for example, this would mean looking at the S-boxes in AES-256 and seeing how they interact with each other, and performing differential, linear, and other types of cryptanalysis. None of these techniques make explicit use of the block size, hence having a smaller block size does not mean you will be able to distinguish a block cipher from an ideal permutation more easily. So when it comes down to block cipher security, the block size does not play an important role.

In contrast, mode security depends strongly on the block size. I mentioned earlier that you also need to look at mode security when the block cipher is replaced with an ideal permutation. Once you do this, you can theoretically analyze the modes and even explicitly compute how its security degrades as you use it. To give an example, GCM has a security degradation of roughly $\sigma^2/2^n$, which represents adversary success probability, with $\sigma$ the number of permutation calls. This means that the more data you process with GCM, the more exposed the mode becomes. The reason this happens is because GCM's security relies on the ideal permutation being "hidden" from the adversary, and as you use GCM you increasingly expose the hidden permutation.

So putting everything together, even if you know that your block cipher on $n$ bits is indistinguishable from an ideal permutation on $n$ bits, your security will still degrade when you use the block cipher in a mode. Hence if you have the option of using a block cipher with small block size, or a block cipher with large block size, then it is better to use the block cipher with larger block size since you'll be able to use it in a mode much longer (assuming all else equal, meaning the cipher is secure for both block sizes).


After some more investigation, the earliest paper I could find that introduces $q$-Strong Bilinear Diffie-Hellman was Reducing Trust in the PKG in Identity Based Cryptosystems by Vipul Goyal in CRYPTO 2007.