There is a protocol similar to SRP but where a part of the secret is stored on the client side?

Actually, if you assume that the client is able to store a secret long-term, it becomes rather easy; just have the client store the private key (possibly encrypted by the password); the server gets the public key.

Then, when it comes time to authenticate, the client takes the password, decrypts the private key, and then uses the private key to authenticate to the server (and ideally generate some shared symmetric keys that can be used to protect the following traffic; defeating MITM is important).

Someone who breaks into the server (and possibly records some transcripts of the authentication exchanges) gets no information about the passwords, all he sees is a series of public keys.  And, with a bit of care, someone who breaks into the client may get no information about the password either (if we are careful to pick a public key algorithm whose private keys look random; ECC is good with this).

Now, one aspect that your protocol doesn't address is 'how does the client make sure he is logging into the valid server'; the easiest way for that is to store the server's public key in with the data the client is keeping around anyways.

With that, one simple way may be the simple STS protocol; the client picks a random DH key, and sends its public key share (signed by its private signature key).  The server picks a random DH key and sends its public key share (signed by its private signature key).  Both sides verifies the received signatures, generate the shared DH secret, and so have keys which can be used to protect further traffic.

Alternatively, you could go a bit fancier and use TLS with client certificates; that's more work, but is certainly standard; it may make preventing dictionary attacks on someone who captures the client a bit more challenging, though...

Of course, the drawback to this 'store some of the secret on the user's device' solution is the assumption that the user will always use that device to log in; he can't use any other.  I suspect that constraint may be why we don't see it more often...


You cannot change the hash size without altering TLS:

From: Appendix C.  Cipher Suite Definitions

MAC       Algorithm    mac_length  mac_key_length
--------  -----------  ----------  --------------
NULL      N/A              0             0
MD5       HMAC-MD5        16            16
SHA       HMAC-SHA1       20            20
SHA256    HMAC-SHA256     32            32

So although the mac_length is part of the SecurityParameters structure, the sizes are still predetermined. The implementation on the other side may not support truncated MAC values.

For the AEAD/GCM cipher the size of the tag is determined in RFC 5116 "Authenticated encryption" (normative reference):

  An authentication tag with a length of 16 octets (128
     bits) is used.

RFC 5116 is a rather strict (too strict in my opinion) as it assumes that the authentication tag is part of the ciphertext. It doesn't allow alterations to the size of the authentication tag either.

You are of course free to alter the specification for your own purposes. In that case the question however simply: what size of authentication tag should I use for ciphertext of "2^14 bytes or less" - as $2^{14}$ is the maximum size of a (data) fragment for TLS 1.2. In that case it depends on the MAC construction used.

For GCM the minimum is 64 bit, but a higher tag size would be preferred. For the HMAC variants you might go lower, but you should only do so for small, infrequent messages. This in turn means you must make sure that an attacker cannot trigger you to use more / larger messages.


Why does RSA give better security on longer messages?

This only applies to "text book" RSA, i.e. plain modular exponentiation with the public or secret exponent.

If you have a $n$-bit modulus, and use a message $x$ shorter than $n/3$ bits, the modular part of modular exponentiation doesn't come to play when calculating the ciphertext as $c = x^3 \bmod n$. The effect is that you can simply calculate the (integer) cubic root of the ciphertext $c$ to extract the plaintext, and don't have to deal with the key at all.

I think similar attacks are possible if the message is only slightly longer than $n/3$ bits.

This is one of the reasons that you normally don't use textbook RSA, but standard RSA, which uses non-zero padding to fill up the message to the size of the modulus, so the modular reduction actually comes into effect. Another reason is that you need some randomness in the padding, to avoid that the same message encrypted twice with the same public key gives always the same result.

Also, in practice you are not encrypting the message directly, but encrypt a key for a symmetric algorithm, which then is used to encrypt the actual message, in a hybrid scheme.


Comparing different hashes to confirm they came from the same string

Here's a thought; we work in a pairing-friendly elliptic curve where the discrete log problem is hard, and we generate a 'hash' of a value $p$ [1] by selecting a random value $r$, and outputting the two points $(rG, rpG)$.

Then, given two such hashes $(rG, rpG)$ and $(r'G, r'p'G)$, we can check if they are hashes of the same password by computing the two pairing operations $e(rG, r'p'G)$ and $e(r'G, rpG)$.  If $p = p'$, then both values will be the same, namely the value $e(G, G)^{rr'p}$.

Reversing the hash, that is, given $(rG, rpG)$, recover $p$, is a discrete log problem, this is assumed to be hard.

And, given a long list of hash passwords $(rG, rpG), (r'G, r'p'G), (r''G, r''p''G), ...$, there doesn't appear to be any obvious way to compare all of then against an attacker chosen password with less than $O(n)$ pairing operations or point multiplications.

The attacker can test a single hash $(rG, rpG)$ against a test password $p'$ by checking if $p'(rG) = rpG$; however with any such primitive where there is a primitive to compare hashes, the attacker could perform this test by hashing the password $p'$ and using the comparison primitive to see if that hash matches the one under test, and so this is not a vulnerability.

[1] The value $p$ might be a conventional hash of the actual password; that detail isn't important for this idea.


TL;DR: Yes, you can use PBKDF2 as a stream cipher.  However, you should not use it for that and for its intended purpose (i.e. password-based key derivation) at the same time.  Instead, if you need to do both, call it twice.

PBKDF2 is a password-based key derivation function — or, rather, a scheme for constructing such a function out of a variable-key-length PRF, which in turn is is usually implemented by taking a cryptographic hash function and wrapping it in the HMAC construction.

As a general-purpose key derivation function, PBKDF2 is designed be able to generate an arbitrarily long* string of pseudorandom bits.  To make it resistant to brute force password guessing, it is also designed to take an iteration count that deliberately slows it down.

However, when used to generate more output than the underlying PRF / hash function produces, PBKDF2 has what is nowadays generally considered to be a design flaw: its runtime is roughly proportional to the product of the iteration count and the length of output requested (whereas, in many real-world scenarios, the time for an attacker to test one guessed password still only depends on the iteration count).  Thus, you really don't want to call PBKDF2 with both a high iteration count and a high output length.

Instead, my general recommendation** for applications that need to generate large amounts of key material using PBKDF2 is to first use PBKDF2 with a large iteration count to generate a "master key" whose size equals the output size of the underlying hash (which should preferable be chosen to make this as large as feasible, e.g. SHA-512 for a 512-bit output), and then feed this master key into a non-iterated KDF (such as HKDF-Expand from RFC 5896, or even PBKDF2 itself with the iteration count set to 1) to expand it into the full required length.

With this scheme, the output of PBKDF2 applied to the master key, with a unique per-message salt and an iteration count of 1, should even be safe to use directly as a keystream to XOR the message with.  Internally, PBKDF2 simply uses (salted and optionally iterated) HMAC in counter mode, which yields a secure stream cipher as long as the underlying hash function satisfies the conditions of the HMAC security proof (which all secure modern hashes, and even some old not-so-secure ones like SHA-1 and even MD5, are believed to do).

You do need to ensure that the salt input to PBKDF2 is unique for each message; otherwise you end up reusing the same keystream for two messages, which breaks the security of any XOR-based stream cipher.

Also, note that, like any XOR stream cipher, this construction does not protect message integrity, and in fact is highly malleable.  To protect against active attacker, you need to combine the encryption scheme with a message authentication code.  Fortunately, you already have one available, namely HMAC.  So just run the XORed ciphertext through HMAC again (preferably with a separate key derived from the master key), append the result to the message, and verify it before decryption, and you're all set.

Indeed, if you really cannot access the underlying HMAC function, even PBKDF2 itself (being really just a thin wrapper around HMAC) could be used as a MAC, by passing the message to be authenticated as the salt parameter and requesting one hash block of output.  While this won't quite produce the same output as raw HMAC (since, even with the iteration count set to 1, PBKDF2 still appends the block counter to the salt), the security proof carries over trivially.

If you wanted to get fancy, you could even use HMAC (or PBKDF2) in the SIV construction as both the MAC / nonce generator and as the encryption primitive.  So, as perverse as it may seem, the following pseudocode should implement a secure misuse-resistant AEAD scheme using nothing but PBKDF2:

// a variable-length PRF, implemented using PBKDF2 with an iteration count of 1
function prf(key, data, len):
    return PBKDF2(key, data, 1, len)

// SIV authenticator / IV length in bytes (32 bytes = 256 bits)
constant token_size = 32

// internal MAC output length, may be larger than token_size
constant internal_mac_size = max(token_size, PBKDF2_hash_block_size)

function SIV_PBKDF2_encrypt(key, plaintext, assoc_data, nonce):
    macP = prf(key, "macP" + plaintext, internal_mac_size)
    macA = prf(key, "macA" + assoc_data, internal_mac_size)
    token = prf(key, "auth" + macP + macA + nonce, token_size)
    ciphertext = plaintext XOR prf(key, "encr" + token, length(plaintext))
    return (token, ciphertext)

function SIV_PBKDF2_decrypt(key, token, ciphertext, assoc_data, nonce):
    plaintext = ciphertext XOR prf(key, "encr" + token, length(ciphertext))
    macP = prf(key, "macP" + plaintext, internal_mac_size)
    macA = prf(key, "macA" + assoc_data, internal_mac_size)
    if token != prf(key, "auth" + macP + macA + nonce, token_size):
        return ERROR
    else:
        return plaintext

In the code above, all variables are assumed to be byte strings of arbitrary length, and may contain null bytes.  The + operator always denotes string concatenation.  Note that the length of the left argument to + above is always fixed, making the concatenated result unambiguous.

The ERROR constant stands for some unambiguous indication of decryption failure, possibly due to malicious input; instead of a special return value, one could also e.g. throw an exception in that case.  The important things is that, however it is implemented, such a failure should not reveal anything about the invalid plaintext string to the caller, as the content of that string may be manipulated by an attacker.

If a distinct nonce is provided for every encrypted message, this code should implement (modulo any possible implementation bugs) an IND-CCA secure authenticated encryption scheme.  Even if the nonce is repeated or omitted, it should still implement a "deterministic authenticated encryption" scheme, in the sense of Rogaway and Shrimpton, essentially meaning that the only information it leaks (besides message length, which all arbitrary-length encryption schemes reveal to some extent) is whether two encrypted messages are identical or not.

The length of the key input is arbitrary, but should be sufficient to resist brute-force guessing attacks (i.e. at least 128 bits, preferably more).  It should not be a user-supplied password — you'll want to run those through PBKDF2 (or some other password-based KDF) with a high iteration count first.

As an optimization, the internal macA variable may be precomputed if the associated data is known in advance; other similar optimizations, as in Rogaway's original SIV scheme, are also possible.

*) Technically, the output length of PBKDF2 is limited to $2^{32}-1$ times the output length of the underlying PRF / hash.

**) Assuming that one cannot or will not switch to a more modern password-based KDF, such as scrypt, Argon2, Catena or Balloon hashing.  Unlike PBKDF2, all of these KDFs are designed to also consume large amounts of memory, which makes them more resistant to massively parallel brute force attacks using GPUs, FPGAs or ASICs.  As a side effect, they also intrinsically support efficient generation of large amounts of output key material.


Practicality of codebook in current-day secret communications

I believe the possible advantages of the principles behind a codebook are:

Can be memorized by humans.
Can be used in normal speech (e.g. over the phone/radio/in normal conversation) or in text (e.g. in a newspaper)
The data is compressed: it can replace longer phrases or concepts with shorter ones.
Plausible deniability: It's possible to deny any code exists at all.
As long as a specific code is only used once and the codebook is kept secret, it's perfectly secure.

So some uses would be for:

Military operations (e.g. "Execute Plan A" would be meaningless to enemies and also allows faster execution of the plan than having to detail it)
Communication to people with no high-tech equipment, e.g. resistance groups with only access to radios/tv.
Groups of people who want to stay anonymous referring to each other by a nickname.
Criminal organizations who do not want to be openly on record talking e.g. about drugs or plans.


Is it secure to transmit a short plaintext with its MAC?

A normal security notion for MAC's is that of unforgeability. So given some set of message,tag pairs $(m_0,t_0),\ldots,(m_k,t_k)$ is should be hard to create a tag for a new message not among the $\{m_0,\ldots,m_k\}$, stated informally.

In your case, you could just use $E_k(m_0)$ with the secret MAC key $k$ ($H_0$ in your notation); no need for the extra XOR (it does nothing for security; you know $m_0$ anyway, so we might as well use $E_k(m_0)$). This is just a standard use of a keyed random function (which we will suppose a block cipher is) as a MAC for short messages. It's construction 4.5 on page 117 in Katz and Lindell (second edition) book "an introduction to modern cryptography", which also has the (short) security proof for this construction for the above notion of security.

You do realise that your construction does allow for replay attacks, I suppose?


Knowing you can combine 2 signatures, Is it possible to remove part of the signature?

As soon as you are working using standard textbook RSA without padding (or hashing), you can fully exploit the malleability of the RSA cipher.

So, let's say you have a message $m$ which is equal to $a\cdot b$, for $a,b$ two values you know. If you can get the signer to sign both $a$ and $b$, you can compute the value of the signature of $m$, thanks to that malleability:
$$m^d = (a\cdot b)^d = a^db^d \mod N$$

Now regarding the possibility to "cancel out a factor" thanks to this malleability, it is partly possible and is actually used in the so-called "blind RSA signatures". (Read it, it explains all the maths.)
However it requires to be able to get the signer to sign a specially crafted message.


Can you explain partial private key extract algorithm in certificateless Public key cryptography?

I still got the impression that you did not really have read my answer to a related question.

But still, I try to briefly answer your questions here. First of all, private key extraction essentially means private key generation. Extraction, because the partial private key ($D_A$) is generated with repsect to an identity string $ID_A$ uniquely identifying the user $A$ (and thus it may be viewed as extracting the private key from the string).

  Why is there a need for a "partial private key extract algorithm"?

Because the certificateless-approach is in the middle between traditional public key crypto (key pairs are generated by the users themselves) and identity based cryptography (private keys are generated for the users by a trusted authority - this is necessary, since public keys are identity strings and otherwise everybody could generate private keys for any public key - and this would be quite bad).

Consequently, in public key crypto, public keys need to be certified by another party and in identity based crypto they do not need to be certified, since a user has to prove the identity to the trusted authority before the private key is generated.

In certificateless cryptography a part of the user private key is generated by a trusted authority (partial private key extraction) and the other part is computed by the user locally.

  Why should it be needed when calculating "user's private keys by user"?

It is needed since users do not compute their entire private keys on their own. Then, they would need to certify their respective public keys (who will certify that they are indeed who they are pretending to be in certificateless crypto?). So a partial private key is issued to users after identity verification by the trusted authority. The remainder of their private key is chosen on their own and used to compute the public key (without requiring to certify it).

  Is "partial private key extract algorithm" further used in other algorithms?

No, this is only used for key generation (of the partial private keys of users).

Summary:

It is important to understand that in certificateless encryption, a message is encrypted with respect to the user's identity ($ID_A$ - which is used for by the trusted authority to generate the partial private key) and the public key $P_A$ (this one does not need to be certified). The ciphertext can then be decrypted using the knowledge of the partial private key $D_A$ and the second part of the private key $x_A$ only known to the user.

Someone that encrypts a message with respect to $ID_A$ and $P_A$ can be sure that only the owner of the private key corresponidng to $ID_A$ can decrypt (this is the only user who will get issued the partial private key after identity verification at the trusted authority) and without the requirement that $P_A$ needs to be authentic (thats the idea).

Sorry, if there are many repetitions in the answer, but I tried to make the essential poits as clear as possible ;)


Zero-Knowledge Proof of honest function execution - Is this possible?

I am not totally clear on what the procedure for actually "buying" something in your protocol should be, but I'd point out that a (totally) fair exchange between Alice and Bob is impossible.
This follows from the fact that no 2 party secure computation protocol can achieve fairness (impossibility result). In a nutshell: When Alice and Bob run a protocol to exchange some secrets, then one party can always abort as soon as it gets its result without letting the other party know their secret.
As pointed out by Yehuda Lindell in the comments this is not true for all functionalities, see link in the comments.

Lets focus on how Bob can convince Alice that he has some secret $x$ that fulfills some predicate $f$.

In the case of arbitrary predicates $f$, like "I know a pre-image to a specific SHA-1 output", you can use something called zero knowledge using garbled circuits. This approach first appeared in the following paper: zero knowledge using garbled circuits.
The high level idea is to use so called garbled circuits that are, in general, used for secure two party computation (which your problems is a special case of).
For your setting, Alice is the verifier and Bob the prover.
The protocol proceeds as follows:

Alice garbles a circuit representing the prediate $f$ and sends this circuit to Bob (note Alice has no input to that circuit).
Bob uses oblivious transfer to retrieve the wire input labels to the circuit that correspond to his input $x$.
Bob evaluates the circuit and commits to his output wire(s)
Alice "opens" the garbled circuit she sent in step 1 to convince Bob that she did not cheat by garbling some malicious circuit
Once Bob is convinced everything was Ok, he opens his commitment.

On a high level Bob cannot cheat because the only thing he is doing is retrieving some input wire labels, and running them through the circuit.

This may sound like a terribly slow approach, but it is actually not that bad and it strongly depends on what you want to do with it.

Garbled circuits, where only one party has an input are more efficient then the general garbled circuits (see Two halves make a whole in the "privacy-free garbling" section).

Another fairly efficient protocol was recently proposed ZKBoo. This protocol also does something similar to using garbled circuits. However, they focus on reducing the computational costs, but slightly increase the bandwidth overhead, which is already the bottleneck in all garbled circuit approaches.

For less general predicates there may be more direct and more efficient solutions.

Update/Answer to comment:

Whether garbled circuits are practical for "complex" predicates very much depends on how well you can represent them as a computation of a boolean circuit. As a rule of thumb, if you have lots of array accesses, e.g. binary search, then circuits are probably not your best option. There are protocols for general secure ram computation (that's where you have array accesses) and even tailored protocols for zero knowledge proofs using secure ram computation (see Efficient Zero-Knowledge Proofs of Non-Algebraic Statements with
Sublinear Amortized Cost). I don't know how efficient this would actually be in practice, but if you want to play around with this, then you should maybe check out the obliv-c library (https://github.com/samee/obliv-c). Even though their protols are not specifically tailored to the zero knowledge setting, it's easy to use and I think the implementation of their oram extension described in the following recent paper Revisiting Square-Root ORAM is also available on their github page.

Regarding your concrete example of a spell checker you should look at a concrete algorithm and then just take the stuff I wrote above into account.


Where can I find test vectors for the PRESENT cipher with a 128-bit key?

The test vectors for PRESENT cipher 128 bit key size are:

$$
\begin{array}{c|c}
\def\tabentry#1 {{\scriptstyle\mathtt{#1 }}}
K & P & C  \\
\hline
\tabentry 0x00000000000000000000000000000000 & \tabentry 0x0000000000000000 & \tabentry 0x96db702a2e6900af \\
\tabentry 0xffffffffffffffffffffffffffffffff & \tabentry 0x0000000000000000 & \tabentry 0x13238c710272a5d8 \\
\tabentry 0x00000000000000000000000000000000 & \tabentry 0xffffffffffffffff & \tabentry0x3c6019e5e5edd563 \\
\tabentry0xffffffffffffffffffffffffffffffff & \tabentry0xffffffffffffffff & \tabentry0x628d9fbd4218e5b4 \\
\end{array}
$$

The intermediate values of 0xffffffffffffffffffffffffffffffff key schedule are:

\begin{align*}
\def\keysched#1:#2 {#1&:\mathtt{0x#2}}
\keysched 0:ffffffffffffffff \\
\keysched 1:22ffffffffffffff \\
\keysched 2:2dffffffffffffff \\
\keysched 3:148bffffffffffff \\
\keysched 4:19b7fffffffffffe \\
\keysched 5:74522ffffffffffe \\
\keysched 6:7966dffffffffffe \\
\keysched 7:47d148bffffffffe \\
\keysched 8:40e59b7ffffffffd \\
\keysched 9:871f4522fffffffd \\
\keysched 10:8003966dfffffffd \\
\keysched 11:f11c7d148bfffffd \\
\keysched 12:fa000e59b7fffffc \\
\keysched 13:e2c471f4522ffffc \\
\keysched 14:ede8003966dffffc \\
\keysched 15:328b11c7d148bffc \\
\keysched 16:3db7a000e59b7ffb \\
\keysched 17:d4ca2c471f4522fb \\
\keysched 18:d9f6de8003966dfb \\
\keysched 19:a25328b11c7d148f \\
\keysched 20:1d67db7a000e59b2 \\
\keysched 21:01894ca2c471f457 \\
\keysched 22:14759f6de8003963 \\
\keysched 23:a30625328b11c7d4 \\
\keysched 24:ec51d67db7a000e3 \\
\keysched 25:d68c1894ca2c4719 \\
\keysched 26:6bb14759f6de8005 \\
\keysched 27:fb5a30625328b11a \\
\keysched 28:00aec51d67db7a07 \\
\keysched 29:1bed68c1894ca2c3 \\
\keysched 30:a902bb14759f6def \\
\keysched 31:2c6fb5a30625328c \\
\end{align*}


Why IV does not have to be secret yet has to be random

OK! This won't be the best answer I can give, but since I know a fair bit about this subject, CSPRNGs (Cryptographically Secure Pseudo-Random Number Generators), also known as Dertemistic Random Bit Generators (DRBGs).

Now your question asked about CBC, so I'll come onto that second, first I want to give a slightly less technical/broad answer, I'll give you an example of where the importance of IVs are crucial.

Let's assume we had a STREAM CIPHER (asin RC4, which is in itself full of problems, but that's not what you asked). In WEP, RC4 was using IVs extremely badly, but let's assume there's a bunch of alterations you can make to RC4 to make it significantly stronger (albeit, less elegant).

In this circumstance, because we have a stream cipher, the vulnrability to plain-text-attacks is very high, that's because if we use the same key more than once, then the relationship between any two texts using that same key is known , this means that if we can guess the plain text, this is often the case in practical everyday transmissions, then firstly we know EXACTLY what the key stream is and from there, finding out the initial key is pretty trivial.

So we NEVER want to use the same key twice for any encryption... Block Ciphers, Stream Ciphers, whatever.

OK So an IV can be used in many ways, the reason I bought up WEP was say you were using a 64-bit key, then to make sure no two "keys" were the same, the IV would act like a nonce, that is, the effective key used for key-scheduling would be (IV|Secret), now as I said, this particular implementation was awful but here's the point.

WE NEVER EVER WANT TO HAVE THE SAME KEY TWICE... There's plenty of ways of achieving this.

Now in WEP implementation of RC4, using (IV|Secret) as the initial key where "Secret" is 40 bits and "IV" is 24 bits, this means there's only 2^64 possible keys, however more importantly if we use the same "secret", then there's only 2^24 (16,777,216) different keys you can create from the same secret... since the 40 bit key is just 5 random bytes chosen or derived from the user. 16,777,216 is a laughably small number and infact, we will find two instances of (IV|Secret) that match half the time inside about 4300 key-streams, providing the "secret" doesn't change. So that was one example of using an IV failing spectacularly.

So if we imagine that our key for any encryption is HMAC-SHA256(IV,Secret), then we can afford for the IV to be the same size as the Secret, as there will be 2^128, that is over 3 * 10^38 and there will also be this many possible IVs, so even if we KNOW the IV and it's being used more or less as a nonce, although HMAC-HASH(IV,Secret) is better than simply using HASH(IV|Secret)... once we have done this, we can PUBLICLY REVEAL what the IV was. Presuming we use a good CSPRNG and a good HASH function, then to attempt a known-plain-text-attack, we would not take a single guess and reveal a fair amount of info, instead we would have to use over 3*10^38 guesses.

This isn't ideal but the point is.... the IV does not to be secret because the IV is there to make sure realistically known-plain-text attacks are significantly more complicated... in my example it becomes 2^128 times more complex to launch a known-plain-text attack OR partially-known-plain-text attack.

In a nutshell one of the primary functions of IVs is to make sure no two encryptions are the same or at very least, finding two the same is exponentially more difficult.

If you want more clarity, just ask. This isn't exactly a well written essay, but I thought I'd have a crack at shedding some light on this question. If needed, I could write a much more technical answer.


If you take a look at the Password Hashing Competiton, you can see, that most of the schemes use Blake2b, some of them uses SHA-512, none of them uses SHA-256.

Blake2b is optimized for 64-bit platforms and this property fits exactly the requirement of a password hashing scheme. SHA-512 would also be OK, but SHA-256 would be much slower in software and the due to the fact, that SHA-256 is used for Bitcoin mining, custom hardware for SHA-256 is very cheap – this is exactly, what we do not want for a password hashing scheme.

I do not recommand to substitute any part of Argon2. All cryptoanalysis refer to the original version. Argon2 is – unlike Catena (another scheme from the password hashing competition) – not a flexible framework, that has been designed to be used with variable algorithms.
Argon2 uses not only the Blake2b function, but also something like a reduced version of Blake2b, the compression function G. You could possibly replace Blake2b by SHA-256, but you can‘t replace easily the reduced version, because Blake2b uses fewer rounds than SHA-256.


CSIDH: Why do we need ideals in the form of $\langle \ell, \pi \pm 1 \rangle$ in order to apply Vélu's formulas when computing the action?

You are right that Vélu's formulas also work for any extension field, but then they require arithmetic in that field.
Doing computations in $\mathbb F_p$ is simply much more efficient than in extension fields.

Generally, for a "random" ideal of prime norm $\ell$, you can only expect the corresponding points to be defined over $\mathbb F_{p^k}$ for some $k\in\mathcal O(\ell)$, hence if CSIDH didn't have those rational points, one would have to compute in extension fields of degrees of a few hundred.

(In fact, the earlier variants¹ of CSIDH were, among other techniques, using subgroups that are not necessarily rational, because it seems hard to find an ordinary curve with many "good" subgroups. The core observation in CSIDH is that switching to supersingular curves makes this trivial, simply by picking the prime $p$ of a special form!)

¹ Couveignes, Rostovtsev–Stolbunov, De Feo–Kieffer–Smith


Adaptive vs. Static security model in ABE

Towards Q1 -- immediately should just mean that the adversary has no more information as the public parameters (so it doesn't have to be "few seconds" but. "without any intermediate messages")

Towards Q2 -- assume you have some system with a weakness like the following: If you get to send an valid encryption to the challenger, the challenger responds with the master key. You won't be able to exploit that in the static model (with overwhelming probability) but in the adaptive case it's easy


Determining interval(s) containing the smallest prime $p$ of an RSA modulus?

Any such nontrivial intervals would be entirely up to the implementation generating the RSA key.  For example, when generating a 2048 bit RSA key, an implementation could generate a 512 bit $p$ and a 1536 bit $q$; such a modulus would work just as well in RSA as any other modulus; this gives us an $a \approx 2^{512}$.

However, while an implementation could do that, they never do; instead, they generally aim to keep $p$ and $q$ balanced; one advantage this has is that it allows the maximum speed-up by the CRT algorithm.

I've seen two different strategies in common use; if we assume $n$ is even, then to generate an $n$-bit RSA modulus, we often either:

Generate two random $n/2$ bit primes with the two high bits set (which ensures that, when $p$ and $q$ are multiplied together, yield a $n$-bit modulus, and not an $n-1$ bit.
Generate two random primes both from the range $(2^{(n-1)/2}, 2^{n/2})$, which yields the same effect, albeit in a slightly more mathematical way.

With the first strategy, we have $\sqrt{3/4}\sqrt{n} < p < \sqrt{n}$; in the second strategy, we have $\sqrt[4]{1/2}\sqrt{n} < p < \sqrt{n}$ (a slightly wider interval).

As I mentioned earlier, there's no requirement that any specific RSA implementation uses either strategy (unless they claim FIPS compliance; FIPS insists on the second strategy).

In addition, you appear to be interested in this to help in searching for factors of RSA modulii; for any RSA modulii that's even slightly secure, the interval is far too wide to make any such simple-minded search for factors feasible.


The "seed" code is known (via $G$) to everyone including the attacker, but the actual code used is unknown. The seed code coordinates are permuted on the right ($P$) after an invertible transformation $S$ applied on the left, forming a trapdoor. $S,P$ are secret. If the permuted generator matrix is $\hat{G}$ we have
$$
\hat{G}=SGP.
$$
If the attacker finds the (unpermuted) generator matrix, then they can just decode as explained in the next paragraph.
If the received ciphertext is $c=c'\oplus e,$ where $e$ is the noise vector added for security, and $c'=m\hat{G},$ the legitimate recipient can do
$$
\hat{c}=cP^{-1},
$$
and can decode $\hat{c}$ to $\hat{m}$ using the standard decoding algorithm for the code. Finally she can compute
$$
m=\hat{m}S^{-1}.
$$
You can check in a routine way this works.
Edit: To clarify where the security comes from, the masking via permutation and matrix multiplication produces an equivalent “pseudorandom” code with similar properties to the original code.
So the equivalent decoding problem looks like a decoding problem for a random code, and since decoding a random code is difficult, the strength resides in the multiplication and permutation, they are trapdoor information available only to the authorized decoder.
Note that the noise added must not be beyond the correction capability of the code. If it was, the legitimate receiver might decode to the wrong codeword even with the trapdoor information or fail to decode to the correct codeword.


Which attacker model is weaker? IND-CPA or OW-CCA?

It is not difficult to build examples to show that the two notions are incomparable, in the sense that there exist schemes that are IND-CPA but not OW-CCA, and there exist schemes that are OW-CCA and not IND-CPA.
For example, take any public-key IND-CPA scheme, and modify it so that ${\sf Enc}_{pk}(sk) = pk$, implying that ${\sf Dec}_{sk}(pk)=sk$. I argue that this scheme is still IND-CPA, since it only reveals $sk$ in the case that a decryption query of $pk$ can be issued. Since there is no decryption oracle, this is safe. However, this is clearly not OW-CCA for any definition, since given a CCA oracle, it is possible to obtain the private key $sk$.
Next, take any OW-CCA scheme with deterministic encryption. (For my answer to be complete, I need to argue that such a scheme exists, but I'll leave that to you.) It is clear that this scheme is not IND-CPA since if you encrypt the same message twice, you get the same ciphertext.


When is a cryptosystem or its algorithm (like RSA) considered efficient?

From a theoretical perspective in cryptography, a cryptosystem is efficient when the execution time of the algorithm run by the legitimate user grows as a polynomial of a security parameter $k$, while the execution time for the best algorithm an adversary can run to break the system grows faster than any polynomial of $k$ (some change that to: exponentially with $k$, thus giving a different, less common definition).

This definition does not require to specify what $k$ is, and it's readily proven that changing $k$ to a polynomial in $k$ does not change the outcome of the above test. But often, $k$ is the size of something in bit, like the key, or the signature. In symmetric crypto, it is typically the size of the secret key.

From a practical perspective, the line is not clear. Make it: whatever is acceptable in the context.


Prove there is PRG that is not necessarily one-to-one

Suppose $F \colon \lbrace 0,1 \rbrace^n \to \lbrace 0,1 \rbrace^{\ell(n)}$ is a secure PRG. Create $G \colon \lbrace 0,1 \rbrace^{n+1} \to \lbrace 0,1 \rbrace^{\ell(n)}$ as follows:

$$G(b ||s) := F(s), \quad b \in \lbrace 0,1 \rbrace, s \in \lbrace 0,1 \rbrace^n.$$

$G$ is as secure as $F$, and clearly $G(0||s) = G(1 || s)$.

To prove the "$G$ is as secure as $F$" part, consider the following proposition$^*$:

Proposition. If there exists a distinguisher $\mathcal{D}$ against $G$,
then we can create a distinguisher $\mathcal{D}'$ against $F$, such that
$$| \Pr[\mathcal{D}'(U_{\ell(n)}, 1^n) = 1] - \Pr[\mathcal{D}'(F(U_n), 1^n) = 1]| > \frac{1}{poly(n)}.$$

Proof. Distinguisher $\mathcal{D}'$ receives as input a string $z \in \lbrace 0,1 \rbrace^{\ell(n)}$. Then he simply forwards this string to $\mathcal{D}$ and outputs whatever it outputs. Since $z$ is distributed exactly like in the distinguishing game $\mathcal{D}$ expects, we have in particular $\Pr[\mathcal{D}'(F(U_n), 1^n) = 1] = \Pr[\mathcal{D}'(G(U_{n+1}), 1^n) = 1]$, and the proposition follows. $\blacksquare$

Note that the above proposition is intuitively correct when you realize that the bit $b$ is independent of the output of $G$. That is, one could think of $G$ as first running $F$ on some input $s \in \lbrace 0,1 \rbrace^n$, and afterwards drawing the bit $b$. Clearly, this shouldn't reduce the strength of $F$ as a PRG.
It should probably also be emphasized that $G$ is as secure as $F$, not more secure. That is, if $F$ has a security level of $n$ bits, then $G$ also has a security level of $n$, not $n+1$ as the longer seed could maybe lead you to believe.

$^*$Technically the proposition does not hold for $\ell(n) = n + 1$, since then $G$ wouldn't actually be a PRG. But I have ignored this above, and simply assumed the more typical case of $\ell(n) >> n$.


What's the difference between the long term key and the session keys?

First, understand that keys need to last only as long as you need to recover what they are protecting. If you are storing a secret in a box until next year, you have to keep the key until next year. But if we're talking on the phone, we only have to keep the key for the duration of the phone call.

If Alice and Bob are going to speak securely, they don't need to keep the shared secret key around for a long time.  They only need it for as long as they're speaking.  And they don't want someone who records their conversation to be able to learn what they said.  If they agree on a temporary key, one that lasts only as long as their conversation, that is a session key.

A session key is one that is not intentionally stored, and is not re-creatable.  Session keys are used only for communications protocols, never for storage purposes.  In computer protocols like SSL, the session key is generated randomly, exchanged securely with the other computer (using a key exchange protocol like DH), and remains in each computer's memory only for the duration it is needed (a session.)  When the session is ended, both sides wipe their copies of the key from memory.*

A long-term key is one that is deliberately stored somewhere, either on a computer disk, flash memory, or even printed on paper.  The key is intended to be used at multiple points in time, such as "I will use this key to encrypt this secret file today, and use it again to decrypt my secret next week."  A long term key can be used for any purpose, including stored information as well as transient communications.

* Note that an attacker can certainly record the session key exchange, and if they can break the key exchange cryptography they can decrypt the session key.


how to let other people respond to emails only decrypt-able with my private key

You are looking for Proxy Re-Encryption. From a high-level viewpoint, a proxy re-encryption scheme is an asymmetric encryption scheme that permits a proxy to transform ciphertexts under Alice's public key into ciphertexts decryptable by Bob's secret key. In order to do this, the delegator $A$ gives a special re-encryption key $rk_{A \rightarrow B}$ to the proxy; this key makes the transformation from $A$ to $B$ possible. So, besides defining traditional encryption and decryption functions, a proxy re-encryption scheme also defines a re-encryption function for executing the transformation.

Your example is one of the traditional use cases of proxy re-encryption. See for instance the introduction of this paper from Ateniese et al. In this case, the manager $A$ creates a re-encryption key $rk_{A \rightarrow B}$  for her secretary $B$, and handles this re-encryption key to the email server. The server simply has to re-encrypt all encrypted emails under the public key of $A$ to encrypted emails under the public key of $B$.

Udpate: For the sake of clarity, I provide here an example of Proxy Re-Encryption scheme. The following is one of the simplest schemes, proposed by Blaze, Bleumer and Strauss in 1998. It is based on the ElGamal encryption scheme. Besides to the usual primitives for key generation, encryption and decryption, the scheme has a re-encryption key generation function and a re-encryption function:

$KeyGen() = (pk = g^x, sk = x)$, for random $x$.

$Enc(pk = g^x,m) = (pk^r, m\cdot g^r) = (g^{xr}, m\cdot g^r)$, for random $r$

$Dec(sk = x, c = (c_1, c_2)) = c_2 / c_1^\frac{1}{sk}$

$ReKeyGen(sk_1 = x, sk_2 = y ) = sk_2 / sk_1 = y / x$

$ReEnc(rk = y/x, c = (c_1, c_2)) = (c_1^{rk}, c_2) = (g^{yr}, m\cdot g^r)$

Note that this scheme is what the proxy re-encryption literature calls "interactive", that is, the re-encryption key generation needs both secret keys as inputs. This is an undesired property, but I preferred to show this scheme because of its simplicity. There are however plenty of non-interactive proxy re-encryption schemes (the re-encryption key is generated from the secret key of the delegator and the public key of the delegatee) such as the ones from Ateniese et al. (see link above).


The Bit Flipping attack
Decryption process in CBC mode is performed as
\begin{align}
P_1 =& Dec_k(C_1) \oplus IV\\
P_i =& Dec_k(C_i) \oplus C_{i-1},\;\; 1 < i \leq nb,
\end{align}
where $nb$ is the number of blocks.
If you know the position of the target byte, then you can modify the corresponding ciphertext position in the previous ciphertext block. For example; if you modify a byte in the ciphertext $C_{i-1}$, then $P_i$ will be changed by one block since $C_{i-1}$ only affects the plaintext $P_i$ by $\oplus$. We can see visually in the below figure;

$\color{red}{\textbf{Red case:}}$ A ciphertext byte of $C_2$ modified. This affects the corresponding byte in the next plaintext block $P_3$ and the corresponding full plaintext block $P_2$ which has the same index as the modified ciphertext which is garbage. This can be seen as there is an error.
$\color{ForestGreen}{\textbf{Green case:}}$ an $\text{IV}$ byte is modified (green), this affects only the corresponding byte in the first plaintext $P_1$. If the target plaintext is in the first block, this will not leave a trace.
An example
Consider this simple message
msg = "Buy 1000 lots of waffles"
Now the attacker intercepts the message and now the default structure and want to modify it into
msg = "Buy 5000 lots of waffles"
Here is the sample Python code ( the full code is here );
def bitFlip( pos, bit, data):
    raw = b64decode(data)

    list1 = list(raw)
    list1[pos] = chr(ord(list1[pos])^bit)
    raw = ''.join(list1)
    return b64encode(raw)

With a call ctx = bitFlip(4,4,ctx) changes the 1 into 5.
This is the green case attack, that leaves no garbage block. Some file formats, like PDF, can live with the red case attack.
A Little Theory
CBC mode for encryption can only provide Ind-CPA security. CPA security doesn't resist active attacks, like CCA (See this post Ind- notions for details). Therefore an active attacker can modify the pure CBC ciphertext on their behalf. If the message format is known, this can cause devastating effects especially if the important part is in the first block.
The Mitigation
The attack is possible since there is no integrity and authentication on the data. A MAC or an HMAC can be used to prevent this like AES-CBC-HMAC if the CBC mode is a must to use.
In other cases, it is better to use modern encryption schemes. The authenticated encryption with Associated Data (AEAD) which provides confidentiality, integrity, and authenticity. The examples are AES-GCM and ChaCha20-Poly1305. In TLS 1.3., CCM,GCM, and poly1305 are standardized authenticated encryption modes.
There are alternatives to the above like AES-GCM-SIV which is designed to resist the (nonce,key) pair resue problem of the CTR based encryptions ( all of TLS 1.3 has) and xChaha20-Poly1305 that uses 192-bit nonces to reduce the chance of collision into very low probability.


How to attack Merkle-Hellman cryptosystem if the first element in the superincreasing series is too small?

Let's begin with a short description of the Merkle-Hellman knapsack scheme. The private key is a superincreasing sequence of $n$ elements $b_1, b_2, \dots, b_n$, along with a secret element $W$ and $N$, with $W$ invertible modulo $N$. A superincreasing sequence is a sequence in which every element is greater than the sum of its predecessors:
$$
b_i > \sum_{j=1}^{i-1} b_j \,.
$$

The public key is the vector $a_1, a_2, \dots, a_n$, where $a_i = W b_i \bmod N$. To encrypt a message, the sender splits the message into individual bits $m_i$, and calculates the encrypted message to be
$$
c = \sum_{i=1}^n m_i a_i \equiv \sum_{i=1}^n m_i b_i W \,.
$$

Decryption begins by multiplying $c$ by $W^{-1}$ modulo $N$, cancelling out the contribution of $W$, and then solving the subset sum for the known superincreasing sequence.

We can break the scheme by recovering either $W$ or $N$. The following simple attack is described in Galbraith's book. Suppose $b_1$ is small—much smaller than $2^n$. Then it is likely that $b_2$ is also similarly small, and we have the interesting property:
$$
\begin{align*}
  a_1b_2 &\equiv a_2b_1 \pmod{N} \\
  Wb_1b_2 &\equiv W b_2 b_1 \pmod{N}\,,
\end{align*}
$$
and therefore $a_1b_2 - a_2b_1$ is guaranteed to be a small multiple of $N$. By bruteforcing $b_1$ and $b_2$, we can recover a short list of candidate $N$, which we can then confirm by trying to recover $W = a_1/b_1 \pmod {N}$ and verify if this $W$ applies to the other $a_i, b_i$ as well. This suggests that $b_i$ should be at least $2^{n/2}$ in size.

This is not the only attack when $b_1$ is small. Odlyzko described another two, including the famous Shamir attack. There are also very relevant lattice attacks on Merkle-Hellman, but those are already seem to be described in Hoffstein et al.


There's no way to verify the strength of a cipher in any automated way, especially given only the ciphertext. Attacking the construction of a cipher is an inherantly intellectual process, which does not fit well to the qualities of computer analysis.

For example, I could write a cipher such that $f(m) = rand(0,n)$ where $n$ is the largest integer representable in $sizeof(m)*8$ bits, and any automated analysis would say "this is an awesome cipher", but a human would immediately realise that it's totally useless.

If you're writing your own ciphers for real usage, I have only one piece of advice: don't.

Creating your own ciphers is fun, and it can give you a learning experience if you're actually doing it based on constructions you understand, but the resulting cipher should never ever go anywhere near a production system. Experts put their ciphers through years (decades, even) of peer review before they're adopted by anyone. If your goal is to learn, do so by breaking ciphers.


Use $5^6\pmod 7 =1,$ to re-express negative powers of $5$ with exponents in $\{0,1,\cdots,5\}.$ This works since $5$ is a generator of the multiplicative group of $GF(7).$


What is the post-quantum cryptography alternative to Diffie-Hellman?

Answering myself...

There is now a very analogous alternative to Diffie-Hellman in post-quantum cryptography: Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies

The research paper is very new, but if the results turn out to be secure, this is a very competitive key agreement scheme for post-quantum cryptography.


How does the Blowfish algorithm key initialization work

The quoted passage of the Wikipedia article is wrong does not at first reading seem to match Blowfish as in Bruce Schneier's Description of a new variable-length key, 64-bit block cipher (Blowfish) (in proceedings of the first FSE conference, held Dec. 1993) which for this same operation reads:

  XOR P1 with the first 32 bits of the key, XOR P2 with the second 32-bits of the key, and so on for all bits of the key (possibly up to P14). Repeatedly cycle through the key bits until the entire P-array has been XORed with key bits. (For every short key, there is at least one equivalent longer key; for example, if A is a 64-bit key, then AA, AAA, etc., are equivalent keys.)

In C++, if P and key are arrays of 32-bit words, and keylen (from 1 to 14) is the key size in 32-bit increments, this can be implemented as shown in the wikipedia article:

for (int i=0 ; i<18 ; ++i)
   P[i] ^= key[i % keylen];

Customarily conversion of key bytes to the array key, and constants for initialization of P, is big-endian (as traditional in cryptography for many things such as DES, RSA, SHA, AES, but not MD5).

Many actual implementations of Blowfish accept keys with size any multiple of 8-bit, and there's nothing in Bruce Schneier's description to forbid that. To cover this, if P is an array of 32-bit words, key is an array of 8-bit bytes, and keylen is the key size (from 4 to 56) in 8-bit increments, the loop can become, on an big endian machine:

for (int i=0 ; i<72; ++i)
   ((uint8_t*)P)[i] ^= key[i % keylen];

or, to keep the code endian-neutral:

for (unsigned i=0 ; i<72; ++i)
   P[i>>2] ^= ((uint32_t)key[i % keylen])<<((3&~i)<<3);

Note: the shift count computed as (3&~i)<<3 is 24, 16, 8, 0, 24, 16, 8, 0, 24.. when i is 0, 1, 2, 3, 4, 5, 6, 7, 8..

Note: while Blowfish's definition states a minimum key size of 32 bits, some implementations lower that to 8 bits, including the one that was used for these test vectors of Blowfish with variable key length (also available as a C header). Further, some implementations (especially of Blowfish as used in Bcrypt) allow up to 576-bit keys (72 bytes), rather than 448-bit (56 bytes).

Example 1: if the key is the string abcd in ASCII, the array key (viewed as a 32-bit array) is the single element 0x61626364; thus after processing the key,
P[ 0] is 0x243F6A88^0x61626364 that is 0x455D09EC,
P[ 1] is 0x85A308D3^0x61626364 that is 0xE4C16BB7,..
P[17] is 0x8979FB1B^0x61626364 that is 0xE81B987F.

Example 2: if the key is the string abcdJKL in ASCII, after processing the key,
P[ 0] is 0x243F6A88^0x61626364 that is 0x455D09EC,
P[ 1] is 0x85A308D3^0x4A4B4C61 that is 0xCFE844B2,..
P[17] is 0x8979FB1B^0x4B4C6162 that is 0xC2359A79.

Note: there are further transformations of P but they are rather unambiguous; refer to either of the articles.

Final Caution: some Blowfish implementations (especially those used in Bcrypt) are known to vary in how they convert text to bytes before applying the above transformation of key to P; some bugs have even crept there, for example

  Versions of jBCrypt before 0.3 suffered from a bug related to character encoding that substantially reduced the entropy of hashed passwords containing non US-ASCII characters. An incorrect encoding step transparently replaced such characters by ? prior to hashing. In the worst case of a password consisting solely of non-US-ASCII characters, this would cause its hash to be equivalent to all other such passwords of the same length.

Notice that if "of the same length" is necessary in this quotation, then some length, padding or terminating character must have been included in the key converted to bytes (otherwise all passwords consisting solely of non-US-ASCII characters would have been equivalent, regardless of length).


How does AES/CTR/PKCS5Padding works when the bits to encrypt is more than 8 bits

PKCS#5 was initially written for block ciphers using 64-bit blocks, and up to and including PKCS#5v2.0 had no provision for larger ones. PKCS#5v2.1 remains littered with references to eight octets, including in padding.

The principle that PKCS#5 uses for 64-bit blocks padding is easily generalized to block ciphers with larger blocks (up to 255 octets per block), and that's what PKCS#7 padding is: for a message of $m$ octets ($8m$ bits) and a block cipher of $k$ octets ($8k$ bits), pad the message with $p=k-(m\bmod k)$ octets with value $p$. When $k=8$, that's precisely PKCS#5 padding.

AES is a 128-bit (16 octets) block cipher, thus (at least in CBC mode) is not amenable to PKCS#5 padding with 64-bit blocks. For this reason, PKCS#5 was revised and for AES-CBC-Pad PKCS#5v2.1 footnote 2 of section B.2.5 prescribes 128-bit padding, effectively that of PKCS#7.

The question's quote sticks to the 64-bit definition of padding of PKCS#5 before revision 2.1, and makes the simplest possible conjecture when it assumes that AES/CBC/PKCS5Padding really is internally AES/CBC/PKCS7Padding. Otherwise, it would be impossible to process some messages. For example, with 64-bit padding, the 2-octet message 0x41 0x42 would be padded to 8 octets as 0x41 0x42 0x06 0x06 0x06 0x06 0x06 0x06, and that can't be CBC-enciphered with a 16-octet block cipher; the padding used by AES/CBC/PKCS5Padding thus is 0x41 0x42 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E 0x0E. And that's what PKCS#5v2.1 prescribes.

Another plausible conjecture is that AES/CTR/PKCS5Padding uses the same padding as AES/CBC/PKCS5Padding, and is internally AES/CTR/PKCS7Padding; but to be sure, we would need to look at the code or some test data, because CTR mode (contrary to CBC mode) does not require padding to block boundaries, and AES-CTR would also be compatible with no padding at all, or with strict PKCS#5 padding. According to this source, this varies across implementations, and it looks like the Sun Oracle Java official stance is that AES/CTR/PKCS5Padding is not supported, should raise an exception if used, and does so with few exceptions that are designated as bugs. Such important boring details are arguably off-topic.


This diagram is not accurate.  Hashing is not a separate step outside signing for the convenience of handling long messages; hashing is an integral part of signing that is necessary for security.  And the verification algorithm does not always return a hash that you can compute separately: it only returns a boolean that indicates a valid signature or not.  In particular, signature is not ‘encryption with the private key’, which is a contradiction in terms, and very few signature schemes even resemble that idea.  Here is an accurate diagram:

Note that hashing doesn't figure into this diagram, because it sits inside the signature algorithm and the verification algorithm; the user, who calls the signature algorithm or calls the verification algorithm, is not concerned with the hash function.

How does it work inside?  Let's examine an example of an RSA-based randomized signature scheme, RSA-PSS, which is related to (but better than) the standard RSASSA-PSS algorithm of IEEE P1363-2000 and PKCS#1 v2.1:

There is a hashing step inside, but it is randomized with randomization that is embedded in the signature, so it's not just that we compute $\operatorname{MD5}(m)$—which would make us vulnerable to collisions in MD5!  If we skipped the hashing step, using $s^3 \equiv m \pmod n$ as the verification equation, the signature scheme would be totally insecure, e.g. I could forge 3 as a signature on the message 9—this is why hashing is not a separate step for the convenience of long messages, but actually crucial for something to be a secure signature algorithm at all.

In other signature schemes like Ed25519, there is no hash concealed within the signature that the verifier compares against a recomputed hash: a valid signature under a public key $A$ is a pair $(R, s)$ of a point $R$ and a scalar $s$ such that $[s]B = R + [H(R, A, m)]A$; here we are working in an elliptic curve, namely edwards25519, with standard base point $B$.  The hash $H(R, A, m)$ uses inputs that are embedded in the signature, so like RSA-PSS the hash can't be computed separately without the signature; and then the hash figures into some fancy math that returns a boolean answer $[s]B \stackrel?= R + [H(R, A, m)]A$ directly.


Probability of SHA256 Collisions for Certain Amount of Hashed Values

The wikipedia page for the Birthday problem gives the details, including the exact formula.

As an approximation you can use:

$$p \approx 1-\exp(-\frac{\tfrac{1}{2}n(n-1)}{2^{256}})
\approx 1-\exp\left(-\frac{n^2}{2 \cdot 2^{256}}\right)
\approx 1-\exp\left(-\tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2\right)$$

If $n \ll 2^{256/2}$ and thus $p \ll 1$ you can use the approximation $\exp(x) \approx 1+x$ and obtain:

$$p \approx \tfrac{1}{2} \left(\frac{n}{2^{128}}\right)^2$$

This means that the probability is negligible as long as you have significantly less that $2^{128}$ values. (For an idea of "how significantly" less, refer to the table on the Wikipedia page, "Desired probability of random collision".) That's the case for any realistic amount of data, so an unbroken 256 bit hash is good enough and there is no need to upgrade to 512 bits.


We call an adversary A nonce-respecting if it never repeats a nonce

Source: Nonce-Based Symmetric Encryption

This is defined in the context of the IND-CPA game.


How difficult is it to brute force d in RSA: d = (1/e) mod φ in a CPT attack?

How can I calculate or estimate the difficulty of attacking d when only the public key is known? (no optimizations)

Generate a few hundred pairs $(n,\varphi(n))$ for whatever key size you are interested in, then compute the average distance  between the pairs. That would give you a guess as to how many values on average you will need to get $\varphi(n)$.

Symbolically we get something like $pq-(p-1)(q-1)=pq-pq+p+q-1=p+q-1$ That number has approximately the same number of bits as the larger of $p,q$. So for RSA-2048, we use 1024 bit primes, so the difference will have around 1024 bits. So your work factor would be around $2^{1024}$.

  With the optimizations listed above, and those you may be aware of, what is the difficulty of attacking d?

For all intents and purposes it will be the same. The factors by which these optimizations reduce things are small comparatively (e.g., not trying odd values, you eliminate half of the choices which when talking security bits that is only 1 bit)

  What is a more efficient manner of attacking RSA?

Factoring is the most efficient method known to date. A 768 bit RSA modulus was factored in 2009 using the number field sieve. That is the largest to date.


How to calculate number of possible key pairs in RSA

Well, if we bound the acceptable $e, d$ values to, say, $(0, \phi(n))$ (as I pointed out in the comments, if we don't have such a bound, then the number of such pairs is infinite), then the number of such pairs is:
$$(\gcd( p-1, q-1))^2 \cdot \phi( \lambda( n))$$
Or possibly one less, if you arbitrarily disqualify the $e=d=1$ pair.
It's fairly straight-forward to see that this is true; if we limit the bounds to $(0, \lambda(n))$, then for every $e$ relatively prime to $\lambda(n)$, there is precisely 1 value of $d$ in that range that is a valid pair; and because there are $\phi( \lambda(n))$ such values $e$ which are in that range, that means that there are that many valid pairs in that range.
However, we specified a larger range $(0, \phi(n))$; it turns out that for all valid pairs $(e, d)$ in the original range, all pairs of the form $(e + a\lambda(n), d + b\lambda(n))$ (for integer $a, b$) are also valid (and for any valid pair, there is a unique representation $(e, d, a, b)$ tuple (with $e, d$ being a valid pair in the $(0, \lambda(n))$ range)).
With that in mind, we can see that, for any $e$, there are exactly $\gcd(p-1,q-1)$ values $a$ for which $e + a \lambda(n)$ is in the range $(0, \phi(n))$, and similarly there are $\gcd(p-1,q-1)$ values $b$ for which $d + b \lambda(n)$ is in the range $(0, \phi(n))$; hence for any $(e, d)$ pair in the smaller range, there are $(\gcd(p-1,q-1))^2$ such pairs; because we have already seen there are $\phi(\lambda(n))$ such pairs in the smaller range, this gives us the formula for the bigger range.


How is the Lai-Massey scheme invertible?

One Lai-Massey round can be described as
$$
\begin{align}
L' &= \sigma(L \oplus F_k(L \oplus R)) \\
R' &= R \oplus F_k(L \oplus R)\,,
\end{align}
$$
where $F_k$ is some round function—not necessarily invertible—and $\sigma(\cdot)$ is an orthomorphism, an arbitrary function such that both $\sigma(x)$ and $\sigma'(x) = \sigma(x) \oplus x$ are invertible.

To invert this,
$$
\begin{align}
L &= \sigma^{-1}(L') \oplus F_k(\sigma^{-1}(L') \oplus R') \\
R &= R' \oplus F_k(\sigma^{-1}(L') \oplus R')\,.
\end{align}
$$
We can see this works because
$$
\begin{align}
\sigma^{-1}(L') &=
L \oplus F_k(L \oplus R)\,,
\end{align}
$$
and
$$
\begin{align}
\sigma^{-1}(L') \oplus R' &=
L \oplus F_k(L \oplus R) \oplus R \oplus F_k(L \oplus R) \\
&= L \oplus R\,.
\end{align}
$$


Why in Android kernel CSPRNG state is saved?

If we not save the state, is it insecure?

Yes, for an answer read on:

  Isn't this saving the state making it predictable.

Yes. If an attacker manages to get access to the /data/system/entropy.dat file shortly after the kernel has loaded, he will have good knowledge of the internal CSPRNG state, could predict the random data and do nasty things.

On the other hand, if an attacker already has that high access rights to the machine predicting the CSPRNG is the least of your problems. He could just as well fool applications by providing it's own /dev/urandom device that generates pseudo random data. In that case he has perfect knowledge.

In case that the attacker does not have access rights to access the entropy file it is safe.

  Also, why the kernel CSPRNG will be in a predictable state after starting?

In an embedded device like an android phone, there aren't many things that generate entropy data. There is for example no hard-drive that you can use as an entropy source by measuring seek and access times. Right after start-up there are also few (if any) network connections that you could use as an entropy source.

Entropy gets collected much quicker as soon as the machine gets operated by a human. You can pull data from input devices etc.

This is by the way not only true for embedded devices such as an android phone but for servers that run without operator interaction as well. So you'll see the same thing done on linux servers as well.


Understanding $\varepsilon$-advantage in cryptographically secure deterministic RNG

Took a while to grasp it, but with the help of a friend we came to a conclusion (and it turns out it was rather easy).

Recall that a function $f_n : \{0,1\}^{n} \mapsto \{0,1\}^{m(n)}$ is said to be one-way if for a positive polynomial $poly(\cdot)$, every randomized algorithm running in probabilistic polynomial time inverts $f_n$ with a negligible probability, i.e.  $\Pr[A\:inverting\: f_n] < \frac{1}{poly(n)}$, with $n$ size of the input. This polynomial comes from the fact that for every possible computational path, the algorithm will follow it with a probability $2^{-n}$, which is bounded by $\mathcal O(\frac{1}{n^c})$ for every constant $c$. Clearly, we want the adversary's advantage to be as asymptotically small as possible.


Why is ciphertext from low entropy plaintext not compressible?

Well, your definition of entropy is known as Kolmogorov complexity, and it's not so much that it is incorrect, as it is that it is inapplicable to what gzip does.

For example, the value $\pi$ can also be generated by a short program; however, if you attempt to compress a 2.2Mbyte sample of the binary expansion, you'll also find that gzip will also not be able to compress it.

What we can tell from that is that gzip doesn't actually do a good job of estimating the Kolmogorov complexity.  Now, this is not actually a major criticism of gzip; it is actually impossible to write a program that computes it (!).

Instead of attempting to wrestle with Kolmogorov complexity, what gzip (and every other compression algorithm out there) relies on to compress the data is heuristics. That is, it has a model of redundancies that appear in real plaintexts (such as repeated substrings), and is able to take advantage of those redundancies to shorten the length.  Now, if that model corresponds to the text it is given, gzip can compress quite well; if the model doesn't correspond (and both the encrypted text and the binary expansion of $\pi$ fall in this camp), it can't compress at all.

And, no, encrypting more data would not make the result any more compressible.


Actually, as you note, XOR doesn't satisfy the bilinear condition.

What does is multiplication $\otimes$ in $\mathbb{F}_2$, that is:

$$\otimes(u \oplus v, w) = \otimes(u,w) \oplus \otimes(v,w)$$

or, as more traditionally expressed (using $+$ and $\times$ as the field operations):

$$(u+v) \times w = (u \times w) + (v \times w)$$

This is one of the fundamental properties of a field; since $GF(2)$ is a field (with $\oplus$ and $\otimes$ as the field addition and field multiplication), this holds.

And, in $GF(2)$, $\otimes$ is equivalent to bitwise $AND$


You cannot decrypt any ciphertext encrypted by CBC using GCM. GCM mode uses CTR mode internally. CTR mode only uses the block cipher only in the encryption direction, while CBC mode relies on AES decrypt. Thus it is impossible to use GCM to decrypt ciphertext encrypted using CBC. You need to use CBC decrypt to retrieve the plaintext.

Instead you should use some kind of protocol version to detect with scheme was used. Then you can distinguish between the ciphertexts and use CBC or GCM where required. Of course you may want to convert the CBC ciphertext to GCM ciphertext anyway - by decrypting and then encrypting the data again, preferably using a different key for GCM encryption.

Introducing a protocol version field is kind of tricky if you've just got the CBC encrypted ciphertext as the ciphertext is indistinguishable from random. That said, the output of CBC mode encryption is always a multiple of the block size (unless ciphertext stealing is used), so you could introduce a version number and make sure that the version, IV and GCM ciphertext are not a multiple of the block size. If you can store the protocol version elsewhere then this should be preferred.

If possible you should try and use a container format such as CMS or PGP instead of trying to invent your own protocol. There are also more lightweight protocols such as Fernet.


Security limits of password-based encryption

An $O(\log l) $ cost for $l \le m$ seems a little simple given the many components (Argon, AES, hard & soft optimisations and bounded RAM & I/O).
Have you considered an empirical simulation?  You could lash something together in your favourite programming language, set all soft and hard parameters to reasonable levels and just see. So either an iterated approach, or a Monte Carlo simulation. It might at least suggest a real world relationship between all the parameters.
I don't know whether they'd talk to you about scale, but is it worth asking someone who actually does this? Apparently the Inmanis appliance has 'monstrous performance'.
P.S Whilst the application of your theory to a singular very large message seems sound on the face of it, the password wouldn't be recovered from such (knowing the presence of AoNT). Clearly you'd attack the shortest  message which might be "Toodles" covered by the same password. Don't know whether that has any bearing on what you're trying to demonstrate.


"Random permutation" in the random oracle model?

From the middle of p. 561:

  Algorithm $A$ accepts the public keys $P_1, P_2, \dots, P_r$ (but not any of the corresponding secret keys) and is given oracle access to $h$, $E$, $E^{-1}$, and to a ring signing oracle.  It can work adaptively, querying the oracles at arguments that may depend on previous answers.  Eventually, it must produce a valid ring signature on a new message that was not presented to the signing oracle, with a non-negligible probability (over the random answers of the oracles and its own random tape).

Specifically, $A$ is allowed to query $E$ and $E^{-1}$ at any key and any message, with the keys obtained from the oracle for $h$ as stated a little below.

(It doesn't matter that $A$ is allowed to know the bits of the key because presumably the choice of permutation is independent uniform random for each distinct key, so there's no meaningful structure to be had out of the bits of the key.)


Yes, there is.

I'm assuming your broadcast stream is (or can be) somehow broken up in smaller messages (or "packets"), and you don't need to retire a key before a message is finished.

Then you produce a random session key for each message, and encrypt this session key with each of the subscribers' keys, prepend them (together with some tagging) to the message.

Each subscriber than filters the header for his section, decrypt the session key and then can decrypt the whole message.

This gives some overhead proportional to the number of subscribers for each message, so it works better when the messages are large enough and the number of subscribers is low. On the other hand, if subscribers can switch on at every time, you'll want to have the message size small so they don't have to wait long until the next session key comes around.

The OpenPGP protocol includes this feature, and is commonly used for sending encrypted emails to multiple receivers. I suppose S/MIME does it similarly.

This method works both with symmetric long-term keys as well as with asymmetric key pairs for encryption (such as RSA or ElGamal).

If you have a "normal" directed communication method in addition to your broadcasting channel, you could also send each subscriber the session key (encrypted with his key) directly, without the bandwith overhead for all the other subscribers.

There might be some more fancy method of encrypting a session key to more receivers without the linear bandwith growth, but I know of none. (1-of-n secret sharing or such?)


There are two blocks to consider here. The 16KiB blocks you mention you have to encrypt and the blocks as encrypted by the AES block cipher. Let's call your blocks fragments.

ECB is secure for blocks that are not related to each other in any way. Your fragments, however unique, may still contain blocks that are not unique. If this is the case then ECB will leak information about identical blocks. CBC will overcome this, especially if each block has it's own key.

So:

  Given 1 + 2, is it still safe to waive the salt and the IV?

Yes, but not for ECB; ECB is almost never a good idea.

  Which mode should i use?

CBC or any other mode that is secure for protecting data at rest.

You need an authenticated cipher or MAC if you also require integrity and authenticity. These are basically always required within transport protocols.


The underlying principle here is that of combinatorics. Think of banks and PCOs as abstract parties. Party $A$ has $|A|$ many members and party $B$ has $|B|$ many respectively. For each $x \in A$ we have $|B|$ secret keys which $x$ shares with members of $B$ meaning we have $|A| \times |B|$ keys.
In your first question, we assumed that for all $x \in A$ and $y \in B$,  we know that $x \neq y$. I. e., The two parties $A$ and $B$ don't share any members! In your second question however, that assumption is not true since $A = B$ which means the party of banks sharing keys with the party of banks, id es, among themselves.
The question here is then how many ways to pick unique $\{x, y\}$ combinations from a set $A$. Well, this is just an $n$ chose $k$: $\binom{n}{k}$ problem. In this case $k = 2, n = |A|$.

How many secret keys will be needed if each PCO shares a unique secret key with each bank?

$$|A|\times |B| = 10^4 \times 10 = 10^5$$

How many extra secret keys will be needed if every two banks share a unique secret key?

$$\binom{10^4}{2} = \frac{10^4!}{2!(10^4-2)!} = \frac{10000!}{2(10000-2)!} = \frac{10000!}{2(9998)!} = \frac{9999 \times 10000}{2}$$


In bilinear pairings, is it possible to let someone be only able to decrypt ciphertexts in $G_1$ but not able to decrypt the ciphertexts in $G$?

No, because the guy who can only decrypt in the target group $G_1$ can take any ciphertext in $G$, use the pairing to map it to $G_1$ and then decrypt in $G_1$ (here I assume the full scheme where the message is a number and not a group element).

You could do it the other way round, i.e., let the guy only decrypt in $G$ and not in $G_1$, by giving him not the full private key $q_1$ but only $g^{q_1}$. Then you force him to decrypt by using a pairing and thus force the ciphertext to be in $G$.


How do I express each element in a field F as a power of a primitive element?

Just enumerate all powers of your primitive element.  There are only 15 of them.  That will give you a lookup table that allows you to translate from field element to its expression as a power of the primitive element.


What asymmetric key exchange algorithms are known besides DH?

Using lattices/ring-LWE, there is Lattice Cryptography for the Internet (by me), which inherits from Ring-LWE encryption, and has been implemented by Bos et al. with further improvements by Alkim et al.

The underlying mechanism is conceptually DH-like, but uses completely different mathematics.  We start with a uniformly random $a \in R_q = R/qR$, which can be chosen by one of the parties or by a trusted third party.  Here $R$ is an appropriate choice of ring, e.g., $R=\mathbb{Z}[X]/(X^n+1)$ for power-of-two $n$ (in the few hundreds, for current security estimates).

The basic protocol works as follows (oversimplifying a bit): to establish a key, the first party chooses a "short" random $e \in R$, and announces $E \approx e \cdot a \in R_q$, where the approximation hides some short random error.  Similarly, the second party chooses a short $f \in R$, and announces $F \approx a \cdot f \in R_q$.  The first party can then compute $e \cdot F \approx e \cdot a \cdot f \in R_q$, and the second party can compute $E \cdot f \approx e \cdot a \cdot f \in R_q$.  The parties then use some kind of "reconciliation" mechanism to extract a common secret key from their shared "noisy" versions of $e \cdot a \cdot f$.

The above mechanism can be proved secure against passive eavesdroppers assuming the hardness of the corresponding Ring-LWE problem (which itself can be proved quantumly as hard as worst-case problems on ideal lattices, for appropriate parameters).  Of course, in reality we need authenticated key exchange and other properties; these can be obtained using additional techniques that originated in the DH setting (see the first link for details).


This is prevented by:

by requiring authentication of B using a private key only known to B and a public key trusted by A;
by making sure that messages are protected by a message authentication code (MAC) / authentication tag, created using a session key only known to A & B.

Step 2 requires a key agreement step, e.g. Diffie-Hellman or the encryption of a secret by A to B using the public/private key pair of B.

I'm guessing that step 2: message authentication codes is what you're after. Message authentication codes provide integrity and authenticity for the messages they protect.

Note that you may also want to protect against replay attacks. Replay attacks however do not let E pose as B.


If OAEP is introducing randomness to encryption how could be ciphertext decrypted?

To decrypt the ciphertext you definitely need to recover the random token $r$.
But $r = Y \oplus H(X)$. Then knowing $r$ the padded message can be recovered as $m0\dots0 = X \oplus G(r)$. The decryptor only need to known the size of the random token $r$ and this is usually part of the standard. Of course the standard has to define the $F$ and $G$ functions and how to pad the message. The padding process has to be such that unpadding the message after the decryption is deterministic and unique.

The randomness added to the encryption process makes impossible for an attacker having access to an encryption oracle (or observing a lot of messages and their effect) to create a dictionary of corresponding couples of $(m_i, c_i)_{i\in S}$ where $c_i = Enc(m_i)$. This property has been defined for the first time in the paper by Goldwasser and Micali "Probabilistic Encryption" (Shafi Goldwasser and Silvio Micali, Probabilistic Encryption, Special issue of Journal of Computer and Systems Sciences, Vol. 28, No. 2, pages 270-299, April 1984)


Hardware random number generator for lottery?

The wording of this requirement contains the meaningless

  has to work with a length of at least $2^{64}$ period

that I hereafter reorder into

    has to work with a period of length at least $2^{64}$

We need to solve the ambiguity left in

  must produce a sequence of game results based on initial values that are random or unpredictable

about if random or unpredictable applies to initial values or to game results. Because of the earlier text "deterministic algorithm to determine the game result", the game results can't be random, since that opposes squarely to deterministic. Thus random or unpredictable can only apply to initial values. We are left with a sequence of game results that is never prescribed to be unpredictable, and the requirement is perfectly met by a generator that

uses 8 throws of 8-sided dices to build a 64-bit seed initializing a 64-bit counter;
at each uses, increments the counter modulo $2^{64}$ and outputs it.

Yet this generator is clearly unsuitable for a lottery, because the next result is trivially inferred from the previous one.

Also missing is the range of game outcomes ($2^{64}$ outcomes as in the above example is unheard-of in lotteries); a requirement that these game outcomes are equiprobable, and to what degree; if two outcomes in the sequence generated from the same seed can repeat (they should not in something that mimics a traditional loto).

Ah, and if we take it to the letter, it seems we must have a period of at least $2^{64}$ for all seeds, and that condition is not part of P2 Class of BSI AIS-31 or FIPS 140-2 Level 3. Therefore, game outcomes determined by some deterministic memory-less function from output of generators certified by these standards arguably can not meet the requirement. Further, AIS-31 allows (or requires for some class) that the generator is reseeded while used, when the requirement asks for something deterministic except for seed.

In the end, even after it has been reordered, the requirement remains utterly technically defective, and arguably prevents using established RNGs. The best is to ignore this requirement entirely and start afresh, if that can be done without getting fired poorly graded.

To engineer sound requirements, we must know the intent. It could be that the seed is archived, so that it can be proved afterwards that the PRNG worked correctly. It could be that this archival is distributed, so that collusion of some number of dishonest parties in the archival process would be necessary to predict the outcome. Again there's the range and rules for outcomes. There are assumptions to be made on what is trusted, and what's not.


Logarithmic brute-force for stream-ciphers

This way the brute-force search space is reduced logarithmically.

Well, no.

If there are $N$ possible keys, then you test $N$ keys on the first byte.  Then, you keep only those that succeed on the first byte, and test those on the second byte; that's approximately $N / 256^1$.  Then, you test those keys that succeed on both bytes, that's approximately $N / 256^2$ keys.

When you count the total number of keys you've tested (including those you tested multiple times), you come up with an expected:

$$N + N/256^1 + N/256^2 + N/256^3 + … = (256/255)N$$

And, $(256/255)N$ is not a "logarithmic reduction" over $N$...


Converting Ed25519 public key to a Curve25519 public key

ge_scalarmult_base returns GroupElementP3 which doesn't have (x, y) as members. It has X, Y, Z from which you can compute x = X / Z and y = Y / Z.

So you have two choices:

Compress the point with ge_tobytes:

byte[32] Abytes;
fe y;

ge_scalarmult_base(&A,sk);

ge_tobytes(Abytes, &A);
fe_frombytes(&y, Abytes);

// your code here using `y` instead of `A.Y`

The downside of this technique is that it costs two field inversions. So I'd only use it if the input is a compressed point.
Modify the formula to work with X, Y, Z coordinates:

$$x_{mont} = \frac{1+y_{ed}}{1-y_{ed}} = \frac{1+\frac{Y}{Z}}{1-\frac{Y}{Z}} = \frac{Z+Y}{Z-Y}$$

fe_sub(v, A.Z, A.Y); //v = Z - Y
fe_add(u, A.Y, A.Z); //u = Z + Y

This solution is preferable if you just computed the point without having reduced yet. Typically directly after a scalar multiplication.


Are there any deterministic multi-block encryption constructions that have an avalanche effect going both ways?

I know no classical deterministic multi-blocks encryption construction with the desired avalanche property. And a serious problem is that any such construction, simply because it is deterministic, won't pass the formal definition of security under chosen plaintext, which CBC, CTR, CFB, OFB.. with random IV achieve.

So what's asked does not come with a precise definition of security. Given this, I can state anything without risk of contradiction from the standpoint of security. So here is something, essentially two passes of CBC encryption with IV the last block of the previous pass. For encryption:

Pad de message to an integer number of blocks; e.g.: append a single bit 1, then as few bit(s) 0 (possibly none) as strictly necessary to reach a multiple of the block size.
Let $b>0$ be the number of blocks of padded plaintext $X$
If $b=1$, do $X_0\gets E(E(X_0))$ where $E$ is block encryption
Otherwise repeat for $i$ from $b$ to $3b-1$ (that is, $2b$ times):

$X_{i\bmod b}\gets E(X_{i-1\bmod b}\oplus X_{i\bmod b})$

Output ciphertext $X$

Decryption is:

Let $X$ be the ciphertext of exactly $b>0$ blocks
If $b=1$, do $X_0\gets D(D(X_0))$ where $D$ is block decryption
Otherwise repeat for $i$ from $3b-1$ downto $b$ (that is, $2b$ times):

$X_{i\bmod b}\gets X_{i-1\bmod b}\oplus D(X_{i\bmod b})$

Remove padding; e.g.: while $X$ ends with a zero bit and is non-empty, remove the rightmost 0 bit; then if $X$ is non-empty, remove its last bit.
Output the plaintext $X$

We can improve diffusion in decryption by using PCBC rather than CBC, make the thing less malleable by throwing an extra $\oplus i$, do more passes, have an extra index hopping into $X$, derive a different key at each pass.. but without a definition of the security goal, that is moot.

Note: as pointed out elsewhere, plaintext changes do not propagate at all in CTR mode, contrary to the question's statement.


Algorithm for computing modular inverse in MPC

In general: $a^{-1} \equiv a^{\phi (q)-1} \pmod q$ where $\phi$ is euler totient function. If $q$ is a prime, then $\phi (q)=q-1$ and thus $a^{-1} \equiv a^{q-2} \pmod q$.


How to to calculate the hash of an unordered set

A well known technique to form the hash of an unordered set given hashes of the elements, is to order the hashes lexicographically, concatenate them in this order, and hash the result. The order of the elements in the original set does not influence the result, and this demonstrably inherits the properties of the hash (collision-resistance, preimage resistance, security in the ROM). The reader is left to decides if this is the trivial one of sorting the elements. That has serious drawbacks: the hashes must be stored; this is not an online algorithm.
This would be fixed by XORing the hashes of the elements of the set, but (as conjectured in the question) this gives a weak hash. In particular, if the hash is $b$-bit, then after a little more than $b$ elements we likely can find $b$ hashes that are linearly independent (w.r.t. bitwise XOR), and then by XORing some of these hashes we can form any value desired; that's a first-preimage attack.

Update: Meir Maor's comment pointed this very relevant paper: Dwaine Clarke, Srinivas Devadas, Marten van Dijk, Blaise Gassend, G. Edward Suh, Incremental Multiset Hash Functions and Their Application to Memory Integrity Checking, in proceedings of AsiaCrypt 2013. It builds hash functions for multisets, and their results apply directly to sets, which are multisets with multiplicity restricted to $\{0,1\}$ .
Based on their MSet-Mu-Hash construction, the following works, requires no sorting, and can be computed  with constant memory as the hashes of elements of the set are made available to an online algorithm:

Choose a nothing-up-my-sleeves 2049-bit public prime $p$ with $(p-1)/2$ also prime, e.g. $p=\lfloor2^{2047}\pi+494382\rfloor$ ; we assume the discrete logarithm modulo $p$ is hard, about as much as breaking SHA-256 collision resistance.
Expand each given SHA-256 hash $H_i$ of an element of the set into a 2048-bit bitstring $S_i$, e.g. as $S_i=\operatorname{H}(H_i\|K_1)\|\operatorname{H}(H_i\|K_2)\|\operatorname{H}(H_i\|K_3)\|\operatorname{H}(H_i\|K_4)$ where $\operatorname{H}$ is SHA-512 and the four $K_j$ are short distinct public arbitrary constants.
Compute the product modulo $p$ of the $S_i$ (converted to integer per big-endian convention); this can be done jointly with the previous step. The product will be $1$ for the empty set.
Hash the product (converted to a 2056-bit string per big-endian convention) with SHA-256 in order to produce the final result.

Note: in order to avoid certain attacks in certain hypothetical proof-of-work protocols (see this) both when sorting or when using the modular multiplication combination, the one or two hashes used on top of the initial hash should be different (e.g. use a different initial constant).


Bcrypt is a password hashing function likes PBKDf2, Scrypt, and, Argon, where in the password hashing the collision is not important, pre-images are important.
If you just iterate the $\operatorname{MD5^n}(x)=\operatorname{MD5}(\operatorname{MD5}(...(\operatorname{MD5}(x)...))$ n-times then we will have an already well-known problem. A collision in the inner MD5 is a collision for the $\operatorname{MD5^n}$ therefore simple iteration is not secure only slows the collision finding, really? Just find a collision for $\operatorname{MD5(x)}$ then you have a collision. In other words, the cost of finding collusion is not affected!
An easy fix is for the case $n=2$ is $\operatorname{MD5^2}(x)=\operatorname{MD5}(\operatorname{MD5}(x)||x))$ or similar approaches.
We don't need doubling MD5 or SHA-1 to improve security, we just need new hash functions like SHA3 and the very fast one Blake2b.
Finally, we want cryptographic hash functions to be secure and fast, not slow. Slowness is required in password hashing.

update for the comment
It turns out that hashing with MD5 is required for the identification. In this case, the pre-image attack is more important if the public keys are considered to be kept secret. In the pre-image attack, given a hash value $h$ we are looking for an $x'$ such that $h = \operatorname{MD5}(x')$. The $x'$ may be the original $x$ such that $h = \operatorname{MD5}(x)$ or not. If the attackers seek the original they need to search more. MD5 has only one pre-image attack that its practical cost is not faster than the generic pre-images search that has $2^{128}$-time.

2009 - Yu Sasaki, Kazumaro Aoki, Finding Preimages in Full MD5 Faster Than Exhaustive Search. The post is $2^{123.4}$-time and $2^{45}\times 11$ word of memory.

The collision here is only relevant for you since you don't have two or more users who have the same identity.
So you can use a modern hash function with trimmed instead of MD5.


Is there an algorithm that allows to distribute elements securely between parties?

It is doable. Assuming all parties are semi-honest and you have a public key encryption scheme allows threshold key generation and threshold decryption, as well as re-encryption, that is:

$keyGen(\lambda,m)$: given the security parameter $\lambda$ and an integer $m$, output a public key $pk$ and $m$ shares of the secret key, each share is given to a player (each player only knows its own share). The secret key is $sk$ and the $i$-th share is $s_i$.
$Enc(pk;m,r)$: encrypt $m$ with random $r$, using the public key $pk$.
$Dec((s_1,\cdots, s_m);c,i)$: $m$ players jointly decrypt a ciphertext c, and output it to the $i$-th party.
$Reenc(pk;c,r)$: Given $c=Enc(pk;m,r')$, re-encrypt it with a random number $r$, so that the output is a valid ciphertext of the original plaintext (i.e. $Enc(pk;m,r'')$).

Elgamal satisfies the above requirements.

Then the players do the following:

They run $keyGen$ jointly to get the public key and shares of secret key.
The first player $P_1$ encrypt each of $n$ numbers, permute the list of the ciphertexts randomly, passes the permuted list to $P_2$.
Then $P_i$ re-encrypts each ciphertext in the list it received and permute the list randomly, and passes the permuted list to $P_{i+1}$.
$P_m$ re-encrypts each ciphertext in the list it received and permute the list, and publish the final list.
Each party pick a different ciphertext in the list.
From $i=1$ to $m$, the players jointly decrypt $P_i$'s ciphertext and reveal it to $P_i$.

If the parties are malicious, zero-knowledge proofs need to be in place to ensure the parties follow the protocol.


Calculating the multiplicative inverse of a number in $GF(2^n)$ where $n > 8$

First, let us take AES as an example.

We have $\operatorname{GF}(2^8)$ where each bit represent the coefficient of a polynomial in $\operatorname{GF}(2)[X]$. The modulo reduction is done with $$p(x) = x^8 + x^4 + x^3 + x+ 1$$

Thus you can generate all the elements from a $1$ to $255$ and this forms a cyclic group : $<g^1, g^{\ldots}, g^{255}>$

Notice that:
$g^{2^8-1} = g \iff g^{255} = g$
or:
$g \cdot g^{2^8-2} = 1 \iff g \cdot g^{254} = 1$
thus $g^{254}$ is the inverse of $g$ or in other words:

Computing the $254^{th}$ power of an element give its inverse (more here)

This exponentiation can be quickly done using square-and-multiply.

  Thus for a field of $2^n$ with $p$ being an irreducible polynomial of degree $n$, for $g$ an element of $\operatorname{GF}(2)[X]$: $$g ^{-1} = g^{2^n-2} \bmod p$$

Also the use of tables is ill-advised do to the constant timeness. A bit-sliced implementation of this operation will be preferable.


On AES, is a true random string enough for a key?

Even if the 32 characters are completely random, they won't contain non-printable characters. Actually, there are only about 107 printable characters in ASCII (out of 256 values for a full byte) and that even includes the space character. So if all the printable characters are used, it would result to a security level of about $log_2(107^{32}) = 215$ bits, which is quite a lot.

AES reaches the highest level of security for random keys, so in general it is better to put the value through a KDF (Key Derivation Function) together with a salt, possibly a label (OtherInfo) to derive a specific key and possibly - for a Password Based Key Derivation Function such as PBKDF2 or Argon2 - a work factor. That way the security of the key may get closer to the 256 bit strength that e.g. AES-256 promises.

So yes, deriving a key would be more secure. Doubly so since your first sentence "The string (32 ASCII characters) is entered by a human, and considered truly random" is usually not correct in practice. Humans are horrible with regards to entering truly random numbers, even if just because of the typo's when entering it from another screen.


Since $\mathbb{G}_T$ is $\mathbb{F}_{q^2}$ in the setting you are mentioning, you would have to choose them so large that your implementation will no longer have the performance one would hope for.

I would recommend to switch to the asymmetric setting. Currently the probably best choice regarding performance and existence of optimised implementations is to use BN parings. However, recent progress in solving the discrete log problem in prime extension fields suggests that BLS curves might be an even better choice (see here). In the aforementioned paper you can also find estimations on the impact of the recent improvements on the key length. For BN pairings these estimations suggest that it is required to increase the bit length of $p$ to 461 bit for 128 bit security. There is also an alternative estimation which suggests that it is sufficient to use $p$ of length 383 bits for 128 bit security. The conservative choice would thus be 461 bit.

I would probably also use another library - as far as I know JPBC is not the best choice regarding performance. There are various Java implementations for BN pairings available. One option would be to rely on the bnpairings library. Another option would be to go for the ECCelerate library, which is free for educational and research purposes, and also provides a very recent and highly optimised implementation of BN pairings. Since you mentioned that you implemented BLS signatures: it might also be interesting for you that ECCelerate already offers means to hash to the groups as required by BLS signatures. I don't know whether this is implemented in the BNpairings library.


number theory question in a group with unknown order

Define the function
$$\begin{align}
f: G&\to G\\
x&\mapsto x^{\prod_i e_i}
\end{align}$$
$f$ is injective. Proof: if $f(x)=f(y)$ then $x^{\prod_i e_i}=y^{\prod_i e_i}$, thus $(x\cdot y^{-1})^{\prod_i e_i}=1$, thus the order $k$ of $(x\cdot y^{-1})$ is a divisor of $\prod_i e_i$. Since the order of any group element divides the group order, $k$ is also a divisor of $n$. Since $\gcd(n,\prod e_i)=1$, $k$ must be $1$. Thus $(x\cdot y^{-1})=1$, thus $x=y$.

Any injection over a finite set is a bijection. It follows that $f$ is a bijection over $G$.

Thus $h$ is constructed as the image of a uniformly random element $z$ of $G$ by a bijection $f$ over $G$. Hence $h$ is a uniformly random element of $G$.


Can `hash( messageA ) + messageB` be used to determine `hash( concat( messageA, messageB ) )`?

With a little more information, an attacker can indeed get up to some funny business by abusing this "internal state-revealing" property of Merkle-Damgard style hash functions (this includes MD5 and SHA-1 and SHA-2 but not SHA-3).

With hash(message1) and len(message1) but not message1 itself, there is one specific message2 such that an attacker can forge a valid hash(message1 || message2) by running further iterations of the hash algorithm starting with hash(m1).

When a hash of this style is used to generate a Message Authentication Code (MAC), that message is vulnerable to "length-extension attacks". That means an attacker can append the message with their own malicious message and forge a valid tag.

Of course, there are ways to prevent this kind of attack. One easy method is the "wide pipe" strategy -- simply generate your hash with more bits than you need, and truncate your final result! Now the hash code you output no longer represents a valid internal state of the algorithm.

Modern standards for hash functions use this or other such strategies to prevent this from being a problem in practice. For example, HMAC (the standard way to build a MAC from a hash) runs the hash function twice in a way that avoids length extension attacks.


Proving the security of a one-way function with partially known input

You are right, it does not seem as if a reduction from OWF works here. Indeed it rather seems like a separation is possible. This is what @RickyDemer describes in his comment, i.e. showing that there exists at least one OWF $h$ for which the above use case is insecure. This would show that a reduction from OWF is impossible.

You definitely can get a proof if you assume $h$ is a pseudorandom function family. In that case $TXT$ would have to be treated as key and the counter as message. Finding the (secret) key used for a PRF would allow to distinguish it from a truly random function with high probability and hence learning $TXT$ from the above inputs means breaking the PRF property of $h$... In practice you can for example use any HMAC as PRF.


Is the one-time-pad a secure system according to modern definitions?

Modern security has moved beyond looking just at passive attacks (in which the attacker is just a passive eavesdropper seeking to learn what was said); attackers are generally considered to be able and willing to pull off active attacks of various types (in which the attacker can modify or forge messages to achieve some goal). One-time pads are extremely vulnerable to modification; if an attacker knows that a message says "Pay Robert \$100,000", they can trivially change it to "Pay Joseph \$999,999". They share this property with all stream ciphers; if your ciphertext is the plaintext XOR a keystream, then an attacker who knows $P_1$ and $C_1$ can easily compute $C_2=C_1\oplus (P_1\oplus P_2)$, which decrypts to $P_2$. Working around that requires some way to verify message authenticity, which a one-time pad doesn't do (and doesn't try to do). This is provided by message authentication codes (MACs), or by a cryptosystem that combines authentication and encryption (like AES-GCM).

Also, many security properties literally do not apply to OTPs, because the properties are along the lines of "given the ability to encrypt multiple messages with the key, do X."

Uselessness is broader: even if you just need confidentiality, OTPs have serious issues for usability. That's because a OTP key has to be as long as the message and transmitted in secret; cryptography is most useful when you just need to transmit a little information secretly to encrypt a lot of stuff. An OTP is only as secure as the key exchange, so to be useful the keys have to be exchanged without relying on cryptography for security (else you're not getting perfect security). There are a few cases where they work well (like distributing in person to someone who's about to go on a mission and will need to send stuff back to you over an insecure channel), but they're rare.


Is using SHA256 to extract entropy from a p-rand nonce a good way to create keying material?

CryptGenRandom is supposed to produce cryptographically strong random numbers, so you shouldn't need to process it before using as a key.

However, if you want to treat it as of suspect quality, I would go with SP 800-90B recommendations: assume it has entropy at least half the bits, so request double what you need. Then run it through HMAC with a suitable hash function.