How to mix external entropy to a random number generator?

Based on the current details, this will work where I = internal generator and E is the external one:-

random bytes = I ⊕ SHA1(E)

The equation assumes that I is a good quality RNG.  The key here is to get enough entropy from E.  You should measure it's (min.)entropy generation rate in bit/s sample and then take enough samples to ensure you have F times 16 bytes of it.  F is a safety factor which ideally should be >2 but I'd just go with F = 100.  If you have an analogue entropy source you can easily get 10 kSa/s with an on chip ADC, and a digital entropy source can be sampled at something in the order of 10 MSa/s.  Depends really on the features of your micro controller.

The hash allows a dissimilar amount of entropy to be easily combined.  It also acts as a randomness extractor for E, so you don't have to be debias the entropy and it'll deal with huge auto correlation.

Note.  I would make the argument that there's no point in having the internal generator (I).  If you have the luxury of a true entropy generator, use it.  The hash extractor function means that additional whitening is not necessary.  As Shane tells Joey, if you can use it, one's all you need.  And how would I be seeded anyway?


This question is based on opinion. At least kind-of. But the variants from which one can choose are quite a few.

As for general construction the sponge construction (like Keccak / SHA-3 uses) are very versatile and can be used for many purposes, for example hashing, authenticating (= "MAC'ing"), authenticated encryption (see “General Overview of the First-Round CAESAR Candidates for Authenticated Encryption”, Version of March 14, 2015 by Farzaneh Abed, Christian Forler, and Stefan Lucks).

Of course one can also use such constructions or already exisiting construction to construct the rest, PRNGs may use hashes at some point, stream ciphers can be hashes in counter-mode, HMAC can use sponge-based hashes, KDFs can be based on sponge-based hash functions, using the arbitrary output size and tweaking the input for other parameters.

Now if you're specially looking for one cipher / hash-function which can be used without much effort in a variety of modes, I think (and others as well as the comments suggest), that Threefish is the cipher to choose. Threefish was designed as a building block for a hash-function, meaning all known attack scenarios were considered, like standard attacks and related-key attacks. Threefish and it's associated hash-function Skein can also be used in a variety of modes:

Threefish can of course be used as a standard block cipher. (Maybe set the tweak to $0$?)
Skein, which is a lightweight construction around Threefish, can be used as a standard hash-function.
Skein-MAC, a mode of operation for Skein, is a provably secure MAC (like HMAC).
Skein-HMAC, Skein can of course also be operated in the standard HMAC construction.
Skein-KDF, a mode of operation for Skein, is a highly customizable variant of Skein, using the fact that Skein can output arbitrary sized digests.
Threefish stream cipher. Threfish can be used as a standard stream cipher in CTR-mode.
Skein stream cipher. Skein has a mode of operation allowing it's output to be used as a stream cipher pad.
Skein-PRNG is proposed in the original Skein paper. I'd recommend against using it but rather use Skein and Threefish within Fortuna instead of AES and SHA-256.
Skein-PBKDF is a PBKDF2-like mode of operation for Skein. I'd recommend against using it but rather use scrypt, bcrypt or any of the PHC-winners (to be announced). Some of the finalists allow usage of arbitrary hash-functions, where Skein could be used.
Threefish authenticated encryption is a bit more tricky, but there are a few schemes that use tweakable block ciphers (like Threefish) to construct fast AEAD ciphers.


Signing and verifying message consisting of several parts

The standard way to do this is with a hash list.  That is, you would hash each of the messages $m_i$ to produce a hash $h_i = H(m_i)$, and then combine all the hashes and hash them to obtain a master hash $h = H(h_0 \| h_1 \| h_2 \| \dots \| h_n)$.  Finally, you can e.g. digitally sign the master hash to prove that the hash, and by extension all the messages, were sent by you.

(You can, of course, also use a keyed MAC instead of a hash for this, if you want.)

Hash lists can also be generalized into hash trees.  For very large numbers of messages, hash trees are potentially more efficient, since they can let you verify the integrity of an individual message without having to load and hash together all the intermediate hashes $h_i$.  They're also more efficient to update, if your messages may sometimes change.  (That said, if your messages don't change, and you know you're going to want to verify all of them anyway, a simple hash list will have somewhat less overhead than a more complex hash tree.)

Of course, you could also just simply hash the whole combined message $m = (m_0, m_1, \dotsc, m_n)$ at once, without bothering with hash lists or trees.  But the advantage of hash lists or trees is that they let you verify the individual message parts without loading and hashing the whole combined message.


The requirement of the function in Winternitz OTS+ is a pseudorandom function family, or PRF: a family of functions $F_K\colon \{0,1\}^n \to \{0,1\}^m$ such that if $K$ is uniformly distributed in all $k$-bit strings, then $F_K$ is indistinguishable from a uniform random choice of function $U\colon \{0,1\}^n \to \{0,1\}^m$.  Specifically, the best known random algorithm $A(G)$ taking a function $G\colon \{0,1\}^n \to \{0,1\}^m$ to a true/false value and having a plausible computational cost has a negligible PRF advantage, $$\operatorname{Adv}^F_{\mathrm{PRF}}(A) = |\Pr[A(F_K) = 1] - \Pr[A(G) = 1]|,$$ which compares the probability that $A$ returns true for $F_K$ under uniform random distribution on $K$ to the probability that $A$ returns true for a uniform random function $U$.

Poly1305 is a one-time message authentication code, or one-time authenticator/MAC: a family of functions $H_K\colon \{0,1\}^n \to \{0,1\}^t$ such that if $K$ is uniform random, then given up to a single message $M$ and its authentication tag $T = H_K(M)$, an adversary has no hope of finding another message $M'$ and authentication tag $T'$ such that $T' = H_K(M')$—it resists forgery after a single message.  That is, the forgery probability for a random algorithm $A(M, T)$ giving $(M', T')$, namely $\Pr[M' \ne M, H_K(M') = T']$, is negligible.

A PRF makes a passable MAC, even a one-time MAC, although as you note Poly1305 is a much more efficient one-time MAC than a PRF.  However, a one-time MAC does not make a passable PRF.  Why not?  The adversary's algorithm $A$ in the notion of PRF advantage is allowed to call the function more than once.

To make this concrete, consider the secure one-time MAC $H_K(M)$ for $K = (K_0, K_1) \in \operatorname{GF}(2^{128}) \times \operatorname{GF}(2^{128})$ and $M \in \operatorname{GF}(2^{128})$ defined by $$H_{K_0, K_1}(M) = K_0 M + K_1.$$  (This is essentially GHASH, of AES-GCM, limited to one message block, which is a polynomial evaluation MAC much like Poly1305.  We can naturally interpret any 128-bit string as an element of $\operatorname{GF}(2^{128})$ given a choice of irreducible degree-128 binary polynomial like the standard GHASH one.)

How do we define the algorithm $A$ to distinguish $H_K$ from $U$?  We can first compute $T = K_0 M + K_1$ and $T' = K_0 M' + K_1$ by evaluating the putative $H_K$ on two different inputs, and then solve for $K_0$ and $K_1$ using secondary school algebra.  Then we can immediately distinguish $H_K$ from a uniform random function $U$ with high probability by computing the candidate function on $M''$ and checking whether we get $K_0 M'' + K_1$: with high probability, a uniform random function will give something else.

Actually, Winternitz OTS+ requires a slightly weaker notion than pseudorandom function family, namely key one-wayness: for uniform random key $K$ and input $X$, letting $Y = F_K(X)$, the success probability of the best known algorithm $A(X, Y)$ for recovering the key (or an equivalent), $$\operatorname{Adv}^F_{\mathrm{KOW}}(A) = \Pr[Y = F_{A(X, Y)}(X)]$$ is negligible, as long as it has a plausible computational cost, where $Y = F_K(X)$.  I leave it as an exercise to the reader to define such an algorithm $A$ for a polynomial evaluation MAC like the above example.


What is a (smooth) projective hash function?

Smooth projective hash functions have been introduced by Cramer and Shoup under the name hash proof systems. An SPHF for a language $L$ allows to hash a word $x$, in two different ways: either with some secret key (the hashing key, usually denoted $\mathsf{hk}$) or with the associated public key (the projection key, usually denoted $\mathsf{hp}$). It must satisfies two properties:

If the word $x$ is in the language, both ways of hashing will return the same hash value
If the word $x$ is outside the language, the hash obtained with the secret key is statistically indistinguishable from random, even given the public key

Intuitively, this can be used as a kind of designated-verifier zero-knowledge proof (although it does not satisfy the classical zero-knowledge property): to prove the $x \in L$, the prover receives the projection key $\mathsf{hp}$ from the verifier, and hashes the word with respect to $L$, using $\mathsf{hp}$, and sends back the result. The verifier compares it to the hash obtained with the secret key and accepts the proof if both hashes are the same.


Predicting PRNG given some of its previous output

I'm not familiar with the terminology "reduced state", so I can't address that half of the question.

However, this particular PRNG makes it easy to reconstruct the internal state; we note that the state function can be rewritten as:

x := 2*x + 5 - kx * p
y := 3*y + 7 - ky * p

for some small integers $k_x$, $k_x$ (in fact, $0 \le k_x \le 2$ and $0 \le k_y \le 3$.  Once we do that rewrite, we notice that the lower bits no longer depend on the higher bits.

So, what we can do is:

Iterate over the possible $k_x$, $k_y$ values used to generate the second, third and fourth outputs; a total of 1728 possibilities.
For each set, we go through the possibilities for bit 0 of p and the initial x (note: because the initial y can be immediately deduced from the x and the first output, we don't have to iterate through that)
Check to see if there's a combination that gives the bit 0's on the second, third and fourth outputs that we have; if there is, then start looking through the various possibilities for bit 1 of p and initial x.

When we manage to get through all 29 bits, and get all the bits of the output we observed, then we have the answer (and in fact, continuing the generate outputs will, in this case, continue to generate the listed outputs).

Going through the above procedure gives us the answers p = 295075153, x0 = 89059908, y0 = 164204369, next output = 231886864


How is a public/private key pair generated from a Diffe-Hellman key exchange?

So is 2 the private key here ?

No, it's referred to as a "shared secret" (because it is shared between Alice and Bob, and is secret to everyone else).

If there were 'private' and 'public' keys (which is not the standard terminology with DH), then Alice's private key would be $a=6$, and the public key would be $g^a = 8$.  In this case, the 'private key' is private, in the sense that it allows her to perform the operation of deriving the shared secret; something that we hope is difficult if someone has only the public keys.


Is it possible to ensure security with zero pre-shared information?

No. Consider using encryption to protect against a passive adversary. In this case, encryption needs to hold from the sender to the receiver. The sender can verify that the message leaves them encrypted but they have no guarantee that it is not decrypted before the receiver unless if they can authenticate the receiver. Authentication requires knowledge of some secret which would constitute preshared information in your definition.

The closest I believe you could come to a secure channel in this setting would be what is called Secure Message Transmission Protocols. The basic idea is that the sender would split up the message into shares (say 10 shares) such that some threshold (7 shares) are required to reconstruct the message. The sender would send the 10 shares over different channels. This is not secure against an adversary that is one all channels (which your question implies, which is why the answer is still likely "no") but if the adversary is on 6 or less, you get passive security. Active security is possible but the adversary is bounded to less than a third of the channels (byzantine agreement). Anyways, you could also argue that knowing the algorithm to reconstruct the message from the shares is pre-shared information (although not a secret).


How can I validate a given Server-Certificate behind a HTTPS-connection?

OK, so let's step through this, but first:
CAs have exactly one raison d'être and that is to attest the link between a domain, a public key and optionally an entity.

As an overview, a CA validation of this set of information can go as follows:

You register with the CA, so they can attribute actions made from a specific account to you.
You request validation that your account represents a given entity (this can be a natural person or a legal person like a bank). Note that only validated information will be placed in the certificate.

This may include copies of official documents (passport, driver's license, governmental ID) if you want to validate as a person.
This may include an attestion letter of the CEO of the company.
If you are really interested, read the CA-Baseline Requirements (section 3.2) and the EV-Guidelines (section 11).

You request validation that you control a certain asset (usually a domain).

This means that you have to prove control over the asset, which can be proven by placing a file on a webserver or by clicking on a link sent to an email strongly associated with the domain owner (like the hostmaster entry in the WHOIS database)

You send the CA your public key and they give you a certificate.

This usually uses a PKCS#10 certificate signing request (CSR). Note that CAs keep track of whom they issued which certificate for which domain(s).

So what if a CA doesn't do its job properly? Well if it violates the CA-Baseline requirements or the EV guidelines for an EV certificate, it will be untrusted by the browsers and operating systems and thus can no longer issue default-trusted certificates, ie it is out of business. Historically, this did happen, for example with Diginotar but also with StartSSL and WoSign. They all failed to adhere to the baseline requirements and thus got marked "untrusted" to varying degrees.

Also note that the browser will validate the domain name, the public key and the signature chain of the certificate automatically and will display you an error message if any step of this process fails. So you can trust the fact that the certificate the browser presents you is the right one for the domain you're on.


Is it insecure to encrypt the wrong plaintext?

As long as you're using any modern encryption algorithm (and you're using it correctly: random key, new random or unique IVs for each message, depending on the mode of operation, etc.) then you'll be fine. In fact, you'd be fine even if an attacker got to choose which plaintext you encrypted and got to see the result; this information would not help him decrypt other ciphertexts. (This is a chosen-plaintext attack, and any standard encryption algorithm can withstand one. Unless you consider ECB a standard encryption algorithm. Don't use ECB.)

There is, however, a possible exception to this rule that might relate to your third question. If you accidentally encrypt a plaintext that includes your encryption key, then in theory this could lead to problems. At least, one could no longer prove the system's security under standard assumptions about the blockcipher.

If your third point was asking "What if I use the wrong key?" then, yes, this is a problem. They key you accidentally use might be brute-forcible. For example, a 128-bit AES key consisting of 16 ASCII hex characters (0-9, A-F) permits only $16^{16} = (2^4)^{16} = 2^{64}$ possible keys.


Short answer: Yes, I'd still trust SEED.

The topic you linked to is from 2013 (2 years) old and for cryptography nearly never any advances will be made for a 15 year old, rarely used cipher after just 2 years.

As the best cryptanalysis only penetrated half of the rounds back then I'd highly doubt there're any advances by now, as this is only a legacy cipher in most systems and hence not a target like AES which is in widespread use.

EDITED TO ADD(1): As pointed correctly in a comment, if you plan to secure data against nations / national intelligence agencies, you can not rely on the security of SEED and therefore must consider using AES(-192/-256) or maybe even multi-encryption with ciphers with different designs (-> SEED & AES & Threefish/ChaCha & Serpent).


How can a company have its own Certificate Authority for internal use?

This is done fairly often in companies, but any browser, client, or device which is to trust the internal CA needs to have the internal CA's root key added to its trust store. Browsers which haven't been set to trust the company's CA will not see its certificates as valid.

It's possible to run a CA using only openssl, but very painful. There are projects which make it significantly easier, such as FreeIPA.


When using Client Certificates, is it usual to generate your own?

In a typical business to business setting it may  be that the client is also a server for other use cases. In that case the server cert and corresponding private key of the other party could be reused. To be able to verify that it is correct you should probably pin (trust just that) certificate as you may not want to trust other certificates issued with a generic CA to connect - although you could also whitelist the particular server name.

Yes, it is perfectly valid to issue your own certs in this setting. For security reasons it is best if the other party creates a key pair with corresponding certificate request, which you then use to create a signed certificate that you can trust. For this you need a CA & CA software (and trust your own CA certificate). You could also simply  trust a self signed certificate from the other party.

I think it generally just makes sense to use a normally issued certificate by a third party CA iff:

either you want to reuse the cert / key material and/or
you have some reason to only trust a cert with a particular host name.

Key management is a complicated matter. To avoid awkward conversations I would definitely ensure that you create the protocol together with the other party. Time for coffee and cookies!


Difference between computational complexities in General Number Field Sieve

By moving the $o(1)$ and using elementary algebra, the formulas given can be rewritten with a single digit difference, as
$$\left(e^{(3^{-2/3})\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}\right)^{4+o(1)}\;\text{ and }\;\left(e^{(3^{-2/3})\;(\ln n)^{\frac{1}{3}}\;(\ln\ln n)^{\frac{2}{3}}}\right)^{3+o(1)}$$

Two things are now apparent:

The exponent changes from about 4 to about 3; this qualitatively explains why there is such an enormous gap.
The $o(1)$ beats any outer multiplicative factor, and the formulas are thus missing some unknown, possibly large multiplicative factor when we use them for any particular $n$. This explains why we can at best use the formulas to predict approximately how the run time of each of the attacks (or the ratio of the two run times) scales with $n$ (and then, not rigorously); but not to quantitatively predict the relative runtime of the two algorithms for some $n$.


How does one use AES block cipher modes of operation?

Your question is pretty confusingly written, but let me try to make some sense of it.

You say you receive 8 bits of input every cycle.  You want to encrypt the input using AES, which operates on 128 bits at a time.  This means that you need to buffer the input somehow (a shift register might be handy here) for 128 / 8 = 16 clock cycles, until you've accumulated a full buffer to encrypt.

Conveniently, while you're accumulating the next input block, you can encrypt the previous block at the same time.  If you can do one full AES round per cycle (which apparently is indeed possible, if you can afford the gates), then you should have plenty of time to finish the encryption before the next block comes in.

Presumably, you also need to buffer the output in another shift register, and shift it out 8 bits at a time, but you can also do that in parallel with the input buffering and the encryption.  So, at any given moment, your circuit will be doing three things: reading in the next 128-bit block, encrypting the current block and writing out the previously encrypted block.

All that's assuming that you want to implement the raw block cipher, i.e. "ECB mode".  (The "scare quotes" are there because ECB isn't really a proper mode of operation suitable for securely encrypting long messages.  It's really only good as a building block for implementing other modes, but it's pretty useful for that.)  Once you have an ECB implementation, you can easily use it to implement any other mode.

Note that, for efficiently implementing the "feedback" modes (i.e. CBC, CFB and/or OFB), which require you to feed the previous encrypted (possibly modified by XORing it with the plaintext) block back into the cipher to encrypt the next block, you have two choices: you can either build the circuitry to do that into your AES module, or you can leave it as the responsibility of the user of your module to do that.

The first option is technically pretty simple (you need to be able to feed the block back through the round function several times anyway) and efficient, but it does make your circuit mode-specific, and requires you to implement some way to select the mode of operation, if you want to support more than one.  For most modes, you also need to handle the encryption and decryption operations differently.

The second option is even simpler (at least from your viewpoint; it might not be simpler for the user of your circuit), but having to feed the output back in through the 8-bit I/O bus could reduce encryption speed considerably (at least by a factor of 2 if the input and output timings are staggered appropriately, by a factor of 3, or more, if they're not).

You don't need to generate a new IV for every input block — indeed, that couldn't possibly work, since the IV is a full input block.  Typically, the IV is supplied as the first block of each multi-block message.  If you do decide to implement the feedback internally, you do generally need to treat this first block somewhat differently from the later ones.  (That's not always the case, though: for example, for CBC and CFB mode decryption, the IV can be treated just like any other ciphertext block, with the user being responsible for throwing the first plaintext output block away.)

There's also a very handy variation on CBC mode encryption where the initial "IV" is simply set to all zeros, and the actual IV is obtained by encrypting the first plaintext block, which should consist of a nonce.  Decryption still works exactly same as usual.  You might want to support this scheme explicitly (avoiding the need to actually feed in the dummy null IV), since it's more resistant to certain attacks involving poor IV generation than standard CBC mode encryption.

In fact, there's a another, more general case where using a fixed (say, all-zeros) IV is OK: whenever each message is encrypted with a different key.  For some applications, this might be a common scenario, in which case you may want to provide it as a general option for any mode.

One final feature you're typically going to need is some way to change the key.  There are applications for which having a single, fixed key permanently embedded in the encryption circuit may be sufficient, and it does simplify the circuit considerably, but for most purposes you do need to support changeable keys (which implies that you need to implement key expansion).

Another simplification you may be able to make, in some applications, is that many modes of operation (such as CTR, CFB and OFB, as well as many AE modes like EAX or SIV) only use the underlying block cipher to encrypt blocks, never to decrypt them.  Although you can generally reuse much of the encryption circuitry for decryption, omitting the decryption parts still makes things a lot simpler.  You do, however, need the decryption circuitry if you want to implement CBC or OCB mode (or, obviously, ECB mode) decryption.


How can I determine key length for message encrypted by many-time-pad?

I am basing my answer on Cryptopals.

The basic idea is that as {c0,c0+3,c0+6,…} have all been xor-ed with the same byte, the number of differing bits between c0 and c3 is the same as between p0 and p3. (this number is called the Hamming distance between two characters.

Furthermore, the distance between [c0 c1 c2] and [c3 c4 c5] is the same as between [p0 p1 p2] and [p3 p4 p5], assuming the key length is 3. In regular English text, the hamming distance between two blocks of plaintext should be small, as the letters actually used occupy a highly ordered small fraction of the total ASCII range.

However, the distance between [c0 c1 c2 c3] and [c4 c5 c6 c7] would be ~50% of the total number of bits, because the xored key does not "cancel itself out".

So iterate over a range of possible keysizes, and compute the hamming distance between the first two blocks. Then normalize this result by the keysize.

The lowest value should correspond to the keylength.

Now you have a many time pad, where many = len(m)/keylength.
Each message is [c0 c1 c2] or [c3 c4 c5] or [c6 c7 c8]

Once you know this, then apply frequency analysis to {c0,c0+3,c0+6,…};{c1,c1+3,c1+6,…};{c2,c2+3,c2+6,…} independently to find each key byte.

You could also apply crib dragging. This is basically where you guess that a word is in a certain spot

There is also a cool attack that relies on a quirk of ASCII: 'a' ^ ' ' = 'A'. That is, xor-ing an English letter with a space simply flips the sign.
Helpfully, spaces are statistically the most common "letter" in English text.

If you take {c3,c6,c9,c12,…} and xor each byte with c0, you get {p3^p0, p6^p0, p9^p0,...}.
If this resulting sequence is mostly (~70%) in the range of "a-z" union "A-Z", then 9/10 times, p0 is a space.

You can of course instead xor the sequence with p3 or p6 or ... to check if that character is a space. Given a long enough message, one of the plaintext characters WILL be a space, and then you can instantly get every other plaintext characters which were xor-ed with the same key byte!

As a rule of thumb for attacking N-time pads:

Frequency analysis works once N =~ 6 and is a joke below that
Crib dragging becomes slow past N =~ 8, but is your best bet for small N.
Finding spaces works better than frequency analysis at ALL message sizes. It works even on 2-time pads.


Comparing elliptic curves over prime fields against EC over binary fields

Binary fields were developed since they yield more efficient implementations. This is especially true given the Intel PCLMULQDQ instruction. Note, that there are special types of Binary fields that are even more efficient, like Koblitz curves.

However, in general, our confidence in the security of these curves is less than for prime-field curves. Thus, in general, my preference is to use prime-field curves unless there's a special reason why not to.


Public key in fully homomorphic encryption over the integers

(even number mod even number) is always even number and (odd number mod even number) is always odd number. If $m=0$, the result of modular $x_0$ will be always even number. If $m=1$, the result will be odd number. So $x_0$ should be a odd number.


Calculate entropy of key derived from PBKF2 function

According to the paper “Stronger Key Derivation Via Sequential Memory-Hard Functions”…

If

$$2^k = x$$

the entropy of the derived key (DK) key will be

$$2^{k}+y$$


Why is the GHASH output in GCM mode encrypted to calculate the tag?

What would the security problem be, if I just used the output of GHASH directly as the authentication tag?

Then someone listening into encrypted messages could recover $H$, one of which is correct.

The output of GHASH is a public polynomial (based on the ciphertext and the AAD), evaluated at a secret value $H$.  It turns out that, given such a polynomial, $H$ can be efficiently recovered, either by rewriting the polynomial as $\mathrm{GHASH}(H) + \mathrm{Tag} = 0$, and recovering the roots of that (which can be done in a finite field), or even easier, getting two such ciphertexts, rewriting both of them, and use an Extended Euclidean value to recover their common root.

Given $H$, an attacker can trivially make arbitrary modifications to encrypted messages; yes, that's bad.


Does larger key size mean larger data size in asymmetric encryption?

In addition to kelalaka's answer, keep in mind that the amount of data that can be encrypted with RSA is relatively small (keysize+padding/8), so most schemes use hybrid encryption to use RSA to encrypt a symmetric key and some other critical information and most data is encrypted using the symmetric key.


Why does entropy halve during its extraction?

I'm sure that somebody can give a better answer, but I can at least point the HKDF paper as containing some references that you might want to chase.  See, e.g., Section 2, "Statistical and Computational Extractors," p. 5:

  Efficient constructions of generic (hence randomized) statistical extractors exist such as those built on the basis of universal hash functions [15]. However, in spite of their simplicity, combinatorial and algebraic constructions present significant limitations for their practical use in generic KDF applications. For example, statistical extractors require a significant difference (called the gap) between the min-entropy $m$ of the source and the required number $m'$ of extracted bits (in particular, no statistical extractor can achieve a statistical distance, on arbitrary sources, better than $2^{−{m−m'\over 2}}$ [60, 63]). That is, one can use statistical extractors (with its provable properties) only when the min-entropy of the source is significantly higher than the length of output.

See also Section 5, "Random Oracles as Computational Extractors," pp. 11-12:

  We note that random functions do not make by themselves good statistical extractors (here the key to the extractor is the description of the function itself). For example, if $\chi$ is the uniform distribution over $\{0, 1\}^{2k}$ (thus having min-entropy $2k$) and we choose a random function $f$ from $2k$ to $k$ bits, we expect $1/e^2$ of the points in $\{0, 1\}^k$ not to be in the image of $f$ (i.e., they are assigned probability 0 regardless of the sample from $\chi$), thus inducing an output distribution that is statistically far from uniform.  Furthermore, the lower bounds on min-entropy gap from [60] mentioned in Section 2 apply to random functions as well.

So the short answer is: because of established theorems about randomness extractors.


O(1) EC Linkable Ring Signature Without Group Manager

So, non-interactive zero knowledge proofs, including the ring signature zero-knowledge proof that you want, are impossible in the standard model, as shown by Goldreich and Oren somewhere on this stylish webpage.

So this means we need some trusted party like the group manager, or we need some trusted setup in order to generate a common reference string, or we need to model hash function as random oracles in order for security definitions to hold. I linked an article in the comments (here it is again... :D) that gives constant size ring signatures, which also offers membership revocation (which might be something useful to you depending on the use case).

The other option at this point in time is using a signature scheme in which the signature grows logarithmically with the size of the group over which it is signed -- even with constant size ring signatures, the verification may be O(n) in which case a group of 1 million would be infeasible. If log(n) sized signatures are okay, then something like this could be used, which doesn't need a trusted setup/group manager (the protocol is secure even if the CRS is generated maliciously).

I don't think you're going to be able to find an actual peer reviewed implementation of something like this though -- even Monero, a cryptocurrency which is worth ~$ 400 million at the moment, hasn't been peer reviewed, except kind of by this paper, which reviews the blockchain metadata more than the code anyway...

If privacy of resources is really necessary, and proof generation time doesn't matter too much, looking into using something like libsnark might be your best bet, as their signatures are ~288 bytes, I think (+ ~700 byte verification key). The time taken to generate a proof can be upwards of a minute, though.


Encryption that can only be decrypted once?

If I understand your query correctly then you mean that if the decryption is successful then the original message should be destroyed. That said you can do this in such a way that once the password entered is correct the Plain Text should be displayed and the cipher text should be altered beyond recovery. You can write a program to do that. There are some companies which employs such techniques e.g. you can install some features from a CD only once.

If this is a research question then read ahead.
The computing which we do on our computers is called classical computing. A classical computers is independent of the path it chooses to produce the result. However a quantum computer is dependent on how it produced result i.e. the paths available and the paths chosen affects result. So what could have happened but did not heavily affects the outcome. In a quantum system once we take any measurement the state of the system is disturbed. So if you have a ciphertext which is in a quantum system then if you make an observation the system gets disturbed and the original message is lost.
I hope the firs part answered the question but if it did not then I have an upsetting information for you, the quantum cryptography is a theoretical model which has not been fully practically realized(as far as I know).


Security services provided by digital signature

The Digital signature provides following services :
1. Non forgeable : No one else other than signer can sign it
2. Sender Authentication : Signer deliberately signed the document as it uses private key
3. Data integrity : The algorithm uses hashing functionality
4. Non repudiation : Signer cannot claim he/she didn’t sign it
5. Tamperproof : Document cannot be altered after signature
6. Non malleable : Signature cannot be cut /paste to another document
7. Receiver Authentic : No as it uses only receiver public key

Hope this helps


DES with the bitwise complement of a key

This is known as the complementation property of $DES$; I had thought that it actually predated Biham and Shamir's work.

In any case, your questions:

  Does this hold for only that particular combination of $S$-Box or it will be same for any $S$-Box combination?

It'd remain even if you change the $S$-Boxes arbitrarily. The reason for this is that it is not actually caused by the $S$-Boxes. $DES$ generates the inputs to the $S$-Boxes by $XOR$ing $R_i$ with $k_i$. The reason this property holds is if you complement $R_i$ with $k_i$, the result of the $XOR$ won't change, and so the input the to $S$-Box is exactly the same (and hence the output of the $S$-Box is exactly the same).

  Also there is one more thing mentioned on the paper, but I am not able to get it.

Actually, that's a fairly straight-forward exploit of this property. I'll see if I can state it more explicitly.

Suppose you knew the ciphertexts for two plaintexts, and these plaintexts happened to be the complement of each other. That is, we know the value $T_1 = E_k(P_1)$ and we also know the value $T_2 = E_k(P_2)$, where $P_1$ and $P_2$ are complements of each other (that is, wherever $P_1$ has a $0$ bit, $P_2$ has a $1$ bit, or in other words, $\overline{P_1} = P_2$

Consider further that we don't know the key $k$; and we'd like to find it.

One thing we can try is pick a random key $k'$, and do a trial encryption of $P_1$ with it.  If our $k'$ just happened to be the value $k$, then $E_{k'}(P_1)$ would be $T_1$, and so we know know that $k'$ is likely to be the correct value.

However, consider if our $k'$ is the complement of $k$ (that is, we got every bit wrong).  In that case, the key complementation property would hold, and we would have $E_{k'}(P_1) = \overline{E_{\overline{k'}}(\overline{P_1})} = \overline{E_k(P_2)} = \overline{T_2}$, that is, we would see the bitwise complement of $T_2$.  So, if we see that value, that also tells us what the key is likely to be.

Hence, by doing a single $DES$ encryption, we can actually test two keys -- that's what Biham and Shamir are pointing out.


How to implement a hash function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$?

A possible method is to build $k=1+\lceil\log_2(p)/256\rceil$ 256-bit hash functions $H_i(x)$ per the HMAC construction, by choosing $k$ arbitrary distinct 512-bit constants $c_i$, by defining
$$H_i(x)=\operatorname{SHA-256}\Bigl((c_i\oplus\mathsf{opad})\|\operatorname{SHA-256}\bigl((c_i\oplus\mathsf{ipad})\|x\bigr)\Bigr)$$
then build
$$H(x)=\Bigl(\bigl(H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)\bigr)\bmod(p-1)\Bigr)+1$$
where for computation of $\bmod$ the $256k$-bit bitstring $H_0(x)\|H_1(x)\|\dots\|H_{k-1}(x)$ is converted to integer per (say) big-endian convention.

$H(x)$ is slightly biased towards zero, but the advantage an adversary can get from that is negligible.

There would be two issues when directly using $H(x)=\operatorname{SHA-256}(x)$ as considered in the question (or $H(x)=\operatorname{SHA-256}(x)\bmod p$ which is equivalent if $\log_2(p)>256$ ):

Except for $p$ just above $2^{256}$, it is easy to recognize such $H$ from a random function $H \colon \{0,1\}^* \to \mathbb{Z}_p^*$, because $H(x)<2^{256}$.
It is quite possible that there exist $x$ with $\operatorname{SHA-256}(x)$ the all-zero 256-bit bitstring, so that $H(x)$ is not in $\mathbb Z_p^*$; however we know no computationally feasible way to exhibit such $x$, thus this might not be a practical issue.


Highest prime number calculated on a regular PC

You don't use a sieve to find cryptographic-size primes.

One method chooses an odd number of the appropriate size at random, then tests it using a Miller-Rabin or Lucas pseudoprime test, incrementing the number by 2 until a probable prime is found; an alternative is to pre-sieve with small primes (less than 1000, say), and perform pseudoprime tests only on those numbers that survive the sieve. That works, and is commonly used in cryptographic practice, but is not guaranteed to find a prime number. An implementation of this method is available at my blog.

Also at my blog is an explanation of a better method for generating cryptographic primes:

  Sometimes you need to have a large prime, for testing, cryptography,
  or some other purpose. I’m talking about primes of several hundred to
  a few thousand digits that are certified — proven to be prime
  — rather than probable primes according to a Miller-Rabin or
  other probabilistic test. Henry Pocklington’s Criterion, which dates
  to 1914, gives us a way to find such primes quickly. Paulo Ribenboim
  explains it thus:

  Let p be an odd prime, and let k be a positive integer, such that
  p does not divide k and 1 < k < 2(p + 1). Let N = 2kp + 1. Then the following conditions are equivalent:

  N is a prime.
  There exists an integer a, 1 < a < N, such that a(N−1)/2 ≡ −1 (mod N) and gcd(ak + 1, N) = 1.

  This gives us an algorithm for generating large certified primes.
  Choose p a certified prime. Choose 1 ≤ k < 2p at
  random; we ignore the last two possibilities for k, so we don’t have
  to worry about k being a multiple of p. Compute N. For each a
  ∈ {2, 3}, test the conditions for primality. If you don’t find a
  prime, go back and choose a different random k. Once you have a
  prime N, “ratchet up” and restart the process with the new certified
  prime N as the p of the next step. Continue until N is big
  enough.

There is code and a more complete explanation at my blog.


In HMQV, can one use multiple identities with one public key?

I think you are not familiar with the PKI-based setting. In the PKI-based setting, each user owns a certificate that binds his/her identity with his/her public key. If a user uses multiple identities with one public key, that means he/she must use same public key with a different identity to register many times, at this point he/she will receive different certificates(the number of which is the number of the identities belonging to a user). Well, this is very easy to avoid in the CA, it is only required that repeated registering is not allowed.

Actually, even if this case happens, then HMQV is still secure only if the secret key corresponding to the same public key isn't compromised.


Is TrueCrypt's multiple/cascading encryption safe?

Cascading cipher gives a sense of security; and one that is technically justified with respect to the possibility that a weakness in one of the cipher would allow recovering the encrypted data. That's Bruce Schneier's argument, and it made sense in an era where DES, the then leading cipher, was a closed design, clearly deliberately weakened by a small key, giving rise to the fear that is was also deliberately weakened otherwise (which turned out not to be the case).

On the other hand, the more serious threats facing systems like TrueCrypt are not a weakness of the cipher; they include compromise of the software, compromise of the hardware running the software, compromise of the key (by eavesdropping, guess of the passphrase, rubber hose cryptanalysis, recovery from hibernation file or RAM memory..), analysis of changed sectors.. These risks are hard to mitigate, and in the opinion of many (including me), much more likely to materialize than cryptanalysis of AES, for at least decades even if we consider AES-128. And further, technological progress likely will enable a guess of the passphrase by brute force sooner than a cryptanalysis of AES.

Cascading ciphers has at least one obvious drawback: performance is lowered. Often it matters, sometime it does not, e.g. when enciphering a key. In my opinion, compared to AES, cascading might only improve practical security by a side effect: making it harder to verify a guess of the passphrase (that would be the case in a system where the only way to check such guess is to turn the passphrase into keys, decipher something using the cascade of ciphers, and check that it makes sense).

So all in all, I would think of cascading a cipher in addition to AES only as a way to damp paranoia or indicate an extra level of care, like telling to someone knowing little about cryptography: for the cold storage of your all-important master keys, you could use a Truecrypt volume on a USB stick, perhaps even with cascaded ciphers; and most importantly, strive for the integrity of all the hardware and software used!

Addition following comment asking how to do cascading (of block ciphers) properly. My answer to that would be that if one uses cascading:

That might be considered in the key-stretching phase (turning the user's passphrase into the key of the bulk cipher), where cascading is useful, because it makes construction of a device that successfully brute-force passphrases significantly harder/more expensive/less likely. Cascading is useful in key stretching because when a cascade of encryptions is iterated, a fast implementation must be fast on each of the cascaded ciphers, which is a very serious problem in a password cracker using ASIC or FPGA; search FPGA password for some interesting links. Beware however that speed optimization of the legitimate implementation for each of the cascaded cipher iterated in the key-streching phase is important for security (because we need to push the number of iterations as high as feasible), when it is immaterial to security in the bulk-encryption phase.
At least the first cipher in the cascade (the one in contact with the plaintext during bulk encryption, or to a lesser degree the one in contact with the passphrase during key stretching) should be implemented in a manner protecting from any likely side-channel attacks, including timing and unwanted emissions (for an illustration of that later danger in a slightly different context, see this).
When the key must be secret (in particular the key used for bulk encryption), the cascaded ciphers positively must use different keys (e.g. extracted from a wide derived key); otherwise using a cascade could well turn out to enable an attack if any of the ciphers turns out to leak its key through a side channel.

Truecrypt's use of cascaded ciphers definitely follows 3; I can't tell for 2, and the most important 1.


What is the security strength of McEliece variants?

Further search at this Round 3 Official Comment Newsgroup - found here
https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/official-comments/Classic-McEliece-round3-official-comment.pdf
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/EiwxGnfQgec?pli=1
OP (Kirk Fleming) sets up these estimates

mceliece-3488-064   143
mceliece-4608-096   207
mceliece-6688-128   272
mceliece-6960-119   272
mceliece-8192-128   272

DJ Bernstein (from the submitters - the Classic McEliece team) doesn't appear to be too enthusiastic about those security strength bits.


Public key cryptography per-ce cannot protect the authorship. In your example, e.g., Bob could re-type Alice' joke, sign it with his own valid key, and claim that he thought about it before Alice sent him the joke.

A possible solution could be to use a trusted escrow: Any party who invents a joke and wants to hold title to it has to send the joke to the trusted escrow before telling the joke to anyone else. The escrow timestamps the joke and signs the timestamped joke with their private key.

Now if Carrol receives the same joke from both Alice and Bob, who both claim title to it, and Carrol wants to know who is the real author, then she goes as follows:

Ask both Alice and Bob to send the joke as was originally signed by the trusted escrow.
If one of them fails to provide a signed joke then we assume that she/he is an imposer.
If both send a signed joke then Carrol will:

a. Verify with the trusted escrow's public keys that both signatures are valid.

b. Compare the time stamps.

We formally define the author of the joke as the one whose timestamp is the earliest.


This is a summary of the indicated section of Cryptographic Extraction and Key Derivation: The HKDF Scheme from user4982's comment.

Because this is in the context of an academic paper describing a HMAC based KDF, the terminology can be a bit excessive. I have tried to trim it down in this summary.

Definition of a KDF:

A KDF takes four inputs: a key source value, an output length, a salt, and a context variable. The last two are optional. The security and quality of the KDF depends on the properties of the key source value.

Definition of a key source:

A source comprises two values, the key source material and auxiliary knowledge about it, created using an algorithm with sufficient statistical entropy to be considered random. (The auxiliary knowledge can be the distribution from a statistical entropy source, or the non-secret values of a DH key exchange, or any other related, but not secret data about the key source material)

Definition of the security of a KDF:

A KDF is secure if an attacker knowing the auxiliary data and salt value has little chance of deriving the key source material and context variable from repeated attempts at using the KDF with the auxiliary data, salt, and random key source materials and context variables (a.k.a brute forcing the KDF).


Good layperson analogy for password and encryption keys

A cryptographic key is a string of bits. For example, AES-128 uses 128 bits, each one of them being either 0 or 1. To be able to encrypt or decrypt, each one of those 128 bits must be set correctly. This key is the input to the encryption algorithm. For AES-128 it has to be exactly 128 bits - not more nor less.
For humans, remembering 128 bits (= 16 bytes) is very difficult and impractical. It's much easier to remember (and type) a passphrase such as "mary had a little lamb" than an AES-128 key such as 0a fc 5d e7 43 21 9c b3 6f 1b 93 c7 70 55 24 18. Furthermore, a requirement that all passwords must be exactly 16 bytes is silly. For AES-256 you woud need twice as much. And of course, the true entropy of a 16-character password is much less than 128 bits because of language redundancy and the fact that an ASCII character takes up only 7 bits.
This is why we have key derivation functions (KDF). You input a password of any length into a KDF and tell it how many bits you need for key. The KDF takes the bits from the password, adds some magic spices (called salt) and mixes them up using some cryptographic hash function. You get out just as many bits as you wanted which have the same statistical properties as if they were random. They are based on password, so the same password will always give you the same key. As such, KDF are a perfect "converter" of passwords into cryptographic keys.
If an adversary wants to break the encryption, he/she ultimately needs the encrption key (e.g. 128 bits for AES-128). With a truly random key, this means trying 2^128 combinations, which is an awful lot. Because passwords have less entropy, it would make more sense to attack the passwords as this would reduce the needed effort by several orders of magnitude. However, good key derivation functions such as PBKDF2 are designed to counter this by requiring to do a long computation (basically applying the hash function 10000 times). This "computational cost" slows down the attack on passwords significantly and makes it unfeasible.
As an analogy:

Cryptographic key is a key that actually opens the door.
Password is the secret word that you tell to the locksmith (KDF) so that he can make a key for you. If you tell the same password to the locksmith, you get the same key.


With AES-CTR does the block input need to be implemented as nonce || counter?

Usually a 128 bit counter is implemented, and the 16 byte IV is really just the initial counter value, consisting of the nonce and a counter. The counter is generally an unsigned value. So your scheme is very possible, but other implementations may make other choices (and if you look at NIST SP 38A, Appendix B, about any scheme suffices).
The fully random IV scheme however has a problem. You never know how close the initial random value is to another initial random value. The chance of two counters out of $N$ counters being close to each other quickly increases with the number of IV's generated.
If you have a incrementing part consisting of $l$ bits then you can have $2^l$ separate counter values before you may run into a collision. There is still a birthday problem, but it is now at least quantifiable, and it's only an issue for the nonce, not for the entire counter. Furthermore, you know exactly how large your message may be.
Let's create an example, which one would you rather have of these initial IV's?
Fully randomized:
27df9ad9921861c7 b53ab03a aad9bf3f
27df9ad9921861c8 dca9d07a 2f50dc18

or nonce || iteration counter:
27df9ad9921861c7 b53ab03a 00000000
27df9ad9921861c8 dca9d07a 00000000

On the first you've got a random amount of counters for each message (in this case 0x84771CD9 or 2,222,398,681), for the second you've got exactly $2^{32}$ counters. Worse, in the first case you don't exactly know how much space you have, because you're not going to store the random values.
The fully random scheme is also somewhat slower as it requires more random bytes. It also requires careful handling of overflows, as you don't want to have an issue after you hit FFFFFFFF.
In short, if the random scheme has any advantage then I'm missing it; I would strongly recommend keeping to a concatenated nonce and counter as input block.


Am I understanding AES key padding correctly?

AES by definition takes 16, 24 or 32 bytes as key, and nothing else. If you have a different size input use some kind of KDF to transform it to the correct length.

If that input is a password this step is even more important. You should a key strengthening construction, such as PBKDF2 with sufficient iterations and a salt.
If you use authenticated encryption, the verification of the authentication tag will fail if the key is incorrect. It's strongly recommended to use authenticated encryption. Not only will it tell you that the key is correct, it'll also prevent a variety of active attacks, such as padding oracles.

You can either use an authenticated mode, such as AES-GCM, or normal AES followed by HMAC (Encrypt then MAC).


Filter party-1 strings against party-2 white/black list keeping the lists private

I see two problems;

The number of keywords is very small and a dictionary attack is possible from the server.

for i in English_Dictionary
    if Hash(i) == target_hash
       return success

Also, one can use Rainbow tables, too. To overcome these, you will need to add salt to your plaintext to prevent any dictionary or rainbow attacks from the server side.

There are more advanced methods for protection, as;

The search on encrypted data which is started with the Song et. al's
idea.
There is another method, which may be too slow, use FHE
techniques. You can totally blind the server.
If the client asking whether this string is black or white, you can also use Private Information Retrieval (PIR) techniques. There is an FHE PIR implementation.

Also, the frequency of the hit may leak information 1,2. The frequency attack really depends on the application. The method listed above, not the salt, can overcome the frequency attack, too.


Security of Carter-Wegman polynomial authenticators, and their concatenation?

Tight security bound for elementary attack model:

Well, here's the general theory; suppose the attacker had a valid message, MAC pair $(m_{1,...,l}, H)$ with

$$H=s+\sum_{i=1}^l m_{(l+1-i)}\cdot {r}^i$$

and he selects a different pair $(m'_{1, ..., l}, H')$.  His pair would authenticate if:

$$H'=s+\sum_{i=1}^l m'_{(l+1-i)}\cdot {r}^i$$

or, if $r$ happens to be a root of

$$0 = H-H' + \sum_{i=1}^l (m_{(l+1-i)} - m'_{(l+1-i)})\cdot {r}^i$$

This is an $l$-degree polynomial over a field, and hence has at most $l$ roots.  And, as $s$ is chosen randomly, the attacker gets no other information about what $r$ can be, and hence he has to guess blindly; the bottom line is that the probability of success for any chosen ciphertext is bounded by $l/f$ (or, more generally, the probability of success after $z$ queries is bounded by $lz/f$.  And, if we consider an attacker that selects $l$ values $a_{1..l}$, and uses $(x-a_1)(x-a_2)...(x-a_l)$ as the different polynomial, we can see this will succeed iff $r = a_i$ for some $i$, and hence this probability is tight.  (for $lz/f \le 1$).

  Do we reduce $\epsilon$ by excluding some $r$, e.g. requiring $r \ne 0$?

Actually, we increase it somewhat.  If the attacker knows that some of the potential values of $r$ are impossible, that is, there are actually only $f'$ possible $r$ values, he can use this knowledge to increase his success probability to $l/f'$.  As you can see, this doesn't harm security much if we just exclude a handful of values; however we probably don't want to eliminate a large majority of them.

  Are some fields better than others ?

Actually, no (other than the size of $f$); the above logic used no property of the field (other than that it was a field), and hence it applies equally to all fields.

  Concatenation of authenticators using the same field

The attacker gets to play the same game, he gets to pick $l$ values $a_{1..l}$, and he'll succeed only if both $r, r'$ are within the $a_{1..i}$ values (actually, he can pick different values for the different authenticators, as they do not share the constant term; that doesn't appear to change the conclusion).

Hence, we get a probability bound of $(l/f)^2 = l^2 / f^2$ (or, more generally, of $k$ authenticators, $l^k / f^k$)

At first glance, this looks better; however remember that, in this case, $f$ is smaller; if $f$ is $1/k$ the size of the field size of the original approach (that is, the same total tag size), then the success probability we allow an attacker increases by a factor of $l^{k-1}$.

This may be a reasonable approach, if $l$ isn't too large.  On the other hand, if we allow quite long messages, this just doesn't work.

  Concatenation of authenticators using different fields

Same reasoning applies, $l^2 / (f \cdot f')$.  Now, I don't know how feasible the attacker will find it to a common message that generates difference polynomials in the different fields all with lots of roots; I'm guessing that it may be possible, and so I wouldn't want to make a security assumption based on it.


What is the difference between MAC and HMAC?

A Message Authentication Code (MAC) is a string of bits that is sent alongside a message. The MAC depends on the message itself and a secret key. No one should be able to compute a MAC without knowing the key. This allows two people who share a secret key to send messages to each without fear that someone else will tamper with the messages. (At least, if someone does tamper with a message, this can be detected by checking to see if the MAC is right.)

The term "MAC" can refer to the string of bits (also called a "tag") or to the algorithm used to generate the tag.

HMAC is a recipe for turning hash functions (such as MD5 or SHA256) into MACs. So HMAC-MD5 and HMAC-SHA256 are specific MAC algorithms, just like QuickSort is a specific sorting algorithm.

There are other ways of constructing MAC algorithms; CMAC, for example, is a recipe for turning a blockcipher into a MAC (giving us CMAC-AES, CMAC-DES, CMAC-PRINCE, and the like).

Some MAC algorithms use IVs. Others, such as HMAC, do not.

MAC algorithms should have the security property of being unforgeable under chosen-message attacks. Let's say that Alice and Bob share a secret MAC key (which they use when sending messages to each other), and that Eve is spying on them and sees both their messages and the corresponding tags.
Eve should not be able to use what she learns to fake valid tags. This should even be true if Eve can convince Bob to send specific messages.

For example, pretend Eve tells Bob to send the message:

  Dear Alice,

  Eve said "hi."

  Love, Bob

and then Eve sees the corresponding tag.
Eve should still be unable to "fake" the tag for the message:

  Dear Alice,

  Please give Eve $100 for me. I'll pay you back.

  Love, Bob

In addition to being unforgeable under chosen-message attacks (UF-CMA), HMAC has the stronger property of being a pseudo-random function (PRF). This means that if Eve doesn't know the key, then all of Bob's HMAC tags look like completely random strings of bits, even if Eve knows or even chooses what messages Bob sends. This is a stronger property because every PRF is UF-CMA (you can't guess a big random number), but not every UF-CMA MAC algorithm is a PRF (it's possible that for some MAC algorithm, all the tags begin with 10 zeroes --- not very random-looking at all, but the other bits could still be hard to guess without knowing the key).


Confusing terminology about stream ciphers

If you used the randomly generated keystream bit $k[i]$ twice (think of it as a random variable, uniformly and independently generated at time $i$) at positions $i,i+\tau,$ then you'd have
$$
c[i]=p[i] \oplus k[i]
$$
and
$$
c[i+\tau]=p[i+\tau] \oplus k[i],
$$
then adding the ciphertext bits would yield the plaintext bit "difference"
$$
p[i+\tau]\oplus p[i],
$$
destroying the property that
$$
c[i]\oplus c[i+\tau],
$$
is independent and uniformly distributed, and making the conditional distribution of $c[i+\tau]$ given $c[i]$ dependent on the plaintext difference $p[i+\tau]\oplus p[i],$ which need not be uniform.

Thus the ciphertext sequence is no longer purely random (independent and uniformly distributed) which destroys the perfect secrecy property of the OTP system, since the ciphertext distribution is no longer independent of the plaintext distribution.


Proper uses for CTR and CBC AES block cipher modes

As said by Thomas in the comment, modern encryption algorithms should work for all kinds of data, regardless of whether the plaintext is partially known or not.

In both modes of operation (CTR and CBC), for stored data you should remember to get a new initialization vector and reencrypt your whole "message" (or database entry) when changing any part of the data, not try to reencrypt only the changed parts. (Though CBC is likely a bit more robust here – the attacker in the case of IV reuse only gets to see from which block on the data changed, while with CTR mode she can see the XOR difference between the old and new values, assuming she can observe both ciphertext.)

  Is it possible for someone to discover the CTR counter value
  knowing some of the bytes in the original message?

The counter value can be derived from the initialization vector, and thus is considered public knowledge (even if nothing is known about the plaintext). There is no weakness resulting from that, as long as you take care not to repeat your counter values.

With CTR mode, you don't get authentication, which means that an attacker who is able to change your message and observe your programs reactions to that might gain some knowledge about the contents. To avoid this, combine it with a MAC algorithm (preferably on the ciphertext), like a HMAC, which refuses decryption if failed. (Have an independen key for your MAC.)

The same is valid for CBC, just the methods of attacking are different. Here it is even more important to apply the MAC on the ciphertext, not on the plaintext, for the mentioned padding oracles.

As Ricky Dehmer mentioned in a comment, an attack scenario would be someone who got write access to your database, but doesn't have the key, and aims either to maliciously modify the data, or to use chosen-ciphertext attacks to break your encryption privacy.

Don't forget to include the initialization vector in the MAC-ed message.

For an encrypted database column, you could store the tuple (IV, Ciphertext, MAC tag) together, either in one column (most easily in this order) or in three columns, and for decryption pass them together to your decryption function, which should first check the MAC, and then decrypt the ciphertext.

A authenticated encryption mode like OCB or GCM already includes the authentication, so you have less hassle to worry about.


Understanding calculation of collisions in hash-functions

I suspect you are misrepresenting what your professor actually said.

Since I'm not certain exactly what he said, here is how I would explain it:

With 1024 outputs, there are $\binom{1024}{2} \approx 1024^2/2$ pairs of outputs.
For each pair of output, that pair has a $2^{-12}$ probability of being a collision (that is, those two outputs being exactly the same).
Hence, the expected number of collisions would be about $1024^2/2 \times 2^{-12} = 128$

The exact expected number would depend how you count a multiway collision (where 3 or more outputs have the same value); it turns out that, if you count it right, $\binom{1024}{2} 2^{-12}$ is the correct answer.


Hashing passwords with a salt - why use different salt for everyone?

Let's try to avoid random per-password salts. If the only requirement for salt is to be unique, which is the case for good password hashing schemes, you'll need:

$globalSalt$ is a secret random 32-byte string.
$userId_n$ is a unique user identifier.

You can use, for example, $HMAC$-$SHA256(globalSalt, userId_i)$ to generate salt for each user $i$. Or, with PBKDF2 or scrypt, you can just concatenate the values of $globalSalt$ and $userId_i$.

This scheme achieves uniqueness for salt only when you don't allow users to change their passwords. If you do, salt will be unique per user, not per password, so if someone changes their password, their salt will stay the same. In which case, if there are database leaks at, say, three points in time, given that the salt is unique per user, not per password, the attacker gets some information about passwords (e.g. if the user changed their password to the same value.)

To make salt unique per password, you also have to include some counter of password changes, which you have to update and store, and concatenate with $userId$. Storing this counter per-user defeats the original intention, so you can have a single global counter, making sure it never repeats, in which case you can also drop $userId$ and just use this counter along with $globalSalt$.

If $globalSalt$ is leaked, the only advantage the attacker gets is that he will be able to precompute future hashes for current and future $userId$s, which doesn't seem very useful.

We avoided generating and storing random salts by building a more complex and less secure system. Thus, it's much simpler and more secure, as others said, to use random salts instead of bothering with implementing your own scheme.


Why does CBC-MAC need prefix-free inputs to be a good PRF?

Because CBC-MAC with inputs that are not prefix free is weak against existential forgery, meaning it is not a "secure" MAC.  More precisely, CBC-MAC is easily distinguishable from a random function (i.e. not a PRF) when the input domain is not prefix-free.  This is because an adversary can request the CBC-MAC of messages $M_0$ and $M_1$, and then xor the MAC for $M_0$ with the first block of $M_1$, and thereby trivially construct another message, $M_2$ (such that $M_2 = M_0||\overline{M_1}$, where $\overline{M_1}$ is $M_1$ with the first block altered).  $M_2$ will have the same MAC as $M_1$, which is a collision that should be very hard to find for a PRF.  Note that $M_0$ is a prefix of $M_2$.

CBC-MAC can be made secure by either i) only using it for fixed-length messages (because no message of length $l$ can be a prefix of any other message of length $l$), or ii) always prepending $L_m$, the length of the message, to the message and using CBC-MAC on the string $L_m || M$.


No, this is not the case. We can't guarantee an honest prover is verified by a dishonest verifier (they could always lie and say "no, you failed"), but they could very well be authorized by the dishonest verifier (in addition to lying and saying "you passed" for everyone, they could act like the honest verifier if it's to their advantage). A dishonest verifier can generally do anything, so it's impossible to say anything about whether the prover will be verified by them. In addition, the most likely sort of dishonest verifier (the one who seems to be following the protocol, such that a third party seeing the messages doesn't know they're dishonest) will always authenticate honest provers.

What "honest verifier" refers to is not the authentication bit; it's about zero-knowledge. We can't stop a dishonest verifier from refusing to authenticate an honest prover; however, we might be able to keep them from learning about the secret. For honest verifiers, who select the challenge at random, we can prove that the honest verifier cannot be learning anything about the secret. But this proof doesn't work with a verifier who selects the challenges very carefully; there's no known proof that they can't learn about the secret (other protocols have proofs that a cheating verifier can't learn anything, but Schnorr does not). That doesn't mean we know they can learn something; we don't know one way or the other.


Cryptographic enforcement schemes using Diffie-Hellman

1) The meaning of a poset is that there may also be members $x,y \in X$, where neither $x \leqslant y$ nor $x \geqslant y$. Now consider such incomparable $x$ and $y$ with $parent(x)=parent(y)=w \in X$ and furthermore $u \in X, y=parent(u), x \nleqslant u, x \ngeqslant u$

Now $k(x)=f(k(w))=k(y)$. Then also $k(u)=f(f(k(w))=f(k(x))$, even though $x$ is not a predecessor of $u$. This is clearly a security violation in almost any information-flow control policy.

2) you would need an additional hash function to return the result of the DH exponentiation back to the key-domain.

3) It is not a good idea to change identities while changing keys

4) You will need information on the DAG structure to define the actual function used, which is considered inefficient in HKAS

5) In general, it is not a good idea to have node keys computed from parent keys, instead other secret values are used, to enable efficient key-updates

6) It is more efficient in change management and initial deployment to have anything depend only on one predecessor rather on multiple ones. Remember, the nodes are security levels, not users or computers.


Are my random numbers really "bad" or is that a statistical effect which "must" happen from time to time?

One of the failing test discussed in the question was coded for the purpose. It could be useful to validate that code using a known-good pseudo-random source (the output of SHA-256 for incremental values qualifies). If it failed too often, the code would need a fix! The test's definition is complex, for example in 2.7.4 (2) defining how to count the number of occurrences of the pattern searched, and an error could have crept.

But I fail to imagine an error giving what's observed, and (after fixing an issue about the definition of the incomplete gamma function that had no influence for the reference test case, and a typo of mine in one count) I confirm that the question's P-values match the question's counts.

With these results (especially the second test case, with a P-value < 1/9830), at least one of the following must hold:

the generator's output is quite distinguishable from random (my guess);
that's a serious case of bad luck (how bad depends strongly on among how many tests the failing cases shown have been picked, see below);
the question's counts are somewhat wrong in a strange, irregular way;
the math in the reference is seriously bad (but I guess that would be known).

Importantly: it appears that the test is run with many patterns. In that case, the P-value threshold considered a failure should be lowered (like, divided by the number of tests); or best, the P-values should be aggregated. For aggregation, we could use Fisher's method. In theory that requires the tests to be considered independent, which would be the case if a sample RNG output is never tested with multiple patterns. Practitioners occasionally are not so careful, but that seldom is a game-changer.

Note: The reference only skims at the issue of choosing P-value thresholds (noted $\alpha$), and does not tell how to decide if the overall result of multiple tests is pass or fail. It even makes highly misleading statements on how to interpret P-values, like the second of these three sentences at end of section 1.1.5 (emphasis mine):

  An $\alpha$ of 0.001 indicates that one would expect one sequence in 1000 sequences to be rejected by the test if the sequence was random. For a P-value ≥ 0.001, a sequence would be considered to be random with a confidence of 99.9%. For a P-value < 0.001, a sequence would be considered to be nonrandom with a confidence of 99.9%.

The question rightly observes

  Most interestingly, when I increase the block size by a factor of 10 (800,000 random bytes: N=8, M=800000) I get only good results on all patterns.

Especially if the generator tested is an unconditioned TRNG (see below), that would match a failure mode where the generator locally has repeating patterns, but these evolve over time.

If the source of the data tested is an unconditioned TRNG, and unless the supplier of that thing guarantees in a contract with severe penalties that no conditioning is necessary to pass any kind of test (which would be a foolish move), then failing a RNG test should be considered normal. Correspondingly, submitting this output for validation by a lab should be considered a procedural mistake: these tests are intended to test if a RNG is distinguishable from random, and unconditioned TRNGs often are!

On the other hand, if what's tested is the output of a PRNG seeded with the TRNG (as would be typical for a black-box test), and the test fails, that's indicative of (both) an extremely poor/defective PRNG and a failure of the TRNG.

Unconditioned TRNGs typically have defects, often subtle, dependent on manufacturing variations and environmental conditions. The design engineer has to factor that in. The output of an unconditioned TRNG should be used (exclusively when in operational mode):

to monitor failure of the unconditioned TRNG; the monitoring's goal is ensure that the source delivers some entropy, above some designed-in limit, without raising false alarms.
and to feed a PRNG, which results are used (not the TRNG's unconditioned output).

Further, if that PRNG is not a CSPRNG (which is typical of hardware PRNGs, often a variation around LFSR), for some critical usages the output of the PRNG should be the input of a good CSPRNG (it is often considered OK to directly use the hardware PRNG for more mundane things, like massive DPA countermeasures).

It is easy to turn a passable TRNG into a good RNG that passes all standard test. What's hard is to make monitoring that demonstrably detect failure on the field and acts accordingly, but does not falsely detect failure under normal use. True failure could be because attackers do all sort of nasty things: under/overvoltage, heat or evaporation of a liquefied gas to reduce the entropy rate of the RNG source, or superimposed clock/glitches on the power supply (and more) in an attempt to control the TRNG source and make it near deterministic. Sometime the adversary is only Murphy's law (perhaps in the form of poor contacts, long wires, unclean power supply, insufficient decoupling, manufacturing defect) but succeeds just as well.

Note: I heard a tale about a then inexperienced hardware manufacturer proposing an IC with module initially specified as a directly usable TRNG that always work; then found to sometime fail a test; and hastily replaced by a conditioned TRNG, with no access to the unconditioned TRNG specified. That reportedly made it difficult to properly monitor the TRNG: the only sound option would have been to break the conditioning, but the tale ends without clear indication that this was achieved and deployed.


Are MAC algorithms and digital signatures secure from quantum computers? If not, why?

MACs don't involve any key exchange. The ability to share the key is assumed, just like with symmetric encryption. I'd tend to recommend a 256 bit key over a 192 bit key, because the effective key length is halved. 96 bits effective security might be breakable eventually, 128 bits effective security basically never will without discovery of flaws in the algorithm or implementation.

I understand that asymmetric encryption is fundamentally deemed useless under Shor's Algorithm,

This is incorrect. RSA and the usual ECC constructions (ECDSA, EdDSA, ECDH) are breakable for all practical key sizes. Other asymmetric constructions not based on integer factorization (RSA) or the discrete log problem(s) (ECC, ElGamal, traditional Diffie-Hellman) can be secure. EG Lattice-based cryptography (including but not limited to learning with errors, ring learning-with-errors, module learning-with-errors, and module learning-with-rounding), code-based cryptography, supersingular isogeny Diffie-Hellman are all asymmetric encryption thought to be resistant to attack by quantum computers. NIST is running a public contest to standardize some of these quantum-resistant asymmetric algorithms. It's currently in its third round.


In the article, "weak PUFs" are for key storage, and "strong PUFs" are for authentication, but both are PUFs.  It's just a function of how you use them.  A 32-bit PUF is just a random 32-bit number.  What makes a weak PUF strong is pairing it with an HMAC circuit, or something for a challenge response.
A few notes on the article:  the assumption that EEPROMs are expensive in both power and area is not really true.  It's difficult to find any IC without some sort method to hold the serial number, and if it is not EEPROMs, it's e-fuses (eFUSE, antifuse).  Everything in IoT has some sort of method to program memory.   To that end, if I have EEPROM infrastructure already, PUFs cost more regarding area, and both circuits have the same issues when I de-cap something and put my probes on it.  The circuit discussion was rather weak and some of the implementation examples in the overview won't work on aggressive nodes.


GCM cipher M0 tables : semantic questions on how to implement GCM

$M$ is a table with 256 elements, where each element has 16 bytes (128 bits), such that $M[x]$ is equal to $x \cdot H$

In the first step, the 128-th element is set to $H$, i.e. $M[128] = H$. The reason for that is the confusing bit order convention of GCM (see What does GHASH really do?). GCM works with binary polynomials, and the polynomial $1$ is represented, as a byte, as the integer value $128$ (e.g. $1000000$ in binary) instead of of $1$ (e.g. $00000001$ in binary). Therefore, what the first step is doing is setting $M[1] = H$, if GCM were defined with a more conventional bit order.

The rest of your confusion probably arises from the same issue. So anywhere you see $M[i]$ in the algorithm, pretend it's $M[rev(i)]$ where $rev$ reverses the bits of the input, and things may start to make more sense.

Also, $P$ is not the plaintext, it's the polynomial $\alpha$ (i.e. $010000...0$)


Can you help me understand Bernstein’s Notes on Diagonal constant of Salsa20?

The Salsa20 core is defined on a $4\times4$ matrix $x$ of 32-bit words by $\operatorname{Salsa20}(x) = \pi(x) + x$, where $\pi$ is a permutation.

Consider a matrix:

\begin{equation}
  x =
  \begin{pmatrix}
    A_0 & B_0 & C_0 & D_0 \\
    A_1 & B_1 & C_1 & D_1 \\
    A_2 & B_2 & C_2 & D_2 \\
    A_3 & B_3 & C_3 & D_3
  \end{pmatrix}.
\end{equation}

If we transform it into the matrix

\begin{equation}
  S(x) =
  \begin{pmatrix}
    D_3 & D_2 & D_1 & D_0 \\
    C_3 & A_0 & B_0 & C_0 \\
    B_3 & A_1 & B_1 & C_1 \\
    A_3 & A_2 & B_2 & C_2
  \end{pmatrix},
\end{equation}

that is move every cell downward and to the right along the diagonal, then it turns out that $\pi(S(x)) = S(\pi(x))$, for the particular $\pi$ used in Salsa20; consequently, since $S(x + y) = S(x) + S(y)$, the Salsa20 core has the property that $$\operatorname{Salsa20}(S(x)) = \pi(S(x)) + S(x) = S(\pi(x) + x) = S(\operatorname{Salsa20}(x)).$$  This transformation $S$ is called a shift, and it is invertible, so the space of all transformations $S \circ \cdots \circ S$ forms a group called the shift group; there are, of course, only four distinct shifts, since shifting four times is the same as not shifting at all.  The orbit of an element $x$ under the shift group is the set $\{x, S(x), S(S(x)), S(S(S(x)))\}$.

Similarly, consider a 32-bit integer $A \in \mathbb Z/2^{32}\mathbb Z$ of the form $$A = a_0 + 2 a_1 + 4 a_2 + 8 a_3 + \cdots + 2^{31} a_{31}.$$  Define the 32-bit integer $$R(A) = a_{31} + 2 a_0 + 4 a_1 + 8 a_2 + \cdots + 2^{31} a_{30},$$ and for a $4\times4$ matrix $x$ of 32-bit integers define $R(x)$ elementwise; that is,

\begin{equation}
  R(x) =
  \begin{pmatrix}
    R(A_0) & R(B_0) & R(C_0) & R(D_0) \\
    R(A_1) & R(B_1) & R(C_1) & R(D_1) \\
    R(A_2) & R(B_2) & R(C_2) & R(D_2) \\
    R(A_3) & R(B_3) & R(C_3) & R(D_3)
  \end{pmatrix}.
\end{equation}

It turns out that, again, $$\operatorname{Salsa20}(R(x)) = R(\operatorname{Salsa20}(x)).$$  The transformation $R$ is called a rotation, and it too is invertible, so the space of all transformations $R \circ \cdots \circ R$ forms a group called the rotation group; there are, of course, 32 distinct rotations.  Again, the orbit of an element $x$ under the rotation group is the set $\{x, R(x), R(R(x)), \dots\}$.

We can also consider shifts and rotations, like $S(R(R(x))$.  As it happens, this is the same as $R(S(R(x))$ and $R(R(S(x))$, because $S$ only affects the matrix structure while leaving the elements intact, while $R$ only affects the elements and leaves the matrix structure intact—it doesn't matter which order you shift or rotate, so you can always uniquely write a composition of shifts and rotations as $R^\nu \circ S^\mu$ for some $\nu, \mu$, forming the shift/rotation group; as before, the orbit of an element $x$ under this group is the set $\{R^\nu(S^\mu(x))\}_{\nu,\mu}$.

These symmetries spell trouble if we use the Salsa20 core directly with arbitrary matrices—cryptography is normally about destroying structure so an adversary can't recover it, but shifts and rotations pass through the Salsa20 core unscathed.  Fortunately, we don't use the Salsa20 core that way.  When we use it with a key $k$ to generate the $n^{\mathit{th}}$ block $\operatorname{Salsa20}_k(n)$ of pad material for encryption, we encode the 8-word (32-byte) key $k$, the 4-word (16-byte) nonce/counter $n$, and a constant $\sigma$ (4-word/16-byte) into the matrix $x$:

\begin{equation}
  \operatorname{Salsa20}_k(n) = \operatorname{Salsa20}(x), \quad\text{where}\quad
  x =
  \begin{pmatrix}
    \sigma_0 & k_0 & k_1 & k_2 \\
    k_3 & \sigma_1 & n_0 & n_1 \\
    n_2 & n_3 & \sigma_2 & k_4 \\
    k_5 & k_6 & k_7 & \sigma_3
  \end{pmatrix}.
\end{equation}

This form has the property that there is no rotation or shift $R^\nu(S^\mu(x))$ that has the same form $$\begin{pmatrix} \sigma_0 & \cdots \\ \vdots & \sigma_1 \\ & & \sigma_2 \\ & & & \sigma_3 \end{pmatrix},$$ except when $\nu = \mu = 0$, i.e. the trivial shift and rotation that leaves the matrix unchanged.  That is, under the shift/rotation group, the orbit of $x$ in $\operatorname{Salsa20}_k(n)$ is entirely distinct from the orbit of $x'$ in $\operatorname{Salsa20}_{k'}(n')$ when $(k, n) \ne (k', n')$—there is no amount of shifting and rotating you can do to get from $x$ to $x'$.  So no amount of control over the inputs to Salsa20 encryption—not control of the nonce, not control of the message, and not even control of the key!—enables an attacker to exploit the shift and rotational symmetry of the Salsa20 core.

This depends, of course, on the particular string $\sigma$.  Had we chosen, say, $\sigma_0 = \sigma_1 = \sigma_2 = \sigma_3$, then the Salsa20 stream cipher might be vulnerable to attacks exploiting shifts, because $S(\operatorname{diag}(\sigma)) = \sigma$.  Had we chosen, say, $\sigma_0 = 1 + 2^{16}$, $\sigma_1 = 2 + 2^{17}$, $\sigma_2 = 4 + 2^{18}$, and $\sigma_3 = 8 + 2^{19}$, then the Salsa20 stream cipher might be vulnerable to attacks exploiting rotations, because $R^{16}(\sigma_i) = \sigma_i$.


Why is lattice-based cryptography believed to be hard against quantum computer?

Because no one has developed a quantum algorithm (yet) that breaks these crypto primitives.

Wish we could do better than that, but that is the best we have at the moment. We believe these primitives to be quantum resistant because no one has given evidence otherwise.


The correct use of the term "TLS session"

Yes, that looks like a correct usage of the word session.

Of course the session keys are only valid for the record layer. But the session keys are tied to the session, not the other way around. And usually the TLS session is of course tied to a TCP/IP session, but that doesn't need to be the case.


Analysis of a primitive often times is conducted on a reduced strength variant of the actual algorithm. This makes it easier to find the weak points of the design, which can become obscured after many iterations.

Assuming a "regular" collision means a collision over the entire 80 rounds, then a 76-step collision finds a collision after 76 rounds.

The paper for the result in question does mention that it is for a free-start collision. As for what this means, there is a Q/A here that does a goob job of explaining. Basically, it means that the attacker is allowed to select the initialization vector.


How hard is to figure out the ENCRYPTION key given message and clear text?

The attack you describe is called a "known-plaintext attack". It was commonly used to break older encryption schemes, most notably Enigma in the second world war.

AES/Rijndael is not susceptible to known-plaintext attacks.

Further reading:

Wikipedia: Known-plaintext attack

Why is AES resistant to known-plaintext attacks?


Why don’t all AES encryption tools produce the same key from the same password?

There are two things here:

Encryption uses mode of operation, and not "AES alone". Some of them are randomized by an initialization vector - that means the encryption of the same text under the same algorithm is still randomized and not deterministic. The encryption methods take care of that. You only need the correct key to decrypt.
Passwords are not keys. If you meet in person, you can create a real random key. That means each bit drawn independently from $\{0,1\}$, not just a password of a certain length, which can be found in any dictionary. If you want to use a password or a passphrase, then you are advised to use a proper key derivation function for passwords, e.g. PBKDF2, bcrypt or scrypt (most recommendations today go towards scrypt).

The problem with tools is, that if they just write "AES" on top, that doesn't mean they use the same mode or the same key derivation function inside. If they do, then the decryption will work. Still, there are non-deterministic modes, where it is an explicit goal, that the same message encrypted twice can not be distinguished from random gibberish.

All you can do is to actually test the tools available to you, if they work in conjunction. And you can stick to the verified, popular implementations. Never use some amateur implementation - never implement your own crypto.


how to obtain the plaintext in counter mode using the AES block cipher

You can't obtain the nonce without having the key which was used for the block cipher.

For CTR mode the ciphertext is $c = m \oplus s$ where $m$ is the message and $s$ is the keystream (which is derived from the key $k$, a nonce and a counter, but this is a minor detail, important is, that re-using the nonce results in the same keystream).

Take two messages $m_1$ and $m_2$ and their corresponding ciphertexts $c_1$ and $c_2$. If we XOR those ciphertexts we get: $c_1 \oplus c_2 = m_1 \oplus s \oplus m_2 \oplus s = m_1 \oplus m_2 \oplus s \oplus s = \mathrm{???}$. Just apply the rules of XOR and you will see, what you get.

Our exercise sheet you are trying to solve, provided another hint: XORing a " " (space) with a letter (in ASCII) flips between lower- and uppercase, e.g. $\mathrm{‘a\verb!’!} \oplus \mathrm{‘\;\verb!’!} = \mathrm{‘A\verb!’!}$. If you XOR two plaintext messages in a character position, where one plaintext message has a space, what can you tell about the other message if you see a letter in uppercase or lowercase?

Now, you might ask yourself: How do I figure out, which of the two plaintexts contains the space? Use the other ciphertexts (there are 11 of them on the task sheet with the same nonce!). What will most of them tell you, if you XOR them with a ciphertext, you presume to have a space at position $i$?

Looking forward to see your solution tomorrow!

Your friendly teaching assistant

PS: You can ask on our Mattermost chat too ;-)


Is it possible to represent max{a,b} as a binary polynomial?

I found the following solution due to Damgard et al.

[1]. Ivan Damgard, Martin Geisler, and Mikkel Kroigaard. Efficient and Secure Comparison for On-Line Auctions. ACISP 2007, LNCS 4586, pp. 416-430, 2007.

Background. Given the binary represetations of $m=m_{\ell}..m_1$ and $x=x_{\ell}..x_1$, let
$$w_i=m_i\oplus x_i\quad\mbox{and}\quad c_i=x_i-m_i+1+\sum_{j=i+1}^{\ell} w_j,$$
then if $m>x$ there is exactly one position $i$ where $c_i=0$, otherwise, no such position exists.  (Please see Page 423 of [1].)

A maple code：

with(Bits)：

pcomp := proc (a, b)

local abin, bbin, la, lb, w, v, c, i, f;

abin := convert(a, 'base', 2); la := nops(abin);

bbin := convert(b, 'base', 2); lb := nops(bbin);

if la < lb then

abin := [seq(abin[i], i = 1 .. la), seq(0, i = 1 .. lb-la)]; la := lb;

elif lb < la then

bbin := [seq(bbin[i], i = 1 .. lb), seq(0, i = 1 .. la-lb)]; lb := la;

end if;

w := [seq(Xor(abin[i], bbin[i]), i = 1 .. la)];

c := [seq(bbin[i]-abin[i]+1+sum(w[j], j = i+1 .. la), i = 1 .. la)];

for i to la do

if c[i] = 0 then f := 1; return f; end if;

end do;

f := 0; return f;

end proc;


RFC 6979 - Why not simply hash the message & the private key for deterministic ECDSA?

Deterministic signatures are safe in the random oracle model. Using HMAC_DRBG allowed me to rely on existing research on the safety of that construction and how close it comes to a "true" random oracle. If I had used any other "handmade" construction, then I would have had to provide extensive analysis on why it is secure. Being naturally lazy, I chose HMAC_DRBG.

Moreover, this use of HMAC_DRBG makes the end result more "convincing" -- and a large part of specifying a cryptographic algorithm as a RFC is to get other people to use it.

(If I had been aware of its existence at that time, I might have considered HKDF instead of HMAC_DRBG, but that does not matter much in practice.)


Lehmer random number generator - cipher?

Is this type of encryption secure?

Nope (even if you make all the $a_i$ values odd, which you need to make it invertible).
It turns out that there are high probability differentials in this structure; in particular, you have a one-round differential with an input xor difference of (01111...11110) (that is, all bits except the first and last are flipped) and the output xor difference of (01111...11110); this differential holds with probability $> 0.5$.  Because the output differential of round $X$ is the input differential of round $X+1$, the entire differential holds through the entire cipher with probability $> 2^{-10}$


The probability of breaking symmetric encryptions

Technically the Caesar cipher is a symmetric encryption algorithm and it is broken so easily it barely requires pen & paper.

So no, this does not hold.

Also, I'm not sure where you got that figure but that is the probability of guessing the correct key in one attempt. Given a modern computer it should at least be feasible to attempt two guesses. ;)


I think you misunderstood a detail of PGP encryption. Only the random symmetric key is encrypted under the recipient's (asymmetric) public key. This way to encrypt stuff is quite common and is called KEM/DEM paradigm: Key Encapsulation Method/Data Encapsulation Method oy Hybrid Encryption. Some refs: en.wikipedia.org/wiki/Hybrid_cryptosystem and en.kryptotel.net/encryption.html.


What I was thinking so far is as follows:

When user first logs into app, input their password along with a salt (stored in a database) to a key-derivation function to generate a
hash
Use this hash to encrypt an AES key
Store this on a database

Firstly, make sure that the user's password has good strength. In general, this is the weakest point even there are strong encryption methods. The usual advice is to tell/teach them to use dicewire method (see in xkcd 936). This will make the passwords have good strengths. If the user's password is weak then password cracking methods will break the encryption; John the Ripper password cracker or the Hashcat searches. It is ciphertext only attack, however, the file structure of the image files will help to determine the correct key.
You can use the password-based key derivation like PBKDF2, or, better use Argon2 as the winner of the password competition in 2015, to derive a key with a random 256-bit salt for each file. The random salt can be appended to the encrypted file. Prefer the Argon2 if possible. You can also use HKDF to derive the keys.
A crucial part of such an application is that the user can forget their passwords. In this case, all of the photos are lost. The user must that countermeasure for themselves, write somewhere, use keypass, etc. The other mechanism by your application depends on the environment of the application and the risks.
For the encryption method use AES256-GCM* or better prefer ChaCha2-Poly1305 since it is easier to use than GCM. They are authenticated encryption methods that will provide you Confidentiality, Integrity, and Authentication. For those, you need to derive a IV/nonce and that can be randomly generated since you generate a new key for each file. And never ignore the tag mismatch error. If your application is an image processing application that stores the files on the cloud you need to be careful when you upload the modified file. If the key and the IV are the same then an observer can leak information from the differences.
If you don't want to use a new key for each file, then you need to be careful about the IV reuse. In this case, the nonce misuse resistant scheme SIV can be used with AES-GCM-SIV.

* Although AES-128 is secure, prefer AES-256 against the multi target attacks


No, that's not really possible without blatant flaws of the implementation. Modern modes of operation of ciphers are resistent to attacks even if you know many pairs of plaintext and ciphertext - and the IV is public knowledge. Knowing it is the normal case. You also didn't mention what operation mode was used.

Well, of course you could brute force the key, but that would take more time and computational power than you can ever muster.

Oh, and a small note: AES is a symmetric cipher, so there's just one key, which is normally not called private key. It may be true, but this term is generally reserved for asymmetric encryption.


Encrypting multiple small messages with a single reused symmetric key

You can use any authenticated, secure cipher. AES-GCM is currently used a lot. You need a nonce per message to use AES-GCM or you can use one of the SIV variants, which calculate a nonce (Synthetic IV) assuming that the messages are all distinct.

The question is more how to store the symmetric key than anything else, but that's not really a cryptography question - it's more about browser security and offline storage and such. Deriving a key from a passphrase might be a good idea, but note that you need a good key derivation mechanism in addition to a strong passphrase.

Often it makes sense to use asymmetric cryptography so that you don't need the private key during encryption. Keeping the key secure is the main issue with cryptography after all. In that case the passphrase could be used to wrap / unwrap (encrypt / decrypt) a private key value. Unfortunately you'd need local storage to store the wrapped private key - and this might be an issue in itself.


Encryption modes have lots of differences. Putting all of them in a table would be tricky. I would recommend you to do some work and read through the NIST documentation on Block cipher modes.
If you are unsure and you don't have particular requirements, you could check if GCM mode is available. It is an authenticated mode that also provides the integrity/authenticity of the ciphertext. You can also add any other non-confidential data such as configuration data in the Additional Authenticated Data (AAD) - this is separate input to the cipher. Beware that GCM mode fails catastrophically to IV nonce / reuse (GCM-SIV mode could correct that).
In the end, all modes described by NIST - except of course ECB mode, note the NIST hint - are secure for providing confidentiality when used correctly. So in that sense there is little point in comparing them without going into the specific use case.
[EDIT] I've removed the requirement that the IV needed to be put in the AAD data. I don't know what I was thinking when I wrote that and I didn't get corrected...


Effect of $L_n[1/4,c]$ integer factorization on RSA-2048

Unfortunately, deriving actual numbers from asymptotic bounds makes little sense (after all, $10^{36}$ and $10^{23}$ are both $O(1)$). Getting an idea of the actual cost of running an algorithm requires a fine analysis of the algorithm itself; asymptotic results are not sufficient. An $L_n[1/4]$ algorithm for factoring would be a great theoretical result, but it wouldn't necessarily perform better than the current algorithms on, say, RSA-2048.

Fear the hidden constant factors.


An alternative:

Client generates preliminary keypair $(t, T)$ with $T=tB$
Clients sends $T$ to server
Server sends a random scalar $n$ back(alternatively choose $n = \mathrm{HMAC}(k, T)$ with secret key $k$), and assigns the public key $A = T + nB$ to the client
Client uses $a = t+n$ as private and $A$ as public key.

That way the server decides the public key, without knowing the associated private key. If the server shouldn't be able to influence the public key either, you can use a commitment scheme that allows mutually distrusting parties to generate a random number.

Your proof-of-work approach doesn't really work since there isn't a good value for the timeout. For typical hash proofs, an attacker can easily have several thousand times the computational power of a defender. GPUs, FPGAs, using cloud computing to rent lots of power for a short time, etc.


How can I prove in zero knowldege that an ElGamal shuffle is correct for a special setting?

I don't understand the question (what is public? what is secret? what is the definition of all variables and functions?), but I can give you a pointer to literature that I strongly expect is highly relevant:

Take a look at mixnets.  There's an enormous amount of research literature on the subject.  It solves the following sort of problem (as well as variations): given a list of ciphertexts, Alice randomly permutes and decrypts them and then outputs the list of plaintexts, and now Alice wants to prove in zero knowledge that she did this correctly, without revealing the linkage between ciphertexts and plaintexts.  Sounds like exactly what you need.

P.S. It sounds like your system is a special case of a mixnet, with only two ciphertexts.  You might be able to design a custom protocol, using a disjunctive zero-knowledge proofs.  There's a standard way to prove $\phi \vee \psi$ in zero-knowledge, without disclosing which is true (assuming you have a zero-knowledge protocol for $\phi$ and a zero-knowledge protocol for $\psi$).  Also, there's a standard way to prove that $m$ is a correct decryption of ciphertext $c$.  So, you could try using these methods to prove that $(D(a)=m_1 \wedge D(b)=m_2) \vee (D(a)=m_2 \wedge D(b)=m_1)$.  You'll probably want to use a proof of knowledge.