When does a multiple Vignere cipher become intractable? Multiple Vignere ciphers do not repeat the key until the message gets longer than the LCM of the cipher lengths.  Are messages shorter than that safe?  If not, what is the attack strategy?

I believe there is a known plaintext attack which has an algebraic solution if the message is longer than the sum of the cipher lengths.  Are messages shorter than that safe?

Are messages shorter than the longest key in the set of ciphers safe?

Yes, if you know the key lengths and have a sufficient amount of known plaintext, you can easily recover the keys (or at least something equivalent to them) using linear algebra.

How much is "a sufficient amount"?  Well, to fully recover all the key characters, you would need to solve as many linear equations as there are characters in all the keys combined, and would thus need at least that many ciphertext/plaintext character pairs to get a unique solution.

However, in general, some of those equations will be redundant, because multiple Vigenère encryption has equivalent key(set)s.  This implies that a) you cannot, in general, fully recover the original keys, but b) you can generally recover an equivalent set of keys with less known plaintext than the combined length of all the keys.

The exact amount of redundancy will depend on the key lengths.  As an extreme example, encrypting a message with two keys of length $a$ and $b$, where $a$ is an integer multiple of $a$, is obviously equivalent to encrypting it with a single key of length $a$.

More generally, adding a constant to all characters of one key and subtracting the same constant from all characters of another key obviously won't change the result of the encryption.  By choosing suitable constants, we can transform any set of keys to an equivalent one where (e.g.) the first character of each key except one is zero.  So, in general, a set of $n$ keys with total length $\ell$ can have at most $\ell - n + 1$ non-redundant characters, and thus finding an equivalent keyset requires at most that many known plaintext characters.

(Of course, that's assuming that each ciphertext/plaintext character pair actually contributes to the solution.  Depending on where the known pairs are located in the message, this may not always be the case, either.  For example, trivially, two ciphertext/plaintext character pairs separated by a distance that is divisible by the least common multiple of the key lengths will be encrypted with the same key characters, and thus knowing them both won't provide any more information about the key than just knowing one of them.  On the other hand, I would conjecture — but cannot prove off the top of my head — that a sequence of $\ell - n + 1$ consecutive ciphertext/plaintext character pairs should always be sufficient to find an equivalent keyset.)

If all the key lengths are coprime, I believe $\ell - n + 1$ ciphertext/plaintext character pairs is also the minimum number needed to fully determine the key set (up to equivalency).  Otherwise, fewer should be sufficient.

Also, yes, if the message is no longer than the longest key, and that key is fully random, independent of the other keys and used only for one message, then the system is equivalent to a one-time pad, and thus provides perfect secrecy.

Essentially, this is because just encrypting the message with that one key is sufficient to provide perfect secrecy, and anything else we do with the message cannot compromise that.

In fact, since Vigenère encryptions commute with each other, we can always arrange them so that the encryption with the long random one-time key happens last.  Thus, we can treat the result of all the other encryptions as the plaintext input to a one-time pad scheme, which of course perfectly conceals its input.  Thus, nothing about any of the other keys matters in any way, as long as at least one of the keys satisfies the criteria (randomness, independence, length, non-reuse) for being a secure one-time pad.


Use Microsoft word and digital certificates to notarize documents (USA) I'm trying to figure out how notaries public in the USA could use Microsoft Word and the popular X.509 digital certificates to notarize a document. Lets make four assumptions about the state law:

The notary gets to pick the technology; the state government does not restrict this.
The notary and the signer meet in person with their computers.
The signer and the notary each have their own digital certificate and their own computer.

The notary is required to apply a seal after the signer has signed, and the seal is a jpeg image.

The problem is, the notary isn't allowed to add the seal image until after the signer has signed. But if the notary adds the seal image after the signer signs, Microsoft Word considers the document invalid because the addition of the image is an alteration.

Ideas?

I feel like the JPEG seal is the problem. why is it being used? the digital signature should be more than sufficient. the seal does nothing but complicate the whole process.

But lets assume you MUST add the seal. One solution is to keep them segregated. instead of appending the seal to the document, have both parties digitally sign the document. then afterwards have the notary edit the seal with the documents name and author name and date. then he can digitally sign that as well. sending both of these documents together as separate entities.

EDIT: on a side note, most notaries for any documents that I have used have a sort of cover letter they draft up stating they have indeed seen and verified the documents. This perhaps is the best place to put that seal. Since it already has the document name date and notarized author. A natural fit for the segregation method I stated earlier.


How can I accomplish Key Derivation in JavaScript? I need to take a potentially weak user password and derive a strong key for AES encryption in JavaScript. How can I do this?

I expect the hardest problem is generating a good random salt - perhaps an SSL request could be used to ask a server to provide half of the salt. This would work but I'd rather keep it simple if possible.

Should I use bcrypt? Perhaps with however many iterations are necessary to hit about 1 second on slow hardware (current model smartphones).

I only need to support modern browsers, my userbase is small and everyone is a geek.
The derived key will be used to encrypt plaintext passwords with AES, similar to how LastPass works.

Okay, for key derivation in the browser you will be using third party libs.

If you want to be the absolute top of the line then scrypt (potential lib to consider) is your best bet with a medium to high work factor based on what your users are going to be using. Bcrypt works but is not memory hard so take that into consideration. (Even 5MB of memory usage could severely impede the usage of custom hardware to attack your keys)

A salt can be derived from the crypto.getRandomValues which takes a typed array and returns it filled with trustworthy random data.


Memory-hard proof-of-work: are they ASIC-resistant? Is a memory-hard proof-of-work scheme necessarily resistant to speedups from custom ASICS?

Background: Bitcoin uses a proof-of-work scheme based on SHA256 hashing.  The scheme is compute-bound.  Initially, people would mine solutions on their PCs or GPUs.  However, eventually it was noticed that a custom ASIC (a custom-designed hardware chip) can compute SHA256 hashes much more rapidly and thus a custom ASIC can mine more efficiently and more rapidly, so people built custom ASICs that can compute SHA256 hashes much faster than any general-purpose CPU.  Today ASICs have a 100x advantage over mining on your PC, so PC-based mining is not very competitive.

Some folks have proposed fixing this by designing a memory-hard proof-of-work scheme.  A memory-hard scheme is one that fundamentally requires some minimum amount of memory (e.g., 1GB of RAM) to solve efficiently, and where there are no useful time-memory tradeoffs.  These are hard to design, but suppose we were able to construct one.  For instance, Cuckoo Cycle is one plausible attempt at such a scheme.  Suppose we use Cuckoo Cycle, or we find another scheme.  I've seen it argued that such a scheme would end the monopoly of ASICs and thus make mining more democratic, because ASICs can speed up computation-bound tasks but not memory-bound tasks.

Here's my question.  Is this argument correct?  More specifically, is it true that memory-hardness is enough to ensure that ASICs won't have much of an advantage over general-purpose CPUs?  What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip?

What prevents an attacker from building a custom ASIC and buying off-the-shelf DRAM chips, and building systems that pair each ASIC with a DRAM chip?

DRAM memory is already pretty optimized for random memory accesses per second per dollar. Since a memory bound PoW spends more time waiting for memory than doing computation, there's little point in using an ASIC to speed up the computation. The bottleneck is DRAM latency. The ASIC is just a very expensive way to spend a larger fraction of time waiting for memory...

Also see related discussion at reddit.com/r/Bitcoin/.
For reference purposes (and in the unlikely case Reddit shuts its doors), here’s a copy of my post there:

hashcash functions must be cheap to verify to achieve their purpose.

  And thus memory hardness can only be achieved by going beyond the hashcash proof of work, as I wrote about in “Beyond the Hashcash Proof-of-Work (there’s more to mining than hashing)”, published at  cryptorials.io.

  The desirability of a memory hard PoW for a high market cap crypto currency is an open question with no easy answers and one that deserves more study.

  I think it could be desirable if it can radically change the economics of mining, to the point where mining is profitable for no one. That means that even the (hypothetically) most energy-efficient ASIC with custom memory technology, would still not have a positive ROI, due to the following reasons:

  fabrication costs are going to be much larger than for whatever memory technology is used for commodity computing devices, which still enjoy much larger economies of scale.
  electricity costs, while lower than for commodity memory, are unlikely to to be more than an order of magnitude lower.

  and the main reason:

  huge numbers of people could be willing to mine at a loss, just as they are happy to play the lottery. this requires a very low barrier to entry, like one click to install a mining app on your phone that will make it mine overnight while charging. it helps to know that your mining efficiency is not more than (roughly) an order of magnitude worse than with custom hardware.

  Of course I'm not claiming this is a likely scenario, but I think it's at least imaginable...

  Another possibility to consider is having 2 PoWs: one compute bound, and one memory bound, splitting the blocks between them. Mining the compute bound one would be (barely) profitable with ASICs, while the mining the memory bound one would be unprofitable, but help decentralization.

  Still, unprofitable mining is by no means a requirement for making memory hard PoWs desirable.

  It is conceivable that any memory technology developed to make the PoW's memory accesses as energy efficient as possible, will benefit many other classes of computation especially in mobile, solar powered, and other low-powered settings, as thus inevitably lead to commoditization.

  This argument works best for PoWs that do as little computation as possible apart from memory accesses, and I believe this is where Cuckoo Cycle's edge trimming shines.


Can two files/strings have the same SHA-256 value? I was wondering whether, theoretically, 2 files can have the same SHA-256 value.

Since there are only $16^{256}$ or $2^{1024}$ SHA256 sums, all 1024-bit files (with $2^{1024}$ different combinations) will have to have different SHA256 sums (if I'm not mistaken).
Additionally, for files with larger file sizes (such as, let's say, 2048-byte files, where there are $8^{2048}$ = $2^{6144}$ different combinations), there will have to have 2 files with the same SHA256 sums.

And, once there are two files with the same SHA256 sums, what then? Will that mean that SHA256 sums are broken?

Thanks for feeding my curiosity.

I'm not sure where you're getting $16^{256}$. SHA-256 produces a hash that
is $256$ bits long, so there are $2^{256}$ possibilities.

So, let us consider all $256$-bit inputs. Will they map onto the set of
$256$-bit SHA-256 outputs, one-to-one, no collisions? Almost certainly
not.

If we were encrypting $256$-bit blocks, then yes, they would, because by
definition encryption has to be reversible, so encryption algorithms do
map things one-to-one. But secure hash algorithms are not designed in
this way.

So, instead of thinking there are $2^{256}$ inputs, and $2^{256}$ outputs, and
therefore they're one-to-one, instead think that you are selecting from
a set of $2^{256}$ items, randomly, with replacement. There will probably be
many collisions. Some inputs will map to the same output.

And, of course, once you start considering longer inputs, there are more
inputs than outputs and collisions are inevitable, by the pigeonhole
principle.

However, this does not mean that SHA-256 is broken. Not at all. This
problem of collisions is inherent in any secure hashing system, but
still, we use secure hashes and they work. We wouldn't be able to buy
things online if they didn't work.

In theory, there are collisions, yes. But a hash is only broken if there
is a practical way to generate collisions on purpose. Thus far, no one
has published any such attack on SHA-256, or any of the SHA-2 family of
hashes.


Useful pairings for cryptography I've recently looked a bit at pairing based cryptography and I was wondering what properties the groups involved should have in order to be useful for cryptographic purposes? Has anything more exact been formulated? As an example, we could just take the pairing

$\mathbb{Z}_p\times \mathbb{Z}_p\to \mathbb{Z}_p,\;\; (x,y)\mapsto xy,$

where the group is the additive subgroup of $\mathbb{Z}_p$. Clearly, this would not be terribly useful for cryptographic applications, since picking any nonzero $a\in \mathbb{Z}_p$ as a generator, we can trivially solve the discrete logatithm problem in this additive group. Hence any standard formulation of Diffie-Hellman can be solved as $c$ from $ca$ can be solved just by multiplying with the inverse of $a$, which is efficiently computable. How do we differentiate between ''good'' and ''bad'' groups?

That depends on the protocol being used, but most pairing-based protocols assume that the Bilinear Diffie-Hellman (BDH) problem is hard: given $P, aP, bP, cP$ for group element $P$ and integers $a, b, c$ it is hard to compute $e(P, P)^{abc}$ for a given pairing $e$.

There are many related problems that, if broken, could be used to break the BDH: the discrete logarithm, the Computational Diffie-Hellman (given $P, aP, bP$ compute $abP$), etc.


Storing RSA private key Currently I'm developing an application where users generate their own pair RSA keys in order to achieve a secure communication with my server. Also clients are able to communicate directly, sending signatures (proving authentication, as PGP does), therefore I cannot use Diffie-Hellman for this scheme.

Indeed, I'm aware of some techniques of storage of private keys. I thought on enciphering them with AES-256 asking the user an alternative password since using their personal/client password could be a risk if my server gets compromised and the attacker counts with clients private key's ciphertext somehow.

I was thinking about https://en.wikipedia.org/wiki/Zeroisation. Just decipher the ciphered private key and delete it from memory when not needed. Also I read some info about TPM, but I'm afraid this only concerns cryptographically secure hardware equipment and other devices based on vendor's signature verification before booting (maybe I'm not right with it).

I would want to know which is the "best way" for storing private keys in the clients computer, because I cannot store them in my server.

I am currently hoping to find an answer to a similar problem, but maybe I can share some ideas. I would say that your problem is more standard than mine, and therefore it has the benefit that the existent options are relatively standard. However, my own question made me realize that key storage is an information security problem, as opposed to a cryptographic problem. With this, I mean that there is no provable best approach, but there are techniques and good practices that could help to mitigate risks, given some threat model.

Said threat model is, in fact, the most critical aspect to determine what is relevant. There are some approaches in terms of good practices, but they should be considered more as suggestions than as a checklist or a perfect answer.

One aspect that seems to be relatively agreed upon is that the encryption should happen within an environment separated from the normal processor (i.e. TPM, HSM, smart cards). I haven't looked into TPMs, but the other two seem to be the standard way to go.

Now, if additional hardware is out of the table, I can see that your approach makes sense in general. I would worry for the way in which each copy of the key is handled (encrypted and unencrypted, in RAM and in disk, in active usage and in backup), and the way in which the password is used for encryption. In particular, the less the key exists in plaintext, the better.

But mind the threat model. Knowing what you are concerned about is key to know whether your defenses are actually defending you.


What approach is used here? Here is an image hidding some information.
I need to discover, what is the hidden text.

I tried to interpret this as 27 letter alphabet(with space) in columns, tried this with Ceasar cipher.
No meaningfull English word has occured.

Does somebody have an idea what else can I try?

You tried interpreting this as a ternary code written in columns, but why not in rows?

It was really quite simple to solve.

Here's the code I used:

for n in ['110','012','111','120','112','001','011','012']:
    x = int(n,3) + 64
    if x==64:
        x=32
    print chr(x),

and here's the answer:

   LEMONADE


Enhance CSPRNG output If I XOR the output from 2 CSPRNG will the result be better (more random) than the output from either one?
Assume one of the PRNG is biased.

If you XOR two independent streams of two random number generators together then the result is as strong as the strongest of the two.


Interpolation in the Exponent (Shamir Shared PRF) Trying to implement the Diffie-Hellman distributed PRF mentioned by Cachin : https://cachin.com/cc/papers/abba.pdf.

It makes sense to me... just use the same Lagrange coefficient I'm using to combine shamir shares, but instead use exponentiation and multiplication ... so the interpolation is happening in the exponent.

But something isn't working out.

Right now I'm simply doing this for each share:

shares[i].data = pow(gen, shares[i].data, prime)

Then (essentially) this to combine:

comb = 1
for share in shares:
   comb *= pow(share.data, lagrange[share.index], prime)

I'm using pycryptodome's implementation of SSS and pulling out the coefficient calculations.   I know that when I do this on the unmodified secrets they recombine just fine, so the L vals are OK:

comb = 0
for share in shares:
   comb += share.dat * lagrange[share.index] % prime

I think the issue is doing all this exponentiation in a prime field breaks things... maybe I need to choose the generator (base) more carefully... but it doesn't seem to matter what I choose.

I tried using ECC instead instead of g^secret (which is probably better anyway, since some generators could fail to explore the prime field properly and need to be chosen correctly)... I'm using the secp256k1 field prime.   Shares are modified (Gen * share) and combined via:

comb = [None,None]
for share in shares:
   comb = curve.add(comb, curve.mult(curve.import(share.data), lagrange[share.index])

But I get the same issue (nondeterministic results).

Does anyone know of a library in any language that does this sort of  "combination of modified secrets"?   The Cachin paper seems to address it as a pretty trivial solution to the distributed PRF problem.   I'm fine with the random oracle model assumptions.

(If I could see a working example of any version, it would probably be obvious what I'm doing wrong.)

The answer to this is that you need to select "gen"  not randomly, but specifically as a generator of order P (your modulus prime used for shamir).

For secp256k1 field of size P this works:

Select R = P*4-1.
Select a gen=H(w) such that pow(gen, P, R) == 1
During reconstruction choose R as the modulus

Now you've basically chosen a field R of order P, and everything will reconstruct correctly.

With ECC, you'd need to use curve.n as your modulus during sharing, but then you'll run into trouble with "hashing into the curve".  See: https://eprint.iacr.org/2009/226.pdf to use ECC.


What are some of the best prime factorization algorithms and their effecitvity I was wondering aren't the most used prime factorization algorithms a symbolic mile behind the security of the RSA cryptosystem?
The way it looks to me is that every time an algorithm is able to crack RSA or in specific to find the two prime factors, you can just simply change the size of the prime factors.
Is it really that simple?
Anyways thank you all for your time and effort!

Is it really that simple?

If it weren't we would have to abandon RSA.
Here's why: To be able to run RSA somewhat decently fast, it needs to run in polynomial time in some parameter, let's call it $\lambda$. RSA is basically the same as modular exponentiation and thus runs in time $\mathcal O(\lambda^3)$ when $2^\lambda\approx n$. Now the best known generic factorization method, the GNFS runs in time $L_n\left[\frac13,\sqrt[3]{\frac{64}9}\right]=\exp\left(\left(\sqrt[3]{\frac{64}9}+o(1)\right)\cdot\sqrt[3]{\ln{2^\lambda}}\cdot\sqrt[3]{\ln{\ln{2^\lambda}}}^2\right)$, which is sub-exponential in $\lambda$. So if we double the key length (that is $\lambda$), we may 8-fold our workload, but we also take the attacker's workload to the power of at least $\sqrt[3]2$, which turns an $2^{80}$ attack into an $>2^{110}$ attack, thus increasing the attack complexity by at least a billion.

Now assume we could factor in time $\mathcal O(\lambda^n)$ for some somewhat small $n$. Now if we double the key length, we (the legitimate user) take 8-times the time, but the attacker now only takes $2^n$ times the time, so if he has $2^{n-3}$ as many cores or as good cores, he could recover the new key in the same time as before. So we'd have to repeat the increase in key length a few times (assuming $n\leq 20$) so that we, the user, get an edge of the attacker, but at this point key length become so large that RSA will be too slow to be good choice, especially if you consider low-power embedded systems.


Differential privacy definition Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between these distributions is multiplicative, i.e.

$\left| \frac{Pr[A(D) \in S]}{Pr[A(D') \in S]} \right| \leq e^\epsilon$

I have difficulty in understanding this choice of this multiplicative distance measure, as opposed to the standard distance (statistical difference) as in cryptography (indistinguishability), i.e.

$|Pr[A(D) \in S] - Pr[A(D') \in S]| \leq neg(.)$

The paper "Calibrating Noise to Sensitivity in Private Data Analysis" by Dwork et al. put forth two reasons for using the multiplicative distance:

It is more stringent, since if one probability is 0, the other must also be 0 (which is not guaranteed when using standard measure of statistical difference). This, I understand.
The leakage (distance between the distributions) must be non-negligible for the utility of the mechanism. This I really struggle to understand. Could anyone give an simple example to illustrate this, please?

I can't give an example illustrating why leakage must be non-negligible for the utility of the mechanism, but I can give a proof of why leakage must be non-negligible for the utility of the mechanism.

Let $\;\; U \: = \: \left\{\langle D,D'\rangle : D,D' \text{ differ in one element}\right\} \;\;\;$.

By the triangle inequality, for all $D$ and $D'$, for all $S$,

$|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|$
$\leq$
number_of_elements $\cdot \operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\}$

If number_of_elements is polynomial and $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})\:$ is negligible, then

for all $D$ and $D'$, for all $S$, $\:|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)|\:$ is negligible.

If number_of_elements is polynomial and

$\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$

is negligible, then $A$ is statistically close to being independent of $D$.

Therefore, if $\:\operatorname{sup}(\{|\operatorname{Pr}(A(D) \in S)-\operatorname{Pr}(A(D') \in S)| : \langle D,D'\rangle \in U\})$

is negligible then the mechanism is not useful.


Is elliptic curve point multiplication semantically secure? Is elliptic curve point multiplication semantically secure? I'd like to know if there are some sets of elliptic curve parameters (e.g. NIST curves) that are proved to be semantically secure or that are not disproved.

By "elliptic curve point multiplication is semantically secure", I mean the following:

Suppose an elliptic curve over a finite field $\mathbb{F}_p$ where $p$ is a prime number. The equation is $y^2 = x^3 + ax + b$. $G$ is a base point and it generates all the points $E = \{G, 2G, ..., (q-1)G, \mathcal{O}\}$ in the curve. Here $q$ is prime and it is the order of the curve. We have the following cryptosystem:

The encryption of a point $P$ ($P \ne \mathcal{O}$) is $sP$ where $s$ is a random secret key and $1 \le s < q$.
The decryption of a point $Q$ is $s^{-1}Q$ where $ss^{-1} \equiv 1 \mod q$

Suppose there is a set of $n$ distinct points $\{P_1, P_2, ..., P_n\}$ and their encryptions $\{Q_1, Q_2, ..., Q_n\}$ with a secret key $s$. The orders are not necessarily the same, i.e. $Q_1$ might or might not be the encryption of $P_1$. If it is infeasible to determine which encryption belongs to which point better than random guessing, then this cryptosystem is semantically secure.

If an attacker can choose the points $P_i$, than this system is not semantically secure. For example, they may choose $P_2=2P_1$, and the corresponding encryption $Q_2$ would be equal to $2Q_1$.

If the points are chosen at random, this system is semantically secure if decisional Diffie-Hellman assumption holds for the curve. This assumption is presumed to hold for elliptic curves typically used in cryptography, unless the curve is chosen to have a bilinear pairing.


What is a multi-target attack? What exactly is a multi-target attack? How does the attack work on different cryptographic schemes (block ciphers, hash functions, elliptic curves)? How can it be avoided?

A multi-target attack is an attack on many users of a cryptosystem at once.

The attacker might be satisfied with breaking one user—for example, if there are a thousand human rights activists in a network under attack by an authoritarian state, breaking into the Signal chats of one activist may be enough to compromise the whole network.

Moreover, the state's intelligence agency may have many more targets than the one activist network—there may be an environmental activist network, an anticorruption activist network, foreign intelligence networks, different branches of government, etc.—and it is in the state's interest to break into any of these.

Of course, there may actually be only one human user who has many keys—for example, a thousand (say) HTML documents encrypted with different AES keys derived from a master key with HKDF-SHA256, so the adversary has the ciphertext for the same plaintext <!DOCTYPE html>\n under many different keys.  More generally, a multi-target attack is an attack on many instances of a cryptosystem: many keys with known plaintext/ciphertext pairs under the same cipher, many group elements with the same discrete log base, many public keys for the same signature scheme, etc.

There are many different batch advantages that multi-target attackers might take advantage of—you asked about block ciphers, but it's worth noting several different settings because their qualitative differences can lead to substantial quantitative security differences:

For a hash function $H$, the adversary may have hashes $H(k_1),$ $H(k_2),$ $\dotsc,$ $H(k_t)$ for $t$ different unknown target keys $k_1, k_2, \dotsc, k_t$.  The goal is to recover any one of the $k_i$.  Examples of $H$:

AES in CTR mode on a known file header:
$k \mapsto \operatorname{AES}_k(0).$
A message authentication code under HMAC-SHA256 on a TLS record:
$k \mapsto \operatorname{HMAC-SHA256}_k(\text{‘250 OK’}).$
A seed phrase from which a cryptocurrency address is derived:
$\mathit{seedphrase} \mapsto \operatorname{X25519}(\operatorname{HKDF-SHA256}(\mathit{seedphrase}), \underline 9).$

The best generic multi-target preimage search algorithms—parallel versions of Oechslin's rainbow tables and Rivest's distinguished points—have area*time cost proportional to $2^\lambda\!/t$ evaluations of $H$ where $\lambda$ is more or less the size of the $k_i$.

That is: The cost of a generic preimage search to break the first of $t$ targets is $1/t$ the cost of a generic preimage search to break one specific target.  Have a thousand activists to target?  It'll cost a thousand times less to compromise one of them if you attack them in a batch than if you try to attack them one by one independently.  It will still cost $2^\lambda$ to find all of the target keys, but you usually don't need to wait that long.

How do these algorithms work?

You might think of a multi-target ‘speedup’ as populating a hash table ht and then replacing the single-target test for a candidate key H(k) == h by H(k) in ht which also runs in ‘O(1)’ time but tests $t$ keys at once.  However, this simplified algorithm doesn't actually reduce the adversary's area*time cost—which is generally a good proxy for cost in, e.g., yen to power a machine for long enough to find the key—because for very large numbers of keys it spends lots of time sequentially waiting for communication due to memory latency twiddling thumbs that could have been spent running random walks in parallel.  Instead:

Rainbow tables.  We do a pseudorandom walk on the space of inputs and compute a chain of $$\sigma_0 \xrightarrow{H} h_0 \xrightarrow{R_1} \sigma_1 \xrightarrow{H} h_1 \xrightarrow{R_2} \cdots \xrightarrow{H} h_\ell,$$ alternating between inputs and hashes with a family of reduction functions $R_i$ mapping a hash back to some other input, e.g. yielding a 128-bit candidate key or a candidate BIP39 passphrase.  We store the starting point $\sigma_0$ and the ending point $h_\ell$.

Actually, we don't do this just once; we do this in parallel on a large number $p$ of randomly chosen starting points.  We also compute the ending point in chains starting at $H(k_i)$ as if it were $1, 2, \dotsc, \ell$ iterations from the end:

\begin{align*}
    \sigma_{1,0} \xrightarrow{H} h_{1,0}
                 \xrightarrow{R_1} \sigma_{1,1}
                 \xrightarrow{H} h_{1,1}
                 \xrightarrow{R_2} \cdots
                 &\xrightarrow{H} h_{1,\ell}, \\
    \sigma_{2,0} \xrightarrow{H} h_{2,0}
                 \xrightarrow{R_1} \sigma_{2,1}
                 \xrightarrow{H} h_{2,1}
                 \xrightarrow{R_2} \cdots
                 &\xrightarrow{H} h_{2,\ell}, \\
    \vdots \\
    \sigma_{p,0} \xrightarrow{H} h_{p,0}
                 \xrightarrow{R_1} \sigma_{p,1}
                 \xrightarrow{H} h_{p,1}
                 \xrightarrow{R_2} \cdots
                 &\xrightarrow{H} h_{p,\ell}; \\
    H(k_1) \xrightarrow{R_1} R_1(H(k_1))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{1,1}, \\
    H(k_1) \xrightarrow{R_2} R_2(H(k_1))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{1,2}, \\
    \vdots \\
    H(k_1) \xrightarrow{R_\ell} R_\ell(H(k_t))
           &\xrightarrow{H} h'_{1,\ell}; \\
    \vdots \\
    H(k_t) \xrightarrow{R_1} R_1(H(k_t))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{t,1}, \\
    H(k_t) \xrightarrow{R_2} R_2(H(k_t))
           \xrightarrow{H} \cdots
           &\xrightarrow{H} h'_{t,2}, \\
    \vdots \\
    H(k_t) \xrightarrow{R_\ell} R_\ell(H(k_t))
           &\xrightarrow{H} h'_{t,\ell}.
  \end{align*}

Then we sort all the ending points—the $h_{j,\ell}$ and the $h'_{i,r}$—and look for a collision among them.  If we find a collision $h_{j,\ell} = h'_{i,r}$, then we can start up again at $h_{j,0}$ and compute forward by $\ell - r$ steps to find a candidate input $\sigma_{j,\nu}$ if $H(\sigma_{j,\nu}) = H(k_i)$.  (Of course, $H(\sigma_{j,\nu})$ may turn out not to be $H(k_i)$ if two random walks happened to collide temporarily, but false positives should be fairly rare.)

The batch advantage arises in part because in the sorting step, we are effectively simultaneously testing all hashes from the $p$ parallel chains against the $t$ target hashes (with some false positive rate), at cost about $(p + \ell t)^{1.5}$ of sorting a $(p + \ell t)$-element array rather than at cost $\ell\cdot p\cdot t$ of testing all $\ell\cdot p$ guesses directly against all $t$ hashes (with zero false positive rate).  When $p \geq t^2$, the net reduction in cost is a factor of about $t$.
Distinguished points.  We pick small subspace of points in the key space that are easy to discern, say those whose first 23 bits are 10100011110110001010, and call them distinguished points.  Again we will do many independent pseudorandom walks in parallel, but instead of stopping after exactly $\ell$ iterations, we will stop when we find a distinguished point.

On $p$ parallel machines, we pick starting points $h_j$ uniformly at random from the key space and iteratively compute $H(h_j),$ $H(H(h_j)),$ $\dotsc,$ $H^\nu(h_j)$, until either $H^\nu(h_j)$ is a distinguished point, in which case we store $h_j$ and $H^\nu(h_j)$, or $\nu$ exceeds a limit $\ell$, in which case we throw it out and start over with a different $h_j$:

$$h_j \xrightarrow{H} H(h_j) \xrightarrow{H} H^2(h_j) \xrightarrow{H} \cdots \xrightarrow{H} H^\nu(h_j).$$

We also iteratively compute $H(H(k_i))$, $H(H(H(k_i)))$, etc., for each $i$, until we find a distinguished point $H^\mu(k_i)$.  Then we sort the $H^\mu(k_i)$ and the $h_{j,\nu}$, and if there is a collision $H^\mu(k_i) = H^\nu(h_j)$, we start over at $h_j$ and iterate $H$ until we find a candidate $k_i$: $$h_j \xrightarrow{H} \cdots \xrightarrow{H} H^{\nu-\mu}(h_j) \stackrel?= k_i \xrightarrow{H} H(k_i) \xrightarrow{H} \dotsc \xrightarrow{H} H^\nu(h_j) = H^\mu(k_i).$$  Of course, this might also happen because of a collision in $H$ elsewhere causing the two chains starting at $h_j$ and $H(k_i)$ to spuriously merge, so there's some false positive rate.

Again, the batch advantage arises in part because in the sorting step, we are effectively simultaneously testing all hashes anywhere in the $p$ parallel chains against the $t$ target hashes at cost $(p + t)^{1.5}$ rather than $\ell\cdot p\cdot t$, with some false positive rate arising from collisions in $H$.

(Extending distinguished points with reduction functions to make the technique work on, e.g., password spaces is left as an exercise for the reader.)

For detailed analyses of the expected costs and success probabilities, see Oechslin's paper and Wiener's paper (paywall-free).  (To my knowledge, the distinguished points technique first appeared in an abstract by Quisquater and Descailles at CRYPTO 1987 and in the followup paper at EUROCRYPT 1989, but it is usually credited to Rivest.)

What countermeasures can you use as the user or cryptosystem designer?  The standard two options are:

Make $\lambda$ so large that a factor of $t$ doesn't matter.  Don't use AES-128 for a 128-bit security level—use AES-256.  (Even better, use ChaCha so you can largely forget about side channel attacks.)  In general, always make sure that the narrowest pipe of secret key material is 256 bits wide.
Separate the input spaces.  For example, salt your password hashes, so that instead of having hashes $H(p_1),$ $H(p_2),$ $\dotsc,$ $H(p_t)$ for secret passwords $p_1, p_2, \dotsc, p_t$, the adversary will have salted hashes $H_{\sigma_1}(p_1),$ $H_{\sigma_2}(p_2),$ $\dotsc,$ $H_{\sigma_t}(p_t)$, which thwarts the batch advantage of the rainbow table and distinguished points algorithms.

This can be applied to block ciphers too, e.g. with randomly chosen initialization vectors, but there are costs: extra data transmission, limited block sizes for randomization, the implied secret key inside the randomly chosen IV, missed opportunity to detect replay attacks or nonce misuse, etc.

Input space separation also doesn't make it any harder for the adversary to find your key in particular, so you personally have little motivation to choose a cryptosystem with input space separation; it only makes it harder for the adversary to find anyone's key.  In contrast, using a 256-bit key provides you and the herd immunity against brute force.

But generic key search is not the only setting where multi-target attacks might be relevant.  Here are some others:

For a DLOG group with generator $g$—e.g., RFC 3526 Group #14, or Curve25519, or secp256k1—the adversary may have the powers $g^{x_1},$ $g^{x_2},$ $\dotsc,$ $g^{x_t}$ for $t$ different unknown target exponents $x_1, x_2, \dotsc, x_t$.  The goal is to recover any one of the $x_i$.

Of course, this can be solved by any generic preimage search under the hash function $H\colon x \mapsto g^x$, but there are much cheaper algorithms that cost $O(\sqrt q)$ where $q$ is the largest prime factor of the order of $g$—a combination of Pollard's $\rho$ and Pohlig–Hellman, and Pollard's kangaroo if more information is known about the ranges of the $x_i$, as well as other alternatives like baby-step/giant-step.  For specific groups there may be speedups too over generic algorithms, like the elliptic curve negation map in Pollard's $\rho$.

The cost to find the first of $t$ target discrete logs cannot be much cheaper than finding one target discrete log!  Why?  Fix a single target $h = g^x$, and pick $g^{r_1},$ $g^{r_2}$, $\dotsc,$ $g^{r_t}$ for uniform random exponents $r_i$; then apply a multi-target attack to $$(h g^{r_1}, h g^{r_2}, \dotsc, h g^{r_t})$$ to find $\log_g (h g^{r_i})$ for some $i$, figure out what $i$ was by a linear list search at worst, and finally return $$\log_g (h g^{r_i}) - r_i = \log_g (h g^{r_i}\!/g^{r_i}) = \log_g h.$$  So a single-target DLOG can't be substantially more expensive than a multi-target DLOG attack, because this shows how to use a multi-target DLOG attack to perform a single-target DLOG attack at essentially negligible additional cost.  In other words, having multiple possible targets can't make a DLOG attack cheaper the way it can make a generic key search cheaper.

This is why, for example, Curve25519 should be considered to have a ‘128-bit security level’ while AES-128 should not: in the multi-target setting of the real world, the cost of breaking the first of $t$ target Curve25519 keys is still about $2^{128}$—the same as the cost of breaking one target Curve25519 key—while the cost of breaking the first of $t$ target AES keys is only $2^{128}\!/t$.

On the other hand, there is still a cost reduction to finding all of the $t$ targets with parallel $\rho$: while it's $O(\sqrt q)$ for the first of any number of targets, it's $O(\sqrt{tq})$ for all of $t$ targets rather than $O(t\sqrt q)$ for a single-target attack repeated $t$ times—that is, a multi-target attack to find all of $t$ keys is a factor of $\sqrt t$ cheaper than $t$ independent single-target attacks.  There may also be an advantage to precomputation: for finite fields, the best DLOG algorithms factor into an expensive target-independent precomputation that can then be done once and then reused over and over again to quickly attack many targets in the same group, leading to attacks like logjam.  An intelligence agency could use that to intercept TLS conversations in real time.
For a Diffie–Hellman function $f(n, P)$ with standard base point $B$—e.g., FFDH under RFC 3526 Group #14, or X25519—the adversary may have the public keys $f(n_1, B),$ $f(n_2, B),$ $\dotsc,$ $f(n_t, B)$, for $t$ different unknown DH secrets $n_1, n_2, \dotsc, n_t$, along with oracles for $P \mapsto H(f(n_i, P))$ by claiming to have public key $P$ and trying to have an encrypted conversation with the $i^{\mathit{th}}$ user.  The goal is to recover any one of the $H(f(n_i, f(n_j, B)))$ shared secret keys used by user $i$ and user $j$ to have a private conversation.

Of course, when $f(n, P) = [n]P$ in a group written additively, this can be solved by any generic DLOG algorithm.  But the oracles provide additional information that could be exploited—Lim–Lee active small subgroup attacks if the points $P$ live in a group of composite order, Cheon's strong DH attack if the key derivation function $H$ is the identity.  These themselves don't provide batch advantages, but they are evidence that the DH problem is qualitatively different from the DLOG problem, so in principle it may admit batch advantages that DLOG does not.
For a signature scheme the goal is to forge a message/signature pair $(m, \sigma)$ under any of $t$ public keys $A_1, A_2, \dotsc, A_t$.  The story depends on the details of the cryptosystem; see an analysis of Schnorr signatures in the multi-target setting for example.  The countermeasure chosen by EdDSA, for example, is to hash the public key in with the message to limit the avenues for multi-target signature forgery.


Diffie-Hellman and secret key size How can one guarantee that the generated DH secret key is of certain length? Say 256bit. Actually, prime length is not enough since the remainder of the last process, the modulus, may result in too small number.

Once you have computed a DH shared secret, $g^{ab}$, you always hash the result, $k = H(g^{ab})$, before (authenticating it and) using it as a secret key—and preferably, hash the entire transcript of the conversation so far that went into it, like $k = H(g^a, g^b, g^{ab})$, to prevent an adversary from tweaking any part of the handshake that is not authenticated.

The hash $H$ is sometimes called a key derivation function, and there are standard examples like HKDF, often with an extract/expand structure: let $k = \operatorname{HKDF-Extract}(g^a, g^b, g^{ab})$ be the master shared secret key, and then derive subkeys for different purposes by $k_1 = \operatorname{HKDF-Expand}_k(\text{‘first purpose’})$, $k_2 = \operatorname{HKDF-Expand}_k(\text{‘second purpose’})$, etc.


Why Boneh-Franklin BasicIdent IBE is not chosen-ciphertext secure? Why use random oracle? I don't know why BasicIdent is not chosen-ciphertext secure. If there are anybody who knows well, please explain it to me with example.
Moreover, I don't know random oracle and its usage for security analysis.

First, recall that in a chosen-ciphertext attack (CCA) model, the attacker has access to a decryption oracle. A scheme is said CCA-secure if access to a decryption oracle does not give any advantage to the attacker.

Knowing this, a very simple CCA attack can be done on BasicIdent. I will use the description of the scheme from Wikipedia.

As you can see, ciphertexts in BasicIdent are tuples of the form
$$c = (u,v) = \left(rP, m \oplus H_2\left(g_{ID}^r\right)\right)$$

The important thing here is that the second term of the ciphertext is simply the message XOR'ed with a hash. So, in the IND security game, the attacker can take the challenge ciphertext $c^* = (u^*, v^*)$ and produce a new ciphertext $\hat c = (u^*, v^* \oplus \hat m)$, for some random message $\hat m$. This new ciphertext must  be accepted by the decryption oracle since $c^* \neq \hat c$. The result from the decryption oracle is $m_b \oplus \hat m$, and the attacker can trivially extract the original message $m_b$ from this since he knows $\hat m$.


Is it possible to retrieve the original hash of a digital signature using a public key? I am running a server that is receiving packets. Each packet is signed with an RSA 512 SHA-256 digital signature. I have a public key and exponent that I use to verify the digital signatures.
I'm currently trying to do this in Python using Cryptodome. I am able to verify signatures but am unable to get the original hash.
If verification is failed, I want to obtain the original hash that was signed. Is there a way to do this with the public key?

Yes, this is usually possible. You can use the RSA public key to:

perform modular exponentiation using the public exponent and modulus (raw RSA, sometimes you can use raw RSA decrypt with the public key for this);
interpret the result as unsigned big endian integer (usually this is already the case);
perform the unpadding (usually this just means finding the hash within the padding).

Note that there are multiple RSA schemes possible, e.g. PKCS#1 v1.5 padding or PSS padding. It depends on the signature generation which one is used. For an insecure 512 bit key you would generally bet on PKCS#1 v1.5 padding.
You can find both schemes in the relatively readable PKCS#1 RFC which includes the full description of above steps. However, it ends with creating the padding from an existing hash instead and compare, you need to reverse the padding creation instead - this isn't hard for PKCS#1, but you would not be able to do it for PSS as the hashed (mHash) value is hashed again (to get a hash value H).
For PKCS#1 v1.5 padding the hash value is just the hLen bytes that are right before the last byte, where hLen is the hash size in octets / bytes. Of course you'd still have to validate the rest of the padding as well to perform full signature verification.

If you are very lucky then decryption with the public key while choosing the PKCS#1 decryption scheme will directly give you the hash. But note that decryption generally requires the private key and a different unpadding scheme (also generally referred to as PKCS#1 padding, but the padding for encryption is still different than that for signature generation). However, it may just choose the signature unpadding instead for compatibility reasons.


PRG existance and P versus NP how can we prove that if there is a secure PRG then P!=NP or in reverse order?(is there any reduction?)

a secure PRG is a pseudo random generator that for every eficient (running in probabilistic polynomial time) statistical test algorithm A , A cannot distinguish PRG from a truly random generator with a non-neglogible advantage.

"Negligible" means "within $O(2^{-p})$" where p is a security parameter associated with the algorithm.

I know that we must use a reduction. reducing P!=NP to existance of PRG or reverse.but how to reduce?

suppose we have a secure PRG , then for every "eff" adversary A , A cannot distinguish PRG from a truly random function with a non-negligible advantage. so it implies that there is no polynomial time algorithm to solve it without having the key. and it shows that P!=NP.

Is my reduction correct?

First, note the following:

If one-way functions exist then P!=NP (src)
Pseudorandom generators exist if and only if one-way functions exist (src)

From there the proof is trivial.

Now, I wanted to explain (or at least try as this stuff is not my expertise) why the reduction you have in the question is not sufficient.

NP does not mean not-polynomial time, it means nondeterministic polynomial time. Your reduction argues that there is no poly time algorithm. That says nothing about whether or not there is a nondeterministic poly time algorithm. You would have to first show that there is a nondeterministic poly time algorithm, then show that there is not a poly time algorithm (or vice-versa). There may be other problems with the reduction in the question (again this is not my area of expertise). For example, the argument seems to be circular. Hopefully others can comment on this.


Safe primes and subgroups I've been reading about safe primes and their use in: Cryptography Engineering by Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno.
Having a safe prime $q$ with $q=2p+1$ where $p$ is a Sophie Germain prime
They claim that the elements of the subgroup $p$ are the elements that are preferred to be used. Why?
Why not the elements in $2p$?

The Decisional Diffie-Hellman assumption, on which the key-exchange would be based on does not hold in $\mathbb{Z}_q^*$. The reason is that the Jacobi symbol "leaks" information about the shared key. Therefore one, instead, works with the subgroup of $\mathbb{Z}_q^*$ of order $p$, which is intuitively obtained by "quotienting out" this information. (This group is sometimes called the Schnorr group.) You can read the details on why DDH doesn't hold here (Exercise 2).


private keys for multiple devices I have an architecture where:

a user can have multiple devices (phones)
the server needs to broadcast the payload to all devices through the same channel
(basically, all devices listen and receive the same payload)

Now, I need encryption for messages from server to devices.

the first phone will have to create a private/public key
server will use this public key to send encrypted messages.
How do I solve the problem for the other devices? Is this mechanism (private/public) wrong and not appropriate in such case? User can't obviously ssh between devices to exchange data here...

The encryption protocol itself has not been chosen yet. If you believe one is more appropriate in this case, let me know!

A simple solotion could be that all phones need to have the same pre-shared key.
The pre-shared key could be downloaded once at first run, maybe from a password protected httpS site, or maybe from a url that delivers an encrypted and signed file with private/public key.

Then the pre-shared key is used on all phones, and it is used to encrypt by the sender, and decrypt by everyone else.

This simple solution provides only encryption, because  this is what the only requirement of the original question.

This doesn't address all security issues, for example replay attack and impersonation.
If you needed more than just encryption, then the solution will have to be a bit more complex.


In perfectly secret scheme, if key and message space are uniformly distributed, is ciphertext space always uniform as well? Following up on a similar question, Does perfect secrecy imply uniform ciphertext distribution?, the answer seems to be that in a perfectly secret encryption scheme, the distribution of the ciphertext space is not necessarily uniform because the message space is not always uniformly distributed (although the key space is assumed to be uniform).

Question: If we say that the message space and key space are uniformly distributed, this seems to me to imply that the ciphertext space must also be uniform. How would one go about proving this fact?

Question: If we say that the message space and key space are uniformly
  distributed, this seems to me to imply that the ciphertext space must
  also be uniform. How would one go about proving this fact?

You don't because this statement is false.
Here's a simple counter-example:

Let $k,m\in\{0,1\}$ be a key and a message bit, both chosen uniformly at random. Then let the ciphertext $c=m\oplus k\parallel 0$, that is you do the standard OTP encryption and append a zero bit. Obviously this scheme is perfectly secret because the OTP is and the zero bit is completely independent of the key and the message. Also obviously the ciphertext doesn't have a uniform distribution from the set $\{00,01,10,11\}$ because $11$ cannot occur.

A more interesting (new!) question though would be though whether for each length-preserving perfectly-secret encryption scheme the ciphertext follows a uniform distribution.


Using the a multiple of the x coordinate as a private key ECDSA specs require private key ($d$) to be a random integer ($r$) in the range $[1, N-1]$, where $N$ is the order of the base point ($G$). What if the private key instead is set to the x-coordinate of the EC point $r \cdot G$ (i.e., $G$ added $r$ times)?

What if the private key instead is set to the x-coordinate of the EC
  point $r\cdot G$

Then your "private" key is the x-coordinate of your public key and thus public, unless you also want to redefine how the public key is constructed.

Additionally, the idea of ECDSA / Schnorr signatures is to prove knowledge of a solution to the discrete logarithm problem at the example of a message hash and if your private key is the x-coordinate of a point, you don't know said discrete logarithm and thus also need to come up with a new signature scheme.


Compression in Symmetric Encryption? When using symmetric encryption is it important to compress the data first?

I think that compression will make data look "more random" and therefore be more difficult to crack, but I am not sure if this is a requirement.

Could compression be necessary for some ciphers but not for others?

When using symmetric encryption is it important to compress the data first?

No, not really (unless you're concerned with bandwidth usage).  On the other hand, compressing the message can leak data (for example, how compressible the data is).

  Could it be the case for some ciphers but not for others?

No, or at least, not for any cipher that we would consider secure.  If there is a cipher that is marginal enough for this to matter, we would consider that cipher to be insecure (and ought to be replaced by something where this doesn't matter).

It might be of some marginal help if the key is weak.  For example, if the key is based on a guessable password, compressing the plaintext might make it marginally more difficult (because, to test a trial password, the attacker would need to decrypt slightly more before being able to check to see if the decryption is plausible).  On the other hand, if you were close enough to the margin where this matters, you're in danger anyways.


Is HMAC-SHA256 a PRF? In the abstract of The Exact PRF-Security of NMAC and HMAC, Gazi, Pietrzak, and Rybar state:

NMAC was introduced by Bellare, Canetti and Krawczyk [Crypto’96], who proved it to be a secure
pseudorandom function (PRF), and thus also a MAC, assuming that (1) f is a PRF and (2) the function we get when cascading f is weakly collision-resistant. Unfortunately, HMAC is typically instantiated with cryptographic hash functions like MD5 or SHA-1 for which (2) has been found to be wrong.

This implies that HMAC-SHA1 and HMAC-MD5 are not PRFs. However, I'm not sure whether SHA-2 (particularly, SHA-256) is considered to satisfy (2) from their abstract, and thus whether HMAC-SHA2 (particularly, HMAC-SHA256) is a PRF. I'm further confused by result from Bellare, 2006 which seems to contract the more recent paper by proving that collision resistance of the underlying function is not necessary in order for an HMAC to be a PRF.

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.


Is my XTEA encryption key safe if I publish my firmware both as plain text and encrypted? I'm using this bootloader that implements XTEA encryption for uploading an encrypted firmware to small MCU:

https://github.com/nyholku/diolan-plus2

the actual XTEA code is here:

https://github.com/nyholku/diolan-plus2/blob/master/fw/xtea.asm

It is not my code but to me it looks like it uses 16 byte key and 64 iterations
and seems to be pretty much equivalent to the wikipedia XTEA C-implementation.

Now my questions is, is my encryption key safe if I publish my firmware both as plain object code i.e. plain text and encrypted?

The firmware size if max 48kB out of which several kilobytes at the end will be 0xFF.

How about if over the years I publish number of ( <50 ) such plain text / encrypted text pairs?

I've read from the interweb that this should be safe but because the subject is so complex I would like to make sure I don't make a rookie blunder.

What you are describing is called a known plaintext attack. Modern ciphers should be even secure if the adversary chooses the plaintext to encrypt. That would be called a chosen plaintext attack (CPA), and a cipher that protects against is called CPA-secure. Actually, it goes even a bit further than that: IND_CPA means that the ciphertext is indistinguishable from random even if the adversary choses the plaintext.

Basically you can publish any amount of pairs and still be secure. This of course isn't the case anymore if the cipher gets broken. The cipher is completely broken if a key can be retrieved by a CPA attack. Fortunately no such attack is known against XTEA. But note that there are no ciphers that can be proven to be secure.

However, XTEA is a block cipher. A block cipher isn't a generic cipher by itself. It needs a mode of operation to turn into a real cipher. This mode of operation should be initialized using an initialization vector. Without a unique or random initialization vector the ciphertext may leak information about the plaintext. For instance, if you would encrypt two different versions of the same firmware you could see where changes were made.


Losing entropy after re-hashing a hash Suppose you have a string AAA that was hashed with SHA1 to produce 606ec6e9bd8a8ff2ad14e5fade3f264471e82251.

If I rehash 606ec6e9bd8a8ff2ad14e5fade3f264471e82251 10x times with the same SHA1 algorithm, would the entropy keep on decreasing?

If so, would it ever reach a dangerous level to a point where AAA could be recovered?

P.S: SHA1 was just an example. Ideally, I'd use BLAKE2b or a SHA3 candidate.

Let's assume your actual input/output has entropy (which it doesn't for a given string or output hash value).

  If I rehash 606ec6e9bd8a8ff2ad14e5fade3f264471e82251 10x times with the same SHA1 algorithm, would the entropy keep on decreasing?

Yes, but by ever so tiny amount. Hashes are designed so that every bit is dependent on all the bits of the input. Hashes do get into so called cycles after iterating quite a few times, showing that entropy can and does decrease. It is however unlikely to influence practical situations.

The initial hash will of course extract the entropy into a maximum of slightly less than 160 bits.

  If so, would it ever reach a dangerous level to a point where AAA could be recovered?

That's of course nonsense statement; the amount of entropy doesn't influence the one-way-function property of a cryptographic hash function at all.

Let's take an extreme and assume that, after a while, all many messages will generate the same hash (a next to impossible situation in itself). Then the (Shannon) entropy will be lowered. So in this situation it becomes more likely to generate this iterated hash by trying out different messages.

However, if you try and revert it you will find many messages instead of one, and it is impossible to detect which one is the original input message. So if anything, you've just made the function harder to reverse.

As example: I've "hashed" all bits of a fully random message into a single bit by XOR-ing them together. Entropy is hugely decreased to a single bit worth of it. Which message did I use to create this one bit of entropy, even if you (get to) know it is 0 or 1?


Length extension attack SHA-1 message division with padding problem? I'm was reading this example for length extension attack given here
link

When working out, how the extended block length be divisible by 512 (SHA block size).

I'm assuming following:-

In SHA, the size of the blocks is 512 bit.
The last block must contain:the rest of data in message (mod 512).
some filling (padding)
the last 64 bits as length

In example given in link shared above, this is what extended msg looks like

http://example.com/downloadfile=report.pdf%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%A8/../../../../../../../etc/passwd&mac=ee40aa8ec0cfafb7e2ec4de20943b673968857a5

Example 1
Calculating

A more precise of asking is that,
message =10 bytes = 80 bits
secret key = 11 bytes= 88 bits
168 mod 512= 160 bits= 21 bytes
64 - 21= 43
padding +message length= 464+552 =1016 bits
adding /../../../../../../../etc/passwd 32 x 8= 256 bits
Adding it to A8/=  424

How I make sense If I add the missing padding which is 256 mod 512 =256=32 bytes

64-32  = 32 x8= 256 bits

Example 2

count=10&lat=37.351&user_id=1&long=-119.827&waffle=eggo\x80\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00
          \x00\x00\x02\x28&waffle=liege

Going on by logic

message =55 bytes = 440 bits
secret key = 14 bytes= 112 bits
length encoding = 552
552 mod 512= 40 bits= 5 bytes
64 - 5= 59 bytes
If you check the padding its 58 bytes not 59 . Can you tell why?
padding +message length= 472+552 =1024 bits
adding extra &waffle=liege 13 x 8= 104
adding to existing message length(552) + 104= 656
How I make sense If I add the missing padding which is 656 mod 512 =144
= 18 bytes
64 - 18= 46 x 8 = 368 bits
104 + 368 (message length and padding)

OK, lets go through this step by step:

the message size of http://example.com/downloadfile=report.pdf is 10 bytes, as only the filename (report.pdf) is hashed according to the article;
the key size is usually known and was explicitly set in the article to 11 bytes, not 15 (11 bytes is a bit short for a key size, by the way);
so the length of the message is 10 + 11 = 21 bytes, or 168 bits and A8 is indeed 168;
to the padding + length encoding needs to be 64 - 21 = 43 bytes, lets check that:
%80%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%00%A8
yep, that seems to be correct.

Note that 64 bytes is 512 bits for the block size and that e.g. %80 is the encoding of a single byte with value 80h, so you need to count the characters and then divide by 3.

So I'm not sure how you got your input values for the message size and key size, but they are way off. So you would not end up with the right values, regardless of the correctness of your formulas.


How to prove to a third-party that a given response came from a specific domain? Suppose I've got a response from a website using https. Is it possible to store the certificate and keys exchange to prove to a third-party that the response came from that domain?

No, at least for standard ciphersuites, TLS/https does not allow proving to a third party that an https payload was received from a certain domain.

Problem is, the initial TLS handshake leads to symmetric keys known by both parties, used to secure the rest of the exchange. Thus each party can forge messages and pretend the other side sent them.


Is it possible that a SHA256 hash has the same hex character over and over again? In theory, there are infinite inputs, that you can hash with SHA-256. So theoretically it would be possible that one hash string would read 0xaaaaaaaa...
But would that also be possible practically, or do the algorithms check that this is not happening?

First of all, the output of SHA-256 is binary and consists of 32 bytes (256 denotes the output size in bits). What you are talking about is apparently the hexadecimal encoding of these bytes.
The possibility that you are talking about is called (1st) pre-image resistance (Wikipedia):

Given a hash value $h$, it should be difficult to find any message $m$ such that $h = \text{H}(m)$.

("difficult" is a non-technical term here, generally we use "computationally infeasible", obviously there will be messages that map to any hash value, the difficulty is finding them for a one-way hash)
No, the algorithms do not check this explicitly, because the algorithm by itself needs to be resistant against it. Furthermore, the repetition of certain bits is not that special all by itself. It would be unclear what you would need to test for.
"But would that also be possible practically" well, no, unless SHA-2 gets broken. Generally it is collision resistance that gets broken first. That means finding a hash where $\text{H}(m) = \text{H}(m')$ for any $m$ and $m'$. This is easier to attack because an attacker can try and find weaknesses in the algorithm that create an internal collision while controlling both $m$ and $m'$. SHA-256 is still considered secure in this regard.


How does concatenating diverse hash functions affect collision resistance? Let's suppose I take 3 different types of hash functions and concatenate them for future safety so that: digest = Hash3( Hash2( Hash1( text )))

Does the birthday attack mean in this case that I must double the input data set size of every hash function starting from the end?

If so, does it mean that if the output hash function had to have a 128 bits digest, the middle one must have a 256 bits long digest, and the first one 512 bits in order to gain a collision resistance that takes 2^64 trials?

Hash3( Hash2( Hash1( text )))

The collision resistance of $H'(x):=H_3(H_2(H_1(x)))$ is most likely $\operatorname{CR}(H')=\min(\operatorname{CR}(H_3),\operatorname{CR}(H_2),\operatorname{CR}(H_1))$, that is the combined scheme is at most as collision resistant as any individual scheme. Of course it has to be admitted that for most choices of the three hash functions, you don't have enough control over the input of $H_2,H_3$ to exploit structural collisions.

So the two main strategies to find collisions in this construction are:

Find a structural collision for Hash1, i.e. something like what was found for SHA-1 or MD5, or
Find a generic collision against any of the three hash functions, i.e. run through $2^{n/2}$ messages for $n$ being the minimum of the hash function output lengths in bits. Note that if an intermediary has a small output, e.g. 128-bit then finding a collision there will propagate the collision to the end.

  Does the birthday attack mean in this case that I must double the input data set size of every hash function starting from the end?

No, see above.

  If so, does it mean that if the output hash function had to have a 128 bits digest, the middle one must have a 256 bits long digest, and the first one 512 bits in order to gain a collision resistance that takes 2^64 trials?

No, see above. Also note that we usually model hash functions as outputting random values and no matter what you do with that output, you can't deterministically make more messages than could have been generated. That is, if you have $2^{128}$ possible hash outputs, you can't magically, deterministically make $2^{256}$ possible inputs to the next hash function out of that.


How long to bruteforce a RSA key Suppose I have a 2048 bit RSA public key, and want to brute force the corresponding private key. I guess there are 2048^16 possible combinations?

How long would this take me to brute force with an i7, with a GPU, and with Amazon Cloud?

Is there any benchmarking data, that can be used to calculate similar for a 16 bit key, or a 1024 bit key?

Thanks

We do not know the number of possible combinations, since the exact numbers of 1024 bit primes is unknown, but it is MUCH larger than $2048^{16}$. I do not know how you guessed this number, but here are some estimates:

For N with 2048 you need primes p,q with 1024 bit each. There are $2^{1023}$ numbers with this length (a leading 1 and then 1023 binary digits).

According to the prime number theorem, we get this:
$$
\pi(2^{1024}) \approx \frac{2^{1024}}{ln(2^{1024})} \approx\frac {2^{1024}}{710}\approx 2^{1014.53}
$$

Similar you can approximate the number $\pi(2^{1023})$ to almost exactly 1 bit less, and subtract those primes (all the primes with lower length). This leaves still over $2^{1013}$ prime numbers of the according size.

However, the list of all prime numbers is way too huge and does not exist. This is beyond the capability of all computation power on earth for a couple of millenia.


Asymmetric Cryptography Confusion - 'Sign' a file to guarantee its source What I want to do is use asymmetric crypto to guarantee that a file comes from a source. I have software that runs on lots of wireless devices, and each of those has a license file with an encrypted date that they expire. I'd like to be able to encrypt it in the office and have the devices decrypt/read the date. The purpose of using asymmetric crypto is so someone can't pull the key out of the software and encrypt their own license file. We want to be the only ones who can generate a license file.

I'm mildly familiar with RSA asymmetric cryptography. My understanding is you encrypt with the public key and decrypt with the private key. I read on https://stackoverflow.com/questions/6352023/rsa-can-you-create-a-public-key-from-a-private-key that the private key comes with the public key by RSA Specification, so I can't just reverse it and keep the private key on the devices and the public key at the office, or is there a way for me to get around this?

What sort of encryption should I use for what i'm trying to accomplish?

You should resort to digital signature to solve your problem. If RSA is used to generate digital signature, private key is first used to "decrypt" the file that you want to sign. The software can verify the "decrypted" file comes from you since it was "encrypted" using your public key.


Some information about zero knowledge proofs How do I start studying Zero-Knowledge proofs? What are some good books and entry-level research papers on that topic? What are some prerequisites of the same?

This depends a bit on your background and what you are interested in. Philosophically speaking, zero-knowledge proofs are easy to understand (correctness, soundness and zero-knowledge), while the technical details often can be very complex. See https://en.wikipedia.org/wiki/Zero-knowledge_proof for a nice intro and non-cryptographic examples.
I think the ZKProof Community Reference (https://docs.zkproof.org/reference.pdf) gives a good intro to zero-knowledge proofs, but maybe the best (cryptographic) example is Schnorr signatures, which you can think of as a zero-knowledge proof of knowledge of the secret key corresponding to the public signing key (see e.g. https://datatracker.ietf.org/doc/html/rfc8235 or https://web.stanford.edu/class/cs259c/lectures/schnorr.pdf). This is a fundamental protocol, and many other zero-knowledge protocols (often called Sigma-protocols, see https://docs.zkproof.org/pages/standards/accepted-workshop4/proposal-sigma.pdf or https://www.cs.au.dk/~ivan/Sigma.pdf) builds upon the same structure. Finally, I can recommend this talk by Dan Boneh: https://www.youtube.com/watch?v=wB3DlND7KEw.


Chosen plain text and chosen ciphertext definitions clarification I am trying to understand a concept of CPA and CCA attack and I cannot get one thing from the definition.

If an attacker can execute a CPA attack for something like Send 100 dollars to attacker that will mean he will get a valid encryption for this message. Now according to the definition of the CCA attack the adversary should send another ciphertext not equal to the just obtained one.

What prevents an attacker from just sending the received ciphertext to the recipient who will think that this is the legitimate message? Or in other words why in the definition is the attacker only allowed to send other messages.

The idea behind these models is to model an adversaries capabilities. To get reliable security the worst case for a capability is modelled. Let's start with chosen plaintext attacks (CPA):

In this game the adversary is given access to an encryption oracle. This models the case where an attacker knows (parts of) the message. For example, the British knew during WWII that German messages will always end with "Heil Hitler" and this was what allowed them to break their encryption. Now, as I said we always want to model the worst case, so let's assume the adversary knows the whole plaintext. For a good encryption scheme this should not give him any advantage. Besides, there might be some messages that are more beneficial to an attacker than others. A good encryption scheme should also be secure in this case. So, that's why we allow the attacker to chose the messages which are encrypted. Thereby we can make sure that even for the most beneficial message the adversary can not break the scheme.

In some cases the above might already be enough. However, sometimes it might be the case that the adversary can learn the plaintexts for some ciphertexts. For example, the decrypted values might be output by an application which the adversary can somehow access or they influence the behaviour of an application which can be observed. Hence, we might also want to cover this case. This leads to the stronger notion of security against chosen ciphertext attacks (CCA). To model the above we give the adversary access to a decryption oracle. The motivation behind allowing the adversary to decrypt arbitrary ciphertexts is the same as above, i.e. modelling the worst case.

These notions define something we call a learning phase. It models what an adversary might be able to learn about the used encryption scheme and the used keys. However, the goal of the adversary is to attack a ciphertext for which he does not know the plaintext, yet. And of course it is about a ciphertext for which he was unable to learn the plaintext from one of the above "side-channels". This is normally modelled in one of two ways.
Either in terms of semantic security which says that an adversary can learn nothing about a plaintext given its ciphertext, or in terms of indistinguishability of ciphertexts (IND). Luckily, these two notions are equivalent and I will not talk anymore about semantic security as it is more complicated to explain the details.

In the case of IND, the adversary is allowed to choose two different messages. One of the two messages is chosen at random and the adversary will receive back the encryption of it. Now the goal of the adversary is to tell which message's encryption he received. As I said before, we want to model the case where the adversary is unable to learn something about the plaintext from a side channel. Hence, he is not allowed to ask its decryption oracle for the decryption of this plaintext.


Encryption of exe file I recently started learning cryptography. I have learned some basic stuff. I'm  also started learning about pc security, so I was wondering how do hackers use cryptography for bypassing antivirus software?  I don't have some deep understanding on how Antivirus software works but I know that every Antivirus has base of signatures, so when we scan exe file it actually compares signature of exe with signatures in it's own base, and if it matches, Antivirus will identify exe as malware. So by applying some cryptographic algorithm on exe file, they change signature of exe, so antivirus can't detect it as malware, right? But concretely, how do they apply cryptograpyic algorithm on exe file? I saw only in my book how plaintext is crypted. There is no information about crypting exe files there (or I didn't see it). I use book "Applied Cryptography, Bruce Schneier". Maybe this was stupid question but don't blame me, I'm amateur :) If there is some book covering this matter, please suggest it to me, I will be grateful.
Thanks in advance

The term "plaintext" in cryptography does not imply that the input is actual text. Traditionally, the plaintext was often actual text, but the term just refers to the input (other than the key) to the encryption algorithm. Plaintext can be a sequence of letters, like in many classical ciphers; it can be an analog telephone signal; it can be an image or map; it can be whatever the cipher uses as an input. In modern digital ciphers, the plaintext is a stream of bits, possibly with length constraints, because that's the kind of data you already have when you're working with computers. Modern ciphers can handle any stream of bits (again, possibly within those length constraints); it doesn't matter what the stream of bits represents. An EXE file is a stream of bits, so it can be encrypted.


Number of cycles in cipher feedback mode (CFB) How many cycles are there in a CFB mode of operation?

Say for example I use AES encryption in CFB mode. How many times will this cycle before outputting the final ciphertext? In the picture below this is done in 3 cycles. Are there any rules on the amount of cycles before outputting the final ciphertext? I may be way off but it's a bit confusing with this specific mode of operation.

In CFB-mode you effectively have a data-dependent stream cipher and you'll need $\lceil\frac{l}n\rceil$ block cipher calls or "cycles" as you call them to process the full message, where $l$ is the mesage length (in bits), $n$ the block size (in bits) and $\lceil\cdot\rceil$ is the ceiling function.
However, you get the encryption of the $i$-th plaintext block after the $i$-th "cycle" or block cipher call. This can be seen if you look at the formal definition of the CFB-mode which reads (in this case):
$$c_i=p_i\oplus E_K(c_{i-1}),\quad c_0=IV$$

where $c_i$ is the $i$-th ciphertext block, $p_i$ is the $i$-th plaintext block, $\oplus$ is bitwise XOR and IV is an initialization vector.


Mapping of message onto elliptic curve and reverse it? I would like to perform a variant of Elliptic Curve ElGamal in java using the BouncyCastle libraries.

I currently face the difficulty of mapping a message $m$ onto the elliptic curve $E_p$. I have so far multiplied the generator $g$ of $E_p$ by the message $m$. However, this is hardly reversible. Hence I cannot retrieve the original message without storing a lookup table for my whole message space.

The post ElGamal with EC quotes that some reversible mapping exists, described in Elliptic Curve Cryptosystem, Koblitz.

After doing some research, I found Mapping an Arbitrary Message to an Elliptic Curve when Defined over $GF(2^n)$, King et al.. However it looks quite cryptic to me, and I believe there must exist some library doing this already.

Is there any widely used mapping available? Also, is there any library implementing this?

When using ElGamal on elliptic curves you have two possibilities:

Encoding free Version of El Gamal

Use a version of ElGamal such as "hashed ElGamal" that avoids the task of mapping
messages to points on the curve. In standard ElGamal on elliptic curves you would compute
the ciphertext as $(C_1,C_2)=(kP,M+kY)$ where $k$ is a random integer, $M$ the message $m$
mapped to a point on the curve, $Y$ the public key and $P$ the generator point.

In hashed ElGamal, the ciphertext is $(C_1,C_2)=(kP,m\oplus H(kY))$ where $H:G\rightarrow \{0,1\}^n$
is a hash function that maps points on the curve to $n$ bit strings. Consequently, you can encrypt $n$ bit
messages, for instance 256 bit if you use SHA-256 for $H$. For the input to $H$ you need to encode the points of the curve in a suitable way.

What you describe in your question, i.e., encode $m$ as $mP$, is also known as exponential ElGamal and typically
used to make it additively homomorphic. But in this case, you have to compute discrete logarithms after decrypting.
Note that decryption will yield $mP$ and you have to compute $m=\log_P mP$ which means you have to solve the elliptic
curve discrete logarithm problem. This is only practical for small messages.

Map Messages to the Curve

A standard probabilistic encoding that can be used for curves over $\mathbb{F}_p$ (for a large prime $p$) is that you fix some value $\ell$,
for instance half the bitlength of $p$, and then simply choose a random integer from $\mathbb{Z}_p$ and set the least
significant bits of this value to represent your message, i.e., you have a value $r\|m$. Then, treat this value $r\|m$ as the $x$ coordinate of a (potential) point on the
curve (in affine coordinates). If it is on the curve, take one of the two possible $y$ values and you have your encoding of the
message to a point. Otherwise, start over again
with a new $x$ value.

This is one probabilistic encoding and if you want to have injective maps that
are also efficiently invertible take a look here as pointed out in my comment.

Third possibility: Avoid ElGamal

As @poncho pointed out, you could simply replace ElGamal with another elliptic curve encryption scheme such as
ECIES. It is a hybrid encryption scheme and avoids
the task of mapping messages to points on the curve. In practice this seems to best solution if you want to use
your scheme simply for encryption (and do not need it as a building block in protocols which require proofs of
knowledge or stuff the like).


What scalars produce the wrong values with X25519's montgomery ladder? This question is a consequence of an older one about multiplying a twisted Etwards point in Montgomery space. Turns out that this is unsafe in some circumstances.

The following Montgomery ladder as implemented in the ref10 implementation is unsafe: when the scalar is zero, the result of the multiplication is not the zero point, but a point that has a low order. This caused a critical security vulnerability in my crypto library.

Because of this, I have decided not to use the Montgomery ladder for signature verification. The Double scalar multiplication (with merged doublings and sliding windows) is faster and doesn't take much code. I would still like however to use the Montgomery ladder for signing and public key generation.

My question is, is it safe?

Public key generation multiplies the base point by a random, trimmed scalar. The trimming process is the same as for X25519: set bit 254, clear bits 0, 1, 2, and 255. I guess the Montgomery ladder unconditionally produces good results in this case, because the X25519 public key generation does the same. Is that right?

Signatures still multiply the base point, but they do not trim the scalar before performing the scalar multiplication.  Instead, they start from a hash, which is different from zero, and that hash is reduced modulo L (the order of the curve). Basically, we multiply by a random number between 0 (yikes) and L-1.

I believe we have a negligible chance of multiplying by zero by accident (something like 2⁻²⁵²).  We could check for an all zero input, but this looks overkill.  What I'm worried about is other exceptional values.  Does the Montgomery ladder fail on any other value than zero? Are any of those values lower than L?

Actually, the answer is none. Everything works, and produces the correct results.

Potential problems arise when converting back to Twisted Edwards space, and that's a different question.


Notation for commitment schemes I was reading this set of lecture notes on commitment schemes, where they define a commitment scheme $\text{Com}(b, r) = f(r), h(r) \oplus b$ as a secure commitment scheme. In this case, $f : \{0,1\}^n \rightarrow \{0,1\}^n$ is a one-way permutation, $h : \{0,1\}^n \rightarrow \{0,1\}$ is a hard-core bit of $f(\cdot)$, and $r$ appears to be a random string from $\{0,1\}^n$ (the notation is $r \leftarrow_R \{0,1\}^n$, but I'm not really sure what this actually means and it would be super helpful if someone could clarify what the notation means here!).
My question is what the $f(r), h(r) \oplus b$ means. What is the comma doing? Does this mean that the commitment scheme returns two outputs (I was under the impression that commitment schemes only return one output)? Or am I supposed to combine $f(r)$ with $h(r) \oplus b$ somehow? Thank you for your help!

Or am I supposed to combine $f(r)$ with $h(r) \oplus b$ somehow?

Yes, $\text{Com}(b, r)$ is a function which "combines" them.  However it only "combines" them in the sense that it outputs the pair $f(r), h(r) \oplus b$
The main confusion here stems from not realizing that a tuple can be a perfectly valid singular output. (This is compounded by Boaz Barak writing the tuple without parentheses.)
From the lecture notes:

Definition 2 (Commitment schemes). A commitment scheme $Com$ is an unkeyed function
that takes two inputs: a plaintext $x ∈ \{0,1\}^n$
` and randomness $r$ chosen in $\{0,1\}^n$. The
idea is that to commit to the winner I let $x$ be my prediction, choose
$r \leftarrow_R \{0,1\}^n$
n and publish $y = Com(x, r)$. Later to prove I predicted $x$, I will publish $x$ and $r$.

(the notation is $r \leftarrow_R \{0,1\}^n$, but I'm not really sure what this actually means and it would be super helpful if someone could clarify what the notation means here!).

On page 3 of the notes, the author uses $R$ to indicate random. $\gets$ is assignment.
$\gets_R$ is used for uniform random assignment.
For more see this answer.


Hashing-Simple Hash and Merkle tree Does the output hash of simple hash and Merkle hash are same for same data>>??

No, they aren't, at least if you assume that the Merkle tree has a height of over 1 node, because in that case the "tree" would contain a single node and the two are equivalent. The height and amount of data / number of hashes per node are generally configured beforehand, and specifying 1 doesn't make sense.

A Merkle tree consists of multiple nodes, and each node consist of the hash of the underlying layer. That layer can consist either of other nodes or of data (I've not seen that data and nodes are mixed, and that would be dangerous practice). However, even for a two-height / two-node tree you would have $\text{H}(\text{H}(M))$ instead of just $\text{H}(M)$.

As finding a hash where $\text{H}(\text{H}(M)) = \text{H}(M)$ would amount to a collision, a secure hash will never output the same value for a hash and a Merkle tree.


Do Rabin Fingerprints have any advantages over CRC? Background

In both, bitstrings are interpreted as a polnomical over GF(2) and they each can be used to implement a hash over a sliding window. The definitions of each are as follows:

Rabin Fingerprint: $M(x) = Q(x) \cdot G(x) + R (x)$

CRC: $M(x) \cdot x^{n} = Q(x) \cdot G(x) + R (x)$

Where $M(x)$ is message polynomial, $G(x)$ is the degree-$n$ irreducible 'generator' polynomial, $x^{n}$ represents $n$ zeroes added at the end of the message, $Q(x)$ is the quotient polynomial (ignored) and $R(x)$ is the remainder polynomial (the hash itself).

The Question

According to page 7 (labelled as page 135) of the paper LFSR-based Hashing and Authentication, CRC offers some improvements for hashing under encryption.

Assuming $G(x)$ is the same for the implementation of each algorithm (i.e. ignoring that polynomials under Rabin should be random) and an identical $M(x)$ is used for testing, does the Rabin Fingerprint offer any advantages over CRC? If not, is there any reason why the Rabin Fingerprint is moderately popular in file chunking (using the sliding window technique mentioned above)? For example, 1, 2 and many others on the web. By contrast, I can find very few implementations of a sliding window version of CRC or mentions of it being used for chunking.

This is an expanded version of my comment above.  At the top of page 135 of the paper cited by the OP, the construction of the cryptographic CRC is defined  in the following words:

  $\ldots$ for any message $M(x)$ of binary length $m$ bits, $h_p(M)$
  is defined as (the coefficients of) $M(x)\cdot x^n \bmod p(x)$.

Thus, the definition of cryptographic CRC in the cited paper is
the same as what the OP claims the Rabin fingerprint
is. On the other hand, the cited paper says Rabin's construction
is essentially the same

  $\ldots$ except for the multiplication by $x^n$ in the modular
  process

In other words, the OP seems to have interchanged the
definitions of CRC and Rabin fingerprint in his question.

The cited paper
also seems to be implying (the phrasing is somewhat ambiguous)
that Rabin's fingerprint is weaker than the cryptographic CRC
defined above, which, by the way, is the same as the way CRC
error detection is used in communications systems, as I stated
in my comment.


Shamir Secret Sharing GF(p) or GF(2^8) I'm implementing Shamir's Secret Sharing Scheme, but I've hit a conceptual roadblock.  In Shamir's paper "How To Share A Secret" he creates his shares an a finite field of order p, where p is some prime larger than both the secret and the number of shares.  I understand why this needs to be done to ensure an even distribution of the shares.  However, in nearly every implementation I've seen, GF(256) is used.  I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field?  In the prime field, only modular arithmetic is needed, but with GF(256), you end up writing a ton more code and it is much less intuitive.

I know that this is technically okay, since it is still GF(p^k), but why is this preferable to just using a prime field?

They have equivalent security; however the nice thing about $GF(2^8)$ is that everything ends up to be an integral number of byte.  We could use (say) $GF(257)$, however when the shares will end up being slightly larger than 1 byte, and so if we encode a secret that's an random set of bytes, the shares end up using a bit more space.

If we used a trinary computer, we'd probably end using something like $GF(3^6)$, because that would be an even number of trits.

  with GF(256), you end up writing a ton more code

Not that much; most computer languages support $GF(256)$ addition as a standard operator, and multiplication/division can be done with two tables, and a few lines of code.

Compare this to the logic required to do modular division.

As for "far less intuitive", well, that depends on your experience with finite fields; I find it perfectly intuitive.


Question on the CPA-security proof of the CTR-Mode While reading Katz & Lindell's textbook (2nd edition) I found a proof for the CPA-Security of CTR-Mode. It can be found at the end of chapter 3.6.2 (page 93 and 94). I don't quite understand, why the proof is that complex, so I got two basic questions about it:

Why is the extra Scheme (cryptosystem) based on a true random function instead of a PRF necessary?

Why do we want to proof it with CPA-security for multiple messages? As far as I know, CPA-security for single messages implies CPA-security for multiple messages and vice versa. Therefore that just makes is unneccesary complex.

Why can't the proof be done simpler? The sketch of my idea would be:

Suppose A is an adversary against the CTR Kryptosystem based on a secure PRF function

A runs the CPA-Experiment with two messages $m_0, m_1$ and recieves $(IV,c)$ from the challenger

A can use its encryption Oracle for a polynomial amount of time $p(n)$ and gets, for simplicity, $n$ duples $(IV_i,c_i)$. That leads to 2 cases: 1. An overlap occurs. Because A does not only succeeds, if $IV = IV_i$ but also if $IV+x = IV_i+y$ (for some $x,y \geq 0$, because of the counting factor of CTR-Mode). So this happens in $2p(n)^2/2^n$ instead of $p(n)/2^n$ (birthday paradox, because of $IV+x = IV_i+y$). As probability to win in that case is 1, but the probability for this case is negligible: $2p(n)^2/2^n \in negl(n)$ 2. There is no overlap and A probability to win is $1/2$, because the PRF is secure.

Combining these two cases the probability of A to win is $1/2 + negl(n)$, which means, that CTR is CPA secure.

Edit:
Thank you for the answer! They helped me a lot in understanding the topic. But this led to another question related to this:
My professor proofed CPA-security for Encryption #1 based on PRF via a reduction proof using contradiction. The basic idea:

Basic assumption PRF is secure

Assume an adversary A against #1

Use A to build a distinguisher D to solve the the basic Assumption (D plays the CPA-game with A and therefore can break PRF)

Contradiction leads to proof if CPA-security

Because the proof in the book is based on the proof of the CPA-secure PRF-encryption, it should be possible to construct a proof, based on the the proof of the CPA-secure PRF-encryption using contradiction, right?
I give it a try:
This leads me to the following: A solution using contradiction would be more intuitiv (and I could understand it). So now therefore I give it a try:

Basic Assumption: PRF is secure

Assume an adversary A breaking the the encryption. A is able to use an encrpytion orakle (because we want to proof CPA-security). Let a have a non negligible success probability.

Using A we an build a distinguisher D breaking the PRF: D gets function not knowing weather it is a PRF or a true random function f. D simulates the CPA game with A using PRF or f. This leads to two cases:

3.1 D got a PRF. D is using the PRF-encryption scheme. A can break it with non negligible probability and D outputs what A ouputs.
3.2 D got a true random function. Now it gets funny: D firstly has to construct a new encrpytion scheme. For that he uses the old and just uses f instead of PRF. But now A can't win the game with more than a negligible probability: A can make p(n) many encryptions getting. Now the same argument as above can be used for overlapping (Because A does not only succeeds, if $IV = IV_i$ but also if $IV+x = IV_i+y$ (for some $x,y \geq 0$, because of the counting factor of CTR-Mode). So this happens in $2p(n)^2/2^n$ instead of $p(n)/2^n$ (birthday paradox, because of $IV+x = IV_i+y$). As probability to win in that case is 1, but the probability for this case is negligible: $2p(n)^2/2^n \in negl(n)$)

Therefore D can succeed with more than non negligible probability distinguishing PRF and f, which breaks PRF and therefore leads to a contradiction

Now only ING-CPA-security for single messages was shown, but because ING-CPA-security for single messages implies ING-CPA-security for multiple messages, we also showed that.

The problem is with your statement "There is no overlap and A probability to win is $1/2$, because the PRF is secure." What does that mean? The only way to formalize that is to show that if adversary wins with probability greater than $1/2$ when there is no overlap, then you can break the PRF. That is essentially what the proof does. Note that it doesn't have to be by contradiction - it's also possible to show that when there is no overlap, then a reduction to distinguishing the PRF from random shows that the gap is negligible. That is the way the proof written in the book works.


Is this test result sufficient to steer clear from this RNG for cryptographic applications? I'm not really interested in this PRNG.  I'm more interested in understanding what it takes to fail the security threshold for cryptographic applications.  I'm taking the C PRNG as an example.

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
  unsigned int random;
  srand(1);
  for (;;) {
    random = rand();
    fwrite(&random, sizeof random, 1, stdout);
  }
}

Here's the summary of a small crush by TestU01:

========= Summary results of SmallCrush =========

 Version:          TestU01 1.2.3
 Generator:        crand
 Number of statistics:  15
 Total CPU time:   00:00:21.67
 The following tests gave p-values outside [0.001, 0.9990]:
 (eps  means a value < 1.0e-300):
 (eps1 means a value < 1.0e-15):

       Test                          p-value
 ----------------------------------------------
  1  BirthdaySpacings               1.1e-14
  2  Collision                        eps
  3  Gap                             4.2e-9
  6  MaxOft                           eps
  6  MaxOft AD                      1 - eps1
  7  WeightDistrib                    eps
 10  RandomWalk1 H                    eps
 10  RandomWalk1 M                    eps
 10  RandomWalk1 J                    eps
 10  RandomWalk1 R                    eps
 10  RandomWalk1 C                    eps
 ----------------------------------------------
 All other tests were passed

Is this enough to make me steer clear from C's rand()?  What if it had failed only a single test?

No test is needed to stay clear from srand for cryptographic purposes, including when a pseudo-random generator is thought. The definition of srand is enough to disqualify it.

That definition states:

  void srand(unsigned int seed);

  The srand function uses the argument as a seed for a new sequence of pseudo-random numbers to be returned by subsequent calls to rand. If srand is then called with the same seed value, the sequence of pseudo-random numbers shall be repeated.

Problem is: the key is an int, and that's not wide enough. int is typically 32-bit, sometime 16-bit, rarely more than 64-bit, and 80-bit is a bare minimum for a modern key (we want more like 128-bit, or 192-bit when considering multi-target attacks, or 256-bit for extra peace of mind when considering the possibility of quantum computers).

Poncho beats me at first stating that the test is misapplied, since the output is not supposed to consist of uniformly random bits, which likely SmallCrush expects. Problem is,

  The rand function computes a sequence of pseudo-random integers in the range 0 to RAND_MAX.

  The value of the RAND_MAX macro shall be at least 32767.

and RAND_MAX is often INT_MAX. It's then likely that for sizeof(int) bytes written, one byte has its high-order bit stuck to 0, which should be caught by many statistical tests.

CSPRNGs can not be validated by statistical tests. Failure of such test only indicates (with high certainty) that the PRNG or/and test procedure is flawed (here, both are). Success does not prove anything, and indicates very little. Image: it's like validating a road bridge by having an ant cross it, when the actual things to test are high load, wind-induced oscillations and long-term corrosion of metal parts.

Also, many cryptographic applications need a True RNG (with output unpredictable from the code). That's not even touched by either srand or the test.