Does the following linear equation hold in bilinear pairings?

Yes, sure, in some cases. In the following I assume that we speak about pairings as used in cryptography.

Lets look at the trivial case, i.e., when your equation reduces to $1_{G_T}=1_{G_T}$ where $1_{G_T}$ is the identity in your target group $G_T$. Then any assignment of your variables that makes at least one input element of each pairing the element $g^0=1_G$ ($1_G$ the identity in your group $G$) makes the equality hold. Note if you have $e(a,g^0)=e(a,1_G)=1_{G_T}$ (Observe that for any $a,b \in G$ you have $e(a, b) = e(a, b\cdot 1_G) = e(a, b) \cdot e(a, 1)$ and thus $e(a, 1)=1_{G_T}$). For instance, as in @Artjom B.s example for the case $x_1=x_2=0$.

For the non-trivial case it is quite easy to see that $a_1=a_2=1$ makes the equation hold.


Encrypting 256 bit AES keys with AES ECB?

If you are encrypting a 128-bit key, then it's "OK" since the key size is the same as the block size. However, if you encrypt a 256-bit key, then it's possible to tamper with the result. For example, you can drop one of the blocks and it "looks like" a 128-bit key, or you can make a 256-bit key be the same block twice (so it's of the form $k\|k$ where each $k$ is 128 bits, and so on.

Having said the above, even in the case of 128-bit key, you have the problem that an attacker can tamper with the ciphertext and you won't be able to detect it. It is true that the result will be random garbage, but in most cases, we like to be able to detect the tampering.


Would It Be Technically Possible To Delete Old Blocks From A Blockchain Cryptocurrency?

For public cryptocurrencies, deleting old blocks has the potential to cause long-time inactive users to lose their ledger, thus unable to spend when older blocks are deleted.
Therefore, it would not be technically possible to delete old blocks.


Modification of vigenere cipher cryptographically secure?

Vigenère Cipher

Let's look at some different attacks on the Vigenère cipher and determine how much of a role alphabet size plays.

From Wikipedia:

  The primary weakness of the Vigenère cipher is the repeating nature of its key. If a cryptanalyst correctly guesses the key's length, the cipher text can be treated as interwoven Caesar ciphers, which can easily be broken individually.

With a number like 1114111, breaking the individual Caesar ciphers by brute force would still be pretty easy. Maybe if you increase the size even further (128 bits or higher?). However, there could be attacks that perform better than brute force given the nature of the cipher.

Kasiski Examination:
Analyzing repeated groups of ciphertext which could correspond to the key. Extending the alphabet size would not affect this method, the best defense against this would be extending the key (ideally to the length of the plaintext, more on that later).

Key Elimination:
We can guess the key length (or figure it out somehow, like the Kasiski method) and remove the key from the ciphertext. This makes the alphabet size redundant (even if it was well above 1114111) because the key would be removed from the ciphertext anyway. To stop this, our key must be as long as our plaintext (see one-time-pad below).

Frequency Analysis and Friedman Test:
These rely on having information about the plaintext beforehand. Depending on implementation, your method could break these analysis techniques (or at least make them more difficult to implement).

These are just the methods outlined on Wikipedia for breaking the Vigenère cipher (you can of course look deeper into other methods). It should be pretty clear that Vigenère in the modern world can be considered broken, even if you play with the alphabet length and tweak the cipher in little ways.

One Time Pad (OTP)

Your question is tagged with one-time-pad, so I thought I should address this too. The one time pad can be implemented as a Vigenère cipher with a key that has the same length as the plaintext.

The one time pad is perfectly secure, but it has some stipulations and drawbacks.

The key must be truly random, and at least as long as the plaintext.

This means it shouldn't be entered by a user, repeated to fit the plaintext length, or generated using any pseudorandom number generator
Generating true random numbers is difficult and generally impractical*
Practically, you could use a CSPRNG, but then your OTP is only as strong as your CSPRNG (i.e. not a true OTP)

The key must never be reused. The key is used once to encrypt, then once to decrypt, then discarded. Encrypting multiple plaintexts using the same key can open you up to attacks (like Key Elimination mentioned above).

If these conditions hold, then the OTP is perfectly random, because any one key is equally as likely as any other. Which means that any plaintext is equally as likely as any other plaintext to the adversary. So even with infinite time and resources, the adversary could never reverse the cipher (without the key).

* Generating truly random numbers can be done using a TRNG, usually implemented as an external hardware device. You can purchase these as USB input devices or make your own circuit.


Merkle-like hash tree that mirrors existing tree structure

Yes: this allows the root hash to authenticate the entire content of the directory tree so that, e.g., a malicious storage server cannot fool you into accepting a forgery replacing a file you previously asked it to store.  This is how Tahoe-LAFS is structured, or at least the immutable parts, and how ZFS block pointers are stored when authentication is enabled.  More broadly, there is a modest literature on authenticated data structures that are all built out of essentially this idea.


All primes of the form $2^n+1$ have the form $2^{2^n}+1$.

As the wikipedia article on Fermat numbers says:

  If $2^n + 1$ is prime, and $n > 0$, it can be shown that $n$ must be a power of two. (If n = ab where $1 ≤ a$, $b ≤ n$ and $b$ is odd, then $2^n + 1 = (2^a)^b + 1 ≡ (−1)^b + 1 = 0 \pmod{2^a + 1}$. See Sec. 5 for complete proof.) In other words, every prime of the form $2^n + 1$ is a Fermat number, and such primes are called Fermat primes.

The only known numbers with this format are 3, 5, 17, 257 and 65537.


Clarification of one-way property of hash functions

Your function is too easy. Given an hash value $h$, calculate $b^h$ and $b^{h+1}-1$, where b is the base of your logarithm.

Any value between $b^h$ and $b^{h+1}-1$ will be pre-image.


How can I validate my implementation of Ansi 9.19?

Bouncy Castle has an ISO 9797/ANSI 9.19 Mac implementation with a test vector.

Botan also has an implementation and test vectors, which cross-verify with Bouncy Castle (at least the 128 bit key ones anyway).

From the looks, official test vectors appear to be scarce (unless you want to pay for a copy of the standard and chance one being in there), and it's less than clear that the BC/Botan vectors are official, so cross testing with existing implementations might be the best you can manage.


Is it possible for Alice and Bob to both sign a message "simultaneously"?

This is one of the earliest questions that was asked in modern cryptography. There is a proof that you cannot achieve completely fair contract signing. However, there are some reasonable alternatives. There is one direction called "gradual release" which I personally do not like. A model that I think has a lot of promise is called the "optimistic model". In this model, there is a trusted third server that is only invoked in case one of the parties cheats and may obtain a signature without the other. This model is very nice in the sense that once the server exists, there is no motivation to cheat since anyway an adversary knows that it cannot gain anything. I note that the server is trusted to answer when a party asks for its "help", but does not learn anything. This model was introduced by Silvio Micali in Fair Electronic Exchange with Invisible Trusted Parties. You can read more about this model in Optimistic Fair Secure Computation by Cachin and Camenisch, and Analysis of a Fair Exchange Protocol by Shmatikov and Mitchell.

Another direction which I really like is called Concurrent Signatures. In this model, one party gets the signature first. However, if the other party sees the signature then it can use that to complete its own signature. So, it's actually not fair (one has the signature first) but if the first ever wants to enforce anything with its signature then it would have to show it to the second, in which case the second can complete the signature it is supposed to receive. In most practical cases that I can think of this is sufficient, and it elegantly bypasses the impossibility results that exist. This model has the advantage that you don't need a (minimally) trusted third party (which is problematic in practice).

Finally, I'll point to the recent use of Bitcoin to ensure fairness. The paper How to Use Bitcoin to Design Fair Protocols shows how to do this (albeit theoretically). The idea here is very very nice.


Is BBS+ 1. a multi-messages signing protocol or 2. a group signature signed by a member of a group anonymously?

I've always used it as #1. Hyperledger Ursa has an implementation in Rust
(see https://github.com/hyperledger/ursa/tree/master/libzmix/bbs).
However, it is a type of group signature which allows the type of signing of multiple messages.
When someone says to me group signature I immediately think your #2. If we look at a paper written by David Chaum (https://chaum.com/publications/Group_Signatures.pdf), He mentions
group signatures are a "generalization" of the credential/ membership authentication schemes, in which one person proves that he belongs to a certain group.
So in effect, the proof being made is proving the messages belong to the signature and the signature allows for a proof of knowledge to be made.
It's a different use of a crypto primitive.
Hope this helps


1:1 algorithmic shuffle of massive numerical space

There are three major options available to you, depending on the available preferences and guarantees, ordered in descending order of generality:

Format-Preserving Encryption is a class of encryption schemes that can accept arbitrary input spaces and then produce ciphertext from that input space as output. A classical example would be encryption of credit card numbers to encrypted ones that are still accepted by the database solution validating their format.
Wide Block Cipher Modes, e.g. EME* take a bit string of arbitrary length and then compute a keyed pseudo-random permutation on them, their original intended use was disk encryption where you can't store additional authentication data but want to maximize your chances of detecting modification by randomizing the data sector if the ciphertext sector is changed.
Traditional Symmetric Encryption, e.g. CBC mode with a fixed nonce / IV. Note that these suffer from the isuse that changes at bit position $n$ affect at most a constant amount of bits in front of $n$ and at most all bits following $n$ which seems to not be the avalanche effect you're looking for.

If you're wondering, the recommended baseline block cipher for the above constructions is AES.


Can i generate a SHA512 hash if i know the SHA256 hash of some unknown data?

No, you can’t.

There are (at most) $2^{256}$ different possible SHA-256 hashes.

If it were possible to deduce a SHA-512 hash from a SHA-256 hash with no knowledge of the data, then there would be at most as many different SHA-512 hashes as different SHA-256 hashes.

Then, a SHA-512 hash would be at most as strong as a 256-bit hash.


Is calculating HMAC from hashed input a good idea?

What if text would replaced with H(text)? Will it weaken the HMAC algorithm?

Yes. It makes collision attacks on the hash function apply to the MAC, which isn't normally the case with HMAC. You can find a pair $(m, m')$ that hash to the same value, get the MAC for one of them and move it to the other.

That means that your modified HMAC construction would be insecure with a hash function $H$ that isn't collision resistant, such as MD5. Even though normal HMAC-MD5 is still believed to be secure. In fact, any hash function with a small enough output size to lack collision resistance would be insecure to use in this modified HMAC.

If you use a collision resistant hash function, such as one of the SHA-2 hash functions (notably SHA-256 and SHA-512) or SHA-3 then the modified HMAC should still be secure.


Show number of affected blocks using CFB DES decryption of altered ciphertext

Block size = 1 byte for CFB thus 9 bytes are affected. Why this is true has been answered before. Even for CFB8 it takes 8 shifts to shift the wrong ciphertext value out of the buffer.

To proof this is true just change a single byte of a binary output file using a hex editor (hexedit) and then decrypt. Count the number of differing number of bytes (diff). If you get 8 bytes then the last byte refused to budge - it may regenerate the same value by chance. Redo from start, multiple times if you want "statistical proof".


Why do I need to store the salt for generated hashes?

The hash returned by bcrypt.hashSync is more than the hash itself, it contains all parameters needed by bcrypt. You do not need to store anything else yourself, this information is everything bcrypt needs to hash and compare an incoming password.

The actual hash was computed by combining the password and salt, so no worries there. The structured data is there merely to make your life easier and only need a single object to store.

In your first example, the output is:

$2a$10$M6qZCSbwhXipdmMy7kQ4V.obtALLSAjZsMYD/oGDAo0i/fcSGrmn2

This breaks down into:

version information: 2a
the number of rounds to perform: 10
the salt: M6qZCSbwhXipdmMy7kQ4V.
the actual hash: obtALLSAjZsMYD/oGDAo0i/fcSGrmn2

You can see the details in the code


Why is it good to split a CTR-mode counter into nonce and counter?

Suppose you do CTR mode as:

  $E(k,nonce+1) \oplus m_1$, $E(k,nonce+2) \oplus m_2$, $E(k,nonce+3) \oplus m_3$, etc.

The wikipedia page is talking about a non-random nonce, with a specific example of a packet counter. So suppose $nonce$ is a packet counter and in each packet you encrypt several blocks. You might end up with the following:

In packet #$p$:

  $E(k,p+1) \oplus m_1$, $E(k,p+2) \oplus m_2$, $E(k,p+3) \oplus m_3$, etc.

In packet # $p+1$:

  $E(k,(p+1)+1) \oplus m'_1$, $E(k,(p+1)+2) \oplus m'_2$, $E(k,(p+2)+1) \oplus m'_3$, etc.

The nonces are unique, but CPA security is broken. You have used $E(k,p+2)$ as a mask twice, and are leaking the value of $m_2 \oplus m'_1$.


This is easiest to understand if we use polynomial arithmetic.

The CRC of a message $m(x)$ is the remainder $r(x)$ of $m(x) x^k$ when divided by the CRC polynomial $f(x)$. Or more conveniently, the CRC is congruent to the message multiplied by $x^k$ modulo the CRC polynomial, $r(x) \equiv m(x) x^k \pmod{f(x)}$.

If the message consists of a prefix $m_1$ and a suffix $m_2$ of length $n$, we can express that as $m(x) = m_1(x) x^n + m_2(x)$. If the CRC of $m_1$ is $r_1(x)$ and the CRC of $m_2(x)$ is $r_2(x)$, then the CRC of $m(x)$ is $$r(x) \equiv (m_1(x) x^n + m_2(x)) x^k \equiv r_1(x) x^n + r_2(x) \pmod{f(x)}.$$

If $f(x)$ is not a multiple of $x$ (which it won't be), there is a polynomial $g(x)$ such that $x g(x) \equiv 1 \pmod{f(x)}$, and then $$r_1(x) \equiv r_1(x) (x g(x))^n \equiv (r(x) - r_2(x)) g(x)^n \equiv (r(x) - m_2(x) x^k) g(x)^n \pmod{f(x)}.$$

In other words, you find what you ask for by first finding $g(x)$, then computing a difference, multiplying by a suitable power of $g(x)$, then taking the remainder when dividing by $f(x)$.


How do I explain zero knowledge proof to my 7 year old cousin?

I will use Bertie Bott's Every Flavour Beans from Harry Potter in my explanation. If your cousin has not read Harry Potter, you can refer to Jelly Beans instead.

So let's assume there are two beans which look same but one of them tastes like chocolate and the other one tastes like spinach. Your cousin claims that he can distinguish them just by looking at the beans. You don't believe him, but he doesn't want to tell you which one is which, so there is still a chance that you eat the spinach one.

Instead you hide them both behind your back and randomly choose one of them and show it to your cousin. You then put it back and choose randomly again in a way that allows you to know whether you picked the same bean or not (like swapping the beans x times). You then again show it to your cousin who will have to tell you whether it's the same bean as the one you showed before. Repeat this process until you are sure that he is indeed able to distinguish the beans (or that he's not).

You now know that your cousin is able to tell the beans apart while you still do not know which bean is the tasty one.

Finally, there are two side-channel attacks in this scenario:

He may be able to count how often you swapped the beans, so don't make it too obvious.
You could offer him one of the beans and when he refuses, it's probably the spinach one.


So you have a secret with low entropy which you want to verify in a secure way.

This is a standard scenario in password-based cryptography (PINs are sort of a password).

What you'll do in both scenarios described below:
The user first enters his access-code (=PIN), which get buffered in the RAM. Now storage media (the device/a drive) will provide the program (processor) with a random looking string that the media stored. (This is the salt) The media supplies parameters as well. (Iteration Counts, (N,R,P)-Values, (t_cost,m_cost)-Values). Now you use a password-hashing function (scrypt/winner of PHC) using the supplied parameters, the salt and the password to derive a tag/key.

You have two ways at approaching your problem:

The straight forward way to do what you want is to get a tag generated by the PHS (password-hashing scheme), store this on first entry on the storage media (along with salt and parameters) and just check if the tag matches with what will be generated at verification-time. I wouldn't recommend this way, as it relies on your code to be bug-free.
The better way (in my eyes) would be to derive a key using the PHS, which will be used for verification/decryption. So the security of the data would strongly rely on the password and not on some authorization code. The storage media would only store salt and parameters and you'd  see that the access-code is correct as verification succeeds.


Plain text size limits for AES-GCM mode just 64GB?

The source of the limitation lies in the fact that GCM has a fixed block counter using a 32-bit integer. Since the block size is $2^7$ bits, the total amount that can be encrypted with the CTR component is $2^{39}$ bits.

The first limit reducing this by 128-bits is the fact that the block counter starts at 1 and not 0, at least with a 96-bit nonce. Nonce sizes other than 96-bits are know to have reduced security. The second limit reducing this by 128-bits is because the CTR component is also used to encrypt the final GHASH prior to tag output.

Implementation wise, you should not be allowed to cross this limit. In theory, the security breaks down. There are different security limits for the amount of data encrypted, and for the amount of tags generated. With a long message, an $n$-bit tag provides $n-k$ bits of authentication security for a $2^k$ block message, in your case this brings it down to around $2^{63}$ with a file between 100 and 128 GB when used with a 96-bit tag, much lower than the $2^{128}$ one may expect. The worst case scenario is recovery of the hash subkey $H$, allowing forgery of tags with the same key.

Encrypting a full size 128-bit tag with a separate key in ECB mode should eliminate that problem, as the bits will no longer be malleable. That can be done as a wrapper around a GCM implementation with minimal modification and almost 0 overhead. The implementation would need to be modified to use a larger block counter, and the nonces would need to be shorter. You would no longer be able to call it GCM, but would be able to make use of all the features and code that make GCM implementations fast and timing attack resistant. A 32-bit nonce and a 40-bit block counter (with no additional GHASH) would allow almost 16TB per nonce, without the restriction of changing keys for every message if you encrypt the tag with a second key. If you even consider something like this, a professional consult on both the modifications and the code to do it would be highly recommended, new security proofs would need to be developed.

Other solutions to the problem including not using GCM, but a different mode like Poly1305-AES. OCB mode also has a suggested limit of 64GB per key, CWC mode has the same limit as GCM.


Is TripleDES 168bit vulnerable to Differential Cryptanalysis?

This claim is bogus. DES itself has a 13-round differential with probability around $2^{-47}$, so TripleDES with its 48 rounds is resistant to any sort of differential attack.

The paper authors are not really competent in the subject.


How to compare performances of lattice-based and pairing-based IBE schemes

It is very hard to give a concrete, "apples-to-apples" comparison of lattice-based and pairing-based IBE schemes.  There are many reasons: the research surrounding concrete secure parameters for LWE is still evolving, efficient implementations of operations used in lattice-based IBE (e.g., discrete Gaussian sampling) are still works in progress, one can consider more efficient ring-based analogues, etc. etc.

However, it is possible to give meaningful asymptotic comparisons, at least up to poly-logarithmic factors, under reasonable hardness conjectures about lattices and pairings (so that we're normalizing to equivalent security levels).

To your specific questions: no, the dimension $n$ for LWE and the bit size $\log |G|$ are not equivalent.  However, they are asymptotically close, up to polylog factors, in the following sense: for conjectured $2^\lambda$ security, we can set $\log |G| = O(\lambda)$ and $n = \tilde{O}(\lambda)$.  For pairings, this implies that all key sizes are $O(\lambda)$.  For lattices it implies:

master public keys of size $\tilde{O}(n^2)$ [plain LWE], or $\tilde{O}(n)$ [ring LWE].
user secret keys of size $\tilde{O}(n \cdot \ell)$ for $\ell$-bit messages [plain LWE], or $\tilde{O}(n)$ [ring LWE] for $\ell = O(n)$.
encryption time of $\tilde{O}(n^2)$ [plain LWE], or $\tilde{O}(n)$ [ring LWE].
etc. etc.

In short, for ring-LWE all relevant sizes and runtimes can be made $\tilde{O}(n)$, though the hidden polylog factors can be significant in practice.


Order of an elliptic curve defined over a prime field

The fact that $n_g\cdot h\cdot P=\mathcal{O}$, does not mean that the order of $P$ is $n_g\cdot h$. It means that the order of $P$ divides $n_g\cdot h$, so it could simply be $n_g$.


Why restricting SHA3 to have only two possible capacities?

2 main reasons:

The 2 capacities match the collision resistance of SHA2 for 32-bit (C=256) and 64-bit (C=512) word sizes.
Simplicity, having only 2 capacity/rate combinations means that it does not have to be chosen or calculated from the digest size.

I have implemented Keccak in software, and forcing only 2 capacities means a lot less code in the absorb/squeeze functions. The idea of only 2 capacities with those values was suggested by the designers of Keccak themselves in section 6.2 of their Sakura tree hashing proposal:

Sakura: a flexible coding for tree hashing

Keccak's SHA3 submission originally specified C=512 for a 256-bit hash and C=1024 for a 512-bit hash. The reduction in the slides means 2 things:

Speed; it is 23% faster for 256-bit hashes and a whopping 89% faster for 512-bit hashes due to the corresponding rate changes
Security; resistance against preimage and collision drops from $2^n$ to $2^{n/2}$, where n is the digest size in bits, this would make SHA3 weaker than SHA2, which has preimage resistance of $2^n$

Keep in mind that SHA3 has not even reached draft stage yet, and there are plenty of people who disagree with the chosen capacities, so it may very well change prior to FIPS 202.


The process of turning inputs that are hard to predict (formally, inputs that have some min-entropy) into bit strings that are cryptographically uniformly random is called entropy extraction. So there's your search term if you want to learn more theory.

The problem. The fact that your outputs produce values that can pass a given statistical test (or even a suite of standard tests) is a bit encouraging, but far from a guarantee. The tests in question know nothing about your entropy source or extraction function, but presumably an attacker will. Therefore an attacker may be able to exploit some non-uniformly random characteristic of the output that would go unnoticed by the test.

I have no idea how likely this is in your particular setting. But if you want to place your system on a more solid theoretical foundation, you need to use a proper entropy extractor.

The easy way out. Before continuing, I should say that in practice, a lot of people would simply take the output of the entropy source, hash it (using SHA-256 for example), and use the result to seed an AES-CTR PRNG.

PRNG Seed = SHA-256(Entropy)

Despite the fact that hash functions aren't really designed to take this kind of abuse (they are not random oracles!), so far this approach hasn't led to any practical attacks --- at least, that I know of. This might be good enough for you as long as you harvest enough entropy to make a brute-force attack infeasible.

If you're particularly paranoid and want to be a good cryptographer, read on.

The "Right" Solution. In order to construct an entropy extractor, first you need access to a random seed. Which seems a bit circular, but, crucially, the extractor seed does not need to be secret and it does not need to change. (In contrast, the PRNG seed most definitely does). So you could generate one elsewhere and send it over. The only restriction on the extractor seed is that it needs to be generated in a way that's independent of your entropy source, and you need to assume that an attacker can't influence the entropy source based on his knowledge of the extractor seed.

Now that you have a seed in hand, the question is how much effort you're willing to expend on implementation. You can use the seed as a key for HMAC-SHA256, and you'd probably be fine (see Randomness Extraction and Key Derivation Using the CBC, Cascade, and HMAC Modes by Dodis, et al.):

PRNG seed = HMAC-SHA256(Extractor Seed, Entropy)

If you want to be a bit more paranoid, find code that implements a polynomial hash over a finite field (this could probably be taken SSL's GCM code), use the entropy to encode the coefficients of a polynomial, and evaluate the polynomial at the value encoded by the extractor seed. (See, e.g., Leftover Hash Lemma, Revisited by Barak, et al.)

PRNG Seed = PolyHash(Extractor Seed, Entropy)

Regardless of which of these two approaches you take, in order to get a strong degree of security you'll need around 160 bits of min-entropy to generate a 128 bit PRNG seed (i.e., an attacker should not be able to predict your entropy with probability more than $2^{-160}$). Note that since there are likely redundancies in your entropy source, the strings you get from it may need to be considerably longer.


How does MD5 process text which is shorter than 512 bits

It's called padding.

MD5 fills the "not finished block" with exactly one "1" bit and a number of "0" bits until the length of the number is 64 bits away from being divisible be 512. It could happen that you don't need to add any "0" bits, that's okay, but never omit the "1" bit! After that, the length of the original message in bits is added, formatted with the fixed length of 64 bits in little-endian in words of 32 bit. Now the block is divisible by 512 and ready to be used in the "core" MD5 algorithm.
The biggest message which can be processed in a single block is 417 bits long: 417 bits for the message, 1 bit for the mandatory "1" bit and 64 bits for the length: $417 + 1 + 64 = 512$. (We don't need any extra "0" bits for this message.)

The plaintext of "how" in ASCII is:
$$ \text{01101000 01101111 01110111} $$
Now we concatenate a "1" bit:
$$ \text{01101000 01101111 01110111 1} $$
That are 25 bits. Now we need the lowest number which is divisible by 512 and at least 64 higher than our current message length. 512 is this number for our example. 64 bits lower than 512 is $512 - 64 = 448$. We need to add $448 - 25 = 423$ "0" bits.
$$ \text{01101000 01101111 01110111 10000000 [416 "0" bits]} $$
The length of the original string is 24. The binary representation of 24 as 64 bit number is this. (Little-endian, so the least-significant byte comes first!)
$$ \text{00011000 [56 "0" bits]} $$
Now we concatenate this number to the block:
$$ \text{01101000 01101111 01110111 10000000 [416 "0" bits] 00011000 [56 "0" bits]} $$
Now follows the full block, converted from little-endian and written (big-endian) as 32-bit integers, like MD5 will process them.

0x80776F68 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000000 0x00000000
0x00000000 0x00000000 0x00000018 0x00000000

If you want to hash more data, divide it into blocks. You still have to add the "1" bit and the length of the hashed message. If the last block is already under 64 bits away from being divisible by 512, than you have to add a new block, just for padding! Omitting the padding is very bad because the hash is even more susceptible for length extension attacks than it's normally the case for MD5.


Is there an encryption method where the order of decryption is irrelevant to the order of encryption?

Any synchronous stream cipher, or block cipher in a stream-like mode of operation (such as counter-based modes), will have this property. That's because they are, in essence, stretching a user-supplied key to an arbitrary length, and then using it as an XOR mask to encrypt (or decrypt) the message. Since the message content isn't relevant to cipher stream, and the actual encrypt/decrypt operation is just XOR, the order is unimportant.

Note that ciphers like this are extremely vulnerable to some classes of attacks, such as a bit-flipping attack. It is therefore crucial that you include an integrity check, such as an HMAC, with your ciphertext.

In order to make this secure with multiple messages, you have to do the same thing you do with most ciphers when reusing a key: you need a new nonce or initialization vector (IV). This value is randomly generated for each message, and sent along with the ciphertext in the clear. It is useless for the attacker unless the attacker also has the key, but it allows the same shared key to produce different ciphertexts even when encrypting the same plaintext message. This means an attacker can't determine anything about the plaintext (other than its length, which can be mitigated via padding and so on) by comparing ciphertext messages, even if the attacker knows they were encrypted with the same key.

You do need to be absolutely sure to never re-use the IV, though. IV re-use makes it quite easy to break many crypto schemes. For example, the old Wired Equivalent Privacy (WEP) encryption used for early WiFi had short IV (only 24 bits) and this was weak enough that often possible to break the encryption with only a few minutes of analysis if the network was busy (and therefore had to generate a large number of IVs to encrypt all the packets it was sending).

With all that said... schemes like you describe aren't as secure as you might expect them to be. While they should remain at least as secure as only doing a single round of encryption, they might not be any better than that. Due to attacks such as meet-in-the-middle, using the same cipher for multiple operations (even with different keys) is less secure than you'd expect. Mixing encrypt and decrypt operations is more secure for ciphers where encrypt and decrypt are different operations (which is not the case for cipher classes mentioned above) but even then, it's less secure than you might expect. A real-world example of this is the Triple-DES cipher, which attempts to fix the weakness of the DES cipher's 56-bit key by using three keys, and doing encrypt-decrypt-encrypt (or the reverse, for the decrypt operation). You might think that would produce 168 bits of effective security, but due to meet-in-the-middle, it's actually only 112 bits effective (although you do still need all three keys to be distinct, which is 168 bits of key material).

Still, if you want to generate a bunch of independent keys, encrypt a message with all of them, and then require them all to be re-entered before the message is decrypted without caring about the order of re-entry... this scheme should work. Just don't expect it to be more resistant to cryptanalysis than just encrypting the message once.


How to select elements randomly from a multiplicative group Zn*

$(\mathbb Z_n,+,\cdot)$ and $(\mathbb Z/n\mathbb Z,+,\cdot)$ both denote the ring of integers under addition and multiplication modulo $n$, per perhaps different but in the end equivalent constructions. This set has $n$ elements.

$\mathbb Z_n^*$ and $(\mathbb Z/n\mathbb Z)^*$ both denote the subset of elements of said set which have an inverse under multiplication modulo $n$ (or equivalently, which Greatest Common Divisor with $n$ is 1). It forms a group under multiplication modulo $n$.

The ring $(\mathbb Z_n,+,\cdot)$ is a field if and only if $n$ is prime, in which case $\mathbb Z_n^*$ is simply $\mathbb Z_n-\{0\}$.

By definition, $x$ in $\mathbb Z_n$ belongs to $\mathbb Z_n^*$ if and only if $x$ has a multiplicative inverse $y$ , that is such that $x\,y\equiv1\pmod n$ (or equivalently, if and only if $\gcd(x,n)=1$ ). When $n=p\,q$ with $p$ and $q$ primes, this is if and only if $x$ is such that $x\ne0\pmod p$ and $x\ne0\pmod q$ . The set $\mathbb Z_n^*$ has $\varphi(n)$ elements, where $\varphi$ is Euler's totient function. If $p\ne q$ , then $\mathbb Z_n^*$ is the set of the $\varphi(n)=(p-1)(q-1)$ elements of $\mathbb Z_n$ that are divisible by neither $p$ nor $q$ . If $p=q$ , then $\mathbb Z_n^*$ is the set of the $\varphi(n)=p(p-1)$ elements of $\mathbb Z_n$ that are not divisible by $p$ .

We can obtain a uniformly random element of $\mathbb Z_n^*$ in several ways:

Heuristically: generate a uniformly random integer $x$ in $\mathbb Z_n$ (that is a uniformly random integer in $[0,n)$ ) until $x$ is divisible by neither $p$ nor $q$ (which if almost certain in practice if $p$ and $q$ are large). We can equivalently test if $\gcd(x,n)=1$ using the Euclidean or Binary GCD algorithm, with the advantage that we do not need the factorization of $n$. Also, we can as well generate $x$ in $[1,n)$ before testing it, since we'd eliminate $x=0$ anyway.
Constructively: generate a uniformly random integer $u$ in $[1,p)$ , and

if $q\ne p$ generate a uniformly random integer $v$ in $[1,q)$ , and form $x$ in $[0,n)$ with $x\equiv u\pmod p$ and $y\equiv v\pmod q$ by the Chinese Remainder Theorem; for example, as $x=(q^{-1}(u-v)\bmod p)q+v$.
if $q=p$ generate a uniformly random integer $m$ in $[0,p)$ , and form $x=m\,p+u$.


Can you help me understand Pollard's rho example?

The algorithm is clear about all your questions. The partitions of $G=\mathbb{Z}^{*}_{383}$ are the sets
$$S_1=\{x \in G: x \bmod 3=1\}$$
$$S_2=\{x \in G: x \bmod 3=0\}$$
$$S_3=\{x \in G: x \bmod 3=2\}$$
Here are the left parts ($x_i$) of the computation slightly more detailed with $x_i \bmod 3$ and the corresponding sets $S_k$

i    x_i    x_i mod 3  S_k          x_(i+1)
1    228        0       2       228^2 mod 383 = 279
2    279        0       2       279^2 mod 383 = 92
3     92        2       3       2*92  mod 383 = 184
4    184        1       1     228*184 mod 383 = 205
5    205        1       1     228*205 mod 383 = 14
6     14        ...


Find out a set of values without sharing my own

You are looking for a private set intersection protocol.

For the semi-honest (passive adversary that follows the protocol) setting, go to Benny Pinkas's homepage and read the papers there, e.g.

Scalable Private Set Intersection Based on OT Extension

Efficient Circuit-based PSI via Cuckoo Hashing

For the malicious (active adversary that behaves arbitrarily) setting, go to Mike Rosulek's homepage and read the papers there, e.g.

Malicious-Secure Private Set Intersection via Dual Execution

Improved Private Set Intersection against Malicious Adversaries


Is it safe for the ChaCha8 nonce to be deterministic?

Yes, it is safe. The only requirement for the nonce in Salsa/Chacha is to be unique; being predictable is not an issue, so a counter is fine.

Like CodesInChaos indicated, I believe extending XSalsa20 to XChaCha20 would also work if you want to a larger nonce, but have nothing concrete so will leave the details to him/her.


Can we build authenticated encryption using Feistel Networks?

The simple way to build authenticated encryption using a Feistel Network is to build a Feistel based block cipher, then use one of the many modes of operation that turn a block cipher into an authenticated encryption scheme (eg CCM,OCB,GCM).

For a good survey on the subject of modes-of-operation I would recommend this paper by Rogaway. It does not cover the very most recent designs (such as those discussed at DIAC'13) but covers the more accepted methods in a reasonable amount of detail.


Does the AES Mixcolum Matrix use a fixed or random matrix?

It is fixed.

In the forward direction, it is always:

$$
  \begin{bmatrix}
    02 & 03 & 01 & 01 \\
    01 & 02 & 03 & 03 \\
    01 & 01 & 02 & 03 \\
    03 & 01 & 01 & 02
  \end{bmatrix}
$$

In the reverse direction, it is always:

$$
  \begin{bmatrix}
    0e & 0b & 0d & 09 \\
    09 & 0e & 0b & 0d \\
    0d & 09 & 0e & 0b \\
    0b & 0d & 09 & 0e
  \end{bmatrix}
$$

Note that the multiplication (and additions) done during the matrix multiplication are done using $GF(2^8)$ operations, which are not the same as $\mathbb{Z}_{256}$ (which is what was confusing Frenzy Li)


Is the cipher "Kalyna" with a 512-bit key length more secure AES with a 256-bit key?

... their algorithm is more secure rather AES because of longer key length and lack of any tables in hardware acceleration. Is it truth, or AES is better?

More key material

Using more key material does not improve security once you are already using enough key material to be secure.

A 256-bit key is well out of the reach of mankind to crack, even if quantum computers equipped with Grover's algorithm were being used. So using more key material is not productive.

Using more key material can even weaken the security of the design, or at least make the design less efficient.

The more bits you are working with, the longer it takes to diffuse them evenly through the rest of the state. This implies that larger keys (and larger states) need more rounds to achieve complete diffusion.
Insufficient diffusion is one of the leading causes of weaknesses

The goal of algorithm design is basically to hit the ideal balance between efficiency and security. Due to the fact that using excessive amounts of key material will degrade performance for no benefit in security, this raises a flag regarding the competency of the design.

That being said, if you intend to use the cipher to create a hash function, then a larger key size can be useful to compress more data per invocation of the cipher.

Lack of vulnerabilities in hardware acceleration

While it's correct that tables are a potential vulnerability in an implementation, few algorithms require the use of tables. As long as the table is a memoized function and not just an actual random permutation of words, then an implementation can always choose to evaluate the function discretely instead of using a lookup table. Note that if the table were to be an actual random permutation of words, it probably wouldn't provide good non-linearity.

Hardware acceleration is specified explicitly. The AES circuit is supported as a hardware instruction on modern Intel CPUs. It is thoroughly unlikely that this instruction will ever be replaced by Kalina Kaylna. As far as many (if not most if not all) consumers are concerned, the details of hardware accelerated Kalina Kalyna are of little concern and so are a moot point.

If you are concerned that the built-in AES circuit has deliberate vulnerabilities, you are always free to use a software implementation. While AES-NI will obviously be faster, and a softare implementation that uses tables will be fast but vulnerable to side channels, the average consumer probably does not need huge throughput anyways. So if those are a concern, you can always use an implementation that is designed to be resistant to side channel attacks.

Cryptanalysis

If you want cryptanalysis of AES, then you are free to investigate the huge amount of pre-existing research on the subject. AES has been around for years and is probably the single most heavily analyzed symmetric cipher, possibly only second to DES.

If you want cryptanalysis of Kalina, you're almost certainly out of luck. Searching for "Kalina cipher", I could not even find the proposal or definition of the design, let alone any analysis of it. Searching for "Kalina" on eprint.iacr yields no results.

Edit: With the correct spelling of the design, it is possible to locate the specification and there are a few (3) cryptanalysis results on eprint.iacr.

Because few, if any, will ever use it, it is probable that it will never receive any meaningful analysis from competent cryptographers. It is certain that it will never receive the same amount of analysis that AES has received. It is possible that some of analysis that will be performed (e.g. by NSA) will never be made public.


Understanding the Definition of Most Significant Bits in the Hidden Number Problem

Imagine you are working modulo the prime $p = 2^{255}+95$. Knowing the most significant bit, in the usual sense, of values modulo $p$ gives you almost no useful information—it's virtually always $0$. Knowing the $k$ most significant bits, in the usual sense, gives you roughly $k-1$ bits of information.

For the results to make sense over arbitrary prime fields, one thus needs a definition of most significant bits that is not affected by such quirks, and that's there the weirder definition of $\mathrm{MSB}_k$ comes in, which might be better understood as "suppose you know $k$ bits of information about $x$".


Simple designs for provable security in cryptographic primitives

to design something simply so it can be proved secure

We currently cannot prove the security of anything (well, other than informational secure things such as OTP), without making some assumptions.  The best we can do is:

This is secure, assuming that this abstract problem is hard (but that says nothing about whether the abstract problem is actually hard).  Public key cryptosystems tend to be in this category.
This is secure against these classes of attacks (but that says nothing about other types of attacks).  AES is in this category, as we have a proof of security against linear and differential cryptanalysis.

  and hope that it's not broken in its lifetime?

We don't know how that can be avoided, either in simple or in complex systems.


Increasing Entropy of Limited Information / ID

I tried to figure out salting it, but since the main problem is the
  entropy is too small, i don't think it might work as expected.

With your "salt" being a long, high-entropy and secret blob, it should work alright.

But even more important, don't use a single SHA512. SHAs are fast, that's bad if you want to prevent bruteforcing. There's eg. PBKDF2 or bcrypt.


Is it meaningful to allow parties to use a non-uniform random tape in 2-party computation?

Most models I've come across have a truly random tape. You can use this trick - assume the tape to be uniformly random, but then the party reads a block (of certain size) of random bits and uses that to bias the coin.
For example, if you want the coin to output Heads by probability 0.75, read 2 random bits from the random tape and if they both are 1's, output Heads otherwise output Tails.


If you define $u$ as element of $G_1$, then you can't just use it in $G_2$ (in the first equation), like you did in your equation. Besides, you missed to state, if $u$ and $g$ are generators of those groups. The following holds:

$$e(u^a,g^{\frac{b}{a}}) = e(u,g)^b = e(u^b,g)$$

Anyway, you didn't do that in the actual question, where I don't really see the connection to your construction. Btw, how do A and B know that they are using the same value $r$? And then: How can the server relate anything $B$ sends to $m'$, if the server has no knowledge of $m'$ or a commitment to $m'$? So no, he can't. Because $m'$ is not used in your construction at all.

The question now is: What is your actual goal? Should the server just be able to make sure, A and B committed to the same value? And A and B have to interact to generate the witness for that? You don't need pairings for that.

edit: Maybe even Alice could cheat in the system, by not sending $g^a$ to Bob, but something else. What happens then? Well, if the server check returns true, the "commited" messages are not equal. Too many things that can go wrong, especially with that $r$, which doesn't make sense.


Differential cryptanalysis in "The Block Cipher Companion"

I haven't studied this in detail, but the authors seem to give quite a comprehensive presentation of the differential attack.

Please note that this cipher is essentially the same as the one in Heys' Tutorial on Linear and Differential Cryptanalysis (easily found online by a google search) but the Sbox is different.

I have had students implement that attack successfully. So you can use that text as an extra reference while you are trying to sort things out.

In fact the authors themselves of the Block Cipher Companion state, on page 121, that

  The probability of
  the characteristic we have identified could be too small to effectively distinguish the
  correct key information.


Is there any encryption algorithm that, with small change in input will produce big change in the encrypted output?

What you want, if at all possible, is an IND-CPA (or, preferably, even IND-CCA2) secure encryption scheme.  Such encryption schemes are by definition probabilistic (and/or stateful), so that even encrypting the exact same plaintext twice will produce completely different results.

Conveniently, there are plenty of block cipher modes of operation that provide IND-CPA security, as well as authenticated modes that even provide IND-CCA2 security (which includes resistance to active forgery attacks where an attacker may modify encrypted messages and observe the results of attempting to decrypt them).  Triple DES can be used with most of these modes — but you really shouldn't be using it nowadays, since AES is both faster and more secure.

If you absolutely need your encryption scheme to be deterministic, so that the same plaintext always encrypts to the same plaintext, the next best thing you can have is DAE security.  It's basically the same as IND-CCA2, except that because it's deterministic, an attacker can obviously tell if two encrypted messages have the same plaintext or not.

The first and most popular DAE-secure encryption method is SIV mode, although there are also newer and potentially faster schemes like GCM-SIV.  All of these are designed (and standardized) for use with AES; while you could in principle used them with TDES, that would be less secure (particularly due to the smaller block size) and generally pointless.

Conveniently, SIV and other DAE-secure encryption modes have the useful feature that, if you include a unique nonce as associated data with every encrypted message, they become fully IND-CCA2 secure, and still remain DAE-secure even if you accidentally use the same nonce twice.  This "nonce misuse resistance" is a very handy safety net to have, and IMO is a good reason to use AES-SIV (or AES-GCM-SIV) whenever possible.

Finally, I'd like to note that your description of your attempts so far doesn't really fill me with confidence that you know what you're doing.  (That goes particularly for the fact that you mentioned using TDES, but not which mode you're using it in — that's kind of the crypto equivalent of saying that you're driving a 4-cylinder internal combustion engine from 1995, but not specifying whether it's in a car or a motorbike or a lawn mover.)

If all this talk of "nonces" and "modes of operation" and "IND-CPA/CCA2 security" goes straight over your head, I'd suggest either picking up a good introductory crypto book and/or just browsing this site until it no longer does.
 While there are nowadays some relatively "foolproof" encryption APIs like NaCl crypto_secretbox available, you do still need at least enough basic crypto knowledge to understand the terminology and to be able tell a secure and well designed system from complete snake oil.  Or you can just hire someone who does understand all this stuff to design your cryptosystem (and someone else to review it — which you really should do anyway).


Why ElGamal signature is insecure with nonrandom k?

If we use constant $k$ in this scheme we can find the secret key like this:

We know $(m_1,r_1,s_1)$ and $(m_2,r_2,s_2)$ for two different plaintext, as k is constant $r_1=r_2=r$ so we have this equivalence:
$$s_1k-m_1\equiv-ar\equiv s_1k-m_1\ mod\ p-1 \Rightarrow (s_1-s_2)k \equiv m_1-m_2\ mod\ p-1$$

This equivalence has $d$ answer where $d=gcd(s_1-s_2,p-1)$, $d$ is usually small so we can find $k$ using brute force on $r\equiv \alpha^k\ mod\ p$.

Now we know $k$ we can caluculate $a$ using $a.r\equiv m_1-k.s_1$ equivalence. Number of answer for this equivalence is $gcd(r,p-1)$ by comparing $\beta$ and $\alpha^a$ we can find $a$.

Now we know secret key and sign every plain text we want and that's insecure.


They use their output like a new input.

That's not correct, generally CS-PRNG's keep a state and use separate bits (or possibly the state run through a PRF) as output.

Shouldn't it be like that the ciphers should have long periods in such a test?

Yes, and the same goes for the CS-PRNG's. Yes, if you can trigger a CS-PRNG to repeat a long enough pattern then something is wrong. There are many other reasons why a PRNG is broken of course. It may be biased or how an attacker could get the state back, for instance. Beware that a cipher is not necessarily a CS-PRNG.

And is it possible that cryptographically secure PRNG will have short period for some inputs?

When correctly seeded they should have unpredictable output. If you can seed according to the specifications and it is still computationally feasible to get into a cycle then no, then it would not be cryptographically secure.
Generally you should not get repeated output as long as the seed is unique. Secure hash functions are often used to accomplish this.


How can data be encrypted in a client-server application so only clients can read it?

if all the clients leave the group (at which moment they delete K from their local store), all the information on the server will be useless as nobody has K anymore

Yeah, that is gonna happen, and there is no way to prevent it, unless you add some trustworthy instance to the system to store such keys.

  if Client2 comes online for the first time and another group member is not online it will not be able to obtain K and will not be able to decrypt any of the data stored on the server

Correct. Basically this is the same as the first question, with the others just being temporarily unavailable instead of permanently.

However, there are several aspects of your current solution, which should be discussed:

As cygnusv pointed out in the comments: You have no mechanism to remove users. Changing the master key is necessary then, as you can't enforce deletion of anything.
Encrypting files with the master key... this is bad. Especially if you have to exchange the master key, this would mean that you also have to decrypt and encrypt every single file/database again. Create a fresh key for each file, table, and so on, and then put it in a list, and work with this list afterwards.
You have a hard requirement that the server must not know the data. Have you made sure that the server does not join the group as a dummy-server (just to get the keys)? Because your access control structure is completely missing right now. You also don't state who handles permissions, creates and publishes the keys, etc.
How does the invitation work? Do group members invite? Who publishes the public keys, etc....
What do you want to do with the data? Especially in databases this is an issue, because you can not work on encrypted data. Instead of posting SQL queries, the clients always have to request a lot of data from the DB, decrypt locally and then apply their operations locally. Almost any optimization of this gives information to the server, which he should not have.


Risks hashing salt + 5 - 8 number pin with PBKDF2

Yes, look for example here. Consider using Argon2 for instance.
Yes, your concerns are valid. Password derivation should be slow enough. But in practice users cannot accept if login takes  longer than 1 sec. So the password derivation should take not longer than 1 sec. If a PIN consists of 5 digits, it means 100 000 different PINs. If every one takes no longer than 1 sec, an attacker needs not more than 100 000 sec to brute force it with a single core of CPU, means ~28 hours. In case of 4 core CPU it will take ~7 hours. With 8 digit PINs it will take longer. Roughly it can be about 28000 hours for single core CPU = 7000 hours for 4 core CPU = 292 days for such CPU. Means, if you have 10 CPUs, it will take less than 1 month to break it. With more CPUs the brute forcing will take even less time.
The question about auditing is out of scope on this site. Better is to ask it at Information Security site. But no matter what auditing you will implement, if an attacker obtains database with password hashes, he will brute force it, retrieve plain passwords, and then apply them. When some user complains that something is wrong with his account, auditing might help to track the attacker. But it can be that even finding the attacker will not help to mitigate the damage caused.


What are the steps to decrypt a TLS 1.1 record?

Is the above example correct? If not, how can the IV to be used for decryption be determined?

Yes, it is correct. The vector/mask in CBC mode is generally the previous ciphertext block. The algorithms in 2a and 2b simply extends this notion to the IV so that the CBC mode encryption doesn't have to be re-initialized. The outcome of the IV decryption won't have any meaning, it's the ciphertext block itself that is reused.

In dumb implementations of CBC / block ciphers the re-initialization may take time because it may replay the subkey derivation for the cipher. In general though using the first block directly as IV will be more efficient because it skips one block decrypt.

  Is the decryption for TLS 1.1 the same as TLS 1.2?

Yes, see below:

opaque IV[SecurityParameters.record_iv_length];
          block-ciphered struct {
              opaque content[TLSCompressed.length];

although described somewhat differently the IV length is the same as the size of the block for CBC. It is directly followed by the "opaque" (encrypted) content.


How to ensure that a cryptographic implementation is reasonably sound/robust?

One widely accepted standard for information protection is the ISO Common Criteria framework. This set of slides gives some sense of what a Common Criteria evaluation will ask in its analysis.
The US FIPS-140-3 standard also carries a lot of weight, it specifies certain NIST special publications that give criteria beyond ISO.


NIST elliptic curves behaving anamolous in OPENSSL benchmark

Here is what's likely going on:

Charm represents Elliptic Curve points in affine coordinates, that is, explicit (x, y) values
When doing a single point addition, OpenSSL adds the two points (internally coming up with a point in projective coordinates) and then converts them back into affine coordinates.  Then final conversion involves a modular inverse operation, and so is moderately expensive (more expensive than all the other operations combined).
When doing an point multiplication, OpenSSL takes the point, and does a series of point additions/doublings, keeping the point in projective coordinates.  Then, at the end, it converts the point back into affine coordinates (which involves the modular inverse).  However, you end up doing a single modular inverse, even though a number of point additions/doublings were done.

Hence, because the point multiplication avoids the intermediate modular inverses, it runs faster than expected.


A questions about SP 800-90A DRBG additional input

Some (hopefully) useful information to what you ask can be found in sections 7.2 Other Inputs and section 8.7.2 Additional Input of the SP 800-90A Rev. 1   June 2015   Recommendation for Random Number Generation Using Deterministic Random Bit Generators standard at http://dx.doi.org/10.6028/NIST.SP.800-90Ar1.

I copied and pasted a couple of points which I hope will shed some light, but I would recommend reading those sections in full.

7.2:
Other information may be obtained by a DRBG mechanism as input. This information may or may not be required to be kept secret by a consuming application; however, the security of the DRBG itself does not rely on the secrecy of this information.
...
Additional input may also be provided during reseeding and when pseudorandom bits are requested. See Section 8.7.2 for a discussion of this input.

8.7.2:
Additional input may optionally be provided to the reseed and generate functions during requests. The additional input may be obtained from inside or outside a cryptographic module, and may include secret or public information. Note that a DRBG does not rely on additional input to provide entropy, even though entropy could be provided in the additional input, and
knowledge of the additional input by an adversary does not degrade the security strength of a DRBG.

I'm not sure of real world examples.


Is XTS-AES a NIST-approved nonce-misuse-resistant AES mode?

A tweak collision seems to only disclose whether the same plaintext was encrypted with the same key and the same tweak

Actually, XTS will disclose whether related plaintexts were encrypted with the same key/tweak.  Specifically, if two plaintexts had the same value for block N, then after encryption (assuming the same key/tweak), the ciphertexts would also have the same value for block N (and thus leaking the relationship between the plaintexts).  This is true even if other blocks of the plaintext differ.  This is leaking data beyond what is allowed for 'nonce-misuse-resistance'


General property for a primitive LFSR:

Each nonzero bitstring of length $k$ where $k\leq m,$ occurs $2^{m-k+1}$ times while the all zero bitstring occurs $2^{m-k+1}-1$ times, in a single period of the LFSR. The run of $k$ 1’s is just one of those nonzero bitstrings.

For $k>m,$ some patterns never occur. The ones that do occur are exactly those patterns that satisfy parity checks which correspond to polynomial multiples of the generating polynomial.

Example: For the generating polynomial $x^4+x+1,$ the generating parity check is
$$s_{t-4}\oplus s_{t-1}\oplus s_t=0.$$ Since
$$(x+1)(x^4+x+1)=x^5+x^4+x^2+1,$$
the only $5-$tuples that occur at the output of this generator are those satisfying
$$
s_{t-5}\oplus s_{t-4} \oplus s_{t-2}\oplus s_t=0.$$


It depends on what you mean by "cracking", and also what you mean by "RSA".

"Plain RSA", also sometimes described as "textbook RSA", is the lone modular exponentiation. By itself, it is very weak. For instance, if $n$ is the modulus and $e$ the public exponent, suppose that you want to "decrypt" a cipher text $c_1$ (i.e. you want to find $m_1$ such that $m_1^e = c_1 \pmod n$). You can choose a random integer $c_2$ modulo $n$, and compute $c_3 = c_1/c_2 \pmod n$; then, obtain the decrypted messages $m_2$ and $m_3$, corresponding to $c_2$ and $c_3$, respectively. In that situation, you know that $m_1 = m_2m_3 \pmod n$. This is a chosen ciphertext attack, in which you ask for two decryptions and obtain three plaintext messages, including the target message $m_1$, and yet the decryption oracle did not see any request ending in revealing $m_1$. That's "cracked" by any decent definition of "cracking".

That's why "plain RSA" is not RSA. RSA, the asymmetric encryption algorithm, is described by PKCS#1 and includes a padding operation which is essential to security. With appropriate padding, there is no known attack on RSA which would help in decrypting a given message, even in an adaptative chosen ciphertext context.


How does the CBC Padding Oracle Attack work in General?

First before we can get into the details of the attack, we need an intuition why it works. There's a nice picture hosted on the TLSeminar page illustrating this point:

which basically says that we want to modify the last byte $\color{red}\times$ of the second-to-last block so that the CBC decryption of the last block which has "$\color{blue}?$" as its content yields $\color{green}{\mathtt{0x01}}$ instead. This of course works because CBC decrypts as $\color{green}{M_i}={\color{blue}{D_K(C_i)}}\oplus \color{red}{C_{i-1}}$. Finding the right $\color{red}\times$ is achieved by querying all 256 values to the padding oracle to which you should only get one positive response (when you hit the correct plaintext guess or accidently hit a longer padding).

So now that we know roughly what to do: Namely guess the last yet unknown byte until you get confirmation, let's get into the details.

Let $i$ by the current plaintext octet counted from the end that we are trying to recover, including padding. Initially, let $i=1$. Further let $G_i$ be the set of potential plaintext octets recovered in iteration $i$.
Let $c_{k-1}$ be the second to last ciphertext block or if $k=1$ then it corresponds to the IV. Define $c'_{k-1}:= c_{k-1}\oplus (0^{n-8(i-1)}\|g_{i-1}\|\ldots\|g_1)\oplus (0^{n-8i}\|\texttt{i}^{i})$ where $\texttt{i}^i$ is $\texttt{i}$ encoded as one octet repeated $i$ times and the $g_i$ are elements of their respective sets $G_i$ which we currently use.
For all $g\in\{0,1\}^8$, query the oracle with $c'=c''_{k-1}\|c_k$ where $c''_{k-1}:=c'_{k-1}\oplus (0^{n-8i}\|g_i\|0^{8(i-1)})$, add all $g_i$ for which $P(c''_{k-1})=1$ to $G_i$.
If $G_i$ contains $0$ or $256$ entries, that is the oracle always responded positive or negative, find the largest $j<i$ for which $G_j$ has more than one entry.
Remove $g_j$ from $G_j$ and set any other element of $G_j$ to be $g_j$.
Note that $j$ may be negative here which then implies that a previously "discarded" ciphertext block needs to be re-added and $j$ be incremented by $n/8$.
This addition of old blocks needs to be repeated until $j$ is positive again.
If $G_i$ fulfilled that special condition, set $i\gets j+1$ otherwise update $i\gets i+1$ and pick any element of $G_i$ as current $g_i$.
If $8i>n$ set $i\gets 0, k\gets k-1$ discard the last block and return $g_{n/8}\|\ldots\|g_1$ as its contents.
Go back to 1.

As this is quite the wall of text, here's an UML sequence diagram illustrating the above procedure for the case that the $G_i$ always have size 1:

The idea of the addition of these sets is that indeed we may get unlucky and hit a second-to-last byte of $\texttt{0x02}$ which results in $\texttt{0x02}$ and $\texttt{0x01}$ being accepted by the padding oracle. So instead we take a guess which plaintext guess was right and go back to take another option if needed later, e.g. if we obviously did a bad guess previously due to now always satisfying the oracle.

If the padding oracle enforces a given ciphertext length, we can still recover data, but if the padding is only allowed for up to one block, we can only recover one block or else we can recover at most $255$ bytes if arbitrary length multi-block padding is allowed. For this then we simply don't discard the ciphertext blocks and keep incrementing our $i$ beyond $n/8.$


This function has all appearance of being affine (or loosely speaking: linear), in the sense that has in cryptanalysis:
$$\forall (x,y,z),\;f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$$
In other words: if the exclusive-OR of the inputs in any 4 lines is zero (e.g. the first 4 lines), then the XOR of their output is zero.

It follows that we can compute the output for any input $x$, as
$$f(x)=f(0)\oplus\left(\bigoplus_{j\text{ with bit }j\text{ set in }x}\big(f(2^j)\oplus f(0)\big)\right)$$
where $f(2^j)$ is the output for input the 48-bit bitstring with only bit $j$ set. A similar equation can be derived without guesswork from any set of input/output pairs with one more elements than there are input bits, and all the inputs but one linearly independent.

This also gives the equation for any output bit as a function of the input bits, as a chain of exclusive-OR of input bits and a constant bit.

Code implementing this is a three-liner with a loop on the 48 input bits, plus a table of 48 words of 16 bits; that makes the whole thing less than 200 bytes of compiled code, running under a microsecond on a PC.

Further analysis could perhaps reveal more regularity; like, this could be a truncated CRC of the input bits in some order. That guesswork could be necessary if you do not obtain enough input (in particular, if some input bit does not change in any of the available input/output pairs, the only way to guess its influence on output is to find some regularity in the influence of those inputs bits that vary). That would also allow making the code shorter, faster, and with a simpler specification.

Note: I decided to answer the question even though it contains a dump of plaintext-ciphertext pairs (usually a no-no on CSE), because it illustrates well a common (reverse)-engineering problem: making something compatible with a deployed unknown function, on the sole basis of examples, when that function turns out to be affine, as does any function written using only bitwise eXclusive-OR, shifts and rotations. The technique I describe works for many functions found in the field; in particular anything worth the name CRC, including countless failed attempts to implement some standard or academically proper CRC, which ended up in some ugly proprietary mess.


Why the data length is shifted 3-bit in MD4 Java implementation?

This is not a Java-related issue. All of these implementations are doing what the RFC says. Here are the relevant parts of RFC 1320 (emphasis mine):

  3.1 Step 1. Append Padding Bits

  The message is "padded" (extended) so that its length (in bits) is
     congruent to 448, modulo 512. (…)

  3.2 Step 2. Append Length

A 64-bit representation of b (the length of the message before the
   padding bits were added) is appended to the result of the previous
   step. (…)

The length in §3.2 is again the length of the message in bits. All the Java implementations you've seen calculate the length in bits from the length in bytes. One byte is 8 bits in Java (like on almost every platform, but there are platforms that group bits in bytes of different sizes), so the length in bits is the length in bytes multiplied by 8. Shifting to the left by 3 is equivalent to multiplying by 8.

It is common in cryptographic algorithms to consider the data as a stream of bits, and in particular express lengths in bits. The fact that bits may be arranged in groups of 8 called bytes is an implementation detail that does not influence the behavior of the algorithm.


Here is the issue about hardware errors that Brent is worried about on the slides (I'm not saying I agree; I just saying what the issue is):

Suppose we ran our algorithm, and it gave a result "it's prime"; how can we be certain that the algorithm didn't gave us the wrong answer because of an internal hardware error while running the algorithm?  This may sound like a trivial point, as the error probability on real hardware is actually quite small.  However the entire reason we're not running 100 iterations of Miller-Rabin is that we want to be certain; are we as certain we didn't run into an internal error within AKS as we would be that 100 iterations of Miller Rabin (which is a lot faster than AKS for any reasonable input size) didn't all lie?

Well, AKS just outputs an answer "Prime" or "Not Prime"; if you want to verify the result, we have no better way than to run AKS again.

In contrast, consider the alternative algorithm Elliptic Curve Primality Proving or ECPP.  This algorithm also always answers "Prime" or "Not Prime", and is always correct.  However, it also generates a "Primality Certificate"; this primality certificate can be rechecked with a separate fast algorithm.  No such primality certificate exists for a composite number; hence once we've run ECPP (and have generated a certificate), it is less important if we hit a hardware error during ECPP; if the primality certificate verifies, the number must be prime (even if ECPP did get a hardware error).

The above is the answer to the question; here is another point to consider.

ECPP is, in practice, considerably faster than AKS.  Hence, unless someone finds a further advance in AKS (and reduces its exponent), there's little reason to actually use AKS in practice; if you insist on a provable prime, you use ECPP; if probabilistic methods are good enough, you use Miller-Rabin (or similar algorithms); alternatively, if what you're doing is searching for prime numbers, you can consider provable methods of constructing prime numbers (such as Shawe-Taylor).

So, if AKS is not useful in practice, why are people so interested in it?  Well, while ECPP is faster, it's actually a Las Vegas algorithm; it's randomized, however, unlike Miller-Rabin, it'll never return an incorrect answer; instead, its low probability failure mode is that it might continue to run.  In contrast, AKS is a deterministic polynomial time algorithm.


How to determine the concrete security of lattice cryptosystems?

Depending on whether your lattice-based cryptosystem has security reduction or not, there exists two types of parameters:

$\textbf{1. Provably secure:}$ For a cryptosystem with provable security, the parameters are chosen according to the underlying reduction. For example, suppose your cryptosystem is based on the hardness of LWE problem. Now, assuming that the desired security level $\ell$ is identical to the hardness level of the LWE problem (i.e., without involving the gap induced by the security reduction), one can determines the best known solver $D$ for the LWE problem and ensures that its corresponding
parameters offer a hardness of $\ell$ bits. In order to find also the best known solver for LWE and measure the bit hardness of LWE instances, the estimator by Albrecht et al. [APS15] can be used.

$\textbf{2. Non-provably secure:}$ If the cryptosystem is not provably secure, then identify the best known attack $A$ on the cryptosystem and select parameters satisfying $\frac{t_A}{\varepsilon_A} \geq 2^{\ell}$, where $t_A$ and $\varepsilon_A$
are the running time and success probability of $A$, respectively.

See this paper for more details.


I'm not sure exactly what you're not getting.

You understand that the keyspace for a simple substitution cipher is $26!$; do you understand that $26! = 1 \times 2 \times 3 \times 4 \times ... \times 24 \times 25 \times 26$, correct?

So, we have $26! = 403291461126605635584000000$, correct?

We also have $2^{88} = 309485009821345068724781056$, correct?

Would you agree that these are "roughly" the same (where roughly in this case means within 30%)?

  keys = 26^4 = 2^18

What might be confusing you is the equal sign; obviously $26^4 = 456976$ is not exactly $2^{18} = 262144$; I believe the idea the author is trying to convey is that they're close, well, at least close enough for his analysis.  I'd personally use $\approx$ here...

  (though should it not be 26!^4?)

Actually, for Engima, 26 is correct; each rotor can be set in one of 26 positions; hence each rotor can do one of 26 specific permutations; it can't do an arbitrary 26! permutation.


How to propagate error in variable-sized message?

The scenario you're facing is well-known in cryptography. You can't afford expanding the message at all (maybe by some IV). So you can't get strong authentication but have to rely on what is called poor man's authentication, you rely on tampering causing random messages.

Please note that all of the following modes are somewhat block-based, meaning you'd have to use padding (like PKCS#7) to ensure correctness of the data and you have to actually check the padding to protect against POODLE style attacks.

The exact same scenario is given in the full-disk-encryption (FDE) scenario. This gives you four options, plus those added by other answers.

XTS, the standard mode for full-disk encryption. It allows for two tweaks hiding potential patterns. You can use standard padding methods (PKCS#7) if you're not hitting block boundaries, this is the most standard solution but may not scramble enough as it only affects the current block.
PCBC is a mode that propagates errors infinitely into the following decrypted plain texts. It accepts IVs and also hides patterns. This may not be preferable compared to the all-or-nothing transforms but may be the choice if they're too slow. And you may want to avoid this one if possible to not fall against the "same flip attack"  although this would still mean that two blocks (32 bytes for AES) are scrambled.
EME, a mode originally specifically designed for full-disk encryption and tackling the poor man's authentication best. It turns every block cipher with block size $n$ into a larger block cipher with block size $n^2$ and accepts tweaks to hide patterns and provide random-access. If you'd use AES this would mean you can encrypt up to 2048 ($=128^2/8$) bytes and make sure the whole block is scrambled if tampered. The main drawbacks are potential patents and the lower speed of requriring double the amount of block cipher calls and a finite field multiplication. EME may not be a good choice if patent-freeness is required.
All or nothing transforms. You can use standard XTS or something like that, but apply an all-or-nothing transform on the plain text to make sure the receiver has the complete and correct set of all blocks. This is somewhat non-standard but looks like the best solution.


In two-dimensional even parity, how do we determine the corner parity bit?

Do we look at the number of 1's in the corresponding column and/or in the corresponding row?

Yes; you can do it in whichever direction is most convenient; it'll be the same either way.

In either direction, the parity of $z$ will be the parity of the entire data matrix (1 if there are an odd number of 1's, 0 if there are an even number).


You are confusing your notation. You are saying that $g^A\equiv 70 \bmod{71}$, but then you are also saying that $A\equiv 7^x\bmod{71}$. That is not true. So let's clarify the notation.

Let $A$ be Alice's private exponent and $B$ be Bob's private exponent.

You know that $B=28$ and you know that $g^A\equiv 70\bmod{71}$. You do not know $A$, however, but you do not need to know $A$.

The shared key between Alice and Bob is ${g^A}^B\equiv {g^B}^A \bmod{p}$. So given what you know, you can compute the shared secret.

To figure out what Alice's private exponent is, you would have to solve the discrete logarithm. For numbers this small, that would be easy, but in general (and for the size of numbers we use in practice) that is infeasible.


Is it feasable to combine ECB and CTR block modes of operation?

Yet if you shuffle the blocks, the blocks that changed locations are completely broken.

This may be true, but you'd have to define what you have achieved if you do. What you are trying to do here is to change the error propagation of the mode of encryption. ECB however has very limited error propagation; it only extends to one block. If you change one bit then the whole output changes. But if your input may have a high amount of possible values, then the change won't be detected. Now you could introduce a crib, a known plaintext, but you'd still have to create yet another pass of e.g. a cryptographically secure hash to protect all the blocks using only one crib.

Error propagation was once an important topic for block ciphers. Nowadays however we tend to rely on CRC's or schemes like PAR2 to avoid damaged (cipher)text. And we tend to rely on message authentication codes (MAC's) to create cryptographically secure authentication tags. Finally we have schemes such as OCB and GCM that provide 1 to 1.5 pass authenticated encryption, making your scheme rather inefficient.

  Plus you can't just create an xor key using the same key/nonce, as the data is then still encrypted with a different key. This will also double the key size.

Encrypting twice often does not double the key size due to meet in the middle attacks. You'd have to prove that this is the case.

But given the inefficiency and only partial error propagation and ineffective authentication, I don't think you'd have to delve into that topic.


GPG vs PGP vs OpenSSH and management of them

What is the main difference of the three? Can I use only one of them for everything (e.g. GPG for SSH authentication)

GnuPG is an free and open-source implementation of the OpenPGP standard.
Symantec PGP is a proprietary implementation of the OpenPGP standard.
The OpenPGP standard defines ways to sign and encrypt information (like mail, other documents and code/software).
OpenSSH is about connection securely to remote computers. For authenticating you need some secret, usually this is a passphrase or SSH key.

With OpenPGP, you hold a secret (private key) which also can be used for authenticating yourself. It needs software support for that, and I haven't heard of some code doing this for (Symantec) PGP, but there is a way doing this with GnuPG.

  If I encrypt my private key with a pass-phrase, is it strong enough so that if someone steals my laptop or private key, I'm safe?

Your password encrypts your private key. The key is safe as long as your password is safe. If your password is too weak (dictionary-attacks, not long enough, easy to brute-force for other reasons), your key is vulnerable, too.

Think about how valuable your key is for an attacker and choose fitting security measures like storing your key offline (in the and of this answer).

  If not, what about encrypting my private key with the scrypt algorithm?

If doing so, security depends on the password you're using for scrypt and scrypt's algorithm. You can achieve the same amount of security with a good OpenPGP password, so there is no need for additionally encrypting your key.


implications of SSH server key compromission when authenticating users against a public key

In the common configuration of SSH, the session keys (and a session ID) will be negotiated using the Diffie-Hellman key exchange, and then authenticated by the server, using its private key to sign all the exchanged data (which is then checked by the client).

The public key authentication of the client happens after that, when the actual connection is already running, and does not influence the encryption (and MAC). But the public-key authentication is a signature over multiple values, including the session identifier.

So, in effect, if the attacker has the server's key she can pretend being the server (to the client). She would have to accept the public key login, and show the client some shell or similar.

What does not work for the attacker is to connect at the same time (as a client) to the server and use the client's public key authentication to authenticate itself to the server, as the signature includes the session ID, and the session ID will be different for different Diffie-Hellman key exchanges.

Also, it seems not possible to manipulate the Diffie-Hellman key exhange in a way that one still knows the created keys, and they (as well as the session ID) are the same for both connections.

With RSA key exchange (where the client simply RSA-encrypts the some random data with a transient server key and sends it to the server, and both sides derive everything from this then shared secret (and the other stuff that was exchanged, like the public key, the offered key exchange methods and so on), a MiTM-attack (knowing the server's transient private key) is feasible - simply decrypt this message, then you know the keys used both for encryption and authentication (and the message-ID), and can read and modify all further messages.

If she only knows the server's long-term private key, this is not so simple: While she can replace the transient server key with her own one, this results in a different session ID (and session keys), and as such the public-key authentication of the client will not work anymore for her.


How are Elliptic Curve Cryptography and Pairing Based Cryptography related?

Most pairing-based cryptography (PBC) schemes are based in elliptic curve cryptography (ECC). The main function in PBC is the pairing, which is a function $e$ with two parameters, e.g. $r = e(P, Q)$. The relationship with ECC is that $P$ and $Q$ are points in elliptic curves over finite fields. The value $r$ is an element of a certain finite field (related to the fields used in the elliptic curves).

Some PBC protocols also need to compute point multiplication, e.g. $kP$, which is also the central algorithm of ECC and therefore can use the same existing techniques and optimizations.


Public key on Server Key Exchange Generation vs Public key on Server's Certificate

TLS ≤1.2 allows different types of handshakes where the key exchange and the authentication rely on different mechanisms. The type of handshake is determined by the choice of cipher suite. The page you link to illustrates the most common type, where key exchange and server authentication work independently. This type of handshake is the one used by ciphersuites with ECDHE or DHE in their name.

For this type of handshake, the key exchange uses an [elliptic curve] Diffie-Hellman key agreement algorithm with an ephemeral (i.e. single-use) key. To generate the ServerKeyExchange message, the server generates an (EC)DH private key, and the ServerKeyExchange message contains the corresponding public key. The client does the same for the ClientKeyExchange message. The two sides then perform a Diffie-Hellman key agreement algorithm using their own private key and the other side's public key to generate a shared secret. By the design of DH, the two sides generate the same shared secret. This shared secret is the premaster secret for the TLS protocol.

In the specific example in your link, the server chose the X25519 group for the key agreement. For this particular group, a private key is an integer between $0$ and $2^{256}-1$.

None of this allows the client to know who it's exchanged data with. This comes from a different part of the ServerKeyExchange message: the signature. The server sends a signature of the important handshake data so far made with its private key. Specifically, the signed data includes the client nonce from the ClientHello message, the server nonce from the ServerHello message, and the DH public key. Previously, the server sent a Certificate message containing its certificate. The client verifies that:

The signature sent by the server is a correct signature of the appropriate handshake messages, made with the private key corresponding to the public key in the certificate sent by the server.
The certificate is signed by a certificate authority (CA) that the client trusts, or more generally that there is a chain of trust going from a trusted CA to the server's certificate.
The subject name in the certificate matches the server name that the client was attempting to contact.

A man-in-the-middle attacker who spoofs DNS records won't be able to get all of these verifications to pass.

The attacker can send the expected certificate and replay a good signature from a past exchange that it observed with the legitimate server, but then this signature won't be correct, because the handshake messages include a random nonce sent by the client.
The attacker can forward the ClientHello message to the legitimate server, get the legitimate server's ServerExchangeMessage and forward that to the client. Since the signature in that message includes the DH public key chosen by the server, the attacker won't have a way to find the shared secret. In this case, the exchange can go through if the attacker keeps forwarding both sides' messages intact, but the attacker won't be able to decrypt the messages or to modify them undetected. Since the attacker isn't able to violate the expected security properties of the TLS protocol, they aren't actually attacking anything: they're just a TCP router.
The attacker can send the expected certificate and a signature made with its own private key, but then the signature won't be correct, because the attacker would need the legitimate server's private key to make a correct signature.
The attacker can send a certificate containing fake data, but then the client will detect that the certificate is not internally consistent or that the certificate is not signed by a CA that it trusts.
The attacker can send a valid certificate made by a CA that the client trusts, but then (assuming the CA has done its job correctly) this certificate will contain a subject name that the attacker owns, and not the subject name that the client was trying to contact.


Is it a good idea to use bitwise XOR on a set of MD5 sums?

The short answer is no. The scheme gives poor protection against collisions, that is inputs detected as having the same content (within order) when they have not.

As noted in the question, this can occur when entries in an input are duplicated; e.g. ("O","X","O") and ("X") collide.

This can also occur for maliciously crafted entries. For a start, MD5 is broken, in the sense that it is now easy to create different strings/entries that hash to the same MD5 result; replacing one by the other will go undetected. And even if one uses a collision-resistant hash such as SHA-256, it is very easy to construct a set of messages such that the XOR of their hashes equals a given value, by mere Gaussian elimination. See the answer to this question.

On the other hand, short of the issue of duplicated entries in an input, there is little chance that the scheme fails by accident.

A robust scheme would be:

hash each string using SHA-256
sort the hashes by ascending value
hash the concatenation of the sorted hashes using SHA-256


I need an algorithm for "key generator". It should be initialized with some secret data, such as a (hashed) passphrase, or something generated once by some 3rd-party code.

This is called a Key Derivation Function or KDF. As your question indicates a pre-established secret with enough randomness / entropy a Key Based Key Derivation Function is what is required. KDF's that are used over passwords (that generally require strengthening) are called Password Based Key Derivation Functions or PBKDF's or password hashes.

Given some small input it should be able to generate N bits in a deterministic way, which'd be used as a material for some key. The input consists of a needed key index, and, perhaps, some other flags and parameters.

The small input is called the input key material (IKM or $K_I$), the N is generally called $L$ for the length of the output key material (OKM or $K_O$).
This input is generally called Info, OtherInfo or, for NIST, FixedInfo or Context depending on the standard used. There are a lot of impromptu KDF's so the terminology can change from one protocol / standard to another.

Naturally the generated keys should not reveal other keys or the generator secret.

That's the general idea of KDF's. They are commonly build from one way functions such as hashes or MAC's.

What is the preferred way to do this? Is it ok to just hash all the input?

It is important to be careful with regards to the input. One thing to make sure of, even if a standardized function is used, is that the input data cannot overlap, i.e. there should be a canonical representation of the Info data and the key.
For instance, if variable $x$ can consist of "A" or "AB" and variable $y$ can consist of "BC" or just "C" then two different combinations of $x$ and $y$ will be able to produce "ABC" if you just concatenate the two variables.
Furthermore, if an attacker can influence the input then you may also need to avoid length extension attacks or even attacks on the hash function. Otherwise, yes, it is fine to just hash the Info - or input as you call it.

To be concrete, I need a sort of a DRBG, whereas:

I don't really care about preimage attacks and etc. It's not intended for message authentication. I believe there's no need in HMAC.
The generator must be immutable, i.e. should not mutate after each generation (like auto-hashing).
It should work in O(1) wrt the key index. In simple words, generating k'th key should be no harder than generating the first one.

You don't want a DRBG. DRBG's are defined to generate pseudo random bits using seed information. However, many implementations will be seeded by the system, and may be reseeded at specific times. They also may not return the same random data if you ask it for, say two times 16 bytes or one time 32 bytes. They generally do not have a good means to supply a other info. If you are unlucky you may generate keys that cannot be recalculated and you lose all data; see for instance here.
KBKDF's do fulfill all of these requirements - except that quite a few are based on HMAC as it is immune to some of the attacks such as those that rely on collisions and length extension techniques.
Available KDF's
Currently one of the most advances KBKDF's is called HKDF. It is based on HMAC with a configurable hash function underneath. It consists of two functions: HKDF-extract and HKDF-expand, where the first one extracts (or compresses) the entropy in the input data to a fixed length pseudo-random key. HKDF-expand then uses this fixed length key to derive one or more keys of any length, using the info (counter etc.) provided. It is also NIST approved.
A more simple hash based KDF is called KDF1 (or MGF1 in the simple form with just the counter), KDF2 or KDF3 (which differ only minimally). It is defined in ISO-18033-2,  IEEE Std 1363-2000 with similar functions in ANSI X9.62, which are unfortunately all payware. It uses a hash function, a counter and possibly other Input to derive keys in a pre-defined way (although creating the "Info" needs to be canonical, as already explained).  I asked a question about it here and described the most simple form.
An alternative for KDF1 called KDM has been defined in NIST SP 800-56C Rev 1 which can be used both with a hash or MAC; it includes options for SHA3 and KMAC. Basically it is a re-ordered KDF1 which could be well suited for your purpose and has a publicly available document describing it. NIST SP 800-56A has some interesting information on what to put in FixedInfo (a renamed OtherInfo).
Otherwise any of the key derivation functions of NIST SP 800-108 which is comprehensively called "Recommendation for Key Derivation Using Pseudorandom Functions". It uses MAC's and includes some alternatives that are based on block ciphers instead of hashes.


Attack an stream cypher using 2 XORed LFSRs

The fundamental property that you will use is that the output of an $A$-bit LSFR (using the $A$-bit feedback polynomial $P$) xored with the output of a $B$-bit LSFR (using the $B$-bit polynomial $Q$) is the same as the $A+B$ bit LSFR with the feedback polynomial $P \cdot Q$.  And, don't forget, when you multiply the feedback polynomials, you use polynomial multiplication modulo 2.

Hence, we know your output can be generated by a 32-bit LSFR; the obvious thing to do is use the Berlekamp–Massey algorithm to find the LSFR, and once you have the feedback polynomial, factor it.

If you get a 32 bit LFSR with two 16 bit prime factors, that immediately gives you your answer.

If it factors into smaller factors, well, you need to search for a way to combine the smaller factors to two 16 bit polynomials.  Here, you use the fundamental property in the other direction; for example, if the polynomials you find are 3, 7, 9, and 13 bits; then the obvious way to combine them are the 3 and 13 bit polynomials (which multiplied make up a 16 bit LSFR), and the 7 and 9 bit polynomials (which multiplied make up another 16 bit LSFR)

If BM finds a LSFR which is smaller than 32 bits, well, there are a couple ways for that to happen (after all, the fundamental property says that there exists a 32 bit LSFR that generates the output; it doesn't say that it's the smallest possible LSFR).  One possible reason for this is that a factor LSFR might be initialized to zero; in that case, that LSFR won't contribute anything.  Another reason would be that the two polynomials might share a factor.  In any case, what that means is that you likely won't be able to come up with a unique answer as to the original polynomials.


How can Bob validate Alice’s certiﬁcate?

As CA2 << CA1 >> is a certificate it seems that CA2 is indeed a root certificate. This is not strictly necessary; CA2 just needs to be trusted by Bob.  CA2 << CA1 >> is then an intermediate CA certificate for cross certification.

To verify the certificate you need to verify the certificate chain. So the CA2 certificate is trusted, which verifies CA2 << CA1 >>, which finally verifies CA1 << Alice >>. This is performed by retrieving the public key within the parent certificate of the issuer and then use that to verify the signature of the child certificate of the subject. Besides verifying the signature over the "To Be Signed" part of the certificate you may also need to validate properties such as  validity period, key usage and so on.

Generally if there are two separate CA's that need to trust each other then the trust is established by issuing cross certificates: special intermediate certificates that establish the trust. These certificates may have additional properties that establish the type and level of trust. Here is an explanation of the trust relationships, unfortunately without the intermediate certificates being shown.

The cross certification certificate is placed next to the original certificate in the trust chain. So while you have C1, C1 << Alice >> as the original chain you would have another chain C2, C2 << C1 >> (replacing C1) and finally C1 << Alice >>.


Commiting to a linear relation over a finite field

If we can assume that $k$ is a large prime order (say, 256 bits or larger), one way is with Pederson commitments.

Assuming $g, h$ are two unrelated bases of order $k$ in $Z_p$ (for some large (2048 bit or more) prime $p = kn+1$), then the commitment are the values $g^{a_1}h^{r_1}, g^{a_2}h^{r_2}, ..., g^{a_m}h^{r_m}, g^{-b}h^{r'} = d_1, d_2, ..., d_m, d_b$, where $r_1, r_2, ..., r_m, r'$ are random values between 0 and $k-1$.

Then, to prove that a specific $c_1, c_2, ..., c_m$ satisfies the linear relation, you generate a zero knowledge proof that you know the value $x$ such that $h^x = d_b \cdot d_1^{c_1}d_2^{c_2} ... d_m^{c_m}$

This is equivalent to starting that $h^x = g^{a_1c_1 + a_2c_2 + ... + a_mc_m - b}h^{c_1r_1 + c_2r_2 + ... + c_mr_m + r'}$; if $a_1c_1 + a_2c_2 + ... + a_mc_m - b \equiv 0 \pmod k$, the prover can do this (assuming he remembers the values $r_1, r_2, ..., r_m, r'$ that he used); if $a_1c_1 + a_2c_2 + ... + a_mc_m - b \not\equiv 0 \pmod k$, then this reduces $h^x = g^yh^z$ for a nonzero $y$ and some $z$; as we assume no one knows the discrete log of $g$ to base $h$, the prover cannot know $x$.

I don't immediately see how to make this work in smaller groups (working in a larger subgroup that has $k$ as a proper factor doesn't work), but at least it's a solution that works in some cases...


Cipher based message authentication (CMAC) and block reordering

No, CMAC is not susceptible to block reordering.

Unlike CBC, the attacker does not see the values of the intermediate encryptions (and because of the tweak applied to the last block, he can't find that out by asking for the MAC of prefixes).  Hence, the attack cannot modify the plaintext (including reordering blocks) in a way to make a predictable change to the hash output.


So is it possible for homomorphic encryption to actually filter and return a small encrypted subset of a larger encrypted database based on a query?

Sure it is. Say we have a database with (encrypted) test scores and student id and want to query the DB for the student with the highest score. Using FHE we can do comparison that for our purposes assume returns either 0 or 1.

students,scores = query()
high_student = encrypt(pk, 0) # encrypt with the public key
high_score = encrypt(pk, 0) # same

for student,score in (students, scores):
  bit = score > high_score
  high_score = bit*score + (1-bit)*high_score
  high_student = bit*student + (1-bit)*high_student

return high_student

This illustrates how you can filter as long as the number of returned results is fixed (not even necessarily fixed to 1). What if you wanted every student with greater than a 90%? I don't think that is possible with out returning something the same size as the entire table. this makes sense as you don't want your FHE to leak any information. That would leak how many values are greater than 90%.