How does a chosen ciphertext attack work, with a simple example?

In a chosen-ciphertext attack, the attacker is assumed to have a way to trick someone who knows the secret key into decrypting arbitrary message blocks and tell him the result. The attacker can choose some arbitrary nonsense as an "encrypted message" and ask to see the (usually) different nonsense it decrypts to, and he can do this a number of times.

Having this capability obviously already allows the attacker to read an intercepted message, since he can just ask to have it decrypted. But in this attack his goal is more ambitious than that: he wants to deduce what the secret key is, such that he can encrypt messages himself, and also keep decrypting after his access to having things decrypted for him vanishes.

The attack is successful if if an attacker has a significant chance of being able to deduce the key after having "relatively few" blocks decrypted and without doing so much work himself that he could just as well have brute-forced it.

The term "chosen-ciphertext attack" does not in itself say anything about how the attacker chooses the nonsense blocks he asks to have decrypted, or what kind of computations he does in order to recover the key from the responses.

As a concrete example, suppose General A is sending messages to General B using a Vigenère cipher with an unknown key. The enemy is somehow able to intercept a message and replace it with some completely random letters of his own choosing, say NLLCJOVFXXHMLY. General B decrypts this and gets AKRUWNBXKWNEYX which is nonsense. Bemused, and not thinking this nonsense is worth keeping secret, he picks up a non-secure phone and calls General A: "What the hell do you mean with AKRUWNBXKWNEYX? Did they change the key without telling me?" But the enemy is eavesdropping on the line and now knows that NLLCJOVFXXHMLY decrypts to AKRUWNBXKWNEYX. He can then subtract the two sets of nonsense to get MATHMATHMATHMA, and now he knows the key.

(In this example, getting a single message decrypted was enough for the attacker to learn the key. In general one also considers attacks where the attacker needs to query for multiple messages, perhaps using the response to one somehow to construct the next one).


For discrete elliptic curves, can you find G, if you are given b and B?

$G = [b^{-1} \bmod q]B$ where $q$ is the order of the group generated by $G$, assuming $\gcd(b, q) = 1$.


You have and oracle call of
$$O(\texttt{your-string}) = (\operatorname{AES-128-ECB}(\texttt{your-string} || \texttt{unknown-string})$$
Since you know that the AES has 16-byte block cipher and it uses CBC, request;
$$C = O(\texttt{AAAAAAAAAAAAAAAx})$$ from oracle, where $\texttt{x}$ is the first byte of the random key.
Now ask to oracle  these encryptions $$C = O(\texttt{AAAAAAAAAAAAAAA[a..zA..Z]})$$ and see which character is equal to $\texttt{x}$, sat $1$
Now once we determine the $\texttt{x}$, we can move to the next one. Request from Oracle;
$$C = O(\texttt{AAAAAAAAAAAAAAxy})$$
Now ask to oracle these encryptions $$C = O(\texttt{AAAAAAAAAAAAAAx[a..zA..Z]})$$ and see which character is equal to the second byte $\texttt{y}$ of the string, say $2$
With this method, we can get 16 bytes of the secret. What about if there are more. Request
$$C = O(\texttt{AAAAAAAAAAAAAAA1})$$
then request this will provide the next block's encryption as the input
$$\texttt{234567890abcdef}$$, where you know $\texttt{234567890abcde}$ but not $\texttt{f}$, but you got the encryption of this block. Now ask the oracle
$$C = O(\texttt{234567890abcde[a..zA..Z]})$$
to determine the 17th byte $\texttt{f}$, the rest is similar.


Information leak in ElGamal encryption with message in base group

Let a prime $p = 2qs + 1$.  Consider the subgroup $\mathbb{G} = \langle g \rangle$ of order $q$.  Public key is $h = g^x \bmod p$ while private key is $x \in \mathbb{Z}_q$.  The encryption of $m$ is given by $(c_1, c_2)$ with $c_1 = g^r \bmod p$ and $c_2 = m \cdot h^r \bmod p$ for a random integer $r \gets \mathbb{Z}_q$.  Semantic security mandates that message $m$ belongs to $\mathbb{G}$.

Let $z$ be a generator of $\mathbb{F}_p^*$.  So we can write $m = z^M \bmod p$ for some $M \in \mathbb{Z}_{p-1}$.

Raising $c_2$ to the power of $qs$ yields $${c_2}^{qs} \equiv z^{Mqs \bmod (p-1)} \equiv (z^{qs})^{M\bmod 2} \equiv (-1)^{M\bmod 2} \pmod  p$$
The value of $(M \bmod 2)$ indicates whether or not message $m$ is a square in $\mathbb{F}_p^*$.
Raising $c_2$ to the power of $2q$ yields $${c_2}^{2q} \equiv z^{M2q \bmod (p-1)} \equiv (z^{2q})^{M\bmod s} \pmod  p$$
If $s$ is small or smooth, an attacker can recover the value of $(M \bmod s)$ as the discrete logarithm in $\mathbb{F}_p^*$ of ${c_2}^{2q}$ with respect to base $z^{2q}$.

Let a cryptographic function $H \colon \mathbb{G} \to \mathbb{F}_p^*$  viewed as a random oracle. Semantic security can be met with message space $\mathbb{F}_{p}^*$ by defining the ciphertext as the pair $(c_1, c_2)$ with $c_1 = g^r \bmod p$ and $c_2 = [m \cdot H(h^r \bmod p)] \bmod p$ for a random integer $r \gets \mathbb{Z}_q$.  Decryption of $(c_1, c_2)$ is obtained as $m = [c_2 /H({c_1}^x \bmod p)] \bmod p$.

Another option to get semantic security without random oracles is to take $s = 1$ ($p = 2q+1$ is a safe prime).  The set of valid messages is restricted to $\mathcal{M} = \{1, \dotsc, (p-1)/2\}$.  The encryption of a message $m \in \mathcal{M}$ is given by the pair $(c_1, c_2)$ with $c_1 = g^r \bmod p$ and $c_2 = m^2 \cdot h^r \bmod p$ for a random integer $r \gets \mathbb{Z}_q$.  Decryption of $(c_1, c_2)$ is obtained in two steps as $m^2 = c_2 /{c_1}^x \bmod p$ and then $m$ as the square root (modulo $p$) of $m^2$ in the set $\mathcal{M}$.  Note that if $m \in \mathcal{M}$ then $-m \bmod p = p-m \notin \mathcal{M}$.


Assuming this is "usual" HTTPS using SSL/TLS with RSA key exchange, the client generates a random secret, encrypts it with RSA (using the server's public key) and sends it to the server. The server then decrypts it (using its private key), and both generate from this (now shared) secret (and some public data depending on the messages) several keys which are used for encryption and MAC in both directions.
Then the actual HTTP message is sent encrypted using the exchanged key.

The video is not really clear in how the "hacker" breaks the encryption.

Here are two possibilities how bad random numbers might do this:

The server generated its RSA key pair using bad randomness, and the hacker succeeded to guess these random numbers, and thus arrive at the same key pair. Of course, then a simple packet sniffer can decrypt the message with the RSA-encrypted secret, and from this calculate the session keys.
The client generated its "secret" (which would be sent to the server) using bad randomness. The hacker guessed this secret (verified the guess by RSA-encrypting it using the public key), and then could derive the same session keys as client and server.

Note that using a Diffie-Hellman-based key exchange would prevent at least the first attack, assuming the ephemeral public DH-key has enough entropy to prevent brute-forcing it during the attack.

Using a different RSA public key for each session (or at least rotating every some time) might also help, but requires that there is a master key available to sign it (i.e. have a CA on the server or nearby), and also needs enough entropy to actually help. (And if the master key has not enough entropy, still a MitM can break this.)

I can imagine some other (non-crypto) ways how this video could be created:

The "hacker" might be the owner of the server, and thus knows everything sent to it.
The "hacker" is the owner of the notebook, and thus can see everything sent from it.
The "hacker" configured the notebook to use some proxy, and to trust the certificate of the proxy. The proxy then can log everything.

These don't relate to any random number problem.


Modulus for elliptic curve point multiplication

It's the prime of the prime field.

(Note that, if you're also using the curve for pairings, you'll need arithmetic over both $\mathbb{F}_p$ and $\mathbb{F}_{p^{12}}$. The first can be viewed as arithmetic modulo $p$, but the second is slightly more complex, and can be viewed as arithmetic of polynomials over $\mathbb{F}_p$, modulo a reduction polynomial.)


Trying to understand MixColumns with Hexadecimal matrix

you can done the multiplication operations for the mixcolumn matrices by two methods: either by using the x-time of shifting steps as it you mentioned in your questions or by straightforward multiplication module the (11b) that represent the first irreducible polynomial in the list of polynomial with degree eight for more details see these two manuscripts may be find what you need: (The Euphrates Cipher) and (The New Block cipher Design (Tigris Cipher))

Best regards


Zero Knowledge Proof using hash chains - Is there a flaw in the algorithm?

In fact, it gets even worse if 1+ActualAge is less than AgeToProve, since in that case P would have to find a preimage for the hash in step 3!

But (even without actually following any of your links) I would guess that there's an implicit  assumption that a legitimate P will not even attempt to run the protocol unless ActualAge ≥ AgeToProve, since proving that they're not quite old enough doesn't gain them anything anyway.

Of course, a malicious P could do whatever they want, including accidentally (or deliberately!) revealing the secret.  But in general, we don't really care if a malicious party will do something that only hurts themselves.

OK, let me extend my answer after reading the linked blog post and article.

First of all, note that the blog post and the article actually describe different protocols with different participants and goals.  Specifically, the protocol described in the blog post has three participants:

a prover P who wants to prove to the querier Q that their age $a$ (a non-negative integer number of years) meets or exceeds some minimum limit $q \ge 0$, without revealing how much older than the minimum limit they are;
a querier Q who wants to know whether P is at least $q$ years old; and
a government authority A that knows how old P is, is trusted by both P and Q, and can sign messages in such a way that Q can verify that they come from A, even if relayed by P.

In the protocol describe in the article, however, the authority A does not exist!  Instead, in that protocol, P simply picks an arbitrary (non-negative integer) number $x$ and sends to Q a commitment to that number, such that they can later both:

prove to Q that the number $x$ they picked is greater than or equal to some threshold $q \ge 0$, without revealing how much greater it is; and
optionally, to release the exact value of $x$ and prove that this is indeed the number that they earlier committed to.

The reason this distinction matters is because the protocol outlined in the blog post actually contains some vestigial features (specifically, the way the initial seed for the hash chain is selected) that aren't required for the scenario described in it, and which could be left out to simplify the protocol!  Those features are only needed if we want P to be able to also optionally prove their exact age to Q.

To illustrate how the protocol is supposed to work, let me first start by describing a simpler protocol for the three-party case.  Specifically, instead of all this messing around with hash chains, the authority A could simply issue the prover P with a bunch of separate signed "tickets", each stating that:

  Authority A hereby certifies that P is at least $x$ years old.

where $x$ ranges from zero to P's actual age $a$.  Then, to prove that they're at least $q$ years old, P simply needs to select the ticket with $x = q$ and reveal it.

The problem with this scheme is that it requires A to sign a separate ticker for every year of P's life, and for P to store all of them.  (Honestly, that might not be much of a problem in practice, since in real life $a$ rarely exceeds 100.  But it could be a problem if we, say, decided to count P's age in days or even seconds instead of years.)  It would be kind of nice if we could have a scheme where:

the authority A could send P a single ticket stating their actual age;
there was a way for P (or anybody else!) to decrement the age on the ticket, i.e. to take a valid ticket that says the P is at least $x$ years old, and obtain a valid ticket stating that P is at least $x-1$ years old;
there was no way for P or anybody else to reverse this operation, i.e. to increment the age on the ticket and have it still accepted as valid; and
the authority A could simply sign a single ticket stating that "P is at least 0 years old", knowing that anybody who applies the decrement operation to any other valid ticket (and only to a valid ticket!) for P's age enough times will eventually obtain the signed ticket and be able to verify the signature.

One way to achieve that is to include an arbitrary string of, say, 256 bits on each ticket, and have the decrement operation include hashing that string with SHA-256 and replacing it with the hash output.  That is, A could send P a ticket stating:

  Authority A hereby certifies that P is at least $a$ years old.  Hash: $s$.

and a signature for the ($a$ times decremented) ticket:

  Authority A hereby certifies that P is at least 0 years old.  Hash: $H^a(s)$.

where $s$ is a random 256-bit string and $H^a$ denotes SHA-256 iterated $a$ times.

When P wants to prove to Q that they are at least $q \le a$ years old, they can then apply the decrement operation $a-q$ times to the original ticket sent by A to generate a ticket stating:

  Authority A hereby certifies that P is at least $q$ years old.  Hash: $H^{a-q}(s)$.

and send it to Q along with the signature for the "at least 0 years old" ticket that they received from A.  And Q, in turn, can apply the same decrement operation $q$ more times to re-derive the "at least 0 years old" ticket, and then verify that it matched A's signature.

The reason this works is because SHA-256 is (believed to be) preimage resistant.  This means that, given a random string $s$, it's easy for anybody to calculate SHA-256($s$), but effectively impossible to find any string $r$ such that SHA-256($r$) = $s$.  Thus, given the original ticket stating that they are (at least) $a$ years old (with the random hash $s$), P can easily obtain a valid ticket for any age $q \le a$, but not for any age greater than $a$.

OK, but then why does the protocol described in the blog post (and in the VEX paper) have the authority A first choose a random "seed" string $r$, and then use $s$ = SHA-256($r$) as the hash on the first ticket sent to P?

Well, one reason why one might do that is to make sure that the hash on the first ticket really looks like a normal SHA-256 output.  Sure, a random 256 bit string should be indistinguishable from a random SHA-256 output anyway, but we all know that in reality, random number generators can have subtle bugs that are often hard to test for.  Hashing the initial random value gives a little extra assurance that nobody can find any way to distinguish the original ticket stating P's true age from any decremented derivatives of it.

But that doesn't mean that A would have to ever reveal their original random value $r$ to P.  And indeed, the protocol as described above works perfectly well without it.  So why, then, does the VEX paper (and the blog post based on it) seem to suggest revealing this $r$ to P?  And doesn't doing so let P lie about their age by one year?

I'll answer the second question first.  Knowing $r$ will not let P lie about their age, provided that:

the seed $r$ is deliberately chosen not to be a possible SHA-256 output, and
the querier Q always verifies that the hash on the ticket is a possible SHA-256 output before accepting it as a proof of age.

OK, but what good does revealing $r$ to P do?  Well, it allows P to also choose to reveal (and prove!) their exact age to Q by disclosing $r$.  Since, as noted above, $r$ must not look like a valid SHA-256 output, this means that Q can be sure that it's indeed the first value in the hash chain leading down to the "at least 0 year old" hash signed by A, and that therefore $s$ = SHA-256($r$) must be the hash corresponding to P's true age (at the time A generated the signature, anyway).

Basically, without this extra feature, P could always decide to lie about being younger than they actually are, and there would be no way for Q to detect that, at least not without extra infromation from A.

For the age checking protocol described in the blog post, this isn't really a particularly important feature.  After all, if P needed to be able to prove their exact age, they could just get A to sign a separate message stating it.

However, for the verifiable auction protocol described in the original VEX paper it is essential, because in that protocol there is no central authority A, and the provers instead get to freely choose the value they want to commit to.  Without a way to reveal and verify the actual committed value at some point, the provers could just pick some huge value (say, one billion) at the start of the auction, and only later decide which "at least" queries they actually want to answer affirmatively.

Anyway, it turns out that, while the protocol as designed (and reasonably interpreted) is sound as far as I can tell, the JS implementations linked from the blog post and from your question are both buggy.

In fact, both of them have two bugs: one of that allows the prover to generate a bogus proof for a minimum age one year greater than their true age (revealing their secret seed in the process), and another bug that allows the verifier to accept it.

The first bug is simply that the prover should never attempt to generate a proof for a minimum age that they don't actually meet.  A minimal fix to the code linked from the blog post would be to add the following like to the beginning of the challenge() function:

function challenge(age, age_to_prove) {
  if (age < age_to_prove) return null;  // <- ADD THIS LINE!
  Q = hashchain(S, Number(age)+1-Number(age_to_prove))
  document.getElementById("display_Q").innerHTML = Q
  return Q
}

A similar bug is also present in the prove() function in your code, and can be fixed the same way.

The second bug is that, even if the prover (deliberately or by mistake) tries to use their initial hash chain seed as a proof of age, the prover must not accept it.  The blog post does correctly note this in the "Soundness" section:

  The exception to this is for $AgeToProve=ActualAge+1$, in which case Paula could just send $S$. However, as the format of $S$ is publicly known, a watchful verifier would detect the fraud [...]

but the linked JS code doesn't actually include such a check.  As a result, the verifier in the demo will happily accept the seed $S$ as bogus proof of age (and, due to the first bug, the prover will in fact respond with the seed if asked for a proof of a minimum age greater than their true age).

The blog post also uses a rather unfortunate choice for the format of the initial secret seed: 128 zero bits followed by 128 random bits, for a total of 256 bits.  The reason this choice is bad is that it precisely matches the output bit length of SHA-256, making it theoretically possible (even if extremely unlikely) for a genuine SHA-256 output to match the format of the secret seeds.  Literally any other choice of seed length (including just leaving out the 128 zero bits) would've avoided this issue.

Anyway, sticking with the poorly chosen seed format, a basic fix for the verify() function would be to add something like the following check at the top of it:

if (Q.length != 64 || Q.substr(0,32) == '00000000000000000000000000000000') {
  // this does not look like an SHA-256 output; verification failed!
  return null;
}

Of course, if the format of the secret seed was changed so that it wasn't exactly 256 bits (= 64 hex digits) long, then the .substr() check could be removed.  And also, of course, if the protocol was simplified (at the cost of removing the option for exact age verification) so that the prover never learned the secret seed to begin with, then this check would not even be necessary.


The answer is due to the Stevens et. al's work ;

Chosen-prefix collisions for MD5 and applications,  2012.

They showed that, with an approximately $2^{39}$ calls to the MD5 compression function, it is possible, for any chosen $m_1$ and $m_2$, to construct $s_1$ and $s_2$ such that $$\text{MD5} (m_1\mathbin\|s_1) = \text{MD5} (m_2\mathbin\|s_2)$$
They also gave examples for colliding documents, software integrity checking, etc ...


The "rank-1" specifically refers to the rank of the matrix which is produced.

As for the link to circuits, in zk-SNARKS at least, an arithmetic circuit is converted into a R1CS. Each constraint corresponds to one logic gate.

Here's a more detailed walkthrough by Vitalik Buterin: https://medium.com/@VitalikButerin/quadratic-arithmetic-programs-from-zero-to-hero-f6d558cea649


MAC size: Should MAC be shorter than cipher block size?

Or is that true only under some special circumstances?

This statement is based off of Remark 9.60 of the Handbook of Applied Cryptography (PDF of chapter 9) which reads as when talking about the strongly related CBC-MAC:

  Remark (truncated MAC outputs) Exhaustive attack may, depending on the unicity distance of the MAC, be precluded
  (information-theoretically) by using less than $n$ bits of the final
  output as the m-bit MAC. (This must be traded off against an increase
  in the probability of randomly guessing the MAC: $2^{−m}$.) For $m =
 32$ and $E = \operatorname{DES}$, an exhaustive attack reduces the key
  space to about $2^{24}$ possibilities. However, even for $m < n$, a
  second text-MAC pair almost certainly determines a unique MAC key.

So the idea behind this remark seems to be: If you are given only a single message-tag pair, and you truncate the tag, you cannot possibly find the the right key that produced this tag, because many keys will produce this truncated tag. However as you see more message-tag pairs, this advantage fades away as there are lesser and lesser keys producing the right tags on all these pairs. Also note that assuming you filter the entire keyspace for the first tag to get candidates for the second run, you have to perform $2^k$ operations and will get significantly less than $2^k$ keys in return on which another brute-force attack should take negligible time as the time is dominated by the primary brute-force and that stays true for truncated and non-truncated MACs.

TL;DR: Truncating tags in this case can make brute-force a little bit harder, but it's a case of "infeasible" versus "infeasible", so rather don't truncate and enjoy the ideal anti-forgery probability.


TLDR: (2) is a sufficient condition, but probably not a necessary condition. Most people would probably believe that HMAC-SHA-1 is indeed a PRF, although SHA-1 is not WCR.
The 2006 paper by Bellare claims to prove that e.g. HMAC-SHA-1 is a PRF, if the inner compression function of SHA-1 is a PRF. No known attacks break the pseudorandomness of the inner function, so taken at face value, we would conclude that HMAC-SHA-1 is a PRF.
However, reading that paper closely, this is proven for NMAC, and other two-keyed constructions. The proof for standard HMAC requires a related-key assumption (see Setion 5). This assumption is also pretty mild, and not even close to be broken by any known attack.
So to conclude: In practice, HMAC-SHA-1 is probably a PRF. The 2006 Bellare paper identifies relatively mild assumptions under which this holds, but if you want to precisely identify these assumptions, read Section 5 of that paper carefully.


Revoke a GPG key using previously generated revoke certificate after renewd (change expiration date)

For 3:

I did a simple test and the results showed that after revising the private key, the old revocation certificate can still revoke the gpg public key.

Test steps:

Delete a uid
Export private key
Import the old revocation certificate, the public key is revoked


DES - encrypt 3 times - DES(DES(DES, k), k'), k) - stronger than 2DES with 2 different keys?

As pointed out in the comments two key triple DES (without your complementary key condition) already has efficient attacks against it, going back to the 80's. See for example a detailed analysis in Van Oorschot and Wiener here which converts a chosen plaintext attack by Merkle and Hellman to a known plaintext attack.

Since 2 key 3DES is already weak, trying for sophisticated and complicated improvements based on the complementary key condition is likely not worth the effort.


1. The equation $-x^2+y^2=1-(121665/121666)x^2y^2$ defining the curve $E$ is quadratic in $x$, hence for any given $y\in\mathbb F_q$, there are at most two points on $E$ which have $y$ as their second coordinate. In this case, the two possible $x$-coordinates for a point on $E$ with $y$-coordinate
$4/5\in\mathbb F_q$ are the solutions to the equation
$$ -x^2+(4/5)^2=1-(121665/121666)x^2(4/5)^2 \text. $$
that is
$$ x^2=\frac{1-(4/5)^2}{-1+(121665/121666)\cdot(4/5)^2} \text. $$
Now by considering the symmetric representants (that is, from the set $\{-(q-1)/2,\dots,(q-1)/2\}$) for the elements of $\mathbb F_q$, we can interpret one of the roots of this equation as being positive and the other as negative, corresponding to the signedness of their symmetric representant. The unique "positive" solution to the equation above is precisely $15112221349535400772501151409588531511454012693041857206046113283949847762202$.

2. As far as I am aware, the base point is chosen pretty arbitrarily. As described in the Ed25519 paper, it arises from the choice $u=9$ in the original Curve25519 paper, but there seems to be no justification for that either. However, to the current state of knowledge, there are only very few bad choices for the base points, most importantly those whose order has no large prime divisor. (A nice overview of known weaknesses is SafeCurves.) Besides that, the choice of base point is not all that important, as the discrete logarithm problem has a property called random self-reducibility: An attacker who can efficiently compute logarithms with respect to a sufficiently large fraction of possible base points can in fact compute logarithms with respect to all base points.


What is the one-time signature scheme with shortest signature size known?

Well, if we assume a 128 bit hash function (and arrange things such that we assume only (second) preimage resistance), and use a Winternitz scheme with W=65536 (signing/verifying will be expensive), that'll get you down to about 168 bytes (assuming you insert an 8 byte randomizer into the initial hash, needed if we assume that the attacker can choose the message to be signed).

If we are even more aggressive (80 bit hash; may be good enough assuming it doesn't have to be TLA-proof), and W=$2^{29}$ (so Winternitz needs only a single check digit; signing/verifying will be real expensive), and a 4 byte randomizer, that gets you down to 44 bytes; but you had to make a lot of sacrifices to get to that level.


AES-128 + HMAC-SHA-256 but HMAC truncated

Can I truncate the output of HMAC-SHA256 to a desired bit length?

Yes, in fact, it's quite common to do so...

  what is the minimum required length of it to match the security level of AES128?

Now, that's a hard question; I'll try to try to explain some of the reasons why it is subtle.

To break the privacy of an AES encrypted session, the hard part of the attack is performing a huge number of $X$ operations, where the huge number depends on the AES key size, and desired success probability (that is, the probability that the attack is actually successful); if we assume a 128 bit AES key, and a minimum acceptable success probability of $2^{-\delta}$, then the attacker will need to do at least $2^{128-\delta}$ $X$ operations.  To break the integrity of an HMAC protected session (ignoring brute force attacks on the HMAC key), the hard part of the attack is performing a huge number of $Y$ operations, where the huge number depeonds on the transmitted HMAC size, and desired success probability; if we truncate the HMAC tag to $N$ bits, this requires at least $2^{N-\delta}$ $Y$ operations.

What's so hard about that?  Well, the issue is that the cost of an $X$ operation and the cost of a $Y$ operation is not easily comparable; in most cases, a $Y$ operation is far costlier than an $X$; any analysis that ignores that is (IMHO) a gross oversimplification.

To break privacy, what we do is grab some ciphertext; the $X$ operation consists of selecting an AES key, and checking if that key works with the ciphertext (sometimes, it's a bit more complex than that, but that's the general idea).

To break integrity (again, ignoring brute force attacks on the HMAC key; we'll assume that key is at least 128 bits, so we can ignore that attack), what we do is format some ciphertext (which presumably decrypts to something the attacker would like inject), the $Y$ operation consists of selecting an HMAC tag value, sending the forged message and the HMAC tag value to the legitimate decryptor Bob, and seeing if Bob is fooled.

What's the difference between these two attacks?  In the AES attack, once we've received the ciphertext, the attacker can perform the $X$ operation (the trial decryptions) without any interaction with the systems under attack; our attacker can rent out a large cloud space, grab a large botnet, or throw a large FPGA/ASIC farm at the problem, and we have no idea.  In addition, this attack can be performed even when the session is over; the privacy concerns depend on how long the data will stay sensitive, and that's a property of the data, not the cryptography.

In contrast, in the HMAC attack, we need to get Bob (the legitimate receiver) involved for every single tag we come up with.  If Bob will refuse to check no more than $2^{20}$ tags per second (possibly because that's the limit of what his hardware can do), there's absolutely nothing an attacker can do to speed up the attack.  In fact, if Bob is reading the encrypted message from a storage device, well, he'll realize the storage device has been corrupted after a HMAC failure (which means that we get to do exactly one $Y$ operation.  In addition, even if Alice and Bob use using the HMAC to protect encryption communication, Bob might just notice that the last billion messages all had invalid tags, and so might be able to deduce he's under attack.  Thirdly, this attack can only be done while the session is up; once Alice and Bob have shut down the connection and are no longer communicating, we can no longer try to fool Bob.

Now, if we take the oversimplification that $X$ and $Y$ are approximately the same cost, then it's obvious from the above argument that 128 bit HMAC tags are quite sufficient (and we should use larger HMAC tags only if the larger tags are of essentially no cost).  However, by the above argument, HMAC tags can be safely truncated even more; exactly how far it would be safe would depend on the details of the system.


If H(m) = 0 for some m, how can a DSA signature be forged?

The signature equation is $$r = (g^{H(m) s^{-1}} y^{r s^{-1}} \bmod p) \bmod q,$$ where $g$ is the standard generator of an order-$q$ subgroup of $\mathbb Z/p\mathbb Z$, $y \in \mathbb Z/p\mathbb Z$ is a public key, $m$ is a message, and the signature is $(r, s)$ for scalars $r, s \in \mathbb Z/n\mathbb Z$.

If $H(m) = 0$, this reduces to $r = (y^{r s^{-1}} \bmod p) \bmod q$.  If you pick $r = s = y \bmod q$, then $r s^{-1} \equiv 1 \pmod q$, so $y^{r s^{-1}} \bmod p = y$ and so $(y^{r s^{-1}} \bmod p) \bmod q = y \bmod q = r$ as desired.


how to iteratively calculate a^emod n with modulus n sized 4096 bits

Usually, RSA operations with the public exponent are fast, precisely because the public exponent is short. Hardware accelerators are meant to speed up operations with the private key, which are in much bigger need of it. In particular, hardware accelerators do not need to be "full width" because private key operations use the private key, which contains the factors $p$ and $q$, and allow for doing most of the work modulo $p$ and modulo $q$, both of which being twice shorter than the modulus $n$ (what the CRT is about).

A side note is that some implementation methods of exponentiations are fast but imply some fixed startup and wrapup overheads; e.g. Montgomery multiplication is popular to speed up exponentiations (which consists of many multiplications in a row), but requires converting source values into a special representation, and back at the end, both operations having a non-negligible cost. For a private key operation, the exponentiations used big exponents, and the savings implied by Montgomery multiplications dwarf these overheads, but this might not be true for a short exponent. Therefore, even if your accelerator did support a 4096-bit modulus, it is unclear whether this would have really provided some speedup for your public-key operations.

Anyway, I see no easy way to "split" a 4096-bit exponentiation into several exponentiations modulo smaller values, unless you factor the 4096-bit modulus, which should be infeasible.


Insecure MAC built on pseudorandom function

assuming that it is a deterministic MAC using a canonical verification

It is not, randomness is involved in the tag generation, therefore it is not deterministic and cannot use canonical verification.

This then means that an attacker doesn't have to follow the MAC algorithm but instead has to find $m',(r',t')$ such that verification suceeds, picking $t'=0$ is a good starting point for that.


Paillier encryption problem when q or p divides r

In Paillier encryption, the ciphertext is $c=g^n \cdot r^n \bmod n^2$, and to decrypt, you compute $m=L(c^\lambda \bmod n^2)\cdot \mu \bmod  n$.

For decryption to be correct, $r$ must be a member of group $\Bbb Z_{n^2}^*$, so that $r^{n\lambda} \equiv 1 \bmod n^2$ and $r$ can be cancelled in the decryption process. If $p$ or $q$ divides $r$, then $r$ is not in $\Bbb Z_{n^2}^*$ thus cannot be cancelled and your decryption will be incorrect.

When you use small $p,q$, it is likely you can easily choose $r$ that is not in $\Bbb Z_{n^2}^*$. However, when $p,q$ are large, the probability that a random $0<r<n$ is not in $\Bbb Z_{n^2}^*$ is negligible (otherwise the RSA problem can be solved). So we usually can just use $0<r<n$, without any more constraints (requiring $r$ to be a prime to me is not necessary).


Securing http session id's by appending HMAC hash?

1. Does appending the hmac hash to the session id offer any benefit above and beyond simply setting a version 4 uuid to the cookie?

As you found out yourself, The main benefit is eliminating the database query for authenticating the cookie.

2. Is sha512 overkill for hashing my session id? My understanding is that it should be faster on a 64 bit machine.

The storage/bandwidth constraint is probably more significant than the speed constraint, as cookies are limited to 4K. So as a general design guideline it would be better to use a 256 bit hash. You can achieve that by using only 256 bits from the hash generated by SHA512.

3. Is appending the hashed bytes array to the session id bytes array, base64 encoding and stringifying the result the proper way of storing this information in a cookie?

This is not really a cryptography question but a software engineering question. In a nutshell, you'd want the cookie to be formatted such that you and others will be able to debug problems and fix your code even long into the future.

4. Is $ openssl rand -base64 64 the proper way of generating a key for my purposes? Based on this discussion, my understanding is that my key length should optimally be between 64 and 128 bytes.

Once again a software engineering question. Assuming you write your code in some programming language other than bash, you're better off using a cryptography library for this language. As for the key length, 32 bytes (256 bits) should be enough.

5. Anything else you want to add? Anything I've overlooked?

Try looking at the implementation of established libraries. Not sure what you want to use this for and which language you'll be using, so it is hard to give the right recommendation. One Python example that pops into mind is this but once again maybe you're into a different use case.


What was the first hash and what problem was it supposed to solve?

Knuth, TAOCP, Vol. 3, 6.4 states (on non cryptographic hashing):

"The idea of hashing appears to have been originated by H. P. Luhn, who wrote an internal IBM memorandum in January 1953 that suggested the use of chaining; in fact, his suggestion was one of the  rst applications of linked linear lists."

Konheim has a recent book, "Hashing in Computer Science" which focuses on the mathematics and history of non cryptographic hash functions but considers post 1973 cryptographic hash functions only.

Gustavus Simmons worked on authentication codes at Sandia Labs for many years, I looked up for some history in his book but there isn't anything pre 1970 for cryptographic checksums.

CRC type of linear checksums [not strong cryptographically] conceptually date back to error correcting codes. A CRC was specifically proposed by Peterson in 1961.

Edit: (my thanks to @SamuelNeves) In the Georgia Tech School of Computer Science OSP Research Report from 1978 entitled "Foundations of Secure Computation", which can be found here, Rabin explicitly discusses, from p. 157 onwards, cryptographic hash functions and their use in digital signatures. One year later, Merkle invented Merkle trees for hashing.

IFFs are a kind of authentication mechanism, used in military signaling since the 40s, but more resemble challenge response protocols.

Claude Shannon in his "Theory of Secrecy Systems" from the war years, published in 1949 after declassification, focuses exclusively on secrecy as a goal.

Sol Golomb points out that Jevons (1874) had anticipated the difficulty of factoring and discussed how a type of authentication might work, by means of ruling out messages that don't conform to a set of numbers which were output. See here and the screenshot below.

The second fragment refers to the successive striking out of non-compliant statements, and is almost an algorithmic description of authentication.


Why is Tor alone not enough to guarantee anonymity for Bitcoin?

Bitcoin was designed to be decentralized, but was not designed to be anonymous.  How you use (earn or spend) Bitcoin cannot (in general) be made anonymous because the protocol was not designed to support that.  In fact, the design of Bitcoin,  being decentralized, requires all participants to be able to confirm all transactions.

You can use Tor to add to the level of anonymity of Bitcoin by creating a more anonymous "owner" of a Bitcoin wallet.  The transaction can still be traced back to this wallet, but it may be more difficult to tie the wallet to a specific entity.  This is hindered, however, because the wallet is only useful if it can, at some point, be converted to/from real currency--a process that is frequently traceable through traditional banking means.

Another technique to make tracking Bitcoin transactions more complicated are basically a form of digital money laundering...services that take in Bitcoin from one user and give it out to a different [set of] user(s), and visa-versa.


If you know the plaintext and the ciphertext, getting the key is trivial.

$$c=m \oplus k$$

Try moving the terms around. Hint: $m$ and $k$ can be functionally swapped (change position with each other), ie. only one term needs to be secret. You already know one term. I've pretty much given you the answer.

About the decoding procedure: The ASCII table linked by Reid is a good resource. Alternatively you can use an online ASCII to Hex encoder to

get the binary representation of the ciphertext
get the binary representation of the known plaintext

and then do the prodecure on paper. Once you understand that you can write a Python script to do the job for you.

only one term needs to be secret: That's what I said above and I'll clarify because that statement is not accurate.

You need to know any 2 terms of the equation $x=a \oplus b$. to solve for any other term. That means $a=x \oplus b$ and of course $x= b \oplus a$. Therefore any stream cipher (or OTP) is secure as long as the adversary only knows one term (namely the ciphertext).


The EC_POINT must be a ASN.1-encoded octet string, and the ePass2003 result does not seem to be valid ASN.1 (compare the Safenet 5110 value and the ePass2003 value)
(Due to a fun coincidence, the octet string ASN.1 prefix is also 04, so the byte that identifies that it's an uncompressed point is actually the second 04 in the third byte, in the Safenet 5110 output)
I don't know exactly what it's returning, but it's certainly wrong. It doesn't matter for the signing/verification process because they happen inside the token and don't rely on the EC_POINT value returned by the token.
My guess is that internally it has the correct value, but the ePass2003 code that returns the EC_POINT value has a bug.


Is this cumbersome strategy to produce a ridiculously strong password valid?

This is a broadly sub-optimal strategy because it violates Kerckhoffs's principle: if the attacker knows as much about the steps you're describing as you do, and only lacks the core secret, then most of these steps become useless for increasing the security of the secret.
Put another way: the steps that you're describing aren't actually increasing the entropy by any significant amount.
It sounds like this use case depends on the "survival" of the secret holder - to be alive and conscious enough to be able to always produce the secret from memory? If so,  the optimal strategy is probably:

maximizing the "memorizable" entropy of the input - a randomly generated passphrase, memorized, in the style of XKCD 936, using a mnemonic narrative constructed around it after the fact to aid recall - but with more entropy (five or six words drawn from a dictionary of 20,000 words or more), in order to be bruteforce-resistant even if stored with a weak/fast hash

maximizing the cracking resistance of the output - a true KDF like high-work-factor bcrypt or well-tuned scrypt (which are well-covered elsewhere). These are better because they are cracking-resistant even when their algorithms are public knowledge.

But really, since you often don't have control over how the input is stored (hashes), it's the first step that really matters - because even a weak hash will protect a strong password.
And if you're constrained to using the KDF that's built into the file storage format, the second step wouldn't apply at all - because you wouldn't have access to the salt because it would be hidden inside the document's hash. So you'd have to store it somewhere, which would be fragile.
So for your use case, it's probably best to let the secret (as a random passphrase) do the work.


How does a user register his verifier at host in SRP (Secure Remote Password) protocol?

As mentioned in the comments this is a standard problem not unique to SRP and not really about the cryptography of SRP. So this question would probably be better posted on 'security.stackexchange.com' as it is more of a generic problem.

Fundamentally setting a shared secret like a regular password or a password verifier over a public network has its challenges. For most applications the standard techniques used to reset a regular password can be reused in the setting of the password verifier.

The diagram on this page in the context of a javascript SRP library shows how the user is registered onto a websites secured using SRP. The user keys in the password into the browser and javascript generates the verifier and transmits it to the webserver. You don't want people to run an offline dictionary attack against the verifier so it is a form of shared secret. This means you want to protected it like you would protect them setting/registering/resetting a traditional password (e.g. use https and aes encrypt it within the database).

The only choices you have is whether the salt of the user is generated by the client or the server. It makes sense for the server to do this as it can ensure that the salt has high entropy and is unique to the user.


Is any specific packet cipher mode to be prefered for use with – for example – UDP?

All of them can be used to deal with unreliable, unordered datagrams; as long as you can derive an IV for the UDP packet then a cipher mode of operation should succeed. You need some kind of unique method of identifying the packet of course. Note that (the information used to generate the) IV may be public.

Usually you need some way of identifying the packet in the protocol anyway, otherwise you cannot put the packets in the correct order after you've received them out of order.

The form and properties of the IV of course depend on the mode of operation. For instance CBC requires an unpredictable IV, while reuse of the IV in CTR and related modes of encryption will immediately leak information about the plaintext.

CCM is an authenticated mode of operation that was specifically designed for data packets. It consists of a specific combination of CBC-MAC and CTR mode encryption.

EAX has been specified as a successor of CCM and is a lot easier for general use, but it does not include a specific message format to adhere to. So the I/O of EAX is more like GCM, even though internally it has more in common with the CCM mode of encryption.

[EDIT after re-reading the question]

Note that it is not a good idea to rely on cryptography to reorder your datagrams. If you want to reorder, use a sequence number. If you want to verify the reordering, you can of course use a MAC or signature.


Why does RSA need p and q to be prime numbers?

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

Not categorically. Factoring a large integer is trivial if it is only composed of small factors.

A fairly naive algorithm for factoring N is the following:

while N > 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)

With this algorithm, $340$ $282$ $366$ $920$ $938$ $463$ $463$ $374$ $607$ $431$ $768$ $211$ $456$ can be factored in exactly $128$ iterations of the innermost while. (The number, of course, is $2^{128}$)

The more prime factors a composite number has, the smaller those factors have to be. For example, $919 \cdot 677 = 622$ $163$. With the naive algorithm, this takes $157 + 1 = 158$ iterations to factor. A number of roughly the same size comprised of three factors, $73 \cdot 89 \cdot 97 = 630$ $209$, only takes $25 + 2 = 27$ iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about $10^{497}$ iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about $434$ $294$ $481 + 99 \approx 10^{9}$ iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about $4 + 999 \approx 10^{3}$ iterations.

So, to make factoring as difficult as possible, you want the prime factors to be as large as possible, which means you want N to have the fewest factors possible. With $p$ and $q$ prime, $N$ has two factors. With $p$ and $q$ composite, $N$ has at least four factors, possibly more.

Note that this is far from a complete answer on why (we think) RSA is secure, but I hope it gives a more intuitive / example-based idea of why $p$ and $q$ should be primes.

Note also that $p$ and $q$ should be similar in magnitude. If one is much larger than the other, factorization becomes easier. For example, if $p = 43$, the naive algorithm would only take $14$ iterations.

(After reading the comments (thanks Taemyr and Daz C), I corrected some mistakes in the answer. The main point is unaffected.)


You can use gpg --list-packets [keyfile] to see a list of all packets and their contents. All hash algorithms have numbers which you can look up in section 9.4 of RFC 4880, "Hash Algorithms".

Alternatively, use pgpdump [keyfile] to create a similar output, but already containing the algorithm names instead of their numeric identifiers.


This basically boils down to find a "good" implementation of the S-box and then compute the GE by weighting the operations used (e.g. XOR = 1GE), that is, as you already commented, synthesize the implementation.

Note that the resulting GE greatly depend on the optimization of your implementation, the technology library used etc.

Wikipedia lists some software for this:

https://en.wikipedia.org/wiki/Logic_synthesis#Commercial_tools_for_logic_synthesis
https://en.wikipedia.org/wiki/Logic_synthesis#Free_tools

I've never used a tool to design an ASIC, I have only some basic experience with FPGA development, so cannot tell you more about the different tools.


Practical disadvantages of GCM mode encryption

In comparison to CBC mode and HMAC, GCM mode is quite a commonly better alternative. But, I'll go to detail where it necessarily is not. Just like Richie Frame, I also do not agree that CBC + HMAC is always the best comparison target. I've added a few other details. Hope you find them useful.

Against CBC and HMAC

I'll discuss downsides first.

The authentication part of GCM (GHASH) is weaker than HMAC, GHASH provides a maximum 128-bit authentication tag, whereas HMAC allows lot longer tags (HMAC-SHA-256 would allow 256-bit authentication tag). In addition, forgery of GHASH tags in some cases is easier than HMAC:

  As with any tag-based authentication mechanism, if the adversary chooses a $t$-bit tag at random, it is expected to be correct for given data with probability $1/2^t$. With GCM, however, an adversary can choose tags that increase this probability, proportional to the total length of the ciphertext and AAD. (Borrowed from NIST SP 800-38D.)

Implementations using GCM mode often use short IV (96-bits), in fact, e.g. NIST SP 800-38D recommends using the 96-bit IVs. (Longer IVs are defined but they'll require the extra invocation of GHASH function.)
The 96-bit IVs (GCM) can be too short uses where 128-bit IV (CBC) would be sufficient. Consider e.g. collision probability of random IVs.

Benefits of GCM: Properly implemented GCM is almost always faster, and it is easier to use GCM than operate AES + HMAC combination correctly. CBC mode requires padding input to the block size, thus GCM mode produces smaller output if the input is not multiple of the block size.

Against CTR + HMAC

Because the AES parallelization benefits are available via CTR mode as well, CTR + HMAC is fairly similar to GCM and can perform pretty well. It can be better, in case authentication tag requirements exceed what GCM can provide.

Against CCM

The CCM mode is largely similar to GCM mode. It's the largest benefit is that implementation requires less code (SW) or gates (HW), but CCM implementations generally are slower than GCM.

Overall, some IEEE 802 standards tend to pick CCM over GCM due to the HW implementation gate count.

SIV-AES and AES-KW

It is possible to wrap other keys using AES-GCM (key wrapping).

For authenticated encryption where the target is key wrapping (encryption of key with another key), SIV-AES and AES-KW algorithms are commonly better than AES-GCM. Better in the sense that they can be used without reliance on random
number generation (or a deterministic IV generator) and that their output can be smaller because there is no need IV in addition to encrypted output and authentication tag. (These are commonly considered to be benefits of deterministic authenticated encryption.)

Key, IV pair reuse

I've already mentioned IV, key pair reuse.

GCM mode does not resist the reuse of Key IV combination. To prevent this, some parties like NIST put more requirements on the proper use of GCM mode than the other modes. This is a good idea from the security point of view, but it may reduce the allowed uses of the mode.

Generally, GCM is most convenient for uses where new keys are agreed or transported as a part of the protocol (TLS or IPsec). If there is use where a persistently stored key is needed, then it can be cumbersome to ensure IV uniqueness.

NIST is aware of this pitfall. NIST's CMVP (Cryptographic Module Validation Program aka FIPS 140-2 validation program) has a requirement for the careful use of GCM (FIPS 140-2 IG A.5). FIPS-approved implementations of GCM mode need to be very careful in their use of keys because, in GCM mode reuse of key, IV pair is not allowed to happen.

CBC-ESSIV

AES-CBC mode can be used for disk encryption (especially with ESSIV, see Wikipedia disk-encryption theory). The fact that GCM often uses small IV length and is not IV collision-resistant makes it hard to apply for contexts where it is needed to encrypt a large number of blocks and encryption does not happen in-order (deterministic IV increasing would be ok). For this reason, AES-GCM is not that much used for encryption of stored data, but rather data at transit.

Summary

GCM is a very good mode of operation, and it often is more convenient than legacy algorithms combinations like CBC + HMAC. However, it is not a universal solution (none of the modes is), but rather it is most convenient only for a large number of data at transit.


RSA Key Generation Parameters - public exponent, certainty, string-to-key count

Short answer: public exponent $65537$, certainty $5$. Terms and Conditions May Apply.

I have no clues about string to key count.

Whenever one wants to know " what values are appropriate ", there's the problem of defining appropriate: is there some normative context, e.g. FIPS 186-4? I'll assume that reference.

This, and all standards I know, agree that public exponent can be $65537=2^{16}+1$, and that's a choice that one will regret only on the grounds of performance of the public-key function (used for encryption and signature verification, not decryption or signature generation). A few standards allow $3$ which seems safe with a padding scheme randomizing the message, and can improve said performance by a factor like 8.

Answering the BouncyCastle-and-Java-specific part of the question (which is largely off-topic) would require the effort of ensuring that certainty is actually used as a number of Miller-Rabin primality tests with random base, and for random primes half the key's modulus size. I have no true assurance this holds, and assume it blindly.

FIPS 186-4 only allows $1024$, $2048$, and $3072$-bit public modulus, and requires using random $p$ with auxiliary conditions on the factorization of $p-1$ and $p+1$ at the $1024$-bit level, without stating a rationale for when the auxiliary conditions are required. Some think these are pointless, other including me believe they make some sense when generating extremely many keys, in order to repel down to entirely hopeless levels the possibility that methods derived from Pollard's $p-1$ can factor one of the many moduli with better odds than general methods can factor a single modulus.

Whatever the reason, with the assumption that BouncyCastle uses random primes, FIPS 186-4 leaves us with the only applicable generation method that of appendix B.3.3, at step 4.5.1 of which we are told to " test $p$ for primality as specified in Appendix C.3, using an appropriate value from Table C-2 or C-3 in Appendix C.3 as the number of iterations. ", with a rationale given for these in appendix F.3, telling us we should use table C-2 if we want residual odds of having a composite matching the standard-estimated security level of the key, or table C-3 for $2^{-100}$ odds.

Here are these tables; what interests us for certainty is the values given for " $p$ and $q$ " (which size is, we assume, half the key's modulus size). For example, the bottom entry in the first table tells us that certainty of $4$ is enough to generate each of the two $1536$-bit prime required for $3072$-bit RSA key and odds of generating a composite less than $2^{-128}$. Higher values further reduce the bound for these odds (which is mostly pointless), and make key generation slower (but less than proportionally, so using $4$ instead of $5$ only gives a moderate gain).

Appendix F.1 in FIPS 186-4 gives the method used to compute these tables, and can be used for reduced certainty (thus somewhat faster key generation) for keys larger than $3072$-bit. Actual odds of choosing a composite are believed to be significantly lower than given by theses tables and method.

Note: Nothing in this answer shall be understood as suggesting that generating RSA keys using BouncyCastle with certainty of $5$ may be FIPS 186-4 conformant.


Does knowing modular eth roots help in factoring n?

The RSA problem, which you describe, is not known to be equivalent to factoring and there is evidence both ways. In [BV] it is shown that this barrier might be inherent: using a black-box separation technique called meta-reductions, they show that certain restricted class of reductions are not possible. On the other hand, it was shown later in [AM] that in the generic ring model (see [JS]), these problems are equivalent. That is, any speed-up in breaking RSA has to exploit the representation of $\mathbb{Z}_N^*$.
You can read about more related works in §1.3 in [AM].
[BV]: Boneh and Venkateshan, Breaking RSA may not be equivalent to factoring, Eurocrypt'98
[AM]: Aggarwal and Maurer, Breaking RSA Generically Is Equivalent to Factoring, Eurocrypt'09
[JS]: Jager and Schwenk, On the Analysis of Cryptographic Assumptions in theGeneric Ring Model, Asiacrypt'09


ElGamal Homomorphic Encryption Formula Question

TL;DR: as pointed by DrLecter in comment¹, the question's formula is for exponential ElGamal encryption, with per-encryption random $r$ explicit.

I'll first describe (straight) ElGamal encryption. It works in an arbitrary finite cyclic group of generator $g$ and order $q$ (with the internal law noted multiplicatively). That is, $q$ is the smallest strictly positive integer with $g^q=1$, where $1$ is the neutral in the group (the integer $1$ when working in a subgroup of $\Bbb Z_p^*$, or the point at infinity for an Elliptic Curve group). Private key is an integer $x$ in $[0,q)$. Public key can² be $h=g^{q-x}$.

Encryption of a message supposes that it was mapped to an element $\widetilde m$ in the group by some encoding technique. Encryption draws a random integer $r$ in $[0,q)$, and outputs the ciphertext consisting of two group elements per the formula (different from that in the question):
$$\mathrm{Enc}(\widetilde m,r)\gets(g^r,h^r\cdot\widetilde m)$$

(Straight) ElGamal decryption of ciphertext $(c_1,c_2)$ produced as above obtains $\widetilde m$ as follows:
$$\begin{align}
\mathrm{Dec}(c_1,c_2)&\gets {c_1}^x\cdot c_2\\
&\;={\left(g^r\right)}^x\cdot h^r\cdot\widetilde m\\
&\;=(g^r)^x\cdot (g^{q-x})^r \cdot\widetilde m\\
&\;=g^{rx+(q-x)r}\cdot\widetilde m\\
&\;=g^{qr}\cdot\widetilde m\\
&\;=(g^q)^r\cdot\widetilde m\\
&\;=1^r\cdot\widetilde m\\
&\;=\widetilde m\\
\end{align}$$
(Straight) ElGamal encryption is multiplicatively homomorphic (for multiplication of plaintext as mapped in the group), per the easily established relation
$$\mathrm{Enc}(\widetilde m,r)=(c_1,c_2)\quad\mathrm{Enc}(\widetilde m',r')=(c'_1,c'_2)\implies\mathrm{Dec}(c_1\cdot c'_1,c_2\cdot c'_2)=\widetilde m\cdot\widetilde m'$$
There are functional issues with (straight) ElGamal encryption:

It is non-trivial to map and unmap an applicative message $m$ to and from an element $\widetilde m$ of the group. In $\Bbb Z_p^*$ with $q$ prime or in an ECC group, practical methods are iterative. When working in $\Bbb Z_p^*$ with $p$ prime and $q=p-1$ (implying $q$ is not prime for sizable $p$), we can take $\widetilde m=m$ but then ElGamal encryption leaks one bit³ of information about $m$.
Multiplicative homomorphism is less useful than additive homomorphism, and not directly useful since the multiplication is on mapped messages $\widetilde m$, rather than on arbitrary messages.

Here exponential ElGamal encryption comes to the rescue, solving both problems, at the expense of making decryption hard. Its encryption takes plaintext $m$ in $\Bbb Z_q$, maps it to $\widetilde m=g^m$, then encrypts per straight ElGamal. The encryption formula becomes as in the question:
$$\mathrm{Enc}(m,r)\gets(g^r,h^r\cdot g^m)$$
Exponential ElGamal decryption decrypts per straight ElGamal yielding $\widetilde m$, then either verifies an externally supplied guess $w$ of the plaintext by checking if it holds $g^w=\widetilde m$, or solves that discrete logarithm problem yielding $w=m$.

Exponential ElGamal encryption is additively homomorphic (for addition of plaintexts modulo $q$) by composing ciphertexts as in straight ElGamal encryption.

Note: while getting $m$ in exponential ElGamal decryption requires solving a discrete logarithm problem, that's still possible for moderately large $m$, including deterministically by using baby step/giant step, which has cost $\mathcal O(\sqrt m)$ group operations. Also, when in a sugroup of $\Bbb Z_p^*$, sizable speedups are possible because the discrete logarithm for base $2$ is easier: we use $g=2$, or modify encryption to $\mathrm{Enc}(m,r)\gets(g^r\bmod p,h^r\cdot2^m\bmod p)$ with $2$ of the same (prime) order $q$ as $g$.

¹ That was minutes after the question was posed and years before this answer.

² Sometime the public key is given as $h=g^{-x}$, which is equivalent, or as $h=g^x$, in which case $x$ should be changed to $q-x$ or equivalently $-x$ for decryption.

³ The Legendre symbol $\bigl(\frac mp\bigr)$ can be found from the ciphertext. This issue was not highlighted in the original description: Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984).


It is important to understand that although a very large random function will only have linear biases with very low probability, this is simply not true of small random functions. If you choose a small random function, then it is unlikely that you will get one that is suitable for block cipher constructions. In addition, it is not enough to construct an S-box with low linear biases; one must also take into account differential cryptanalysis, and more.

Having said all of the above, this does raise an interesting question. Can we even define an ideal S-box? This doesn't necessarily mean we could find one; for example, the AES S-box has an 8-bit input and 8-bit output. This means that there are $2^{128}$ possible functions of this type, and this cannot be enumerated. Nevertheless, I would be interested to know if an "ideal" construction even exists, in terms of our best cryptanalysis knowledge.


Digital Certificates genereted from Hardware Security Module

HSMs are not purchased just for the feature of generating certs.

HSMs also store the certificates very securely. You cannot use the cert in the HSM unless you are authorised
HSMs also provide very secure management of the HSM itself - for e.g. you can create smart cards for 5 admins & say that atleast any 3 of the cards have to be used to administer the HSM
HSMs provide very high speeds for signing. If you are doing really huge amount signings per second, then this reduces the load on your software.
HSMs also provide high speeds for key generation. This may be important for temporal certificate generation - each certificate is used only for one signing.


OpenSSL & TLS1.2 with aes-cbc and initialization vector

Or does OpenSSL derive the IV by the decryption key somehow from the packet ?

Well, yes.  Actually, it's not that complicated; for DTLS and AES-CBC mode, the IV is the first 16 bytes of the encrypted region, so it just reads it from there, and starts decrypting from there.

In DTLS, we assume that encrypted packets can be dropped in flight (or received out of order), and so the system cannot assume that the decryptor has seen the previous packets.  Everything that is needed to decrypt (except for those parts, such as keys, that were established in the initial negotiation) must be in the UDP packet.  When it comes to IV, well, IV's can be sent in the clear; we need to communicate the IV to the decryptor, and so the obvious approach (which DTLS uses) is just include the IV in the UDP packet.

Now, for TLS, this 'missing records or receiving them out of order' is not an issue (as the TCP stack will ensure that, absent someone in the middle tweaking things, we will receive things as sent).  So, what TLS 1.0 used to do is make the IV for the next record the same as the last ciphertext block of the previous record.  However, it turns out that opens things up to chosen plaintext attacks, hence with TLS 1.1 and on, they also send the explicit IV, just like DTLS has always done.

  The DTLS rfc did not talk about this either.

Actually, DTLS1.2 RFC (6347) just says 'we do it the same as TLS 1.2' (see section 4.1.2.3), the TLS1.2 RFC (5246) explains the explicit IV structure (see section 6.2.3.2)


However, usually in lattice based cryptography a balanced
  representation is used [...]

Is this true? I'd be interested in seeing some instances in the literature (or implementations) which actually use this representation. In my experience, the literature (such as the paper you linked) assume the ordinary representation of $\mathbb{Z}_q$.

I don't see a practical benefit to using the balanced representation. Random numbers are indeed sampled from a truncated discrete Gaussian centered around 0, and a negative number can easily be added to the value in $\mathbb{Z}_q$. Sometimes this result may be negative, so a $\mod q$ operation needs to be done. But this operation is necessary for whichever representation you use. In the balanced representation, if you add a positive error to $(q-1)/2$ you will need a $\mod q$ operation as well to keep the result in $\mathbb{Z}_q$.

To answer your question, the Bitdecompose procedure can be done by simply adding $\lceil-q/2\rceil$ to $a$ first, which shifts the representation back to normal. Then Bitdecompose is nearly free in practice.


Generating cyclic group for Ciphertext-Policy Attribute-Based Encryption

There are libraries allowing to do that:

PBC: C library
JPBC : Java library

Hope it helps.


In use of AES CBC, can a cipher text signature be replaced with appending a known string to the plain text?

Would appending a known string to the end of plain text then validating the string after decrypting adequately verify the authenticity of the cipher text?

No.

Here's what CBC-mode decryption looks like

Consider what happens if the attacker modifies the the first ciphertext block shown (as marked in red).

Then, the decryption of that block produces something unpredictable; that block turns into an unpredictable (by the attacker) value; the corresponding plaintext block is unpredictable.

For the second plaintext block, the modified first ciphertext block is xor'ed in with the unmodified decrypted second ciphertext block, the result is original plaintext block, except that the bits the attacker flipped in the ciphertext block will be flipped.

As for the rest of the decrypted plaintext, there are totally unchanged.

Hence, if you were to append a known string at the end, that part would decrypt properly, and hence your check would not detect the modifications done earlier.


Is it secure to use ciphertext feedback with RC4?

At least one thing goes very wrong: if an adversary can obtain the ciphertext for a few short chosen plaintexts and the same reused key/initial state, that allows reconstructing the state because the indexes vary in a controlled way. That certainly works if we obtain the ciphertext for the $2^{24}$ plaintexts consisting of the 3 bytes $u$ $v$ $w$ $0$ (basically, we can make some hyptohesis on a few state bytes, and confirm or rule it out based on the ciphertext for that chosen plaintext); or something on that tune. Likely, it is possible to mount an attack requiring much less chosen plaintext.

It might even be possible to mount an iteratively chosen plaintext attack working without key reuse.


As Chris Smith notes in the comments, HMAC is a specific MAC algorithm (or, rather, a method for constructing a MAC algorithm out of a cryptographic hash function).  Thus, HMAC can be used for any application that requires a MAC algorithm.

One possible reason for requiring HMAC specifically, as opposed to just a generic MAC algorithm, is that the HMAC construction actually provides (as long as the underlying hash function satisfies the appropriate assumptions) stronger security properties than what's required of a MAC.  For example, nothing in the definition of a secure MAC algorithm (resistance to existential forgery under a chosen-plaintext attack) says that the MAC output can't reveal information about the plaintext to an attacker.  If the plaintext is secret but the MAC is public, that would obviously be bad.  HMAC, however, is guaranteed not to reveal any information about the plaintext as long as the underlying hash function is secure.

In particular, Bellare has shown that HMAC is a pseudo-random function (PRF) as long as the compression function of the underlying hash is also a PRF, and a "privacy-preserving MAC" (PP-MAC) as long as the compression function of the underlying hash is also a PP-MAC.  Both of these are strictly stronger security properties than what's required of a plain MAC; in particular, being a PRF is a very strong security property — it essentially says that there's no practical way for an attacker to say anything about the output of the function based on the input, or vice versa, except for the obvious fact that the same input always yields the same output.  There are many use cases for which a PRF will do whereas a plain MAC may not; HMAC, instantiated with a secure hash function, can be used for those.

Also, as Chris notes, some other MAC algorithms require a random IV to be secure; HMAC does not, so it can be used even in situations where deterministic output is required, or where messages must be kept as short as possible.

As for why you might not want to use HMAC, well, one reason is that it's not really optimized for speed.  Dedicated MAC functions, particularly those based on universal hashing (the Carter–Wegman construction) like UMAC and VMAC, can be significantly faster.  Also, MACs based on block ciphers (such as CMAC) can be very useful on limited platforms where an efficient block cipher primitive (like AES) is available but a secure hash function is not.


Is there a general method to crack this type of fractionating cipher?

Known plaintext attacks and chosen plain-text attacks

The attack here is straightforward. If you have any known plain-text at all, you can find  codes for all the letters in the plain-text you have. You can then use this knowledge to decrypt other messages whose plain-text is unknown.

A very small number of known plaintexts would completely compromise this scheme.

Ciphertext only attack

Each letter within a language has a certain probablity of occurring. In English, the letter "e" is the most frequently used letters.

This wikipedia article gives a nice table of all the English letters and their frequencies.

The attack is fairly straightforward. Take a given cipher-text and build a frequency table for all one digit strings, two digit strings, three digits strings etc.

Then compare each string's relative frequencies compared to the table linked in the Wikipedia article. If there is a rough correspondence between a given sequence of digits and a given letter, substitute that sequence for the letter in question.

Most of the time, the substitution will be valid and the plaintext will quickly fall in to view.


For example, let say that you have a message: "100 dollars should be moved." and you encrypt it with OTP. Then everybody can just take the first character "1" and change it to a 9 by XOR the 1 from the cipher-text and then XOR a "9" with the key you got.

What you are describing is what happens if an attacker introduces changes in the ciphertext by a man-in-the-middle attack. This kind of attack is not protected against by OTP. OTP only provides for confidentiality, not integrity and authenticity. To add integrity and authenticity you need to add a message authentication code or MAC to the ciphertext.

Unfortunately MAC's won't provide perfect integrity or authenticity. In practice this doesn't matter much as - for instance - HMAC is pretty secure. It cannot be proven secure just like OTP however. Ciphers such as AES have the same properties; they are rather secure, but they cannot be proven secure. Generally they are considered secure enough and they are much more practical than OTPs.

OTP doesn't propagate errors introduced to the ciphertext. CBC does propagate errors. If you could reliably detect such errors then you would have integrity protection. This is however not the case:

CBC error propagation is localized to the current block and a single bit of the next block;
CBC decryption always succeeds, you just get incorrect plaintext;
if the plaintext is a padded message then the padding may trigger padding errors, but it may also - by chance - create a valid padding scheme;
if the plaintext is a padded message then plaintext/padding oracle attacks may apply, destroying not just the integrity but also the confidentiality (leaving you with no protection whatsoever).

Nowadays we don't care about error propagation all that much; we apply a (H)MAC over the IV and ciphertext or we apply an authenticated mode of operation (an AEAD cipher) such as GCM. In that case the verification of the authentication tag will fail if any changes are made to the IV, ciphertext or authentication tag.

The CBC mode of operation is defined for keyed block ciphers. OTP however isn't a block cipher, so CBC cannot be directly applied to it. In CBC the block cipher is executed for each block of plaintext. As you should never reuse the key for a one time pad, CBC can not be made applicable to OTP.


In what cases might PRESENT be implemented as encryption-only?

So in what cases might we need only encryption but not decryption? It seems strange we would encrypt something that does not need decrypting at some point.

For example, the CTR mode uses only Encryption, and CFB, OFB.

  It seems PRESENT can decrypt a ciphertext by running it in reverse. So why the need for some careful management for PRESENT to be used for both encryption and decryption?

The correct sentence is

  In this way it can be used within challenge-response authentication protocols and, with some careful state management.

All about the hardware implementation of PRESENT.

This paragraph from the article;

  Encryption and decryption with present have roughly the same physical requirements. Opting to support both encryption and decryption will result in a lightweight block cipher implementation that is still smaller than an encryption-only AES. Opting to implement an encryption only present will give an ultra-lightweight solution. The encryption subkeys can be computed on-the-fly.

So they compare their encryption and decryption supported hardware implementation to encryption-only AES claiming that PRESENT has smaller requirements.


Vigenère cipher with sha512 and a little foresight turns to one-time pad. How safe can be?

Is this a real one-time pad?

No, it's not a one time pad; as the keystream is not generated from a truly random process, hence you don't get the informational security guarrantees that you'd get from a true OTP.

Instead, it's a stream cipher; in particular, counter mode (with SHA512 is the "block cipher"; in counter mode, the block cipher needn't be invertable).

It's actually decent at providing privacy (albeit not very fast at it); however, it still would need some integrity protection (unless you're absolutely positive that an attacker cannot alter the ciphertext)


Is a PRF applied to a secure MAC also a secure MAC?

Yes.

A secure PRF is a secure MAC. A secure MAC of a secure MAC is a secure MAC. Therefore, applying a PRF to a MAC still gives you a MAC.

Depending on the length of the inner MAC and the PRF you may lose security bits, but if they are long enough it works.


Is a composition of computational hardness problems still hard?

This is essentially equivalent to factoring $n$.

From the composition you have given it is obvious that this is at most as hard as the easier of the two instances of the hard problems. So let's look at both of them.

Computing square roots over composite rings. This one is known to be equivalent to factoring the ring modulus.

Computing discrete logarithms over composite rings. This one is more intriguing. It is known that if you can compute prime-based discrete logarithm (for all the prime factors) and factor, then you can compute the discrete logarithm over the composite ring. It is also known that if you can compute the discrete logarithm over composite rings, then you can factor the modulus.

If you wanted the composition to be more like "you need to break both instances", then you should formulate it as, "given $(g,g^y,x^2)$ with $x,y\in\mathbb Z_n$ with $n$ having a secret semi-prime factorization, find $(x,y)$".


The examples I see in wikipedia show that the same key is used for
  both.

Doing so is fine in most constructions, however "most" is not "all". Also the graphics could be read as "derive a key from the given input key somehow".

  Why would the encryption key be different than the MAC key?

Cryptographically speaking, it's cleaner to use different keys for the different primitives, as it definitely prevents subtle interactions due to the key-reuse and thus makes formal proofs about security claims easier.

Also there are cases where you actually have to use different keys for the MAC and the encryption scheme, the most well-known example being the combination of CBC and CBC-MAC which allows for modification of (nearly) the whole message on key-reuse.


Existential unforgeability vs strong unforgeability

It is easy to construct a signature scheme that is existentially unforgeable but not strong. All you have to do is add a bit to the end of a strong scheme, and ignore it upon verification. This enables an attacker to flip a bit and have the new signature accepted. In some "real" settings this arises as well. For example, with ECDSA, a signature $(r,s)$ can be modified to $(r,q-s)$ and it will still be accepted (where $q$ is the group order). This can be prevented by forcing $s<q/2$, but the original signature is indeed not strong.


How are IVs used in association with RSA Encryption?

IV is not commonly used in RSA Encryption.

Do you mean:

AES Encryption? AES Encryption in some modes, for instance CBC or CFB uses IV (Initial Vector), which is (often) unpredictable value that never repeats for the same key. It is fairly common to generate IV randomly
Random padding in RSA Encryption? There are several padding mechanisms defined for RSA Encryption, including e.g. PKCS#1v1.5 padding and OAEP. In RSA encryption, parts of the padding commonly are random, just like some IV's used for symmetric encryption.

In case you are thinking of RSA Encryption padding where IV is actually used, please, provide name of the padding scheme in the question.


How to tell if a hardware RNG is rigged?

While unfortunately that is not possible deterministically, if you have a small amount of "guaranteed trustworthy" randomness, you can use several untrusted RNGs together to generate an unlimited supply of good randomness (under some weak assumptions of non-signaling between the RNGs). This is called "randomness expansion" and I am not aware of any use in practice yet, unfortunately.

See these papers by Colbeck and Kent and Coudron and Yuen


Does knowing common prefixes help crack blowfish?

The answer depends a great deal about what you're actually doing.

For one, "salt" is not a commonly used term if you are encrypting; public data that is used to modify how the encryption is done is commonly termed an "IV" (Initialization Vector).  However, "salt" is the common term for public data that modifies how a hash is generated.  The distinction between "encrypting" and "hashing" is that hashing can't be undone; given a hash, it's impractical for anyone (even for someone with the key) to generate the original string.

I'll see if I can go through the various possibilities:

If you are actually doing hashing (for example, hashing a password so that you can recognize it if someone enters it), well, what salt does is it protects in two different ways:

If you have two different users which have the same password, differing salts will disguise the fact that the passwords are the same.
It prevents an attacker from getting an attacking multiple passwords at once (for example, by hashing a test password, and seeing if that hash is anyone on the system).

Not doing salt isn't fatal, but generally it is easy enough to warrant the protection it does provide.

And, if you are using PHP's crypt() function (as woliveirajr guesses), well, they always provide a salt -- if you don't provide one, the crypt() function will pick one for you (which is a good thing).  So, in this case, you don't have a problem at all.

In addition, having some fixed text at the start of the string you're hashing doesn't help the attacker at all (if it does, the hash function is seriously broken).
If you are actually doing encryption (that is, you expect someone to be able to decrypt the encrypted string), well, you've got a problem.  Most encryption mechanisms do take an IV, and bad things happen if you keep it constant; exactly what those bad things are depends on which 'encryption mode' you are using:

If you use CBC mode (with a fixed IV), the attacker will be able to see if two encrypted messages are identical up to 8*N bytes in length (for any N).  In your example (assuming the fixed part is exactly 20 bytes long), then this means that the attacker can tell if the first 4 bytes of the variable part of two different strings happen to be the same.
If you use CTR mode (with a fixed IV), it gets a lot worse.  The attacker is able to compute the exclusive-or of any two strings; this will likely allow him to deduce the value of the strings.

In both cases, the correct fix would be to generate distinct IVs, and include those in the encrypted messages.

Also, having some fixed text at the start of the string really doesn't affect the security.  If you pick IVs correctly, it won't affect things at all; if you use a fixed IV, well, fixed text doesn't hurt much.


Using weak hash functions to construct a stream cipher

As long as your encoding of $K$, $N$, and $i$ is injective (i.e., for each encoded string you can uniquely derive $K$, $N$, and $i$) and fixed-length, this is almost certainly a decent stream cipher.

It won't break any speed records, obviously!  But collision resistance is not relevant here, and I have no reason to suspect that the distribution of $x \mapsto \operatorname{MD5}(k \mathbin\Vert x)$ for fixed-length $x$ is distinguishable from uniform under a uniform choice of $k$.  Any distinguisher would probably suggest a better than generic partial preimage attack on MD5, and in spite of some papers claiming the contrary in nonsensical cost models, so far there's no evidence of preimage attacks on MD5.

That said: Consider carefully whether you also need to do authentication!  Unauthenticated encryption is seldom useful in real-world applications.  Using the tools you have, you can probably compute HMAC-MD5 too without too much trouble.  Encrypt-then-MAC with MD5-CTR and HMAC-MD5 may be goofy, but it probably makes a reasonably secure authenticated encryption scheme.

Do make sure, though, to limit yourself to ${\lll}2^{64}$ messages under any one key because the 128-bit state of HMAC-MD5 admits a birthday forger, and make sure to use at least a 256-bit key in case there is any danger of multi-target attacks.


Yes (and always).

Given $\mathsf{Enc}(a)$ and $b$, you can compute $\mathsf{Enc}(a \cdot b^{-1} \bmod{n})$ by simply computing $\hat{b}=b^{-1} \bmod{n}$ and $Enc(a)^\hat{b} \bmod{n^2}$.

Paillier encryption is built on the bijeective mapping from $(x,y)\in \mathbb{Z}_n \times \mathbb{Z}_n^*$ to:

$E_{g,n}(x,y)=g^x y^n \bmod{n^2}$.

Generator $g$ is chosen to enforce that $x$ remains in $\mathbb{Z}_n$ (i.e., there exists a $y$ that makes $x$ unique in $\mathbb{Z}_n$). Specifically, it has order $\alpha n$ for a positive $\alpha < \mathrm{LCM}(p-1,q-1)$. A simple optimization is to set $\alpha=1$ by choosing $g=n+1$.

Regardless of variant, in the encryption scheme, $x$ is the message and thus $\mathbb{Z}_n$ is the message space. Contrary to the other answers, this allows $b$ to be generally inverted $\bmod{n}$ (except when 0 or in the negligible case that it is either $p$ or $q$).

Given the confusion, I did a sanity check in Mathematica to make sure (I picked small safe primes but you can set them using RandomPrime):

p = 23;
q = 83;
n = p*q;
lam = LCM[p - 1, q - 1];

L[u_] := Quotient[u - 1, n];

Trap[y_] := L[PowerMod[y, lam, n^2]];

g = RandomInteger[{1, n}];
While[GCD[Trap[g], n] != 1, g = RandomInteger[{1, n}]]

Enc[m_] := Module[{r, c},
  r = RandomInteger[{1, n - 1}];
  c = Mod[PowerMod[g, m, n^2]*PowerMod[r, n, n^2], n^2]
  ]

Dec[c_] := Mod[Trap[c]*PowerMod[Trap[g], -1, n], n];

m = RandomInteger[{1, n - 1}];
s = RandomInteger[{1, n - 1}];
si = PowerMod[s, -1, n];
c = PowerMod[Enc[m], si, n^2];
Dec[c] == Mod[m*si, n]

This answer is the result of a crash course in Paillier. I typically work in the discrete logarithm setting. Feel free to edit if there are any errors (you probably do know more than me).


To attempt such a proof you need a definition of what security properties an IV-based stream cipher is supposed to provide.  For example, like this (very informally):

A nonce-based cipher is secure if and only if its encryptions are indistinguishable from random bitstrings of the same length to a nonce-respecting adversary that's allowed to carry out a chosen-plaintext attack.

The "nonce-respecting" bit is important, because one of the key assumptions in a PRF is that it's supposed to be secure against adversarially-chosen inputs, and the inclusion of "nonce-respecting" in such a definition is to give the adversary as much control over nonces as we can get away with.  (Note not all ciphers meet this standard—e.g., CBC-mode encryption doesn't, because it requires random nonces. Evaluating whether Trivium meets this standard is a whole 'nother topic.)

So if encrypting message $p$ with key $k$ and nonce $n$ is notated as $Enc^n_k(p)$,
then your proposed PRF construction would be:

$$
PRF_k(m) = Enc^m_k(0^{80})
$$

...where $0^{80}$ is the 80-bit all-zero string.  And what you want to prove is that, given a secret, random choice of $k$, if an attacker who can choose messages $m$ could distinguish your PRF apart from a random function, then they could break the underlying nonce-based cipher.

In this case, that follows by observing that if there was such a chosen-message attack they could mount against the PRF, it would imply the existence a corresponding attack on the cipher by querying for the encryption of the same plaintext $0^{80}$ repeatedly but with different, adversarially-controlled nonces.


Reed Solomon secret sharing and as a one-time symmetric key?

Suppose the 10 000-bit message is uniformly distributed and we split it with a $t$-of-$n$ scheme.

With Shamir's secret-sharing where each share is 10 000 bits apiece, if you have only $t - 1$ shares, the $t^{\mathit{th}}$ share has $2^{10~000}$ possible values with uniform distribution, and so the conditional distribution on the secret given $t - 1$ shares can (and does) have 10 000 bits of entropy.
With a conventional erasure coding scheme like Reed–Solomon where each share is 100 bits apiece, if you have only $t - 1$ shares, the $t^{\mathit{th}}$ share has only $2^{100}$ possibilities to determine what the secret could be, so the conditional distribution on the secret given $t - 1$ shares can't have more than 100 bits of entropy—in other words, you can narrow the secret down to a minuscule fraction of the possible subspace.  (If it had fewer than 100 bits of entropy, then it wouldn't be a very efficient erasure code.)

The question you might ask is: Which subspace of the message space does the erasure code use?  Here's a simple 2-of-3 scheme, sometimes called RAID-5: divide the secret into 5000-bit halves $s_1$ and $s_2$, and use $s_1$, $s_2$, and $s_1 \oplus s_2$ as the shares.  A single share reveals a lot about the original message!  So, not very useful for encryption.

What about Reed–Solomon?  We interpret a $t\ell$-bit message $m = (m_0, m_1, \dots, m_{t-1})$ as a degree-$(t - 1)$ polynomial $m(x) = m_0 + m_1 x + m_2 x^2 + \cdots + m_{t-1} x^{t-1}$ over $\operatorname{GF}(2^\ell)$, and evaluate it at $n$ distinct points, say $\{0, 1, \alpha, \alpha^2, \dots, \alpha^{n-2}\}$ where $\alpha$ is a generator of $\operatorname{GF}(2^\ell)$.  Note that the first two shares in this perfectly reasonable choice of Reed–Solomon code are $m_0$ and $m_0 + m_1 + m_2 + \cdots + m_{t-1}$.  Still not very useful for encryption.

‘But you just chose the evaluation points pathologically!’  Well, OK, but let's say you used $\{\alpha, \alpha^2, \dots, \alpha^n\}$ for fixed $\alpha$.  There's a trivial known-plaintext distinguisher for a ciphertext $(c_1, c_2, \dots, c_{t-1})$ and key $c_t$ where $c_i = m(\alpha^i)$: simply evaluate the polynomial at the evaluation points and compare to the putative ciphertext.

What if $\alpha$ were part of the key too?  Well, then $\alpha$ is one of the at most $t - 1$ roots of the degree-$(t - 1)$ polynomial $m(\alpha^i) - c_i$ for each $i$, which we can compute in a known-plaintext attack by standard root-finding.

What if we randomize the first message block too?  Well, there distinguisher still basically works except we have to see whether $m(\alpha^i) - c_i$ (here $m$ is taken to have zero constant term) is the same randomized first block for all $i$.  We could randomize all but one of the message blocks, but then we're just back to Shamir's secret-sharing.

There's another way: We could apply an all-or-nothing transform (AONT), and then use one of the shares as a secret key.  With an efficient erasure code, this is obviously as secure as the AONT itself.  (AONTs were not developed until well after the McEliece–Sarwate note.)

There's still a practical problem with using this as a cipher: How does the recipient get the key if it is determined by the plaintext?  Maybe you actually want a public-key cryptosystem, but it's not clear to me how to get one out of this—although you can get one out of other error-correcting codes, also due to McEliece, where you encapsulate a secret key in the syndrome of a random error under a hidden Goppa code, and derive a key by hashing the error.

So, this idea is mainly useful for storing a message that is already randomized like a large secret key, where knowledge of part of it doesn't help.  Of course, if we want to make sure that the subspace of messages covered by an incomplete set of shares is at least (say) 256 bits for modern security, we might as well just make the secret be 256 bits itself and use a key derivation function to derive a larger key from it.  For storing longer structured secrets, the McEliece–Sarwate is slightly more efficient than just encrypting them, splitting the ciphertext with Reed–Solomon, and splitting the key with Shamir.

Maybe there's a broader use for the McEliece–Sarwate observation but it's not obvious to me!

The standard caveat about secret-sharing applies too: Whenever you reconstruct the secret, someone has to have the whole secret in one place to use it, and could sequester it away.  So if you ever use it, there's a single party with unilateral access to whatever power the secret grants.  Many applications for which secret-sharing might be tempting are better served by higher-level multiparty computation like threshold signatures where no party ever has unilateral power of some central secret.


Is it safe to use pairing-based cryptography in a commercial product?

Pairing-based cryptography has been and is currently used in commercial products sold by Voltage Security, which was recently acquired by HP Enterprise. They seem to have sold the products with a fair amount of success, so there is at least some evidence that a product using pairing-based crypto can work. However, there are two pretty major caveats:

Intellectual property restrictions. HPE owns many patents related to pairing-based crypto, and if you use them without paying a licensing fee you could be the target of a lawsuit.
Cryptanalysis. The hardness assumptions underlying pairing-based crypto are still pretty new and haven't received as much cryptanalytic scrutiny as, say, factoring or ECDLP. This means that choosing parameters for the cryptosystem you're planning to deploy is tricky. For example, a parameter regime you think is offering 128 bits of security could be shown to only offer 80, which is not a very comfortable margin. Changing the parameters after you already have paying customers is difficult at best, and choosing large parameters to account for cryptanalytic advances can make your system slow.

The threat of cryptanalytic attacks is not an abstract one - the situation I described above happened recently to the Zcash anonymous cryptocurrency. If you really want to use pairings in a product I would recommend hiring a consultant who knows the area well to choose the parameters.


Say, $X= a\cdot b$, where $(a, b) \in Z_q^*$ and $q$ is a large prime. If $X$ is given, then what is the complexity (or hardness) of finding $a$ and $b$?

If the multiplication is done within $Z_q^*$, then it's easy - pick an arbitrary nonzero $a$ and compute $b = a^{-1}X$; you're done.  You can compute $a^{-1}$ by either the Extended Euclidean method, or by using $a^{-1} = a^{p-2}$

This will find a $(a, b)$ pair that satisfies the equation.  If you're looking for the unique one that someone else had in mind, well, you're out of luck - there are $q-1$ pairs that satisfy the equation, and with no other information, there is no way to determine which is the correct one.


PKCS#1 contains 4 padding schemes, of which only 2 are suitable for encryption, but only of small data blocks (like up to hundred bytes): the modern RSAES-OAEP, and the obsolete RSAES-PKCS1-v1_5 (which drawbacks include being harder to guard against decryption oracle attacks on the padding). PSS, aka RSASSA-PSS, is strictly for signature.
For comfortable security, AES-GCM-SIV with a random 256-bit key encrypted per RSA-4096 using RSAES-OAEP with SHA-512 and MGF1 using SHA-512, would tick all the boxes (on crypto algorithm choices, ignoring implementation isssues) except resistance to hypothetical quantum computers usable for cryptanalysis. The modern baseline would be RSA-2048 using RSAES-OAEP with SHA-256 and MGF1 using SHA-256.


Encryption with two meanings without computer or programming

This is possible, and it's called deniable encryption. The idea behind this type of encryption is that if you are required (e.g., under subpoena) to provide a key to decrypt your ciphertext, then you can provide an "alternative key" that decrypts it to something else.

However, this is complex, and you cannot do it by hand. In general, it's difficult to do, even by machine.


Is it correct to use MAC instead of HMAC for short?

In general, no.
MAC is a much more general concept than HMAC and thus such an equivalence in saying is clearly inacceptable. However, if you are talking about a specific protocol which authenticates its payload, saying "the MAC" to designate the MAC algorithm or the tag for messages, even if they use HMAC, is fully acceptable, because you are referring to the use of the more general concept with the concrete instantiation here.

Now to answer the question in the title (which will also catch question #1):

  TLS Finished message: is it MAC or HMAC?

The answer is both.
Yes, HMAC is always used here to compute the (correct) PRF value, which is only possible if the same transcript was seen and the same master_secret was generated. Thus the authentication is built-in.

However, prior to this message, the ChangeCipherSpec message was sent for the record-layer protocol, enabling the use of the negotiated cipher suite. So the Finished message is actually send using the (now) encrypted and authenticated record-layer protocol, which does use the MAC specified in the cipher suite (e.g. GMAC or Poly1305).

The relevant quote from the RFC is:

  The ChangeCipherSpec message is sent during the handshake after the
  security parameters have been agreed upon, but before the verifying
  Finished message is sent.