Diffie-Hellman: choosing wrong generator "g" parameter and its implications of practical attacks

As far as we know, Diffie-Hellman is secure as long as the subgroup generated by g is impervious to discrete logarithm. When working modulo a prime p, this is achieved when the following are met:

p is large enough (at least 1024 bits, go to 2048 bits for a bigger safety margin) and is not a "special form" prime (a randomly generated prime will be fine with overwhelming probability).
the subgroup generated by g has an order t which is such that there is at least one prime factor q of t which is "big enough", i.e. more than 2k bits, when k is the "security level" (e.g. to have at least 80-bit security, q should be at least 160 bits).

Note that it is in no way necessary that g generates all non-zero integers modulo p. It is fine if it generates a strict subgroup, as long as that subgroup cannot be split into several subgroups, each being very small. This is the essence of the necessity of at least one medium-sized prime q in the factorization of the subgroup order t.

The order of g, called t above, is a divisor of p-1. With overwhelming probability, a randomly generated g will imply an order which will not be much smaller than p. Indeed, there is only one chance in a billion to hit a g which implies an order t smaller than p by more than 30 bits (because 230 is about one billion). It is preposterous to imagine that a random g, modulo a 1024-bit prime p, will imply a subgroup order smaller than 900 bits.

The biggest prime factor of a random integer of n bits will have length, on average, about 0.3*n. It is extremely improbable that the biggest prime factor will be much shorter than that.

Bottom-line is that a purely random prime p (of at least 1024 bits) and a purely random g modulo p will be fine. To get bad DH parameters, you have to do it on purpose.

However, some people are arguing for ensuring that p and g are fine with "stronger" arguments than the probabilistic properties explained above (mathematically, these probabilities are extremely strong, but convincing people is not only about mathematics, but also about psychology). First, p will be generated as a "nothing up my sleeve" number with a completely open and fully described pseudo-random generator. See appendix A of FIPS 186-4 for an illustration (this is for DSA, but it may apply to DH as well). Then there are two ways for g:

The smaller prime q could be generated first; then p is produced randomly as p = qr + 1 for random r of the right size, until a prime p is reached. Then a random h modulo p is produced, and g is set to g = h(p-1)/q mod p. This yields either g = 1 (with extremely small probability) or a g with an order exactly equal to q, which is fine.
p could be generated as a so-called "safe prime". I.e. random odd integers u are generated until both u and p = 2u + 1 are both prime. Then set g = 2: the order of g is then necessarily equal to u or 2u, and both are fine. Generating a safe prime is computationally expensive, but having g = 2 yields a slight performance boost when doing the actual Diffie-Hellman.

When the whole process is fully described, as in Appendix A of FIPS 186-4, it can be verified, which guarantees against DH parameters which have been made weak on purpose.


The adversary must not be allowed to choose the seed.
(Otherwise, the definition would be trivially unsatisfiable, as the adversary could just check whether the returned string is $G(x)$ for their chosen seed $x$.)

The rationale behind this is that a PRG's seed is understood as (some kind of) a secret key, which the attacker must not be able to know or choose in any threat model. (After all, that's why the secret key is secret. Note that any cryptography trivially breaks when the attacker gets their hand on the key(s).)

By definition, a function $G\colon \{0,1\}^n\to\{0,1\}^{\ell(n)}$ with $\ell(n)>n$ is a pseudorandom generator (PRG) if any polynomial-time adversary is unable to differentiate between a truly random $y\in\{0,1\}^{\ell(n)}$ and the pseudorandom string $G(x)$ for a random seed $x\in\{0,1\}^n$ except for negligible probability.

Intuitively, what this entails is that the output of a PRG, when initialized with a sufficiently random seed, is "just as good" as a real random string.


The modes of encryption that preserve the format

I'm aware of only one official specification: NIST SP 800-38G, and recommend to ignore it. Rather, consider NIST SP 800-38Gr1-draft, still unofficial, if something next to a rubber stamp is badly needed.
That draft changes both modes in the official specification, FF1 and FF3, fixing security issues:

The minimal size of the input/output space is increased from a hundred to a million elements (e.g. from two to six decimal digits).
FF3 is changed to FF3-1 with reduced tweak space, following F. Betül Durak and Serge Vaudenay's Breaking the FF3 Format-Preserving Encryption Standard over Small Domains, in proceedings of Crypto 2017.

Note: the NSA reported that FF2 aka VAES3 of NIST SP 800-38G-draft has less than 128-bit security, NIST confirmed that and withdrew it.


On countermeasures for replay attacks. Does this one require plaint text password storage?

Yes, that is a problem.  There are protocols like SRP that both eliminate the need for Bob to store the password in plaintext and prevent replay attacks.


How to securely share AES key between two remote devices (client and server) through UDP protocol?

You don't transfer the key, not at least un-encrypted.
There are several ways to "establish a shared key" between authenticated systems.
Using key exchange schemes such as Diffie-Hellman, its elliptic-curve versions such as ECDH, X25519/X448, etc, as well as some schemes secure even if you attack it with a quantum computer such as NTRU (formerly NTRUEncrypt), Kyber, Saber.
Notice I said authenticated system. key exchange schemes require the public key of the peer - which is static if you just hard-code it into your application; a better way is to use a digital signature to sign an ephemeral key exchange public key and hard-code the digital signature verification key into the application.
All in all, there is a well-established protocol with existing free and open-source implementations called TLS, which you can use to exchange an initial key, then import that key into your UDP-based protocol.
The QUIC protocol does about just that: it doesn't design new key exchange or authentication handshake protocol, it imports the key from TLS handshake and use it in the en/de-crypting UDP packets.


What are the major advantages of SPHF for PAKE?

SPHF are a very versatile tool, and they have a large number of applications. Their application to PAKE stems from three main properties:

first, they allow for low-interactivity PAKE. Note that this is very desirable, since latency is one of the main source of inefficiency when communicating with a server on the web. To see it, consider a construction with a designated-verifier proof: intuitively, each player could just prove to the other that, say, some commitment contains the right password. The parties could then perform a standard key exchange after verifying the proofs. However, making this formal requires in particular several rounds of interactions. SPHFs improve that because for PAKE, it is not needed at all that each party proves to the other that he knows the right password: we only want to ensure that if both parties know the same password, they get the same strong key. Intuitively, this fits perfectly the SPHF definition: an SPHF gives you some specific kind of designated-verifier proof where the prover and the verifier end up having the same random key in the statement is true, and independent keys otherwise. To make that a real proof, the prover then sends his key to the verifier, who checks that this is the same as the one she got. But in the PAKE application, this last check is not needed: the hash values can directly be used as the strong key, without any further verification step. Hence, this allows for single round PAKE (for more details, see this paper).
Second, they can be built from well-studied standard assumptions, namely, DDH (and it's variant, such as DLIN). In contrast, the natural alternative approach to obtaining a low-interactivity PAKE (which, as I already argued, is very desirable for efficiency reasons) would rely on non-interactive zero-knowledge proofs, which are not known from such well-studied assumptions (existing efficient NIZKs require pairing-based cryptography, or the random oracle model).
Third, they are very algebraic, which is a strong bonus both for optimizing efficiency (since all kinds of tricks, such as batching, become available) and analyzing security. Hence, SPHFs lead to the most efficient PAKEs in the standard model (with only 6 group elements sent by each party, in a single round) with the highest security notion (UC security, which means security even in an arbitrary concurrent setting, as well as full adaptive security for some more recent constructions).


What is the exact purpose of length padding in Merkle–Damgård hash functions?

Hash functions are defined to work on an arbitrary integer number of blocks. The minimal quantity of data that can be processed by an hash function is a single block.

So, if the message size is not an integer multiple of the block size one has to pad it to the right size.

One needs also to make the message + padding have one and one only interpretation, otherwise it would be simple to create collisions. Therefore adding the padding lenght gives an unique way to interprete the message+padding couple.

As example: let's imagine that one pads addings just zeros to achieve the right lenght. Therefore message $m$ and message $m||0$ have the same hash image.


Knowing pre-encryption data, can we find the private key CryptoLocker used?

If CryptoLocker does its job properly, then no, knowing part of the cleartext will not help you recover the rest. If that helped, then the encryption system would be called weak against known-plaintext attacks. From what I read, it seems that the CryptoLocker authors were competent(*), so no such luck.

(In particular, the asymmetric encryption with RSA-2048 is done only for a random symmetric key, and the bulk of the data is encrypted with a symmetric encryption algorithm like AES, using that key. This is the normal setup of hybrid encryption. This means that if you were to find weaknesses with regards to known plaintext, then you would have to look for them in the symmetric encryption algorithm, not the RSA part. The result, though, is the same: no known way to recover your data. Sorry.)

(*) I am here talking about the encryption. I believe the payment system may leave exploitable traces which would allow law enforcement agencies to track down the perpetrators. But this is likely to involve countries of questionable cooperativeness, so don't put too much hope in this.


Key Handling in Multi Platform Applications

This answer will orientate around "Method to Protect Passwords in Databases for Web Applications" by Contini, you really should read this paper and follow it with the here proposed modifications.

Your objective is to secure an AES key on the server end, because it needs to be available regardless of devices and the only ressources you can use are usernames and (bad) passwords.
The obvious strategy is to encrypt this key and only temporarily decrypt it when needed using the password. For this you derive a key from the password using a password-based key derivation function (PBKDF) and encrypt the key afterwards with AES-GCM, which will tell you whether the decryption is valid and the user is authorized as a bonus.
In regards to this, the paper will tell you to hash the password hash one more time on the server end. You replace this with the AES-GCM decryption of the key. Additionally you should use Argon2, scrypt, bcrypt or PBKDF (in order of preference) for the client-side password hashing.

So far for the modifications, now for a quick TL;DR of how the scheme roughly works:

Ask the server for access, include the username and the server (domain?) name
Receive the username, website and server-side secret dependent salt (even for usernames that don't exist in the database)
Do the password hashing and send the result to the server
Try to decrypt the AES key using the password hash
Grant or deny access based on whether the user exists and whether the hash was correct


What Diffie-Hellman parameters should I use?

I recommend avoiding Diffie-Hellman parameter generation.  Instead, use a standardized DH group with a sufficiently large modulus (2048-bit or larger).  For example, group #14 or #15 from RFC3526 (see sections 3 and 4) would be a good choice.  Alternatively, switch to the elliptic curve variant of Diffie-Hellman and use Curve25519.

The article you linked to is based on a great paper that surveys a variety of problems with how Diffie-Hellman is used in the real-world.  One part of the paper (section 4.2) describes how a well-funded attacker could feasibly break a 1024-bit Diffie-Hellman group.  At a high-level, the attack works as follows:

The attacker chooses one Diffie-Hellman group.
The attacker performs some massive computation for that group.
The attacker uses the results of that computation to break any key exchanges made using that group.

The authors point out that a large portion of the web sites that support TLS with DHE use one of only five 1024-bit DH groups.  They thus conclude that if a well-funded adversary performed five massive computations (one for each of the popular groups), the adversary could crack TLS Diffie-Hellman key exchanges cheaply and at a massive scale.  This lead many to believe that standardized DH groups are a bad idea, and that we should be generating a new group whenever possible.

I think this is misguided for a number of reasons.  First, group generation is hard to get right and can easily lead to much more disastrous vulnerabilities.  That same paper discusses "weak and misconfigured groups", and points out that "failure to generate Diffie-Hellman primes according to best practices can result in devastating attacks".

Second, the attack they describe on 1024-bit DH groups can still be applied to randomly generated 1024-bit groups.  The hope is that whatever key exchanges performed using your DH group just aren't interesting enough for anyone to bother spending the millions of USD required to break the group.  This isn't much comfort though.  In cryptography, we generally don't like "secure, except against rich people".  We aim for a higher standard: "secure against the combined resources of the human race for the foreseeable future".  DH groups with a large modulus can meet this higher standard, and it's OK if everyone uses the same large prime.

Note for TLS/SSL users: Use either ECDHE or DHE cipher suites (since these support forward secrecy).  With DHE, follow the above advice on groups.  With ECDHE, use the NIST P-256 curve (secp256r1), since Curve25519 is not yet supported.


Schnorr's signature scheme with addition of modulus secure?

There's no chance to hide private key $x$ in case of re-using $k$ by calculating in the ring modulus $q$.
Formula $\frac{s - s_1}{e_1 - e}$ is well-defined over the ring modulo any prime $q$. In particular, extended Euclidean algorithm would do the division.


Is there a correct way to generate a symmetric key?

Symmetric keys don't need to be in any particular format -- they're just a sequence of (pseudo)random bits.

Most programming environments provide some sort of "secure random" mechanism (a CSPRNG).  You can use this to acquire a byte array of the appropriate length (e.g. 32 bytes for AES256), which can be used as a key.  Be sure to pass in the raw bytes, and not, e.g., a hex-encoded string.

Alternatively, you may want to derive a key from some other source.  A Key Derivation Function (KDF) is a function that transforms some input into a key.  GPG uses a Password-Based KDF (PBKDF, also known as a "password hash") to transform a password into a symmetric key.

Many PBKDFs use an iterated hashing approach; you might be interested in reviewing the design of "PBKDF2", or see scrypt for a more modern design.  Generally though, as a developer, you can use an existing implementation and not be particularly concerned about the underlying details.

For completeness, there are also Key-Based KDFs such as HKDF that can derive symmetric keys from other keys, but I suspect that's not what you're after.


Is there a strong cryptographic reason for GCM's 2^39 - 256 bit limit?

In the same document the authors in section 2.1 specifies the plaintext size to be between $0$ and $2^{39}-256$ bits = $2^{36}-32$ bytes = $2^{32}-2$ blocks of 16 bytes.

That's the rationale behind the choice of the counter size. Given that requirement it will never overlap/wrap, which means you will never end up having repeating the "scrambling pattern" for the same message.

This constrains the maximum message size to $2^{36}-32 = 68.719.476.704 B$ approximately 64GB which didn't seem a problem to the authors.

Now, this choice of the counter constrains also the number of messages that can be protected under the same key at $2^{(128-32)=96}$ since the nonce is made by 96 bits.

If you look at section 3.1 of this paper by the GCM's original authors they gave the rationale above for their choices commenting that "any mode built upon a counter mode will have a similar tradeoff" {between maximum message size and number of messages under the same key}.

Now, you can easily modify GCM, by increasing the counter to 64 bits and decreasing the nonce to 64 bits and still have a secure authenticated encryption mode.
AES-CCM, for example, by specification support messages up to $2^{64}-1$ bytes.


There seems to be no specific condition on $m$ and $n$ except $m,n \geq 1$.

The LWR assumption isn't that the problem is hard for any arbitrary $m, n$, it's there it's true for the specific $m, n$ pairs we use in practice.  Obviously, for $m=n=1$, it's an easy problem; that's not particularly relevant, as we don't use $m=n=1$.

This is similar to the RSA assumption; that assumption isn't that it's a hard problem for arbitrary sized keys (it's not for, say, 10 bit keys); it's that it's a hard problem for the key sizes we use in practice (for example, 3072 bit correctly generated keys).


SSH over TLS isn't just an overkill, it's a software bloat / design creep.

Both protocols provides confidentiality, integrity, and authenticity guarantees, so using two is redundent. And coding for both of them would increase the size of the software, making it harder to maintain software quality, efficiency, and security.

Benefit of SSH

SSH is already a very good application data encapsulation protocol, and in fact, the most widely used SSH implementation "OpenSSH" allows you to setup your own service running side-by-side with sftp. In my opinion, SSH is easier to setup and have many desireable features for specialized application.

On the other hand TLS carries too much legacy, it has too many options that needs to be supported to maintain compatibility with existing implementations. Even if you implement no support for versions before TLS-1.3, incorporating support for it in code still require considerable amount of expertized skills.


Is there a companion algorithm for OTP to ensure integrity and/or authentication?

You can construct a one-time MAC that has similar properties to the OTP. Better still, it uses a fixed number of bits for each message.

Here's how it works. Choose the closest prime to your message block size. Let's say you plan to process 128-bit chunks of your message. Let's say there are $L$ such blocks.

The first job is to pick the first prime larger than $2^{128}$ which is $2^{128}+51$. Call this value $q$.

The key has two pieces. Let's call these $x$ and $y$ and choose these at random from the range $1$ to $q-1$.

Your MAC is then:

$mac(m, x, y) = m_L\times x^L + m_{L-1} \times x^{L-1} + ... + m_{1} \times x + y \mod q $

You basically evaluate a polynomial with a term for each block of the message. The co-efficient is the message block and this is multiplied by the key raised to the power of the current block number. All operations are done mod $q$.

Provided $x$ and $y$ and are used precisely once, this MAC is secure against all adversaries.


total effective key length of the AESX-192

The security bound for this construction is (PDF, section 4.7.3 in v4) $$\mathbf{Adv}^{\text{sPRP}}_{\text{AESX-192}}(\mathcal A)\leq \frac{2Q_sQ_{AES}}{2^{192}\cdot 2^{128}}$$ to be a strong PRP assuming AES can be modeled as an ideal cipher (not perfectly accurate but probably "close enough" here), where $Q_s$ is the number of "online" queries against a keyed oracle of the cipher and $Q_{AES}$ is the total number of AES evaluations for this.

So for an off-line brute-force search you actually get a 384-bit security strength, for a "online" security it breaks after $2^{160}$ queries. Therefore it may be easier to "just" use normal AES-192...


Bits of security vs collision resistance?

I am confused on the bits of security vs collision resistance

Well, here is what "bits of security" means; we say that a primitive offers $\ell$ bits of security if the best known attack against that primitive takes roughly $2^\ell$ operations.  Yes, that is somewhat imprecise (what is "roughly" and what is an operation?), but it is generally sufficient for discussions.

Bits of security for a block cipher depends on the key length (so like the example above with AES 128 with a 256 bit key)

Pretty much (assuming that the block cipher itself doesn't have any nongeneric attacks, and if we don't talk about birthday bound attacks or attacks against the ciphermode).
Nit: in general parlance, "AES 128" is AES with a 128 bit key; we'd call AES with a 256 bit key "AES 256"

Bits of security for a MAC is min(key bits of security, hash bits of security)

Well, here is where the general "bits of security" breaks down somewhat.  It is impractical to do any operation that does $2^{64}$ sequential steps (even if each step takes a nanosecond, we're talking about more than 500 years).  In most cases (e.g. doing a brute force attack against a key), this is not an issue; we can easily run things in parallel (e.g. rent a large number of cloud computers, or use a GPU farm), and so a large organization would have little issue in performing, say, $2^{64}$ operations in aggregate.  However, the generic attack against "size of the MAC" would be "generate the message we'd like, insert the guess of the MAC, and send that to the device under attack".  Since the device under attack would need to process each guess in succession, we cannot parallelize it (unless we have a large number of devices, all with the valid key; generally not the case), and so, in practice, attacks against the "hash length" (as you term it) are considerably harder than attacks against the key.

Bits of security for a hash function is l/2 or l-bits?

Depends on the attack you need to be strong against.  If it's a collision attack (that is, the attacker "wins" if he is able to find two messages that hash to the same value), it's at most l/2 (as there are generic attacks that work in $2^{l/2}$ time.  On the other hand, if you don't care about a collision attack, and care only about a preimage or a second preimage attack, it can be as much as l-bits (as the best generic attack takes $2^l$ time


Information leakage in real-time voice encryption

I'm not sure which post you're referring to, but one possible source of leakage results from using a variable-bit rate codec. If different sounds compress at different rates, than this will be reflected in the lengths of outgoing encrypted packets. By examining those sequences of lengths, it can sometimes be possible to accurately guess what phrases are being uttered.

See "Spot me if you can: Uncovering spoken phrases in encrypted VoIP conversations" by Wright, et al. This extends an earlier work, Language identification of encrypted VoIP traffic, in which the authors showed they could classify a speaker's language, encryption notwithstanding.

Padding the ciphertext packets, to, say, the nearest multiple of 128 or 256 bits can greatly reduce the ability of an attacker to make this type of attack. I would assume that using a non-variable bit rate codec would also work. Of course, there's a trade-off with bandwidth here; you'd have to weigh that against the security risks.

I strongly suspect assymetric crypto is not fast enough for the job. Typically, it's just used to establish a secure, authenticated channel so that users can agree on a symmetric key, which is used to encrypt the actual traffic.

Performing type of attack---looking at lengths, timings, etc. to infer information about content---is called traffic analysis.


It is because the values being calculated are the byte representation of a polynomial in a finite field, and if the polynomial is too large to be in the field it must be reduced.

The reduction polynomial for Rijndael is $x^8 + x^4 + x^3 + x + 1$, which has a byte representation of 0x11b, and after you have shifted the byte by 1 bit, the 0x100 is no longer required so 0x1b or 27 is XOR'd against the value to complete the reduction.


Can several run of a semi-honest protocol be used to infer malicious security?

Detection of malicious behavior can happen anywhere. However, it is not true that you can run semi-honest protocols and then check later. This is because such protocols can reveal the honest party's input when interacting with a malicious adversary. In such as case, even if you detect the cheating, security is not achieved. Thus, you need to make sure that no cheating happens that can break privacy; for correctness, it suffices to detect at the end. (There is a model called covert for which privacy can be breached as long as detection happens with good probability.)


Does an IV need to be used in AES CTR mode?

Yes, you need an IV in CTR mode and you do need to send it with the ciphertext, or at least make it possible for the encryption process to know it. Specifically, you need a nonce. The nonce can be anything, as long as it is unique so no key:nonce tuple ever repeats. The nonce is part of the counter. CTR mode operates by encrypting this value and XORing the result with the plaintext. When the next block is to be encrypted, the value is incremented by one and the process repeats.


Crypto algorithm identification (reverse engineering)

Is there a 2048-bit variant that is commonly used, or some kind of optimization that allows the next round for each block to be computed in parallel while still using an initialization vector?

Bit slicing is an optimization technique that consists in calculating $b$ instances of a function (e.g. $n$ block decryptions/encryptions) in parallel on a machine with $b$ bits. An apparent 2048-bit block size is consistent with a 64-bit cipher and a 32-bit bitslice. Bitslicing can only be done when the data for block operation $n+1$ doesn't depend on the output of block operation $n$, so it's useless for e.g. CBC mode but can be used for e.g. CTR mode.


FFT multiplication for RLWE key exchange

Sage itself has an internal negacyclic convolution, which is what is necessary here. To avoid type errors, we convert the polynomials to lists of coefficients, and work with those instead:

from sage.rings.polynomial.convolution import _negaconvolution_fft

n = 10 # degree 1024
Rq = GF(40961)
R.<X> = PolynomialRing(Rq)
S.<x> = R.quotient_ring(X^(2^n) + 1)
u = S.random_element()
v = S.random_element()

w_1 = S(_negaconvolution_fft(list(u), list(v), n))
w_2 = u * v
assert(w_1 == w_2)


Comprehension question on a signature protocol based on the RSA assumption

Assuming that $x$ is odd, then the answer is no for number (1); to the best of our knowledge, the attacker would not be able to either compute (1/x) or factor N, even with a huge number of sets $(a_i, v_i, m_i)$, even if he got to select the $m_i$ (and even the $v_i$) values.

This follows directly from the fact that no one knows how to factor an RSA number $n$ given an oracle that computes $F(z) = z^{1/x} \bmod n$ for odd $x$.

On the other hand, we have a definite yes for number (2); if an attacker gets two distinct valid triplet $(a_1, v_1, m_2)$, $(a_2, v_2, m_3)$, that is, with:

$a_1 = \left( G \cdot H^{-v_1} \cdot K^{-m_1} \right)^{1/x}\ \bmod\ n$

$a_2 = \left( G \cdot H^{-v_2} \cdot K^{-m_2} \right)^{1/x}\ \bmod\ n$

Then it is possible that he can construct a third triplet $(a_1^2 \cdot a_2^{-1}, 2v_1-v_2, 2m_1 - m_2)$; this will be a valid set as long as $2v_1-v_2$ and $2m_1-m_2$ are both in range; that will happen nontrivially often.  Note that the attacker can compute $a_1^2 \cdot a_2^{-1}$ using $\bmod n$ arithmetic; he can't compute $2v_1-v_2$ using $\bmod \phi(n)$ arithmetic; he has to use standard subtraction, and hope the value is in range, where "in range" means "a value that the verifier will not reject as silly".

As for the expense of finding new prime values $x$ every iteration, the obvious question is "why do they need to be prime?".  The only requirement that RSA places on $x$ is that it be relatively prime to both $p-1$ and $q-1$, where $p$ and $q$ are the prime factors of $n$. An easy way to handle this is during RSA key generation, you select $p$ and $q$ such that $p-1$ and $q-1$ have no small prime factors other than 2.  If you ensure that neither $p-1$ nor $q-1$ have any odd factors less than $2^{k}$, and you select odd values of $x$ less than $2^{k}$, then that value of $x$ will always work, even if it is composite.  On the other hand, perhaps there is something that this protocol needs besides "RSA works"; the paper discussing this protocol might mention any such concern.


Generating the keys for the RSA cryptosystem in probabilistic polynomial time

Short version: All the cool kids are using Randomized Algorithm !

Boring version:

Any deterministic (part of a) crypto system can be broken !  [Goldwasser Micali]
Primes density is pretty high (higher than one intuitively expects) as we talk of big numbers. Prime No. Theorem : #of primes between $1$ and $x$, $\pi(x) = \frac{x}{ln(x)}$ , So if randomly picking no.s usually means you have a fairly high chance of getting a prime.. :)
Primality checking with Rabin Miller (probabilistic) is way faster than AKS (deterministic)


Is there an upper limit to plaintext size in XSalsa20Poly1305?

As a comment points out, it’s most probably a mistake/error in the docs.

If you look at “What is the PRG period of stream ciphers such as RC4 or Salsa20?”, you’ll find an answer which explicitly points out the limits of Salsa20 (quote)

  …Salsa20 used as a stream cipher, it uses a 64-bit block counter and 64-bytes blocks, limiting its capacity to $2^{73}$ bits. After that, the counter would rollover, and thus the output.

That’s a 1180591620717411303424 bytes (around and about 1180591620 Terabyte) maximum size until rollover, which I wouldn’t really call “small”. But that might just be me…

For reference purposes, see the Salsa20 paper (PDF).

EDIT

  Comment by Eclipse:
  SecretBox uses Poly1305 so could it be something about how they work together?

I also don’t see any reason the use of Poly1305 would limit things. If you – for example – look at RFC 7539: ChaCha20 and Poly1305 for IETF Protocols, you’ll read a usefull hint (on page 20) which – from my point of view – practically excludes Poly1305 as the source of any “small message” limits.

Quote:

  …, the ciphertext length field in the construction of the buffer on which Poly1305 runs limits the ciphertext (and hence, the plaintext) size to 2^64 bytes, or sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to be exact).

When you look at page 6 of that RFC, you’ll read that that RFC assumes it’s safe to handle 247,877,906,880 bytes (nearly 256 GB) with Poly1305. So Poly1305 doesn’t really seem to be a limiting factor either which might explain a “small message” comment like that.

All that’s left is a potential limitiation in the implementation itself. If you can’t find “small message” limits in the sourcecode either – which you already checked and confirmed to not exists – an error in the docs is most likely. In the end, the statement …small messages seems to be nothing but a “small” glitch in the docs which causes superfluous confusion where it shouldn’t.


Kryptos : K1. What is the origin of the "palimpsest" keyword?

It was never determined how to derive the keyword PALIMPSEST from the sculpture or its text. It was, as you stated, found by brute-force hill-climbing algorithms.

One theory is that crib-dragging the morse phrase SHADOW FORCES reveals IMPS at SHAD, and working form there retrieving the entire keyword, but I find this far-fetched and implausible.

The keyword for K2 can be found by crib dragging morse phrases, but for K1 it´s still a mystery.


Would this image steganography technique be effective at avoiding detection?

On the one hand, I think that this could be considered a first step into the direction of adaptive steganography, because you do not use some blocks that you think that are easy to detect. In adaptive steganography we modify only the pixels of the image that are more difficult to model statistically and, consequently make the detection harder.
On the other hand, you use a $2\times 2$ block for hiding one bit so you are reducing the capacity. And for doing this, in some cases you need to make two changes! Two changes for hiding a bit is far from being optimal.
Currently steganography is much more advanced than this. You have cost functions that tell you which are appropriate zones of the image to hide information (the state of the art in spatial domain is the HILL [1] cost function), and matrix embedding techniques [4] that allows you to hide a lot of information modifying very few pixels. There is also a field that deals with Wet Paper Codes[2, 3], that makes possible reading a message without knowing which pixels have been modified. This gives you a lot of flexibility for building systems where you don't want to modify some kind of pixels.
[1]. A new cost function for spatial image steganography. Bin Li; Ming Wang; Jiwu Huang; Xiaolong Li. 2014 IEEE International Conference on Image Processing (ICIP), Paris, 2014, pp. 4206-4210.
https://projet.liris.cnrs.fr/imagine/pub/proceedings/ICIP-2014/Papers/1569891955.pdf
[2]. Writing on Wet Paper, J. Fridrich, M. Goljan, P. Lisonek, and D. Soukal, IEEE Trans. on Sig. Proc., Special Issue on Media Security, Eds. T. Kalker and P. Moulin, vol. 53, pp. 3923-3935, October 2005.
http://www.ws.binghamton.edu/fridrich/Research/WPC_TransactionsJournal1.pdf
[3]. Minimizing Embedding Impact in Steganography Using Trellis-Coded Quantization, J. Fridrich, T. Filler and J. Judas, Proc. SPIE, Electronic Imaging, Media Forensics and Security XII, San Jose, CA, January 17–21, pp. 05-01 - 05-14, 2010.
http://www.ws.binghamton.edu/fridrich/Research/tcq_v3.pdf
[4]. Steganography in Digital Media (Principles, Algorithms, and Applications). Cambridge University Press. 2009. ISBN: 9781139192903.


PAK Diffie-Hellman vs. sharing high-entropy key

Are there any advantages to “1.”, especially when users must communicate the password/key through a separate channel in both cases?

As the comments (1, 2) already indicated: the first option “1.” will be easier to communicate.
When you talk about a “high-entropy key”, I assume you are generating that high-entropy with a cryptographically secure random number generator. To make such a random piece of data easy to communicate among humans, you would need to convert it to something like Base64… which means “2.” will have a longer message which needs to be communicated between humans. The longer the message, the more room you’re providing for potential human error during that communication.
To keep human communication easy, you could stick to option “1.” and let users set a (low-entropy) shared password. You can always opt-in to a kdf if you want to make it computationally more difficult to crack attack the user-chosen passwords.
Please note that I’m assuming you generate and communicate that shared key without allowing impersonation. If you don’t authenticate communication, no entropy in this universe is going to help.
TL;DR
I would advise to prefer PAK Diffie-Hellman (as described in RFC5683) because it additionally offers authentication, while sharing a high-entropy key without authentication merely provides more entropy… but not a single bit of security which could prevent impersonation (man-in-the-middle) et al.


If you have an error in a cipher text block you can generally represent this as:

$$C'=C\oplus\Delta$$

Now if you try to decrypt this block using the previous ciphertext block $IV$ as IV you get $P'=IV\oplus D_K(C\oplus\Delta)$ which is completely unrelated to $P=IV\oplus D_K(C)$ assuming the block cipher acts as a pseudo-random permutation. As the input changed the chance for each plain text bit flipping are 50% (independently), everything else would be considered a weakness of the cipher.

Now for the second part:
Assume you have the errorneous message $C_1'=C_1\oplus\Delta$ and a normal $C_2$. The decryption $P_2'$ is then $P_2'=C_1'\oplus D_K(C_2)=C_1\oplus\Delta\oplus D_K(C_2)$ and as $P_2=C_1\oplus D_K(C_2)$, you see that $P_2'=P_2\oplus\Delta$ meaning the error of the previous block propagated perfectly into the next plain text.


handling junk bytes in chi squared character freq analysis

One approach you might try is applying additive smoothing via pseudocounts.  At its most basic, this can be as simple as adding 1 to the number of times each byte (or $n$-tuple, or whatever) occurs in your corpus before calculating the frequencies.
 This allows you to calculate a non-zero (although possibly very small) likelihood for any decrypted byte string, even those containing bytes that never appear in your original corpus.

So, for example, if you started with a 1,000,000 byte corpus of English text, where the byte e occurs 124,319 times and the byte ` occurs 0 times, you'd increment those counts to 124,320 and 1 respectively, and the total number of bytes observed to 1,000,256, before dividing the counts by this total to obtain the smoothed frequency of each byte in the corpus (e.g. 1 / 1,000,256 ≈ 0.000000997 for the byte `).

The mathematical theory behing why this seemingly arbitrary adjustment makes sense is kind of tricky, but basically it turns out to be a sensible way to adjust the probabilities obtained from a series of observations to account for the possibility that some rare but possible outcomes might simply not have appeared by chance during the finite number of observations made.

(In particular, analyzed in the framework of Bayesian statistics, this smoothing rule turns out to yield the same expected posterior probabilities as we'd get by starting from a "flat prior", i.e. the assumption that any distribution of byte frequencies is equally likely, and repeatedly applying Bayes' theorem to update this belief as we observe new bytes in the corpus.  Furthermore, if we did have reason to believe a priori that some bytes should be more likely than others even before looking at the corpus, we could include this prior information by assigning the more likely bytes pseudocounts higher than 1.)

Of course, if you're using a given table of byte / letter frequences instead of compiling your own, you'd have to guesstimate the amount of smoothing needed yourself.  But you can still do it: just multiply each frequency by some assumed corpus size (e.g. 1,000), increment them by one and (if needed) rescale them back down so that they sum to one again.


Depends how secure you want it to be. Do you want to be safe against MITM, against passive attackers, against active attackers, against replay attacks, ... and so on.

Even though that posting links is not that good, I would strongly suggest to read that paper:
http://cs.unc.edu/~fabian/course_papers/needham.pdf
"Using Encryption for Authentication in Large Networks of Computers" - Needham, 1978.

On the second page it has a nice description of quite a secure protocol for that. ("Protocol 2. With Public-Key Algorithms "), though you would have to modify it since you don't have a CA which both parties trust. (and, as a result, be vulnerable to some attacks)

Also, take a look on TLS. TLS could be with server authentication, client authentication, or both present or both missing. Option 4 is for you, since you do not have any CA's mentioned in your question.


You do not need to use XOR as the combining operation. You can use modular addition as the encryption function and modular subtraction as the decryption function and it will remain information theoretically secure.

XOR is typically used because it is convenient -- it is its own inverse (an "involution"), and it is smaller/simpler to implement in hardware than adders and multipliers.


Is there a PAKE algorithm that is fully resistant to a server data leak?

The server's data is public

That assumption makes the idea of a PAKE undoable.

If the attacker has access to all the server's data, here's what he can do: clone the server, place the clone in his lab, and then have his client perform attempted negotiations based on all the passwords in his dictionary.  Because the clone works exactly like the original server, the clone would access the correct entry in his dictionary, and so the attacker now knows the password.

What this means is that you need to change an assumption somewhere.

People have attempted to solve this problem; attempted solutions include having an uncopiable HSM hold a piece that the server needs to perform the authentication, and having multiple servers jointly perform the authentication (so that no one server knows enough, so that the adversary would need to break into all of them).  Since I don't know what your limitations are, I don't know if these ideas would work for you (I suspect not).

As for your idea:

  client can hold secrets

That feels like it's in the right direction; if the client can hold a private key (and the server would hold the corresponding public key), well, you still need to address MITM attacks (how does the client know he's actually directly talking to the real server), but you have solved the 'cloning the server allows someone to test passwords' problem.  Of course, this direction is getting pretty far from the concept of a PAKE (which assumes that the client's knowledge of the password is the only thing it can use to authenticate).


In the field $GF(2^8)$, $x^{254} = x^{-1}$ (except for $x=0$, as $0^{-1}$ doesn't exist; for AES, that's treated as 0), and so it's two ways of describing the same thing.

When we talk about AES, we typically use the $x^{-1}$ nomenclature; for whatever reason, your class decided to go with the $x^{254}$ one.


Why are MACs not included when defining Protocols?

It depends on the protocol. In general IND-CPA secure ciphers are assumed. That would mean that confidentiality is taken care of by the cipher.

If integrity and/or authenticity are also required then it should be made explicit in the protocol. In that case it is however perfectly possible to use one key, e.g. by using an authenticated cipher such as GCM.

If ciphertext only attacks are excluded depends on the context.


Is this a structural weakness of Feistel networks?

If such a network had only a single round, then you might have a valid concern. This is why there needs to be least three rounds, so that every bit from L can potentially affect every other bit from L (via R from the second round).

It isn't a structural flaw, because multiple rounds are assumed. Changing this round structure would mean that it was no longer a Feistel network, and you would lose the reversibility of each round (when the key is known).


Feige–Fiat–Shamir identification scheme: Question about a part of the ZK protocol

If $b$ was always the same value, you could convince the Verifier that you have the private key even though you actually don't!

Case $b = 1$:

Instead of sending $x = {\text{randNum}}^2 \bmod n$, the false Prover can send $x = {\text{randNum}}^2 / \text{pubKey} \bmod n$.

Assuming the Verifier sends $b = 1$, the false Prover can then send $\text{randNum} \bmod n$.

When the Verifier verifies the response, they check if ${\text{randNum}}^2 == (({\text{randNum}}^2)/\text{pubKey} \bmod n) \times \text{pubKey} \bmod n)$, which simplifies to ${\text{randNum}}^2 == {\text{randNum}}^2 \bmod n$, and that's obviously true. So even though the false Prover doesn't actually have the private key, the verification succeeded. But here's the catch: If $b$ turns out to be $0$ instead, they'd have to send $\sqrt{x} \bmod n$ in the final step. This is computationally infeasible.

As you observed, if the false Prover sends $x = {\text{randNum}}^2$ and $b$ turns out to be $0$, they can pass the verification. But if $b = 1$, the false Prover can't pass the final step, as they don't know $\text{privKey}$.

In summary, the false Prover has to commit to $b$ either being $0$ or $1$ before sending $x$. Each guess has a 50/50 probability of being correct. So after $t$ rounds, the chance of the Prover actually being a false Prover is $(1/2)^t$


Does $i^n=j^n$ for $i, j \in GF(2^q)$ and $i \neq j$ for some $n<2^q-1$

Actually, the answer is "such an $n$ exists iff neither $i, j$ are 0".

We have $x^{2^q-1} = 1$ for $x \ne 0$ (because multiplication in $GF(2^q)$ over the nonzero elements forms a group of order $2^q-1$), hence if $i, j \ne 0$, $n=2^q-1$ is one answer (if not necessarily the minimal one).

If we add the simple observation that if one of $i, j$ is 0, then $i^n = j^n$ cannot happen; this gives us the full answer for all possible values $i, j$.

If you want to extend the question to find the minimal $n$, then you can do this if you know the factorization of $2^q-1$.  That's because if $i^n = j^n$, then $n$ must be a divisor of $2^q-1$; hence you can just search through the divisors of $2^q-1$.

If $2^q−1$ is a Mersenne prime, then no such $0 < n < 2^q-1$ will exist, no matter what $i,j$ are. However, if it is composite, then such $i,j$ will exist (and, in fact, you can find such an $i,j$ pair for every nontrivial divisor $n$ of $2^q−1$). If $g$ is a generator, then two such values are $g^{a\cdot(2^q−1)/n}$, $g^{b\cdot(2^q−1)/n}$ for $0\le a,b<n$


The crucial property you want to achieve CPA security is that each combination of $\mathrm{IV}$ and $\mathrm{ctr}$ is used at most once, since you essentially derive a key from this combination and use it to encrypt the corresponding block with the one-time pad. If you choose $\mathrm{IV}$ uniformly at random from a large enough space, this will be the case with high probability for both variants you describe.

If $\mathrm{IV}$ is a packet counter, $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ is still fine if you reserve enough bits for both $\mathrm{IV}$ and $\langle \mathrm{ctr} \rangle$ to exclude overflows. The variant $\langle \mathrm{IV} + \mathrm{ctr} \rangle$, however, now becomes insecure: If two packets are encrypted where the first one contains at least two blocks, the second block of the first packet will be encrypted with $\langle 1 + 2 \rangle = \langle 3 \rangle$, and the first block of the second packet will be encrypted with $\langle 2 + 1 \rangle = \langle 3 \rangle$. Hence, an attacker who knows the contents of the second block in the first packet can learn the first block of the second packet. As long as you only increment the combination of $\mathrm{IV}$ and $\mathrm{ctr}$ by one for the next block, this problem persists unless you ensure there is a large enough gap between two packets. This is exactly what $\mathrm{IV} || \langle \mathrm{ctr} \rangle$ ensures.


SSL Pinning security: can MitM generate the same public key?

It's astonishingly difficult.

With RSA, it's literally a mathematical impossibility.

With Weierstrass, Montgomery and Edwards elliptic curves, the possibility of generating the same public key from different private key should be impossible assuming the private key scalar value doesn't overflow the order of the generator of the group.

With Hash-based digital signatures, this may be possible, because the public key is the tree hash of many one-time hash signature public keys. But still, finding such public key collision is as difficult as finding any regular hash collision. (not to mention real-world hash signatures often use randomized hashing).

Lattice-based schemes have the mathematical possibility of generating colliding public keys if the public component reduces the dimension of the private component, but that's very improbable. However, it should be noted, even the public component are randomly generated in most candidate schemes in NIST Post-Quantum Cryptography Project.


Why R value in signatures have to be 'calculated' values and not just a random numbers?

The DSA signing algorithm involves the value $k$ not only at the step $r=g^k$, but also when calculating $s = k^{-1} (H(m)+rx)$.

So if you assign $r$ randomly, then you would need to calculate $k$ for the calculation of $s$, which is the dlog of $r$ to base $g$.

The argument of Biv's answer is of course valid too: If you choose $r$ randomly, you can't be sure that it is actually in the subgroup generated by $g$. In the verification process you need this fact, so that different powers of $g$ cancel each other out.

Considering ECDSA: Actually, it is exactly the same algorithm, just the additive notation instead of multiplicative. And of course, that the actual addition in elliptic curves have their own unique definition. For example, to calculate modular exponentiations, usually square-and-multiply is used. In additive notation, this is just called "double-and-add", as noted in the Wiki article as well.


When is an asymmetric scheme considered broken?

I think you are referring to Colin Percival's Everything you need to know about Cryptography, in one hour in which he observes:

  An asymmetric authentication scheme is considered to be
  broken if an attacker with access to the verification key can
  generate any valid ciphertext, even if he can convince you to
  sign arbitrary other plaintexts.

This is called a chosen ciphertext attack, abbreviated CCA in literature.

I'm going to look at the RSA case. In the case of RSA, decryption given a ciphertext $c$ is $r = c^d \mod n$ and signing is $s = p^d \mod n$. As you have no doubt gathered, these both use $d$ the private key. So for the purposes of RSA, the two operations are related (this is a trapdoor permutation). However, assuming they weren't, being able to convince an attacker to sign arbitrary plaintexts may compromise the signing key and allow the attacker to pass themselves off as you.

Next up, actually exploiting a cryptosystem such as RSA. This paper discusses encrypting RSA properly (the use of padding) but also contains the observation that:

$$\epsilon_{n,e}(m_1)\epsilon_{n}{e}(m_2) = \epsilon_{n,e}(m_1m_2)\mod(n)$$

Re-writing this using slightly more familiar notation:

$$(m_1^e \mod n)(m_2^e \mod n) = m_1^e m_2^e \mod n = (m_1m_2)^e \mod n$$

Now, the paper notes that chosing $C\prime = C\cdot 2^e$ then $C\prime = m^e2^e$ which is equivalent to $(2m)^e$. Decrypted this is $(2m)^ed = 2m \mod n$ and so the attacker, having access to $2m \mod n$ knows $m$.

From a practical point of view, the attacker still needs to acquire the decrypted output. The attack doesn't make any assumptions as to how they achieve that, but it does demonstrate an exploit of RSA. To counter this, continue reading that paper; specifically, one should use an appropriate padding scheme.

Any crypto-system which has a similar homomorphic property will be vulnerable. For example, these slides explain similar behaviour in ElGamal.


Identifying the type of algorithm for a PRNG that uses modular multiplication and addition

These are called Linear Congruential Generators, and their maximum period is the size of the modulus (e.g., $2^{31}$ in that case).

Finding the previous value is a matter of inverting the iteration: $(\text{state} - 12345) \cdot 1103515245^{-1} \bmod 2^{31}$.


Need Help Reversing my Encryption Algorithm

Unfortunately, you have created an un-invertible cipher, that is why you can't decrypt it.

  Then I would subtract 127 from 226 so it will correspond to ASCII

Since you do charDec * keyLength this will not work when the key is longer (Imagine a 10 char key, you would get 1120 as your intermediate result, you won't get this back into ASCII range with your final subtraction).

So what you would need is to take your result modulo 256 (or modulo 127 if you want to stay in the ASCII range).
But then your scheme will basically amount to a % b = c, where to decrypt you have to recompute a, from b and c. There is an infinite number of solutions. You cannot decrypt.

You could study the design and internal operations of an existing cipher like DES, to see how they achieve invertibility and confusion at the same time.


What are the main weaknesses of a Playfair cipher, if any?

It's a quite a weak cipher, being better than a simple substitution cipher by only using digraphs instead of monographs.

An interesting weakness is the fact that a digraph in the ciphertext (AB) and it's reverse (BA) will have corresponding plaintexts like UR and RU (and also ciphertext UR and RU will correspond to plaintext AB and BA, i.e. the substitution is self-inverse).
That can easily be exploited with the aid of frequency analysis, if the language of the plaintext is known.

Will chaining Playfair with a substitution cipher help?
Nope... The (monoalphabetic) substitution cipher will act (almost completely) transparent against the frequency attack. Eventually, the Playfair cipher is a digraph substitution cipher itself. (But it will make the resulting cipher not self-inverse anymore.)

Well, polyalphabetic ciphers are a whole different case of course. It's still a play-toy for today's computers, but it'd completely render the text unbreakable in that era. But then again, we needed machines like Enigma to properly and acceptably implement it. The German Enigma, if I'm not mistaken, implemented a polyalphabetic cipher.


A block cipher is a family of permutations where the key selects a particular permutation from that family. With a tweakable bockcipher both key and tweak are used to select a permuation. So tweak and key are pretty similar.

The main difference are the security and performance requirements for a tweak:

Changing a key can be expensive, changing a tweak must be cheap.
Being secure when using attacker chosen, or at least related keys are not primary security properties of a cipher. Typically they're analyzed assuming a randomly chosen secret key. Related key attacks are rather academic. For example AES is still considered secure despite related key attacks against it.

Related or attacker chosen tweaks must still be secure. The tweak is often a counter, so tweaks are often related.

If you look at Threefish, tweak and key are pretty much treated in the same way. Changing either is cheap, and it doesn't suffer from related key attacks.

If on the other hand you'd take AES-256 and use part of the key as tweak, that wouldn't work well. Rekeying AES has a cost, and it suffers from related key attacks.

One application of tweakable block ciphers is disk encryption. You encrypt each block with the same key, but a tweak that corresponds to the block index. Currently we usually don't use a tweakable block cipher for this, but rather XTS mode, which turns a normal block cipher into a tweakable block cipher.

Such a tweak counter mode(not sure if it has a standard name) is generally nice. It's quite simple, similar to ECB. It's parallelizable and doesn't suffer from ECB's weaknesses. It also doesn't fail as catastrophically as CTR mode when a key(or key-iv pair) is reused.


You wouldn't be a Dave for presenting RSA, but you would be a Dave for following this description to implement anything, and you risk creating Daves with this presentation. I'm not saying you shouldn't do it, but you should emphasize that this is only the mathematical basis of RSA and a lot more is involved in making it do something useful.

Your description is mostly correct, with just one minor error: in any remotely modern use of RSA, key generation is done a bit differently: first you choose either $e=3$ or $e=65537$, and then you choose $p$ and $q$. It's done that way for performance, but it also highlights an important thing: $e$ and $d$ are not symmetric. You cannot swap them. You cannot “encrypt with the private key”: that's just a bit of popular nonsense that stems from an incomplete understanding of RSA.

There are also few inaccuracies that don't really matter. Alice calculates $d$ at step 2, not each time she receives an encrypted message. Or Alice might not calculate $d$ at all, because rather than calculate $m = c^d \bmod n$ to decrypt a message, she might perform an equivalent calculation nicknamed “CRT” which is a bit faster. But at this level of detail, these are  unimportant.

This is a nice application of mathematics that's generally understandable by people with just a bit more than high school math. But it is of no direct use to anyone using RSA: your cryptography library hides the details for you. In fact, ideally, when you're writing code that uses cryptography, you shouldn't have the letters "RSA" in your code any more than you should have the letters "AES". But in the real world, programmers often need to care about more details. And as a point of interest for non-programmers, this does not give an accurate insight in the kinds of problems that cryptographers and cryptography implementers work on.

As a cryptography implementer, here's the kind of things I've worried about that are related to RSA:

Am I using the right tool for the job? RSA is more popularly known for encryption, but signature is at least as important an application. Signature is not quite dual to encryption: there are symmetries, but there are also many differences.
Is my implementation of computation on large integers (bignums) vulnerable to timing attack and other side channel attacks?
Is my use of RSA properly padded? Plain RSA has more holes in it than Swiss cheese. The reverse side of the coin of RSA's mathematical simplicity is that it's easy to construct relations involving plaintexts or ciphertexts. For example, $c_1^d c_2^d = (c_1 c_2)^e \bmod n$, so if I happen to know what $c_1$ and $c_2$ decrypt to, I can decrypt $c_1 c_2$. And that's just the simplest example.
There are two ways to solve this problem. One is to restrict what gets encrypted. This is the approach in RSA-KEM, where RSA is used solely to encrypt a freshly generated random number. Not a number within a certain range or anything fancy like that: it would defeat the point. And then you have to use that random number in a very specific way. The other solution is to add padding, which restricts which ciphertexts are valid, in order to break mathematical relationships between ciphertexts.
Oh, but if we restrict which ciphertexts are valid, then we open a whole class of attacks: padding oracle attacks. The basic principle is that Eve sends a message $c$ and gets Alice to try to decrypt it. So Alice calculates $c^d \bmod n$ and finds that $c$ is invalid. She might reply to Eve, or she might keep silent but Eve still finds out that the message is invalid because Alice doesn't do what she would do with a valid message. Maybe the difference is even just in the timing of Alice's response. Whatever it is, if Alice is not careful, merely probing with a few thousand ciphertexts, just to know whether each ciphertext is valid or not, can let Eve reconstruct the key. This type of attack is known as an adaptative chosen ciphertext attack.
Historically, the first padding mode for RSA was the one known as PKCS#1 v1.5, and it is prone to this kind of oracle-based adpatative chosen ciphertext attack, mainly Bleichenbacher's attack (one of them) and Manger's attack. The math behind this attack is a little heavier than the basics of RSA, but it doesn't need anything advanced, it just requires somewhat more equations.
Historically? Not just historically. Bleichenbacher's original paper was published in 1998. The latest variant of his attack, with practical impact on many TLS implementations, was The Nine Lives of Bleichenbacher's CAT, published in 2018. Another year, another Bleichenbacher variant.
PKCS#1 v.5 is deprecated, but still in real-world use. For encryption, OAEP should be used instead. For signature, PSS should be used instead. They aren't panacea, but they're considerably easier to get right. They're more complex functionally than PKCS#1 v1.5, but they leave less room for subtle implementation mistakes that break the security.
Decryption is the hardest operation to implement, because it combines the secret key with an input (the ciphertext) that's potentially chosen by an adversary. After calculating $m^d$, you need to decode the padding, and this is where mistakes are very easily made. The slightest timing difference in reacting to invalid padding can allow an adversary to reconstruct the key via Manger's attack or Bleichenbacher's attack.
Signature is usually easier than decryption because the input is more constrained. Encryption and verification are easier because they don't involve the secret key. But that's not to say that they're easy. For example, even in the past few years, implementations of RSA signature verification have been caught forgetting to verify some parts of the input, allowing forged signatures to go through — another type of attack due to Bleichenbacher.
RSA key generation must obviously involve a random generator, and getting random generation right is a hard problem. (Fortunately your operating system often solves it for you. I'm not so lucky: I often work on the part of the operating system whose job it is to solve it for you! But if your operating system solves it for you and you don't hook directly onto that, you're definitely being a Dave.)
RSA encryption must also involve a random generator, because it must not be deterministic. If encrypting the same message twice lead to the same ciphertext, it would be very easy to guess mostly-predictable ciphertexts. For example, if I know that a ciphertext is the encryption of either "Yes" or "No", with a deterministic public-key encryption scheme, I would just need to encrypt those two plaintexts, and to compare the results with the ciphertext. Thus all public-key encryption schemes are non-deterministic. PKCS#1 v1.5 and OAEP both do it by concatenating the message with some random bytes, as part of the padding. PSS also uses random padding, although for signature the randomness is not an absolute necessity.
Of course there's the usual risk of implementation mistakes. What if someone claims their public key has $n=0$? or $e=1$? or $e=n$? or $n$ is a 1210463558412104635584-bit number? or $n$ is a 2049-bit number?

Twenty years of Attacks on the RSA Cryptosystem by Dan Boneh is good reading. 20 years later, a lot of it is still relevant. RSA is so difficult to get right that there's a push to stop using it. Of course, it helps that elliptic-curve cryptography can do pretty much everything that RSA can do, and for the most part does it faster and with smaller ciphertexts and signatures. ECC math is considerably harder, but it's easier to translate to secure implementations (perhaps not so much for intrinsic reasons than because people have learned from RSA and ECC is standardized with formats and protocols that leave less room for mistakes).


how to represent message as an integer between $1$ and $n-1$

How do you represent integers on a computer? In binary format:
$$71_{dec} = 100\,0111_{bin} $$

How do we represent letters on a computer? (Mostly) in ASCII format (and ASCII is in binary):
$$\text{A} = 100\,0001_{bin}$$

How do we represent more than one letter on a computer? We concatenate the seperate letters. We use blocks of 7 bits and not 8 bits to save space:
$$\text{Hello} = 100\,1000\,1100\,1011\,1011\,0011\,0110\,0110\,1111_{bin}$$

Now we can read this number as integer:
$$100\,1000\,1100\,1011\,1011\,0011\,0110\,0110\,1111_{bin} = 19540948591_{dec}$$

With this number we can use the normal El-Gamal algorithm. If the number is bigger than $n$, than we have to split the initial message into smaller parts. It doesn't matter how exactly you split it, but be sure that the decryptor knows how you did it so he or she can decrypt it again. Oh, but be warned: El-Gamal is not secure without additional security measures.


You could have "protocol ID's" which describe the set of primitives and parameters each library version is capable of using. You may deprecate older ID's once they become obsolete by just removing them from some future version, this way you can reject files which are deemed too old (or too recent) and thus unsupported, as long as you don't change how you read the ID's.

To illustrate, suppose you have your initial v1 library, with this sole valid hash/cipher/kdf combination:

<MD4, DES-CBC, MyHomemadeKDF> = 0x01

Thus, because this is the only combination available, all files encrypted with v1 will bear the protocol ID 0x01 (somewhere before the header, in plaintext, next to the file version) and this is recognized by v1.

You then realize this is a pretty poor choice of algorithms, and decide to deprecate it. You create your v2 library, remove 0x01 from the protocol list, and add 0x02 and 0x03:

<SHA256, AES-128-CTR, PBKDF2/128/10000> = 0x02
<SHA512, AES-256-CTR, PBKDF2/128/50000> = 0x03

At this point, any attempt to feed it a file encrypted with your v1 will fail, because its ID is 0x01, which is not recognized by v2 as a valid protocol. Similarly, trying to give a v2-encrypted file to your v1 library will also fail, since the file is using a more recent protocol which v1 does not recognize.

Now, an attacker can obviously change the version number, and cause the software to fail. This cannot be avoided, and in this respect is not important, but can be detected easily: if the attacker changes the protocol ID to an invalid one, the software will complain the file is incompatible, and on the other hand, if he does change the protocol ID to a valid one (say 0x02 to 0x03, for v2) then decryption will clearly fail since you're using the wrong algorithms. You can implement a sanity check in the form of an extra HMAC if you really want to make sure, something like an extra header field:

$$\mathrm{HMAC}(K, \mathrm{ProtocolID} ~ || ~ \mathrm{FileVersion})$$

Which the library can use to verify the ID or file version were not tampered with ($K$ is the encryption, or a derived, key). Either the attacker changes those, or he tries to mess with the encrypted header and HMAC's, he gets busted either way. This way he should not be able to manipulate anything.

This is similar, in essence, to the "cipher suite" concept used by SSL/TLS, which uses them to negociate which algorithms should be used for key exchange and secure communication. You could use a plugin system to transparently let the user decide which set of primitives he would like to accept or reject.

The ID's don't have to be monotonically increasing, as long as you don't reuse them, and so you might prefer deterministically deriving them from the names of the primitives involved just for robustness.

If you end up doing something like this, make sure to provide facilities to upgrade files from one version to the next so you don't confuse users who still have files encrypted with old algorithms.

However, as you want simplicity, this may be overkill as a full-blown version management scheme. How simple does your API need to be? Since your library seems to be very high-level, I imagine you'll have a small toolchain of encryption and decryption programs to go with it eventually? Like OpenSSL's enc?


The quoted sentences means: if there is a collision among the MACs of the $2^{(n+1)/2}$ messages submitted, the attacker playing the distinguishing game announces that the oracle is a random function; else announces that the oracle is CBC-MAC.

This works because the messages submitted differ only in their first block, thus will never collide under CBC-MAC, when they collide with odds $0.632\dots$ (by the birthday "paradox") for a random function. The attacker employing the strategy outlined in a game where the objective is distinguishing between an oracle implementing a random function, and an (equally likely) oracle implementing CBC-MAC with a fixed random key, will have an advantage compared to announcing a result at random.

Update: to prove that there are never collisions with CBC-MAC, assume that there is such collision between two messages identical in all but the first block; use that a block cipher with a fixed key is a permutation over the set $\{0,1\}^n$; and conclude that the first block must be identical in the two messages.

So far, this is purely a distinguisher, without much practical applications. However the paper goes on to explain another attack, which I'll illustrate in a simplified version below.

Assume CBC-MAC using messages of three blocks, a block cipher of $n$ bits, and $n$-bit output. The attacker obtains the MAC of $2^{(n+1)/2}$ messages $M_j=j||j||0$ where the first two blocks are $j$ and the third block all-zero. Odds that a collision on the MAC occurs is about $0.632\dots$ (both for a random function and CBC-MAC). If that happens for messages $M_a$ and $M_b$, the adversary submits $M'_a=a||a||1$ and $M'_b=b||b||1$. If the MAC is CBC-MAC, there will with certainty be a MAC collision between $M'_a$ and $M'_b$, whereas odds of such a collision would be $2^{-n}$ if the MAC was a random function.

This allows computing a second preimage of a message with any desired third block, after little more than $2^{n/2}$ queries.

This attack is known as a birthday forgery. It is briefly discussed in ISO/IEC 9797-1, which standardizes CBC-MAC, as early as in the 1999 edition, with attribution to Bart Preneel and Paul C. van Oorschot: MDx-MAC and Building Fast MACs from Hash Functions, published in the proceedings of Crypto 1995.

For in-depth coverage of similar attacks on CBC-MAC, see the work of Antoine Joux, Guillaume Poupard, and Jacques Stern: New attacks against standardized MACs, published in the proceedings of FSE 2003; or/and Karl Brincat and Chris J. Mitchell: New CBC-MAC forgery attacks (preliminary zipped version here), published in the proceedings of ACISP 2001.


Why was Davies–Meyer chosen over Miyaguchi–Preneel most of the time?

Some ideas (not a definitive answer):

Davies–Meyer is one of the two simplest among the 12 secure methods by which a block cipher and XOR can be turned into an iterative hash with one encryption per block, per the analysis of Bart Preneel, René Govaerts, Joos Vandewalle's Hash functions based on block ciphers: a synthetic approach, in proceedings of Crypto 1993.Note: in the above table, the block cipher $E$ uses its first argument as key.
Davies–Meyer (method 5) is the only of the 12 that works with a block cipher having a key of width different of its block without needing an adapter (the g in the first drawing of the question).
When the key is wider than the block, that characteristic 2 makes Davies–Meyer use less encryptions for large messages, and that can translate into a speed advantage.
MD4, which was influential on MD5, then SHA, SHA-1 and SHA-2, essentially used Davies–Meyer (except for replacement of XOR with modular addition on a word).


Performing EdDSA/Ed448 employing Montgomery ladder

According to Alternative Elliptic Curve Representations,  each other point $(x1,y1)$ of Edwards448 corresponds to the point $(u,v)$ of Curve448, where:
$u = y1^2/x1^2$
$v = y1*(2-x1^2-y1^2)/x1^3.$
Under this isogenous mapping, the base point $(G1x, G1y)$ of Edwards448  corresponds to the base point $(Gu,Gv)$ of Curve448. The dual isogeny maps both the point at infinity and the point $(0,0)$ of order two of Curve448 to the point $(0,1)$ of Edwards448, while each other point $(u,v)$ of Curve448 corresponds to the point $(x1,y1)$ of Edwards448, where:
$x1 = 4*(u^2-1)*v/((u^2-1)^2+4*v^2)$
$y1 = u*((u^2-1)^2-4*v^2)/(2*(u^2+1)*v^2-u*(u^2-1)^2).$
under this dual isogenous mapping, the base point $(Gu, Gv)$ of Curve448 corresponds to a multiple of the base point $(G1x, G1y)$ of Edwards448, where this multiple is $l=4$ (the degree of the isogeny)


Mathematically/Theoretically calculating time to brute-force RSA encryption keys for a quantum computer vs a Classical computer?

Is there any way to theoretically, by the use of mathematics, to calculate the time taken to brute-force RSA keys?

Even classically, this is not so easy as you seem to imply.

RSA is based on the hardness of the integer factorization problem. The fastest classical algorithm known that solves this problem is the General Number Field Sieve (GNFS), and it solves integer factorization in subexponential time, or $\exp((\sqrt[3]{64/9}+o(1)) (\log N)^{1/3} (\log \log N)^{2/3})$ where $N$ is the modulus, and $\log$ refers to the natural logarithm.

However, we can't easily calculate an exact running time using this formula. Asymptotic running times hide constant values, which can vary wildly depending on the algorithm. Additionally, they don't tell us anything about what kind of parallelization may be possible.

GNFS happens to be a very complex algorithm. It involves a significant number of parameters. There are four different "stages" to the algorithm. Some stages can be made to take more time, in order to make the other stages faster. Additionally, some stages are easily parallelizable, while others are not, or only to a limited degree. In other words, coming up with the right set of parameters in order to minimize the total time to break an RSA modulus is very far from trivial. Let alone somewhat accurately estimate how much time it will take.

So unfortunately there's no easy answer to this question. However, you can get an idea by looking at some numbers that have been successfully factored.

  How would one calculate the time to brute-force RSA keys using a quantum computer?

This is easier to calculate but at the same time impossible. Integer factorization can be done using Shor's algorithm on a quantum computer. This algorithm runs in polynomial time, $O((\log N)^2 (\log \log N) (\log \log \log N))$. From this paper you can see that the number of logical qubits required are approximately $2 \log N$, and the number of logical quantum gates $4(\log N)^3$.

As mentioned in the paper, these logical qubits and quantum gates would require many physical qubits and quantum gates to actually implement. It's still not certain whether quantum computation is even possible on a large scale, due to issues with quantum decoherence. So again, I'm afraid there's no answer to this question. How could you possibly estimate the running time of an algorithm on a computer that doesn't yet exist?


Explanation of the Decision Diffie Hellman (DDH) problem.

The Computational Diffie-Hellman (CDH) problem is:

  Given some group $G$ and group element $g$, and the elements $g^a$ and $g^b$, compute the value $g^{ab}$.

The Decisional Diffie-Hellman (DDH) problem is:

  Given some group $G$ and group elements $g$, and the elements $g^a$, $g^b$ and $g^c$, determine whether $g^c = g^{ab}$

These are obviously related problems, the difference is that the CDH problem asks us to derive the DH shared secret, while the DDH problem just asks us to recognize it.

In addition, the CDH problem appears to be potentially harder, in this sense: if we're given an oracle to solve the CDH problem, we can easily solve the DDH problem (simply by handing $g$, $g^a$ and $g^b$ to the oracle, have it compute the value $g^{ab}$ and comparing that value to $g^c$.  In contrast, there's no known generic way to solve the CDH problem given a DDH oracle.

As for why the DDH problem comes up so often (and in cases where one would naively expect the CDH problem to to appropriate), well, many protocols do a DH-type computation, and then use the value $F(g^{ab})$ (for some function $F$); breaking the protocol may allow an attacker to recover the value $F(g^{ab})$.  Now, recovering this value would allow us to solve the DDH problem (by comparing that value to $F(g^c)$); hence, breaking the protocol would allow us to solve the DDH problem; or equivalently, if the DDH problem is hard, the protocol is secure.  However, if the function $F$ is one-way, recovering the value $F(g^{ab})$ doesn't give us the value $g^{ab}$, and so there is no reduction of the security of the protocol to the CDH problem.


In a AES-CBC + HMAC architecture, Is it secure to send a second IV in a message to a device incapable of producing satisfactory random numbers?

And what is the best way to send this IV?

CBC IVs need to be unpredictable to attackers. If you just send them along your other IV they are no longer unpredictable, hence encrypting them as well would be the way to go and should provide reasonable security.

  plain-text IV || cipher-text || HMAC-SHA256

What you are doing here is the infamous Mac-Then-Encrypt with CBC. This is a really bad idea. A really, really, really bad idea. This is the source of many attacks on TLS. Please, learn from the past mistakes done with TLS and use a pre-made authenticated encryption mode, such as EAX or CCM, or at least Encrypt-Then-Mac with CTR.


What does the $\|$ operation mean in cryptographic notation?

In terms of algorithms, it usually means concatenate - as in, join two binary (or otherwise defined) strings together (in this order). For wikipedia's cryptography articles that's nearly always the case.

When it is on the left side of an assignment, this means split the string from the right side into these component strings. This makes only sense if the length of most components is already fixed, of course – like here for the encryption and MAC keys.

In terms of programming languages such as C, however, it means logical or. Whilst it is unlikely the authors have confused them, it is something to be aware of.

Different notations may be used for string concatenation, including the single pipe sign $s_1 | s_2$ and the plus sign $s_1 + s_2$, although the double pipe sign as in the question seems prevalent.


One-one correspondance complete function

What is meant by vectors here?

Just the inputs and outputs of the function.  The function $f$ takes, as input, a sequence of bits (for example, 1010), and returns a sequence of bits (for example, 1100); the text refers to such a sequence of bits as a vector

  Can someone explain this?

Well, the idea is that every output bit depends on all input bits. That is, if we were to compute an output bit $j$, we would still need to know every single input bit (because for every output bit $j$, there is a pair of inputs $X_1, X_2$ for which input bit $i$ matters).  In other words, for any change in an input bit, there's a possibility that it may affect any output bit.

That sounds like a reasonable goal; however it turns out to be a very weak guarantee.

To see this, consider a function f that is made up of two operations:

Take the input, treat in as an $n$ bit unsigned integer, and increment it modudo $2^n$
Take the msbit of the result, if it is 0, the value remains the same, if it is 1, flip all the other bits.  This can also be viewed as xor'ing the msbit into all the other bits.
Return that as your result.

For example, consider the input $1010$; in the first step, we treat that as an unsigned integer (the value ten, as it happens), and we increment it to eleven (or $1011$).  Then, in the second step, we take the msbit (which is a 1) and exclusive-or that into the rest of the values, turning the lower three bits $011$ into $100$, giving us a final result of $1100$.

Now, this rather odd function just happens to meet the criteria of a 'complete function' for $n>2$; it's one-to-one (as both steps are invertable), and for every $i, j$ pair, we can find two inputs $X_1, X_2$ that differ only in the $i$-bit bit and $f(X_1)$ and $f(X_2)$ differs in the $j$th bit (and possibly elsewhere).

For example, for $i=4$ and $j=2$, consider $X_1 = 0010$ and $X_2 = 0011$. These two vectors differ only in the 4th location (counting 1 as the first bit); $F(X_1) = 0011$ and $F(X_2) = 0100$, which differs in the 2nd location (as well as the third and the fourth; we're allowed to change other output bits in addition to output bit $j$).

And, for $i=2$ and $j=4$, consider $X_1 = 0111$ and $X_2 = 0011$.  These two vectors differ only in the 2nd location; $F(X_1) = 1111$ (remember, we first increment $0111$ into $1000$, and then xor the top bit into the rest of them, flipping all three 0's into 1's), and $F(X_2) = 0100$, which differs in the 4th location (in addition to the first and the third).

I won't go through all the combinations, but such pairs exist for all $i, j$ values.

On the other hand, this example shows that it is a rather weak guarantee; I picked the specific function $f$ because it meets the criteria, but not in a particularly useful way.  For large $n$, yes, every $i, j$, you can find a pair $X_1, X_2$; however for most $i, j$ pairs, output $j$ rarely depends on input $i$.


The common reference string in NIZK does not have to be uniformly distributed.

It is to be sampled from whatever distribution the NIZK protocol specifies.

However, the common random string in NIZK does have to be uniformly distributed,

and the setup strings in NIZK also have to be uniformly distributed.


Length of encryption password aes-256-cbc

AES supports three key lengths. They are 128, 192 and 256 bits long. You chose to use the 256 bit algorithm that operates in CBC mode. It's a correct choice.

Now all you need is:

key - 256 bits long
initialization vector - 128 bits long

You can generate them using the command I found here:

openssl enc -aes-256-cbc -k secret -P -md sha1

where the "secret" is your password.

I suggest not using a truly random key and IV, because you have to save them somewhere, and adversary can just read it from your hard drive. It's much better to use a long and complicated password that he has to read from a post-it-note glued to your monitor, and derive the key and IV from it.

As for security, let me put it this way. If I wanted to crack 256 bits long key and 128 bit long IV on my work laptop, I would probably be around a fifth of way done when the universe would collapse. It's much simpler to use rubber-hose cryptanalysis in this case.

EDIT:

Just for you to know you shouldn't use password as a key directly. You need to derive a key from a password. The command I pasted does exactly that. About the security of the password you already answered yourself. 9 characters is the absolute minimum (if there is at least one uppercase letter, one lowercase letter, one number and one symbol). But I strongly suggest using a passphrase instead of a password. They are vulnerable to dictionary hacking, but if you use enough words a dictionary hack also takes years to complete.

There are over a milion words in the English language.

If we use only lowercase letters in our four word passphrase, the dictionary hack has to do in the worst case $1000000^{4} = 10^{24}$ searches. In comparison, there are around 100 characters on the keyboard. A password of 12 of those characters will be cracked in less than $100^{12} = 10^{24}$ searches.

This mean that "singing retracted eleventh elephant" is an equivalent of a 12 character password, and also it's much easier to remember. And if we use a comma somewhere, uppercase letter, or use a word from a different language it gets much safer.


Undefined $E_y(1,r_{i,j,1})$ notation in cryptography paper, suspect ElGamal-like

An ElGamal ciphertext encrypting a message $m$ (as you say) is a tuple $(g^k,m\cdot y^k)$ when working in a group $G$ generated by $g$ with public key $y$.

Some people make the "randomizer" $k$ explicit by writing $E_y(m,k)=(g^k,my^k)$ to denote that they can control and know this input and that this input is not freely chosen by the encryption algorithm (typically if one uses ElGamal encryption as a commitment and requires proofs of knowledge about the plaintext - I guess this is what the guys do). So, people often write $E_y(m)$ if they do not care what the value of $k$ is and write $E_y(m,k)$ if they want to know what the value of $k$ is. Then, $E_y(1,k)$ is just an encryption of the identity in $G$ giving ciphertext $(g^k,y^k)$.


"Memory-Hard" vs. "Memory-Bound" Functions?

The Wikipedia definitions are clear;

memory-bound functions;

Memory bound refers to a situation in which the time to complete a given computational problem is decided primarily by the amount of memory required to hold data.

This is proposed for using against spams, first CPU-bound then memory bound. This algorithms requires to access memory in an unpredictable way so that caches are ineffective. This discourage the spammers.

memory-hard functions

In cryptography, a memory hard function (MHF) is a function that costs significant amount of memory to evaluate. It is different from memory bound functions, the latter incurs cost by slowing down computation through memory latency. MHFs find their use as a form of proof-of-work.

This is against the massive parallelization of hashing etc. For example the bitcoin miners create farms for SHA2d calculations since SHA2 is not memory hard.
There are two variants

Data Dependent
Data independent

For example Argon2 has both mode and even combined. Argon2i for data independent and Argon2d for data dependent. In the combined mode Argon2id.


Could a symmetric encrypted communication with a SHA-512 hash still be manipulated?

Let the message $m$ is encrypted as $c =\operatorname{E}(k,m)$, the hash of ciphertext is $h = \operatorname{H}(c)$, and send as  $(c,h)$ pair. Then the attacker captures the transmission, (possibly stop and send) and

Random ciphertext: change the ciphertext $c$ into any value $c'$ and calculate the hash of it $h' = \operatorname{H}(c')$ and sends. The message will have no meaning at all.

The Replay attack; the attacker sends old messages on their behalf. This is more serious since if not protected, all messages are meaningful. Consider that you send a money transfer message, and it is replayed again and again.

Bit-Flipping attack: If the attackers know the message and for encryption, the CTR or CFB mode of operation is used then they modify the ciphertext bits to their advantage and calculate the hash of the modified ciphertext. This is the strongest assumption, however, can have devastating effects. Like $\texttt{attack at fall}$ can be turned into $\texttt{attack at down}$.

Length extension attack: the attacjer executes a length extension attack on SHA-512 on the hash value $h$. $$h' = \operatorname{SHA512}(c\mathbin\|pad1\mathbin\|extension)$$
Then modifies $c$ as $c' = c \mathbin\|pad1\|extension$ and sends the message pair as $(c',h')$.
The receiver checks the hash of $c'$ and sees that it is a valid hash then decrypt the $c'$ as the intended ciphertext. done!
This length extension attack has almost no cost for the attacker, however, they have no control of the decryption of the appended text.
To make the length extension attack easier the attacker can define a new $\operatorname{SHA-512}$ as $\operatorname{SHA-512x}(IV,m) $. If the $IV$ is equal to initial values of $\operatorname{SHA-512}$ then it is exactly $\operatorname{SHA-512}$, in the other case they can use the $h$ as an $IV$ to execute the attacks as $\operatorname{SHA-512x}(h,extension)$. This will reduce the cost of the extension attack.


Question about the location of the r-torsion in the quotient group used in the Tate pairing

The group $E[r]$ is isomorphic to $\mathbb{Z}/r \mathbb{Z} \times \mathbb{Z}/r \mathbb{Z}$, which has $r^2$ elements, all of order $r$. Since your element $Q$ has order $r^2$, $E(\mathbb{F_{q^k}})$ has also a cyclic subgroup of order $r^2$.
This group has $r (r-1)$ elements of order $r^2$ which cannot be elements from $E[r]$. This implies that $\#E(\mathbb{F_{q^k}})$ must be at least divisible by $r^3$.


Decrypting the same message with the same IV using aes-256-cbc

First of all IV is decided while encrypting, you must decrypt using the same IV that was used during encryption. So, the question should really be about encrypting same message with same IV not about decrypting.
In CBC mode, using same IV and same key for different messages can help you detect the common prefixes in the message which diverges after encountering the first different block. That's why using same IV is never semantically secure as you can easily see where the messages diverge, that is information is leaked even if you are not allowed to repeat messages. Back to the question and similarly, using same IV and key for the same message will always produce same ciphertext, thus you can easily see repeated encrypted message for seen ciphertext. If this much of information reveal is acceptable to you, it's OK but it may not be OK to everybody.
There is no "correct" encryption mode in this scenario, it depends on what type of security you want and is important that you know the risks involved. CBC mode has some flaws and should not be used unauthenticated. It is vulnerable to bit flipping attacks (flipping bits on ciphertext produces predictable change in the next block) and can be devastating if the application accepts random block just before the targeted block or if it is the first block (in which case you can achieve the same by bit-flipping the IV). Similarly, it may be vulnerable to padding oracle attacks depending on what type of system it is used with and what kind of information it reveals deliberately or unwittingly. My best advise is using authenticated encryption modes like GCM or GCM-SIV.
Using same IV on different message wouldn't be as bad in CBC mode as it would be for CTR or OFB or GCM mode (for these, consequences can be devastating) and using same IV for same message in these modes would pose the same problem, detection of repeated messages due to repeated ciphertext and it all depends on whether if they are OK with it.


Choice between AES-128 and AES-256 for password protection in MS Office

A cryptosystem is as strong as its weakest link.  AES-128 is almost certainly not the weakest link in your system.  Therefore, strengthening it by increasing the key length will not make the overall system more secure in practice.

To expand on that, let's consider (some of) the possible attacks on your system:

The attacker finds the user's password written on a post-it note.
The attacker sneaks a keylogger onto the user's computer and captures the password as the user types it in.
The attacker tests common passwords and their variations (e.g. "password" → "P@ssw0rd") until they find the correct one.
The attacker tests all the possible 128-bit AES keys derived from the password until they find the correct one.
The attacker finds a bug in the MS Office implementation of AES encryption that allows them to bypass it without knowing the correct password or key.
A cryptanalytic break of the AES algorithm renders it significantly easier to decrypt than by brute force testing all the keys.

Switching from AES-128 to AES-256 directly affects only one of these attacks: the brute force AES key enumeration attack (#4 above).  Even for AES-128, this particular attack is already considered practically impossible even for large nation states.  Switching to a 256 bit keyspace just moves it from "practically impossible using current or near future technology" to "completely unimaginable using any technology we can currently foresee".¹

That still leaves potential attacks 1, 2, 3, 5 and 6.  Attack #6 (a cryptanalytic break of AES) is not really something an end user should be worried about.  While such a break theoretically could compromise AES-128 while still leaving AES-256 with enough security margin to resist practical attacks, the opposite is theoretically possible as well.²  In any case, a cryptanalytic break on AES itself is a far less likely scenario than a vulnerability in the way a particular commercial software product uses it (attack #5 above).

In any case, the most likely practical threats to your system are attacks 1–3 above, or other similar attacks aimed at compromising the user's password rather than the encryption key derived from it.

While attack #3 can somewhat be mitigated by key stretching (if MS Office uses it, which I don't know), even the best (and slowest) key stretching algorithms can only slow down brute force password cracking by a factor of 230 to 240 or so; i.e. they add at most 30 to 40 bits of effective strength to the password.  Thus, unless your users use passwords with about 90 or more bits of entropy (as provided e.g. by a 7 word diceware passphrase) and unless the software you're using uses proper key stretching with the highest feasible memory usage and iteration counts, brute forcing the password (attack #3) will always be easier than brute forcing even a 128-bit key (attack #4).

And even then, that still leaves attacks 1 and 2, and any other methods (such as "rubber hose cryptanalysis") of extracting the password from the user or their computer.  Those are the threats that you really should be concerned about.

1) In particular, practical large-scale general purpose quantum computers could theoretically break AES-128 about as easily as conventional computers with a similar clock speed could break DES.  So far, the actual quantum computers that have been built aren't anywhere close to being able to do anything cryptographically useful, but it's always possible that there could be some kind of a massive quantum computing breakthrough within our lifetimes.  For whatever it's worth, that's currently the best argument I know of for switching to 256-bit keys.  Of course, such a quantum computing revolution would also totally destroy all public-key crypto algorithms in common use today.

2) Indeed, some currently known related key attacks on AES are more effective against AES-256 due to differences in its key schedule.  Fortunately, such attacks require a very specific combination of circumstances, and are not possible if the AES keys are derived using a proper key derivation function.


Security of zero knowledge proof protocols

I will try to answer your question in three parts. Before I start, let me introduce a somewhat more formal notation to ease the explanation. In particular, let $L = \{x ~|~ \exists~w : (x,w) \in R\}$ be the NP language with associated witness relation $R$ and we will always assume that we have a proof system for that language.

Informally speaking, one proves that a particular proof system satisfies the zero-knowledge property by showing that when setting up the proof system in a special way (indistinguishable from the original setup) one can build an efficient simulator $\cal S$ which can produce proofs for statements in the language which are indistinguishable from real proofs output by the actual prover - but $\cal S$ runs without knowing a corresponding witness. Very roughly, this then shows that - under the assumption which was used to prove zero-knowledge - no information about the witness is contained in the proof.
It is important to note that a zero-knowledge proof only guarantees that the proof itself does not contain information about the witness. However, if $L$ is so that finding witnesses for statements in $L$ is easy, one can always directly compute the witness without looking at the proof at all. More precisely, the problem under which the zero-knowledge property of the used proof system is proven is not necessarily connected to the problem associated to finding a witness for some element in $L$. Speaking in terms of your example: "generating a good graph for the Hamiltonian graph problem" is something which is independent of the zero-knowledge proof system and only depends on your application.
To your question regarding other attacks: of course, the zero-knowledge property does not rule out attacks on the implementation level. For example, if the prover leaks something about the witness upon proof computation via some side channel, one might be able to find out something about the witness. For further reading, I would just recommend standard literature on side channel attacks (e.g., [1]). Alternatively you may also have a look at [2], who explicitly mention how they address implementation-level issues in the context of zero-knowledge proofs.

References

[1] Stefan Mangard, Elisabeth Oswald, Thomas Popp: Power analysis attacks - revealing the secrets of smart cards. Springer 2007, ISBN 978-0-387-30857-9, pp. I-XXIII, 1-337

[2] Endre Bangerter, Stefania Barzan, Stephan Krenn, Ahmad-Reza Sadeghi, Thomas Schneider, Joe-Kai Tsay: Bringing Zero-Knowledge Proofs of Knowledge to Practice. Security Protocols Workshop 2009: 51-62