Differences between AEAD and ECIES when transmitting secret messages

I wonder what are the practical differences between using Authenticated Encryption and then ECIES. It looks like both require communicating the shared secret in some fashion between the parties and both provide encryption and authentication.

ECIES is a specific hybrid encryption scheme using elliptic curve cryptography to enable EC based encryption - that is: encryption using the static public key of the receiver and decryption using the static private key of the receiver.

AEAD is a description of an interface for symmetric encryption with authentication.

ECIES depends on a asymmetric key pair (where the public key is trusted) and AEAD depends on a single symmetric key, which needs to remain secret. ECIES is a specific construct to perform encryption using Elliptic curves, AEAD is a description of an interface for authenticated ciphers. In such, it doesn't make much sense to compare the two.

  To make a concrete example, consider we have a party A, which receives messages {x1, x2, ..., xn} from various other parties, but needs to read the sender from the message itself, because upon receiving a message x A doesn't know the sender. Using some AEAD scheme, A could have a plain-text part in each x telling the sender in an authenticated part and hence would need which shared secret to choose to open the actual message.

You wouldn't really need to authenticate the key identifier; if you'd change the key identifier then the authentication tag is already invalid, as you would use the wrong key to authenticate the ciphertext. You'd only need it if the scheme reuses the key for multiple senders that trust each other (not a common scenario). If this is for transport authentication you'd generally just keep track of a session.

  Can ECIES do this and if so, what is the practical difference? If not, well, what could be the purpose of ECIES? There seem to dearth of information on ECIES.

No, ECIES just performs encryption, and as anybody has the public key, anybody can create a valid ciphertext. It doesn't If you want to add such functionality, you should sign the data, and then encrypt the plaintext and signature.

If you're talking about real time communication between a sender and receiver then you'd just use a transport protocol such as TLS. TLS 1.3 requires AEAD but since there already is a key establishment scheme based on DH, ECIES isn't used.


Indistinguishability under chosen message attacks (IND-CPA) is a security definition for encryption schemes and not for commitments. So we cannot claim that a commitment scheme is IND-CPA.

Notice that the above scheme cannot be an encryption since there is no encryption/decryption key. In fact, if the hash function has a larger domain than range, there may be multiple pairs $(m,r)$ that map to the same $c$ and one cannot know which one is the correct (even if they were all powerful).

It is true, however, that the scheme you propose is hiding: for any two messages $m_0,m_1$ it holds that $H(r,m_0)$ and $H(r,m_1)$ are indistinguishable in the random oracle model.


An efficient PACE protocol with curve25519

Sorry, but this doesn't quite work; it allows the adversary with a dictionary of possible passwords to eliminate large parts of his dictionary efficiently.

Here's how a terminal who doesn't know the $k$ can eliminate half of the possible values in his dictionary per exchange:

The terminal receives $Enc_k(s)$; he remembers it
The terminal sends a random $h_x$ value; doesn't matter what it is
The terminal receives $h_y = s^x$; he determines whether $h_y$ is on the curve or on the twist.

Then, for every $k'$ that is in his dictionary, he computes $Dec_{k'}(Enc_k(s))$, and determines if that is on curve or on the twist.

If $k' = k$, then $y_h$ and $Dec_{k'}(Enc_k(s))$ will both be either on the curve, or on the twist; hence if one is on the curve, and the other is on the twist, he knows that wasn't the correct value of $k$.

This logic will allow him to eliminate about half of his values in the dictionary; going through this process 20 times will reduce a 1 million entry dictionary to the 1 correct entry (and perhaps 1 false hit).

Now, this sort of thing could be made to work over a MODP group; we just pick a Sophie-Germain prime (that is, one where $(p-1)/2$ is also prime) that's just under (say) $2^{2048}$; there we have an efficient mapping between random bit strings to members of the subgroup of quadratic residues (and so testing which subgroup $h_x, h_y$ are in doesn't yield any information...)


Derive cipher IV and cipher Key using PBKDF2 with random salt?

It is secure. The IV only needs to be indistinguishable from random to an attacker, and it is as long as the salt is random.

There is one remark: if you extract more key + iv bytes than the hash function in PBKDF2 returns then the PBKDF2 function is executed twice. An attacker however only has to find the key, not the IV, so an attacker doesn't have to do this, halving the security provided by the number of iterations.

You could use a KBKDF (Key Based Key Derivation Function) rather than direct extraction to get the key and IV. So you would have:

S = PBKDF2(salt, password, iterations)
K = KBKDF(S, 'enc')
IV = KBKDF(S, 'iv')

A good KBKDF is HKDF-expand.


Cutting down the size of a long blowfish key

There is no general way yo use a function implementing Blowfish and enforcing its  maximum 56-byte key size, to emulate a function implementing a variant of Blowfish that does not enforce that limitation (which in practice means it uses up to 72 bytes of key). For most keys over 56 bytes, the plaintext/ciphertext mapping will be different; combining multiple calls won't help.

The only exceptions are keys which after truncation to 72-byte happen to be periodic with a period at most 56-byte. In that case, one can find the period, truncate the key to the period, and pass the truncated key to the function enforcing the maximum 56-byte key size. That works if the function supports the truncated key size, because Blowfish specifies that the key is used cyclically.

Example: key ABCDEFGHIJKLMNOPABCDEFGHIJKLMNOPABCDEFGHIJKLMNOPABCDEFGHIJKLMNOP(64-byte) can be truncated to ABCDEFGHIJKLMNOP (16-byte).

Note: If the minimal period of the actual key truncated to 72-byte is not supported (e.g. because the available Blowfish function enforces that the key length is a multiple of 4 bytes), but some multiple less than 56 is supported, then it is possible to use that multiple. Key ABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFxxxx (76-byte with the first 72 of period 11) can be truncated to ABCDEFGHIJKABCDEFGHIJKABCDEFGHIJKABCDEFGHIJK (44-byte).

But in anything like reverse-engineering or cryptanalysis, I can't understand why there would be the need to "use a standard library to take care of the encryption instead of using a custom implementation". There should be the freedom of using a compiled language like C/C++ or Go, and then Blowfish is available in source form, that's little code, zapping its 56-byte limit is trivial, and such custom implementation can give the best speed by cutting down on interface.


Does the One Time Pad rely on confusion or diffusion?

The One-Time Pad employs neither confusion nor diffusion, as defined by Shannon:

  "Two methods (other than recourse to ideal systems) suggest themselves for frustrating a statistical analysis. These we may call the methods of diffusion and confusion. In the method of diffusion the statistical structure of $M$ which leads to its redundancy is “dissipated” into long range statistics—i.e., into statistical structure involving long combinations of letters in the cryptogram. [...] The method of confusion is to make the relation between the simple statistics of $E$ and the simple description of $K$ a very complex and involved one."

(It's worth noting that, to really understand these definitions, you should read the full paper in detail.  In particular, the earlier definition of a "strongly ideal cipher" that the text alludes to is kind of nontrivial, and not something commonly encountered in modern cryptography.)

In the one-time pad, each ciphertext symbol depends on exactly one message symbol and one key symbol.  Thus, there is no diffusion, in the sense used by Shannon, since the relationship between the message $M$ and the ciphertext $E$ is trivial, nor can there be any confusion, since the relationship between the key $K$ and the ciphertext $E$ is equally trivial.

Instead, the perfect secrecy of the one-time pad follows from the fact that the use of a random one-time key masks any redundancy in the plaintext: without knowledge of the key, the ciphertext is statistically independent of the plaintext, and thus no ciphertext statistics can reveal any information about the message.  (Such statistics can reveal information about the key, if the attacker can guess some of the plaintext; but since the key is never reused, this makes no difference.)

It should be noted that this does not contradict Shannon's statements in any way: the section where the terms "confusion" and "diffusion" are defined is explicitly concerned only with non-ideal (in the sense defined earlier) ciphers using keys of bounded length.  The one-time pad is not such a cipher, and so the statistical analysis techniques that confusion and diffusion are supposed to prevent do not (necessarily) apply to it.  Furthermore, Shannon never claims that confusion and diffusion would be the only ways to protect a cipher from statistical analysis; merely that they are two obvious and general ways to (attempt to) do so.


How to avoid side channel attacks when handling large numbers?

I recently wrote a big page on how big integers are implemented in BearSSL. There are several ways to represent integers in RAM and compute operations on them; also, note that for cryptography, we usually need big modular integers, which is not the same as big plain integers. BearSSL's code is constant-time, thus nominally immune to timing attacks (subject to the usual caveat that integer multiplication opcodes are not constant-time on some CPU).

Timing attacks are attacks for which the physical measure is based on elapsed time. They are special in that they can be performed remotely (either by measuring response time over a network, or by using the target computer's own abilities at knowing the current time); all other side channel attacks require the attacker to have special hardware in the physical vicinity of the target system. Timing attacks are the ones where you have to worry about the whole planet. For more information on timing attacks, see this page.

Smartphones muddy that picture a bit, because they have a lot of sensors that can be leveraged by hostile code, hence "remotely"; think for instance of microphones, cameras and accelerometers. With smartphone hardware, a nominally sandboxed application with access to some of these sensors might leverage some side channels on other operations that occur in the phone. Power analysis, though, should not be in that category, because smartphones don't include hardware for really precise measurement of their own power consumption.

BearSSL does explicitly not do anything against side channel attacks other than timing attacks. Being constant-time does procure a level of protection against some aspects of power analysis (simple power analysis can reveal which code branches the CPU follows, but one of the requirements of constant-timeness is that conditional branches do not depend on secret data, so this does not leak any secret information). Differential power analysis can leverage the difference between writing a 0 or a 1 in a given register or memory slot; you need some really good oscilloscope to pull that off. To protect against differential power analysis, the usual protection is to add random masking, a complicated process since it not only depends on the algebraic properties of your computation, but it also requires a source of good randomness, which might itself be targeted by differential power analysis.

An important point to make is that differential power analysis, and defence against it, depend a lot on the precise hardware involved. As such, there cannot really be such a thing as a "software library immune to power analysis". At best, you have a system that combines software and some specific hardware, which can be declared resilient to some extent. Smart card manufacturers are the people you want to talk with about such issues.


TLS 1.3 Secure Renegotiation not supported

Yes, since TLS1.3 forbids any renegotiation, supporting rfc5746 with it would be meaningless, and rfc8446 doesn't even mention the possibility.

Of course an endpoint that supports both 1.3 and lower versions should (in the 2119-capitalized sense) use 5746 for sessions that negotiate a lower version, and (AFAIK) OpenSSL does.


The attack outlined in the question does not work, at least as is. Still, SRP6a is very vulnerable to leak of server data, which is not part of the threat model that it addresses.

An attacker Mallory with knowledge of $v$ and $s$ (stolen from the server) can indeed masquerade as the server to the client and establish a shared key with the client. However, without the password, Mallory can not masquerade as the client to the server and get to the point where the server uses a private key. Further, if Mallory attempts to hijack a connection previously established with the server by the legitimate client, that will fail because that connection uses another private key than the one shared between client and Mallory.

However, with $v$ and $s$ stolen from the server, and pure SRP6a, an adversary can find a weak password by a dictionary attack (trying likely passwords sequentially starting from most likely), and then impersonate the legitimate client to the server. Technological progress ("Moore's law") tends to make SRP6a proportionally less secure from that standpoint. The only way around (beside not letting $v$ and $s$ leak, or hoping users will magically start using strong passwords) is that SRP6a is modified yet again by using a slow key derivation function for passwords (also known as password hash, password-based key derivation function) such as PBKDF2, Bcrypt, Scrypt, Argon2, Balloon instead of a fast hash.

Bottom line: when using SRP6a, if $v$ and $s$ being stolen from the server is considered possible, then the client software must implement a properly parametrized slow key derivation function for passwords; with the choice of that function, parametrization, and where the salt comes from not defined by any standard that I am aware of, including RFC5054 or ISO/IEC 11770-4:2006 (did not check the latest version). Correspondingly, practice is overwhelmingly to ignore SRP and send the password as keyed-in within an https tunnel (with the problem that a bogus certificate or a variation of the correct domain name that pass user scrutiny glance will reveal the user's login/password to a competent attacker). That practice also solves the problem that typical browsers have no built-in SRP client support, and that bringing one thru https as Javascript is vulnerable to the aforementioned attacks of https.


The intended users know, in fact choose $p,q.$ The attackers aren't supposed to know. Once you know $p,q,$ you use the Chinese Remainder Theorem for efficient computations.


The Secp256k1 curve is used in cryptocurrency. Can someone generate a private key with a different curve?

The Bitcoin network expects secp256k1 when adding something to its blockchain. If you use another curve, it naturally will not produce a valid secp256k1 public key capable of validating the secp256k1 signatures and will be rejected by the network. If some client uses a bugged or even backdoored version of the curve, the client will simply not be able to add anything to the blockchain. This would only become a risk if a significant portion of the network ended up using this same bad library, effectively resulting in a fork of the core client and an entirely new, separate protocol.


Post-quantum candidates for asymmetric cryptography with small key sizes

It appears that SIDH, or Supersingular Isogeny Diffie-Hellman, is the post-quantum candidate with the smallest key size. When using compression, public key size can be reduced to 330 bytes (2640 bits) to achieve the 128-bit security level. For classical Diffie-Hellman, this value is often quoted at 3072 bits. From the above-linked paper describing the attractiveness of the small public key size of SIDH:

  Not only are high-security SIDH public keys smaller than their lattice- and code-based counterparts, they are even smaller than some of the traditional (i.e., finite field) Diffie-Hellman public keys.

The SIDH-based public key encryption and key encapsulation scheme submitted to the NIST post-quantum cryptography process is called SIKE, for Supersingular Isogeny Key Exchange, and specifies parameters called SIKEp503 to obtain a 378-byte (3024-bit) public key for the 128-bit security target.


[...][I]s there such a thing as a dynamic length (output) hash
  function?

Yes, these are called extendable output functions (XOFs), with the most well-known instances being SHAKE128 and SHAKE256 from NIST FIPS 202. Given an arbitrary-length input, they essentially produce an arbitrary length output that you may truncate at any point and that enjoys the usual security properties for hashes.

But beware of the determinism of these functions, that is if you hash $m$ with them, and then take the first 256 and the first 512 bits in two different places, they will both share 256 bits!

  [...][It] but would possibly avoid collisions?

As the names suggest, SHAKE128 aims at a 128-bit security level, meaning you'll need $2^{\min(128,d/2)}$ operations to find a collision, where $d$ is the length of the output. So why does it "only" provide 128-bit security at most? Because you can find a collision on the internal structure with $2^{128}$ operations that will result in a collision on the output stream.


ecdsa nonce reuse to compute the private key, modular inverse question

You are looking for the modular inverse of $r$
By Euler's Theorem
$$a^{\phi(m)} \equiv 1 \pmod{m}$$
Then
$$a^{\phi(m)-1} \equiv a^{-1} \pmod{m}$$
Now, for a prime $p$, $\phi(p) = p-1$ then we have
$$a^{p-2} \equiv a^{-1} \pmod{p}$$

Note 1: The multiplicative group $\mathbb{Z}^*_p$ contains $p-1$ elements, the zero is not included.
Note 2: Not all elements of $\mathbb{Z}_m$ has multiplicative inverse. To have one, $x \in \{1,\ldots,m-1\}$ we must have $\gcd(m,x)=1$
Note 3: The order of Secp256k1 is prime.


The answer is about the difficulty of discrete logarithm. The notion of isomorphism does not capture all that matters in cryptography; we also need to consider computing costs.

Suppose that we have an abelian group $\mathbb{G}$ with additive notation. Let $G$ be a conventional element of $\mathbb{G}$ of order $n$. The subgroup generated by $G$ is:
$$\langle G\rangle = \{ xG \ | \ 0\leq x\lt n \}$$
That subgroup is isomorphic to $\mathbb{Z}_n$ (the integers modulo $n$) and the isomorphism is easily computed in one direction, from $\mathbb{Z}_n$ to $\langle G\rangle$ with a double-and-add algorithm: from $x$, one can compute $xG$ with less than $2\log n$ group operations (see this in the case of elliptic curves, but it really applies to any group).

Discrete logarithm is about computing the inverse isomorphism, i.e. computing $x$ from $xG$. Generically, when the only operations that you can do on elements of $\mathbb{G}$ are applying the group law, and comparing two elements for equality, then the discrete logarithm cannot be computed with an average cost of less than $\sqrt{n}$ operations. We know several "generic" algorithms that offer that kind of performance, e.g. Pollard's rho algorithm. It can be proven that no faster algorithm exists, that would work on a generic group.

Of course, generic groups are an abstract concept. What we have in practice are groups on which we know how to compute the group law and compare two elements, and possibly have some extra information on the group structure that may or may not help in computing discrete logarithms.

Right now, when the group is a randomly chosen elliptic curve, then we have no idea how to compute the discrete logarithm faster than by applying a generic algorithm. Thus, a "256-bit curve" (sub-group order $n$ is a 256-bit prime) is enough to achieve a "security level of 128 bits" (i.e. unbreakable with existing and foreseeable technology). Note that there are some specific curves with a special structure for which we know faster discrete logarithm algorithms (e.g. supersingular curves).

However, when the group $\mathbb{G}$ consists in integers modulo $p$ for some prime $p$, with multiplication modulo $p$ as group law, then we do know faster (subexponential) discrete logarithm algorithms, in particular in the large family known as index calculus. To achieve a security level of 128 bits, one has to choose a modulus substantially larger (somewhere between 2500 and 3000 bits).

Since field operations tend to have a quadratic cost in the field size (at least with the kind of algorithms that are fastest in fields commonly used in cryptography), the speedup obtained by using an elliptic curve and a relatively small field more than compensates the overhead of elliptic curve operations. In practice, on today's computers and for comparable security levels, with decently optimized implementations, elliptic curves offer a 5x to 20x speedup. Which is why we use them. As an added bonus, the corresponding curve points can be encoded over fewer bits, so this also saves a bit of network bandwidth in some cases.


How do high hash rates affect hashed password security?

Linux uses "sha512crypt", which isn't memory-hard but is fine given a moderately strong input passphrase.

HMAC-SHA256 isn't a password-hashing algorithm. It's not even a hash function. It requires a uniformly-random secret key which it uses on a message to produce a Message Authentication Code (tag) of that message under that key. The password-based key derivation function PBKDF2 uses HMAC internally to create a KDF, which can also be used as a password-hashing function. The rest of this question is impossible to answer: a 20-character long secret key just doesn't define much. "Character" isn't well-defined. 16 bytes, chosen uniformly at random (ie 128 bits) will be secure as the key for HMAC-SHA256. No password is used in such a system, since HMAC doesn't take a password.

This question is nonsense. It's impossible to use HMAC with PBKDF2, since PBKDF2 uses HMAC. Likewise bcrypt isn't a cryptographic hash function and therefore violates some of the assumptions used in HMAC's security proofs.

Use Argon2id for your password hashing function if possible. If that's impossible, use bcrypt. If that's impossible, use PBKDF2-HMAC-SHA256 (I doubt you've got scrypt in that case).
Use the EFF Long Word List and 5 good-quality dice, and pick a passphrase long enough for your desired security. Each word is just over 13 bits of entropy, so 7 words is 91 bits (safe for the next few decades), 10 words is 130 bits (definitely safe for the next few million years unless the attacker has a really big quantum computer), 20 words is 260 bits (safe even against planet-sized quantum computers for a few million years). If you're using 10 words or more, password-hashing function choice doesn't really matter much.


Finding and matching SHA512 Unsalted Hash

A brute force search is probably impractical with your resources.

It appears that a CPU-based SHA-512 implementation might be able to do 2,000,000 short hashes per second per core (the figures I have are a bit slower - I'm assuming things will get a bit faster)

Given $32^{16}$ target images, that translates to approximately 20,000,000,000 core-years to search through the entire list (or about have that to get a 50% chance of finding it).  If you have 1,000,000 volunteered computers, and each computer has 10 cores, that translates to an expected time of 1000 years to get to a 50% chance of finding it.

A quick look at GPU performance looks a little closer to practical; however you'll still need millions of dedicated GPUs to get the time down to a practical level.

About the only way to do it practically would be to go with FPGAs or (better yet) dedicated ASICs - either approach would appear to be out of scope for what you have.


Is there an algorithm or hardware that can sign/verify natural time?

A pure algorithmic approach does exist, however it only provides a fuzzy bound. It is related to the proof of work / client puzzles I described in this answer.

The signer will sign the message using a normal digital signature, and use the message and signature to instantiate a "cryptographic puzzle." A cryptographic puzzle is a moderately hard function that takes a certain number of CPU cycles (or memory accesses) to compute. The signer will then immediately begin to solve the puzzle.

Later, if a dispute arrises as to when the message was signed, the dispute can be resolved when the signer eventually produces the solution to the puzzle. The verifier checks that the solution is correct and then backdates the creation of the puzzle according to how hard it is (e.g. a solution to a puzzle that takes a year to solve means the puzzle must have been created at least a year ago). Since the exact puzzle being solved is specific to the message and signature, the message and signature must have been created before the puzzle.

Conceptually, the scheme is neat but it has a number of practical drawbacks:

You can't put an exact bound on the resources available to the signer and therefore cannot timestamp accurately
No puzzle of this type is known that is (a) inherently sequential (parallel computing does not help) and (b) can be created with the solver not knowing (or efficiently computing) the solution. For example, time-release crypto has (a) but not (b). Hash-based proof of works (like in Bitcoin) have (b) and not (a).
The signer must devote an entire CPU to solving the problem for as long as it takes


Not at all secure; generating preimages would be trivial.  Here's a demonstration with a three-block message:

Here is your suggested method (limited to three block messages):

$E_0 = Encrypt( IV \oplus P_0 )$

$E_1 = Encrypt( E_0 \oplus P_1 )$

$E_2 = Encrypt( E_1 \oplus P_2 )$

$E_3 = Encrypt( E_2 \oplus 0 )$

$Hash = E_0 \oplus E_1 \oplus E_2 \oplus E_3$

(with the key for Encrypt and the IV fixed).

Here's how you could find a message $(P_0, P_1, P_2)$ that hashes to a preselected value $Hash$:

Select an arbitrary value for $P_2$ (which may include the trailing padding for the last block)
Select an arbitrary value for $E_2$.
Compute $E_3 = Encrypt( E_2 \oplus 0 )$, $E_1 = Decrypt(E_2) \oplus P_2$ and $E_0 = Hash \oplus E_1 \oplus E_2 \oplus E_3$
Compute $P_0 = IV \oplus Decrypt( E_0 )$ and $P_1 = Decrypt(E_1) \oplus E_0$

You're done: $(P_0, P_1, P_2)$ hashes to preselected value; it's easy to see that hashing this value will cause the internal $E_0, E_1, E_2, E_3$ values that we have selected, and that exclusive-oring them will produce the preselected hash.


Can the attack against SHA-1 be parallelized?

Based on the more recent Disturbance vectors for collision attacks against SHA-1 by the same author, which Maarten Bodewes mentioned in the comments, the initial attack/complexity was optimistic/erroneous. The algorithm actually leads to a disturbance vector that had already been published:

  Using our algorithm and those cost function we retrieved all previously
  known vectors and found that the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak, A matching lower bound on the minimum weight of SHA-1 expansion code.

The estimated complexity of that attack based on the original source is $2^{62}$. The later paper by Stéphane Manuel quotes two estimates of $2^{65}$ and $2^{69}$ depending on the cost function used, and gives some evidence that even those may be optimistic:

  Furthermore, the statistical evaluation of local collisions’ holding probabilities described in the next section shows that local collisions are not independent. Consequently, this type of cost function only gives a rough basis for an estimation of the complexity of the attack.

Either way, this is more costly than the freestart collision attack recently performed ($2^{57.5}$), and similar or slower than Stevens' proposed full collision attack. So that explains why it has not been performed  so far.

Regarding the original question about parallelization, yes, these types of attacks should be "easily" parallelizable (to the degree that implementing them on a GPU is easy).


Is the following crypto compatible so that I can use the same keys for both products (Wireguard & Libsodium)?

WireGuard uses keys that are on the Montgomery curve, not the Edwards curve. It's the standard X25519 or Curve25519 commonly used for ECDH.

In libsodium, crypto_box_keypair calls crypto_box_curve25519xsalsa20poly1305_keypair which calls randombytes_buf(sk, 32), return crypto_scalarmult_curve25519_base(pk, sk). In WireGuard, wg genkey calls get_random_bytes(sk, 32) and wg pubkey calls curve25519_generate_public(pk, sk). It turns out that crypto_scalarmult_curve25519_base(pk, sk) and curve25519_generate_public(pk, sk) are essentially the same thing.

So this means in theory those keys would be "compatible".

However, you should not do this under any circumstances.

Cryptographic protocols make various assumptions on how keys are used. The WireGuard Protocol is formally verified, which means within the WireGuard handshake, it's been verified that none of the constructions will lead to any catastrophic situations. However, there's no guarantee that re-using these same keys within other random constructions that you might cook up won't interact badly and will retain the same guarantees of the WireGuard Protocol. So, if you reuse WireGuard private keys in your own protocol, you do so at your own risk. That's the kind of thing you only do if you really, really know what you're doing and are certain that there won't be any bad interactions.

(Perhaps a more productive way forward would be to describe what you actually want to do with WireGuard key identities and your libsodium-based protocol. Then maybe folks can help you find a safe way of accomplishing this. What's the overall end goal of your project?)


How to compute a discrete logarithm modulo a power of 2?

There are a couple reasons that the discrete log is weak across powers of two, the most basic reason is because it is only considered strong when the modulus is some large prime, p.

This is a good link about how to find the mod inverse, and in it you will find their function for computing it.
https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/

Basically, for your example, the program would solve the mod inverse problem in a very short amount of time (which is bad!). That is why if you use larger values of m and p, the calculations done in the pow function will take much longer than it did with the previous numbers.

As for why powers of 2 specifically are weak, I would recommend looking at the Chinese Remainder Theorem, just know that this requires a lot of math and is just based on the fact that any power of two is comprised solely of factors of 2. https://en.wikipedia.org/wiki/Chinese_remainder_theorem.


What are the implications of a birthday attack on a HMAC?

This is like stating that $H(C_1|m_1|x|C_2) = H(C_1|m_2|x|C_2)$ if $H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ for HMAC.

That is probably correct if $H$ is a hash function based on Merkle–Damgård construction (such as SHA-1 and SHA-2) and if $m_1$ and $m_2$ end on block boundaries.

$H(C_1|m_1|C_2) = H(C_1|m_2|C_2)$ implies that the state after hashing $C_1$ and $m_1$ is identical to hashing $C_1$ and $m_2$. So adding any data to either one will result in the same hash.

If however $m$ doesn't end on a block boundary then changing the data coming after $m$ will still alter the state after the block has been hashed; it is extremely unlikely that the result will be the same for $m_1$ and $m_2$ (if $m_1$ and $m_2$ differ for the last block of course). If $m_1$ and $m_2$ can be chosen freely then this situation can be avoided.

The situation for CMAC (and CBC-MAC) will be more or less identical. CBC is however explicit while Merkle–Damgård isn't. So this seems indeed more true for CMAC.

  If my assumption is true could this be considered as a length extension attack?

You could call this a length extension attack, it's at least pretty similar to one. With additional data coming after it it's more a kind of insertion attack, but the principles are the same.

Note that this is only applicable to the insertion of $x$, not the rest of the attack.


Where can I get information on how to implement AES?

The AES standard is reasonably clear, and (theoretically) sufficient to implement the AES itself. For block cipher modes of operation (including counter mode), see NIST Special Publication 800-38A.


It is in the part of the internal block cipher of SHA2 that has 64 or 80 rounds depending on the mode, SHA256 has 64, SHA512 has 80 rounds.

  Why do we need T1 and T2 in this case?

Except the $T_1$ and $T_2$, everything is linear. In the picture, they are the blue and red word additions ($\color{red}{\boxplus}$). Being only linear is not a good idea in Cryptography. It is easy to attack since one can setup linear equations and solve by Gaussian Elimination. Nonlinearity is necessary but not sufficient. It uses the confusion and diffusion paradigm with many rounds where the key of the block cipher is the message.

  What do the values T1 and T2 represent?

Values changes according to inputs but the function definitions are fixed.

  But why go through so many shifts and other operations?

You can consider the shift operations as the diffusion part of the design, in order to affect each output bits with many key bits and many input bits in lesser rounds.

Of course, all of these above cannot claim that SHA256 is secure. It is designed to be secure with the previous knowledge about hash designs. Yet, SHA2 is not broken even theoretically i.e. even one bit less than the classic generic attacks

pre-image attack that has $\mathcal{O}(2^{256})$
second pre-image attack $\mathcal{O}(2^{256})$
collision attack  $\mathcal{O}(2^{128})$ due to the generic birthday attack.

Best known attacks are on the reduced rounds like preimage attack for 42 of 64 rounds with a $2^{248.4}$ complexity.

Even it is theoretically broken, it might not have a practical effect. For example, a full round pre-image attack with $2^{200}$ cannot be used in practice.

The previous hash of NIST SHA-1 is broken and the first forge is generated, see list of attacks on SHA-1. For SHA-2, the time will show. As said Attacks always get better; they never get worse.


How difficult is it to guess a salt based on a hash and known plain text?

It seems you are looking for a good way to creating different "passwords" from a user specific secret. For that you do not need a password hash, you can use a common key based KDF, assuming that your secret has the properties of a symmetric key.

In that case the secret should take the place of the secret key or password, not the hash. The information on the service and domain should then be part of the "other information" or, if you are dead-bound on using a password hash, the salt. The password hash would be needed if it would be too easy for an adversary to guess the secret otherwise, but note that it only gives you a small, constant size amount of protection against offline guessing attacks.

To do this you should probably prefix the byte-encoded values with the size in bytes, to make sure there is only one possible encoding for both values together. It could make sense to first hash the service and domain with a secure hash (SHA-256) if they are larger, because algorithms may not have been designed for a large info-field or salt - the CPU may otherwise be dependent on the encoded size.

So you would get something like:

$$\text{info} = \text{Encode}(\text{service}, \text{domain})$$
$$\text{passwordBits} = \text{KDF}(\text{secret}, \text{info}, \text{passwordSizeInBits})$$
$$\text{password} = \text{Format}(\text{passwordFormatting}, \text{passwordBits})$$

or, if you take into the hashing of the info:

$$\text{info} = \text{Hash}(\text{Encode}(\text{service}, \text{domain}))$$

It is generally possible to include a random salt as well to the KDF. This makes it possible to create a slightly more secure result, at the obvious expense of complexity of the function and additional storage in your table.

I'd also store the $\text{passwordFormatting}$ string in your table of course. Different services will accept differently formatted password strings, even in 2019. You could mimic/copy the password formatting from an open source password manager, where the password is generated from a random value. Check the license first of course.

A very simple formatting scheme that doesn't require a formatting scheme is base64url. Many sites would allow that if you don't make your password - and therefore the size of the password in bits - too large.

The password size in bits of course depends on how much bits you require for your password formatting. It can be too large, e.g. 128 bits, and then you can toss away the bits you don't require during the formatting / base conversion / whatever to create a password.

Good key based KDF's (KBKDF's) are HKDF, but you might also use ANS X9.63 KDF as KDF if none are available to you - that's probably the easiest one to implement.

Below is a more generic explanation on how a password hash should be used:

  The goal is to have unique hashes for each user at each service without an attacker being able to guess the hash of a user on a specific other service.

No. The main goal is to keep the password secret (and to verify it when using it in the correct use case, of course). That identical hashes leak information or even the password is the reason for the salt. That the hashes are unique is a means to an end, in other words.

  This leaves us with a table of users, services, personal domains and hashes.

Commonly these tables also include the salt, for instance by including it into the password hash. The salt is not kept secret; it would require you to keep a secret value for each user. If that would be possible then you might not need the password hash in the first place; you could just compare the password to one in secure storage.

I would certainly also store something like a version indicator that represents the number of iterations, password derivation function etc. in use, so you can upgrade the entries (one by one) when this is required.

  The attacker should not be able to guess Alice's hash for a new service (e.g. stackexchange.com).

This part is not applicable to the question above

You cannot login with the hash on a service; you need the password and that is converted to a password hash by the service. If you enter the password hash it would calculate the password hash over the password hash and the login should fail (unless the implementers have made a huge implementation mistake). Again, protecting the hash is not the goal; the password needs to be protected.

  Is this guaranteed even when each user always uses the same salt and the salts are kept private?

Well, yes, if there is a secret part within the input parameters of the password hash, and if this secret is one of the parts that is hashed, and if that secret has enough entropy then it would become impossible to calculate the password hash.

However, as explained above, it doesn't make much sense to keep the salt secret.

What is sometimes performed is to have a secret available that is made part of the salt. Then the part consists of the secret part and a (usually randomly generated) nonce (which could be used as a salt by itself). This is then called a pepper.

Without this secret value an adversary cannot start offline attacks as it is impossible to check if a password guess is correct without the pepper. However, this pepper is then identical for all (or possibly large groups of) passwords. It is not a salt by itself.

For this specific problem, I'd use the scheme written down at the start of the answer instead of using a password hash with a pepper


Paillier equality test under the same key

If you intend to make $f$ public, or that $f$ does not depend on the secret key, that's not going to work:

The Paillier cryptosystem is proven to be IND-CPA under the decisional composite residuosity assumption.
If a function $f$ exists, like you describe in the question, this function would immediately break IND-CPA
By contraposition, function $f$ does not exist (under the assumption that the cryptosystem is IND-CPA).

However, if $f$ is actually the decryption function with the private key hard coded or any modification of this, it would work. However, that means Bob might be able to extract the private key from $f$. If you want that to be computationally hard, you will need to prove this property.

That last part is quite difficult and maybe even impossible. I am not aware of a property like that for the Paillier cryptosystem. Composite moduli do have some properties which might be suitable. For example computing an $e$-th root of a fixed public element is computationally hard but knowing this root does not reveal the factorization of the modulus. But I don't know how you could adapt this in the Paillier cryptosystem.


Is it possible to demonstrate that md5(x) != x for any x?

It is not known whether there is a fixed point or not. Since MD5 gives you 128 bits, you would need an input of 128 bits as well. That is you are really considering a function from the set of 128-bit strings to 128-bit strings. Assume that such a function is chosen at random. Then we can calculate the probability that the function has a fixed point. The answer is stated in this answer: https://stackoverflow.com/questions/235785/is-there-an-md5-fixed-point-where-md5x-x. To unpack just a bit more:

Say you have any of the $2^{128}$ possible inputs. Then the probability that this is a fixed point is $(1/2)^{128}$ since, for example, the first bit would have to map to the first bit and so on. So the probability that the input is not a fixed point is $1 - (1/2)^{128}$. So the probability that no input will be a fixed point is

$(1 - (1/2)^{128})^{(2^{128})}$

because there are $2^{128}$ possible input.

The probability that there is a fixed point is therefore $1 - (1 - (1/2)^{128})^{(2^{128})}$. If you calculate this probability you get approximately 63.21 %.

So it is actually likely that there is a fixed point for MD5 or any other hash function for that matter.

Note that this doesn't prove that there is a fixed point, but it just says something about the likelihood.

The only way to demonstrate/prove whether or not there is a fixed point would be to compute all hashes of all 128 bit strings and compare them to the output.  But, as notes in the comments above, this is not very practical.


How to compute $a$ in the complex discard method of NIST SP 800-90

Wouldn't the numbers $a_i$ be too small in that case

No, it's just a simple base conversion; you take the integer $c$, and represent it in base $r$; the values $a_0, a_1, ...., a_{t-1}$ are the digits of the resulting conversion.

There are lots of ways to do base conversion; the simplest (if not the most efficient) would be:

For i := 0 to t-1 do
    a[i] = c % r
    c = c / r

(with % being the modulo operation, and / being integer division rounding down)


Is your "-K" in the code in uppercase or lowercase? If it is in lowercase, the encryption will automatically add a salt value into your cipher text, causing it to have more than 32 bytes. CBC will pad it until it reaches 48 bytes later(the multiplication of 16).


As mentioned by Peikert in [Pei16]:

*) Ring-LWE is parametrized by a ring $R$ of degree $n$ over $\mathbb{Z}$, a positive integer modulus $q$ defining the quotient ring $R_q=R/qR$, and an error distribution $\mathcal{X}$ over $R$.

**) Left-multiplication by any fixed $a\in R_q$ is a $\mathbb{Z}$-linear function from $R$ to $R_q$, so it can be represented by a square matrix $\mathbf{A}_a \in \mathbb{Z}_q^{n \times n}$, which maps $\mathbb{Z}^n$ to $\mathbb{Z}_q^n$.

For example, for $R=\mathbb{Z}[X]/(X^3+1)$ and $R_5=\mathbb{Z}_5[X]/(X^3+1)$, fix $a=3+2X+4X^2 \in R_5$. For $z=1+10X^2 \in R$, we have:
$$
a.z = 4X^2+2X+3 \in R_5
$$
Now, consider the matrix representation of $a$ and $z$:
$$
\mathbf{A}=\begin{bmatrix}
3 & -4 & -2\\
2 & 3 & -4 \\
4 & 2 & 3
\end{bmatrix} = \begin{bmatrix}
3 & 1 & 3\\
2 & 3 & 1 \\
4 & 2 & 3
\end{bmatrix} \in \mathbb{Z}_5^3
\qquad ; \qquad \mathbf{z}=\begin{bmatrix}
1\\
0 \\
10
\end{bmatrix}$$
We have:
$$
\mathbf{A.z}=\begin{bmatrix}
3 & 1 & 3\\
2 & 3 & 1 \\
4 & 2 & 3
\end{bmatrix}\begin{bmatrix}
1\\
0 \\
10
\end{bmatrix}=\begin{bmatrix}
33\\
12 \\
34
\end{bmatrix}=\begin{bmatrix}
3\\
2 \\
4
\end{bmatrix} \in \mathbb{Z}_5^3
$$
which is the matrix representation of $a.z$.

Now from these results, it is easy to see that each random element $a\in R_q$ corresponds to $n$ $\textit{related}$ (non-independent) vectors $\mathbf{a}\in \mathbb{Z}_q^n$, where $n$ is the degree of the ring $R$ over $\mathbb{Z}$.


Have these compositions of block ciphers the same security?

Yes, you can reasonably expect that these will provide equivalent security, if you choose all keys uniformly and independently at random.  The decryption operation is basically the same as the encryption operation, so it would be extremely surprising if there was any significant difference in security among these.

(Of course, if you don't generate the keys randomly, then this all goes out the window.  For instance, $DES_{k1}(DES_{k1}(\cdot))$ has very different security properties than $DES_{k1}(DES_{k1}^{-1}(\cdot))$.  I suspect this doesn't need saying, but I'm listing the caveat explicitly: it is important that you choose all keys uniformly and independently at random.)


Talking TLS with EC cryptography and the secp256k1 curve

BIP32 uses secp256k1 because BIPs are for bitcoin and bitcoin uses secp256k1. (I feel like Buffy 1.01: "[the reason I'm here now is] because now is when we came here".) The same approach(es) would work for any elliptic curve, with obvious substitutions for ser256 and parse256, and for serp if using a non-Weierstrass form like X25519.

But TLS in practice requires certificates for authentication keys (or kRSA, no longer recommended and in 1.3 no longer supported) and certificates don't mix well with rapidly or dynamically creating keys, via BIP32 or any other means, regardless of the curve(s) used. ('In practice' because there is an RFC for using raw keys, but I've never seen an implementation, certainly not in OpenSSL.)

PS: nodejs builtin 'tls' is OpenSSL, compiled into node[.exe] underneath. You can get alternative (pure-JS) crypto including ECC, but I haven't seen pure-JS TLS.


The way the iterations work is that it roughly increases your security (in bits) by $\log_2(iterations)$.  So you would still need $\frac{\log{2}}{\log{97}}\cdot (256 - \log_2(10000)) \approx 37$ characters in your password to have 256-bits of security.  Think of it this way, if you have $2^{256}$ possible keys, that is an astronomically large number.  Much more than the number of elementary particles in the universe.  In comparison, 10,000 is basically nothing.  Increasing the keyspace gives you exponential security, while adding iterations to your key derivation function gives you only linear security.  It's nice, but at the end of the day it doesn't help as much as you think it does.

Having said that,  you probably don't need 256-bits of security anyway.  As I said before, that is a ridiculous amount of security.  No increase in computational power will ever let anyone brute force a 256-bit key.  There are physical limits to computation, and it would take something like the entire energy of a dozen stars to be able to do that.  The reason we have things like AES-256 is that we anticipate in the future people will find more efficient attacks against AES which do not require brute forcing.  But, with a longer key we hopefully delay these attacks.  So, if someone discovers an attack which works in time $2^{n/2}$, AES-128 will be effectively broken.  But, with AES-256 we still have 128-bits of security, which should suffice for a while longer.

For 100 years, the number of bits of security you really need is closer to 120-150.  The outside limit of what anyone can brute force today is probably 70-80 bits, and remember adding bits gives you exponentially more security.  So, you would really only need a password that was 17-20 characters long.


Asymmetric encryption that is secure for (almost) any foreseeable future

I think that there is no chance of getting such an asymmetric cipher simply because you forgot about science.

The security on todays asymmetric cryptography is mostly based on the assumption that some mathematical algorithms cannot be reversed (e.g. the discrete logarithm or integer factorization).

If mathematics solves this problems then the algorithm is broken.

Such a breakthrough in mathematics can occur (e.g. for Fermat's Last Theorem in 1994).

So the major problem with assuring asymmetric cryptography as secure is to assure that no such breakthrough will occur.


Well, if $g$ is a generator of $\bmod\  p$ for prime $p$; that is, if all values in the range $[1, p-1]$ are possible values for $g^i \bmod p$, then we have $g^a \neq 1 \bmod p$ for any $a = (p-1)/r$ where $r$ is a prime factor of $p-1$.

You select $p$ to be a "safe prime", that is $p-1 = 2 \times q$ where $q$ is also a prime.  This implies that, in this case, there are only two values of $a$ that are of interest:

$a = q$ (with $r = 2$), this implies the condition that $g^q \ne 1 \bmod p$
$a = 2$ (with $r = q$), this implies the condition that $g^2 \ne 1 \bmod p$

Both conditions must be true, however your code tests only the first condition; it doesn't test the second.  Now, it turns out that the only possible values of $g$ that do not meet this second condition is $g=1$ (which doesn't pass the first either), and $g=p-1$, or in your case, $g=10$.

Because you're not testing this second condition, you're seeing $g=10$ as looking like a generator when it is not.

Now, $p-1$ is the only value which is excluded by this second condition, in practice it's probably easy just to test values in the range $[2, p-2]$, and not bother explicitly testing this second condition.


The answer to the GitHub issue specifically mentions what you're looking for

The reason why SEAL does not support bit operations is that bit operations require a non-power-of-two polynomial ring degree which leads to much less efficient polynomial arithmetic and hurts the performance of either homomorphic evaluation or encryption or both.

This states that with a non-power of 2 ring degree they could implement bitwise arithmetic, but it would hurt the performance of the algorithm.

We are evaluating the necessity and feasibility of adding support for bit operations. Perhaps we will adopt a different HE scheme for that rather than using BFV (definitely not CKKS).

This second quote states that, to avoid the efficiency issue, they would use a different homomorphic encryption scheme.
It seems to me you have your answer right there: they're confirming it's possible, and that they know how to do it. They're also confirming it wouldn't require changing the homomorphic encryption scheme. But since it would affect performance they're choosing not to.


What do people mean when they talk about forward secrecy in ciphers?

What does 'forward secrecy' mean in the context of hash based signatures?

Well, what that term means is that we have a hash based signature scheme with an evolving key, that is, the private key is constantly being updated, and on a state compromise (at state $N$), you cannot get the private keys used prior to state $N$.

I personally don't see that as a good use of the term (it's feels like 'perfect reverse security' would be more apt terminology, as it's discussing the security of the system prior to compromise).  However, that's what people mean by that terminology.


Is RSA padding needed for single recipient, one-time, unique random message?

I recommend that you stick with the standard padding methods, even in your scenario.

Here's one reason, if your 'random password' consists only of the AES key, and you use the raw RSA operation on it (that is, zero pad it to the size of the RSA modulus, and then compute $M^e \bmod N$), then yes, there does exist weaknesses; there's a meet-in-the-middle attack on it that will search through possible values of $M$ faster than brute force.

Here's how that would work; in a preprocessing phase, the attacker would generate two lists of integers between 1 and $2^{128/2}$ (assuming we're attacking a 128 bit AES key) $A_i$ and $B_i$.  Then, he computes two lists, one consisting of the values $A_i ^ {-e} \bmod N$, and the other consisting of the values $B_i ^ e \bmod N$

Now, when the attacker sees an encrypted message $M^e \bmod N$, he computes the list $(M^e \bmod N) \cdot (A_i ^ {-e} \bmod N) = (M \cdot A_i^{-1})^e \bmod N$, and then scans that list for values in common with the $B_i ^ e \bmod N$ list (which can be done by sorting the lists and doing one pass through both of them).  If there is a pair with $(M \cdot A_i^{-1})^e \bmod N = B_j ^ e \bmod N$, the attacker then knows the value $M = A_i \cdot B_j$.

If the size of the lists $A_i$, $B_i$ are $k$ elements long, the attacker has just searched through $k^2$ values of the message in $O(k \log k)$ time.

Now, I'm not sure how much concern this attack would be in practice; however, RSA with standard padding methods do not have this concern; that would appear (to me at least) enough of a reason to stick with the standard methods.

Another way to look at it; raw RSA (that is, RSA without padding) is fragile; while RSA with good padding is not.  Given that good padding is easy to do, why wouldn't you do good padding?


Best method for checking integrity of 50 GiB files?

Tree hashing would be a natural way to do it.

However, the data still needs to be read. And in practice the hash computation time is negligible compared to I/O, even with a fast SSD.

So, just use a standard hash function. SHA-3 is slow in software, so you'd better opt for BLAKE2.


It is pronounced RIPE "tiny pause" M-D (RIPE for RACE Integrity Primitives Evaluation and M-D for message digest).


GHASH with a finite field multiplication algorithm in reverse order

My question is... what's the most effective way to utilize this existant method?

Well, you could rearrange things to take 1 reverseEndianness operation per block, plus 1 reverseEndianness operation per GCM operation (plus 1 per key setup).

  Let $X_1$, $X_2$, ... , $X_{m-1}$, $X_m$ denote the unique sequence of blocks such that $X$ = $X_1$ || $X_2$ || ... || $X_{m-1}$
  || $X_m$.
  Let $Y_0$ be the "zero block" $0^{128}$.
  For $i$ = $1, ..., m$, let $Y_i = (Y_{i-1} \oplus \text{ReverseEndianness}(X_i)) \cdot H_{\text{reverse}}$.
  Return $\text{ReverseEndianness}(Y_m)$.

where $H_{\text{reverse}}$ is the precomputed $\text{ReverseEndianness}(H)$ value.

This is essentially the same as what you had, except we keep the intermediate $Y_i$ values in bigendian format


You can find the security proofs for 5-round Fiat-Shamir:

Ming-Shing Chen and Andreas Hülsing and Joost Rijneveld and Simona Samardjiska and Peter Schwabe: From 5-pass MQ-based identification to MQ-based signatures. Asiacrypt 2016. https://eprint.iacr.org/2016/708
Özgür Dagdelen, David Galindo, Pascal Véron, Sidi Mohamed El Yousfi Alaoui, and Pierre-Louis Cayrel. Extended security arguments for signature schemes. Designs, Codes and Cryptography, 78(2):441–461, 2016. https://link.springer.com/article/10.1007/s10623-014-0009-7

Their proof (may) contain (2n+1)-round Fiat-Shamir.


How can one parallelize tasks in CTR-AES for maximum performance?

From the diagram on CTR mode

you can notice that there are no dependencies between any of the phases of the pipeline. If you have more than one block-size worth of data, you can process each block-size chunk completely independently of the others by calculating $\mathrm{ciphertext}_i = E(\mathrm{key}, \mathrm{nonce} \, || \, \mathrm{counter}_i) \oplus \mathrm{plaintext}_i$.


Authenticated encryption without padding

If the data to protect has no built-in redundancy at all (for example, has each of its bit determined by fair coin toss), there is no way to protect integrity without expansion (Proof sketch: there are as many distinct possibilities for valid plaintext as there as possibilities for valid enciphered-and-protected data, hence every possible enciphered-and-protected data must be acceptable by the verify-and-decipher operation).

If the data to protect has some built-in redundant part (like, a fixed header of 16 octets), then we can remove it, use normal authenticated encryption, and restore the redundancy after the verify-and-decipher step. Variant: if we are certain that some lossless compression scheme will shrink the data enough (e.g. the plaintext is 2227 symbols restricted to 246 possible values, each coded as an octet, allowing to encode that plaintext as 2211 arbitrary octets by mere conversion from base 246 to base 256, making room for 16 octets), we can compress the data before applying the authenticated encryption, and expand after the verify-and-decipher step.

If the data to protect has some built-in redundancy that we have no way to turn into compressibility but can nevertheless characterize (like, plaintext is the result of applying Bzip2 compression to about one page of sensible English text), we have the option to use Format preserving encryption (that is, in the context, a block cipher with the block size equal to the data size, that implements a key-dependent, random-like, reversible transformation of the whole data). Any alteration of the ciphertext (other than replacing it with a known-valid ciphertext) will make the whole deciphered plaintext random, and we can reliably detect that (with a Bzip2 decompression algorithm hardened against rogue input, followed by even the most basic validation that the output contains a large-enough proportion of English words). Notice however that we loose something on confidentiality: contrary to the previous solution, the same plaintext will always be enciphered to the same ciphertext, which sometime is unacceptable, and does not match the modern goals of a cipher.


Does composing multiple substitution ciphers improve security?

If the substitution ciphers belong to the same family, then their composition will also (typically, assuming that the family is closed under composition) belong to the same family.  Thus, breaking the combined cipher will be no harder than breaking an arbitrary cipher in the family.

For a simple example, combining two Caesar shift ciphers with shifts amounts $a$ and $b$ will just yield a Caesar shift cipher with shift $a+b$.

In particular, all simple substitution ciphers are vulnerable to frequency analysis, and also form a family that is closed under composition — the composition of any two simple substitution ciphers is itself a simple substitution cipher.

Thus, while the combination of, say, a keyword cipher with a Caesar shift might be slightly harder to break than either cipher alone (in the sense that it's not vulnerable to methods that only break either of the component ciphers alone), it's still no stronger than a generic simple substitution cipher.

(Similarly, say, combining two Vigenère ciphers yields another Vigènere cipher, although the effective key length of the combined cipher equals the least common multiple of the original key lengths, potentially complicating cryptanalysis.  Such a combined key does, however, have some repetitive structure that can make it considerably easier to break than a random key of equivalent length.)


Complete Set of Test-Vectors for ECDSA secp256k1

OK, so I quickly found out that there is a test in Bouncy Castle called:

org.bouncycastle.crypto.test.ECTest.testECDSASecP224k1sha256()

which tests exactly what you are trying to do (with a message the same size of a SHA-256 hash).

So I decided to create a new test that duplicates this test, but for SecP256k1 and SHA-256.

I've generated the following test vectors (I'll use hexadecimals):

 d = ebb2c082fd7727890a28ac82f6bdf97bad8de9f5d7c9028692de1a255cad3e0f
 k = 49a0d7b786ec9cde0d0721d72804befd06571c974b191efb42ecf322ba9ddd9a
 M = 4b688df40bcedbe641ddb16ff0a1842d9c67ea1c3bf63f3e0471baa664531d1a

resulting in:

 r = 241097efbf8b63bf145c8961dbdf10c310efbb3b2676bbc0f8b08505c9e2f795
 s = 021006b7838609339e8b415a7f9acb1b661828131aef1ecbc7955dfb01f3ca0e

note that $s$ starts with 6 zero bits, which should be fine.

Finally, you'd want to verify the signature as well of course, so here is the public key:

 q = 04779dd197a5df977ed2cf6cb31d82d43328b790dc6b3b7d4437a427bd5847dfcde94b724a555b6d017bb7607c3e3281daf5b1699d6ef4124975c9237b917d426f

where $q$ is an uncompressed point, consisting of the following coordinates:

x = 779dd197a5df977ed2cf6cb31d82d43328b790dc6b3b7d4437a427bd5847dfcd
y = e94b724a555b6d017bb7607c3e3281daf5b1699d6ef4124975c9237b917d426f

Method of generating the parameters:

private static final void createAndPrintRequiredParameters()
{
    // code used to generate the random key pair (public point converted to uncompressed point encoding manually)
    ECKeyPairGenerator gen = new ECKeyPairGenerator();
    X9ECParameters p = SECNamedCurves.getByName("secp256k1");
    ECDomainParameters params = new ECDomainParameters(p.getCurve(), p.getG(), p.getN(), p.getH());
    SecureRandom kpr = new SecureRandom();
    ECKeyGenerationParameters genParams = new ECKeyGenerationParameters(params, kpr);
    gen.init(genParams);
    AsymmetricCipherKeyPair ecKeyPair = gen.generateKeyPair();
    ECPrivateKeyParameters ecPrivate = (ECPrivateKeyParameters) ecKeyPair.getPrivate();
    ECPublicKeyParameters ecPublic = (ECPublicKeyParameters) ecKeyPair.getPublic();
    System.out.println(ecPrivate.getD().toString(16));
    System.out.println(ecPublic.getQ().toString());

    // code used to generate the message (hash) M
    byte[] mesg = "Maarten Bodewes generated this test vector on 2016-11-08".getBytes(StandardCharsets.UTF_8);
    SHA256Digest dig = new SHA256Digest();
    dig.update(mesg, 0, mesg.length);
    byte[] M = new byte[dig.getDigestSize()];
    dig.doFinal(M, 0);
    System.out.printf("M = %s%n", Hex.toHexString(M));

    // code used to generate the random k
    SecureRandom krng = new SecureRandom();
    BigInteger k;
    do {
        k = new BigInteger(256, krng);
    } while (k.compareTo(params.getN()) >= 1);
    System.out.printf("K = %s%n", k.toString(16));
}

To make sure that the value of $k$ is used directly within the algorithm I did some tests. A $k$ consisting of all FF bytes and a shorter $k$ both failed as expected . A $k$ consisting of 7F byte followed by all FF bytes does work. So the value $k$ within the FixedSecureRandom constructor is indeed directly used.

And finally the method of testing the deterministic result:

private static void testECDSASecP256k1sha256()
{
    X9ECParameters p = SECNamedCurves.getByName("secp256k1");
    ECDomainParameters params = new ECDomainParameters(p.getCurve(), p.getG(), p.getN(), p.getH());
    ECPrivateKeyParameters priKey = new ECPrivateKeyParameters(
        new BigInteger("ebb2c082fd7727890a28ac82f6bdf97bad8de9f5d7c9028692de1a255cad3e0f", 16), // d
        params);
    SecureRandom    k = new FixedSecureRandom(Hex.decode("49a0d7b786ec9cde0d0721d72804befd06571c974b191efb42ecf322ba9ddd9a"));

    byte[] M = Hex.decode("4b688df40bcedbe641ddb16ff0a1842d9c67ea1c3bf63f3e0471baa664531d1a");

    ECDSASigner dsa = new ECDSASigner();

    dsa.init(true, new ParametersWithRandom(priKey, k));

    BigInteger[] sig = dsa.generateSignature(M);

    BigInteger r = new BigInteger("241097efbf8b63bf145c8961dbdf10c310efbb3b2676bbc0f8b08505c9e2f795", 16);
    BigInteger s = new BigInteger("21006b7838609339e8b415a7f9acb1b661828131aef1ecbc7955dfb01f3ca0e", 16);

    if (!r.equals(sig[0]))
    {
        fail("r component wrong." + Strings.lineSeparator()
            + " expecting: " + r + Strings.lineSeparator()
            + " got      : " + sig[0]);
    }

    if (!s.equals(sig[1]))
    {
        fail("s component wrong." + Strings.lineSeparator()
            + " expecting: " + s + Strings.lineSeparator()
            + " got      : " + sig[1]);
    }

            // Verify the signature
    ECPublicKeyParameters pubKey = new ECPublicKeyParameters(
        params.getCurve().decodePoint(Hex.decode("04779dd197a5df977ed2cf6cb31d82d43328b790dc6b3b7d4437a427bd5847dfcde94b724a555b6d017bb7607c3e3281daf5b1699d6ef4124975c9237b917d426f")), // Q
        params);

    dsa.init(false, pubKey);
    if (!dsa.verifySignature(M, sig[0], sig[1]))
    {
        fail("signature fails");
    }
}

which is a direct copy of the test for SecP224k1 and SHA256, but of course with the different parameters.


There are various adversary models, in fact it is typical to test our schemes against multiple adversaries to prove various nuances of security.

The most intuitive of all is an adversary that can produce the plaintext (or a part of it) given only the ciphertext. An extension to this model, stronger than the other, is the one you mentioned, letting the adversary select a number of plaintexts $n$ (which could be infinite), give him the ciphertexts and some random data and let him decide which is which.

In general we require the adversary to produce a result in polynomial time because while many of the primitives can in theory be broken, the probability of this happening in polynomial time is considered negligible.


It doesn't make too much sense at all to send the IV together with the key. The whole idea of an IV is that it is unique per key. But if the key changes value each time, then any IV is unique.

So you could use a static IV or even an IV that consists of all zeros. In that case you only need to worry that you don't reuse the key at other locations in the protocol. For instance for CTR mode, you should not use a Key Check Value that is generated by encrypting a block consisting of all zero's, as it would leak the initial block of the resulting key stream.

It's not a good idea to perform operations with the key to derive an IV though. If you need a separate key and IV from a given secret, please use a KBKDF such as HKDF to separately calculate the key and IV from the secret.

If your key is not changing despite the protocol given above then just prefix a unique (cryptographically safe random) IV to the ciphertext. This should also be the fail-safe default. Using an authenticated cipher like GCM or EAX should also be considered.

Edit

Sending the secret value to the other side over a secure channel is usually not a good idea. Session keys should be established beforehand, preferably by using a key agreement algorithm to provide forward security. Sending the key over a secure channel sounds easy, but if you already have a secure channel, you don't need a session key to establish a new one.


What's the point of hiding the key in white box cryptography if the attacker already has full access to the encryption (or decryption) implementation?

The main goal is to, at least, oblige the attacker to use the software to consume the encrypted message and avoid to use it on a different platform.
It is quite easy to understand this reason if one thinks to the DRM (Digital Right Management) model: one vendor sells hardware with the capability to show some media content. If an attacker can decrypt and use the content on her PC the vendor loses some market.
In the mobile payment context one wants to avoid that a malware could steal payment keys and use them in a different platform against the legit user.
A different use is to protect the Intellectual Property from the final user: some piece of firmware or software has to be given to the final user but the vendor wants to keep it protected.
Other examples can be found thinking when, where and why hardware tokens are used. The white-box encryption can be seen as, with some other software security measures, as a cheap replacement for the hardware tokens (or smart cards).

Moreover you can see the white-box encryption as a way to transform a symmetric key algorithm into a asymmetric one. If it is infeasible to reverse the white-box encryption algorithm into a decryption one and it is infeasible to extract the key, only the encryption algorithm is available and the decryption remains infeasible. The same applies in the opposite direction: providing a white-box decryption makes impossible to encrypt something under the same key.

Some other security properties are discussed in this paper White-Box Security Notions for Symmetric Encryption Schemes

In particular the "incompressibility" property says that "should not be possible to output a program smaller than the challenge one doing the same crypto-operation". Some solutions have published achieving a provable incompressibility, the reason motivating such construction is that it is more difficult for a national agency to store (say) 1 terabyte of key per person to decrypt the targeted user data, while would be feasible to store the corresponding 128-bit key.


Why is double hashing universal hash function still a universal hash function?

Is there a proof that shows that double hashing two universal functions with arbitrary $i$ will produce another universal function?

If $i$ is fixed, then no, $h_i$ need not be universal.

For a simple counterexample, consider $U$ which consists of 2 elements and $H$ which consists of 1 element $h$, with $\alpha$ and $\beta$, with $h(\alpha) = 0$ and $h(\beta) = 1$.  It is easy to see that $H$ is universal.

However, if we select $i = m-1$, then $h_i(x, m)$ is not universal (as it is 0 for both possible inputs $x$).

Now, let us consider where $i$ is uniformly distributed; that is, the family $H'$ that $h_i(x, m)$ belongs to contains all $i$ values.

Then, if $m$ is composite, the answer is still no.  Similar counterexample: suppose $a$ is a proper factor of $m$; then, consider the $H$ which consists of 1 element $h$, with $h(\alpha) = 0$ and $h(\beta) = a$

Then, $h_i(\alpha, m) = h_i(\beta, m)$ with probability $a/m$; not universal.

On the other hand, if $m$ is prime, then $h_i$ will necessarily be universal (and we need not assume that the $h_b$ side is universal); this can be shown for any two distinct inputs $\alpha, \beta$ with a simple case analysis (where the probability in both those cases is $\le 1/m$):

If $h_b(\alpha) = h_b(\beta)$, then the probability is $\le 1/m$ (because of the universality of $h_a$)
If $h_b(\alpha) \ne h_b(\beta)$, then there is a unique value $i$ with $h_a(\alpha) + i h_b(\alpha) = h_a(\beta) + i h_b(\beta) \mod m$, and as there are $m$ possible values of $i$, $i$ will be that unique value with probability $1/m$


How does CBC work with read-write volumes?

You should read the wikipedia article about disk encryption.

In short: for disk encryption, data is organized in sectors (for instance of size 512 bytes), and data may be encrypted with a chaining mode of operation such as CBC only inside these sectors, using a different initialization vector for each sector.


Generate a random number $r \in \{1,2, \dots , k\}$, where $k$ is not public and is distributedly held

You can do anything in MPC, as long as you can express it in a circuit. I assume that there is a known upper bound on $k$ (otherwise you can't even share it). In that case, all you need to do is to take enough randomness (security parameter number of bits more than the upper bound) and then compute the sum of the randomness held by each party modulo $k$ (plus 1). This can certainly be done via a circuit.


Post-Quantum security of Pseudo-Random Functions

The best generic classical attack on a PRF is a generic preimage search for the unknown key.  Given an input $x$ and an output $f_k(x)$ for uniform random $k \in \{0,1\}^n$, the best known algorithm costs about $2^n$ trial evaluations of $f$ to find $k$.  Given multiple targets $(f_{k_1}(x), f_{k_2}(x), \dots, f_{k_t}(x))$, it costs about $2^n\!/t$ trial evaluations of $f$ to find at least one of the $k_i$, using a rainbow table search if it is done on a machine parallelized at least $t^2$ ways.

The best generic quantum preimage search costs about $\sqrt{2^n} = 2^{n/2}$ trial evaluations of quantum superpositions of $k \mapsto f_k(x)$, using Grover's algorithm.  Grover's algorithm doesn't parallelize well: if parallelized $p$ ways, it returns an answer in time $\sqrt{2^n\!/p} = 2^{n/2} / \sqrt p$ and therefore costs $2^{n/2} \cdot \sqrt p$ to run a machine $p$ times larger for $1/\!\sqrt p$ times as long.  In the single-target setting, Grover's algorithm is asymptotically optimal.  The best known batch advantage for a multi-target search (not known to be optimal but dramatic improvements seem unlikely) is modest, reducing the cost by a mere factor of $\sqrt[4]{t}$ to find the first of $t$ targets.

There is also a fantasy threat model where not only does the adversary have a quantum computer, but where you for some inexplicable reason compute quantum superpositions of $x \mapsto f_k(x)$ on behalf of the adversary.

While I don't know of any generic attacks, many particular cryptosystems are breakable using Simon's algorithm (random example) in this doubly unrealistic threat model where the adversary has a quantum computer, you have a quantum computer, I have a quantum computer, and everyone and their dog has a quantum computer, and you blithely compute secret functions on quantum superpositions of inputs on request from the adversary.

Solution: When strange men in dark coats ask you on the street for quantum superpositions of your secret functions, RUN AWAY!

More seriously, if you are tempted to evaluate secret functions on a quantum computer yourself, on behalf of anyone including puppies and unicorns and not just strange men in dark coats, take a moment to do a literature search to reconsider your life choices.


Needed: signature over a collection of hashes

I am not quite sure if I exactly get what you are looking for, but I'll give it a try.

This answer refers to the original question before the edit

  I'm looking for some kind of crypto-based data structure that will allow me to produce a signature over a set of hashes such that I can verify that any of the hashes is in the set at a later point in time without having to distribute all of the hashes.

One possible approach to produce a signature for a sequence of messages $(m_1,\ldots,m_n)$ (or hash values) is to build a Merkle tree from this sequence.

The idea of a Merkle tree is
to assign the messages $m_i$ to the leaves of a binary tree from left to right,
and do the hashing recursively upwards, starting from the lowest level
in the tree.

More formally, a Merkle tree
is a complete binary tree, together with a cryptographic hash function
$H:\{0,1\}^*\rightarrow \{0,1\}^{\ell}$ and an assignment
$\phi:N\rightarrow \{0,1\}^{\ell}$, where $N$ is the set of nodes of the
tree. The assignment $\phi$ for the label of the nodes is recursively
defined, where $v_P$ is the parent node
and $v_L$ and $v_R$ the left and right child respectively. Furthermore,
$x$ is a string that is assigned to a leaf.
\begin{equation} \phi(v_P):= \begin{cases}
H(\phi(v_L)||\phi(v_R)) & \text{if $v_P$ has two children};\\
H(\phi(v_L)) & \text{if $v_P$ has one child};\\ H(x) & \text{if $v_P$ is
a leaf.} \end{cases} \end{equation}
Additionally, define the
authentication path $A_v=\{a_i|0<i\leq
h\}$ of a leaf $v$ as the set containing all values $a_i$. The value
$a_i$ at height $i$ is defined to be the label of the sibling of the
node of height $i$ at the unique path from $v$ to the root.

Note that if your values $(m_1,\ldots,m_n)$ are already hashes, then you can directly assign these values to the leaves (without hashing them again). Subsequently, the $m_i$ are denoted as messages (irrespective if they are messages or hash values).

Put differently, a Merkle tree can be used to release a message $m_i$ and the coresponding authentication path $A_{m_i}$ such that
everybody is able to verify that $m_i$ "is in the tree", but does not require access to the all the remaining messages.

Now take a secure signature scheme and sign the root-hash of the Merkle tree. Then given
the signature, $m_i$ and $A_{m_i}$ it can be checked that $m_i$ is in the signed sequence $(m_1,\ldots,m_n)$ without
requiring all the other messages $m_j$, $j\neq i$. Basically, from $m_i$ and $A_{m_i}$ one recomputes the root hash and checks the digital signature.

However, note that this does not ensure a real hiding of the remaining messages $m_j$. If the remaining messages have a short length and/or are known to come from a small set,
one can mount a brute-force attack by simply hashing all possible values and check whether the result
matches the root hash.

This can be prevented if one does not use simple hashes for the leaf nodes, but uses
commitments instead. This approach is for instance applied in redactable signatures (RS) or content extraction signatures (CES).

How does this related to what you seek

You do not have to distribute all hashes, but for every value $m_i$ a "proof" that the value is in the set (the Merkle tree) you have to distribute $(m_i,A_{m_i})$. The advantage is that if you use the commitment based approach as applied in RS or CES, nobody can test against your signature to check if a given value is in the set, unless you want to explicitly allow that by providing $(m_i,A_{m_i})$.

EDIT (to answer the edited question)

Any approach that will give you cryptographic security guarantees that you will not encounter false positives (such as cryptographic accumulators, Merkle trees, vector commitments, zero-knowledge sets, etc.) will require to provide a "witness" for every value to be able to check against the structure.

If you tolerate a larger false-positive probability you can use for instance Bloom filters to represent your set and allow set membership queries without any witnesses.


the probability of sampling a group element that falls in the subgroup on elliptic curve

Yes, every finite group (including an elliptic curve over a finite field) either is a finite cyclic group or is the product (not sum) of at least two (not exactly two) finite cyclic groups, and in the latter case some (or even all) of those subgroups may be relatively small. But for crypto we only use a prime-order subgroup that is large enough to satisfy a  specified security parameter, which in practice is set close to the size of the full group of the curve (and also close to the size of the underlying field, per Hasse's theorem). For example the widely-used X9/NIST/SECG curves over $F_p$ were chosen to have prime order, so the only subgroup is the full group and any point chosen as G has that order; this is also stated as having cofactor 1. Bernstein et al's Curve25519 has a full group of order near $2^{255}$ and uses a subgroup of order near $2^{252}$, also stated as cofactor 8; this is not negligible.
If a cryptographic scheme (or implementation of one) that intends to use such a sufficiently-large but proper subgroup fails to ensure or verify that elements (for EC points) purported to be in the subgroup actually are, an attacker may be able to cause it to use values constrained to one of the small subgroups, and thereby gain an advantage; these are generically called small-subgroup attacks and you will find quite a few existing Qs and As about them. 25519 makes privatekeys a multiple of 8 to block this.
That's why your question makes sense for EC mathematics, but not for EC crypto as practiced.


Step by step conceptual implementation of AUTHENTICATED Diffie-Hellman?

Both parties are pub-key holders, so let's call them A and B having their private keys $a$ and $b$.

DH conceptually goes (this is something you already may know):

A: computes $g_a = g^a \pmod p$ and sends it to B
B: computes $g_b = g^b \pmod p$ and sends it to A
A: computes key $K = g_b^a \pmod p = g^{ab} \pmod p$
B: computes key $K = g_a^b \pmod p = g^{ab} \pmod p$

and now there are several authentication schemes to validate they're really speaking to each other. You may check the X.1035 or SPKE, there are the complete step-by-step recommendations.

Basically I found 2 methods:

A and B send each other hash of the salt, their public keys, shared password and the computed secret key
DH parameters ($p$ or $g$) depend from the shared password


Decryption or attacking DES encrypted file

Brute force is feasible as codesinchaos points out. That said there is more to it than that.

First you'll need some way to tell whether or not decryption was successful. For example, you may look for english language text upon decryption. Automating this will be essential as you don't want to manually look at every decryption to decide whether or not you were successful.

Second, you'll have to try different modes. If it was encrypted with ECB, you should be able to recognize that by looking at the ciphertext (see if there are lots of repeated blocks of ciphertext; a block in des is 8 bytes). Otherwise, you'll have to try all the common modes. Still, should be able to be accomplished via brute force.


Is using RSA with SHA-1 considered as secure as HMAC-SHA-1?

No, unfortunately your well meant comparison with HMAC fails and RSA with SHA-1 - as defined for PKCS#1 v1.5 padding and PSS - is considered insecure.

The construction of HMAC makes it near invulnerable to attacks on the collision resistance of the underlying hash. That is because it uses the secret key as input to the hash function to create the additional resistance. Any adversary does not have access to that secret key.

However, if the hash is used in a signature, they hashing of the data is commonly performed before the keyed operation is applied. No shared secret is available to allow for the same construction as HMAC and no randomization of the hash is performed. That means that the (lack of) original collision resistance is preserved, and that the signature generation function is therefore vulnerable as well.

As noted in the comments and explained in this answer an additional random input to the data could strengthen the hash and thus signature function significantly, even if that randomization doesn't rely on a shared secret. It would however change the signature API as provided by many RSA functions libraries significantly to add randomization to the hash function as they often directly accept hash values as input.


Signature Generation Time vs Verification Time

I am asking myself whether there are use cases were a fast signature verification is an important requirement and were RSA would be actually the preferred choice?

Well, as you already mentioned the comparison is a bit tricky. For 128 bit security you'd use ECC-256 and RSA-3072 (and using 3072 is on the low end). For most RSA implementations 3072 seems at the high end.
However, the main place where quick verification is important in PKI. Generation of signatures below certificates is generally only performed once, while verification of certificate chains happens all the time. Generally you'd try and cache verified / trusted certificates, but remember that all receivers (such as browsers) must initially verify the certificates none-the-less.
Note that smart cards also may use a PKI using more simplistic Card Verifiable certificates. For smart cards the smaller ECC keys and signatures are an important factor: both IO and RAM is usually limited. So in that case ECC may be more efficient than RSA. There are often other properties than raw CPU time to consider.


Here is the optimization in more detail. Start with $[\bar{A} \mid I_n \mid G']$ where $\bar{A} \in \mathbb{Z}_q^{n \times n}$ and $G = [I_n \mid G']$ (where $I_n$ is the $n$-by-$n$ identity matrix).
Note that the concrete gadget matrices $G$ constructed in the paper already contain an identity submatrix (up to reordering of columns). But in general, $G$ will have an invertible $n$-by-$n$ submatrix $K$, which we can move to the leftmost columns, and then replace $G$ with $K^{-1} G = [I_n \mid G']$. This is just as good of a gadget matrix as the original $G$, because it has the same kernel lattice $\Lambda^\perp(G)$ (up to permutation of coordinates).
Now we can build a public matrix $A = [\bar{A} \mid I_n \mid G' - (\bar{A} R_2 + R_1)]$ for secret short $R_1, R_2$ whose entries are drawn from $\mathcal{D}$, which will serve as the trapdoor. (In fact we really only need to store $R_2$; see below.)
The $[\bar{A} \mid \bar{A}R_2 + R_1]$ part is an LWE instance and hence pseudorandom by assumption, so $A$ is indistinguishable from uniform (apart from its $I_n$ submatrix). We also have $$ A \begin{pmatrix} 0 & R_2 \\ I_n & R_1 \\ 0 & I \end{pmatrix} = [I_n \mid G'] = G, $$ which is the desired "trapdoor" relation. (Of course we can treat the $0$ and $I$ submatrices in that block matrix as implicit.)
We are basically done, but note that LWE instances constructed from $A$ should ignore its $I_n$ submatrix (see also this question and my comment); let's make this explicit. By dropping the $I_n$ submatrix from $A$ we get $A' = [\bar{A} \mid G' - (\bar{A}R_2 + R_1)]$ and $$ A' \begin{pmatrix} R_2 \\ I \end{pmatrix} = G' - R_1 .$$ This is a good enough approximation to the trapdoor relation when we use only "short" LWE secrets $s$ and the identity tag: given $b^t = s^t A' + e^t$ for sufficiently short $s,e$, we can use the trapdoor $R_2$ to compute $$ b^t \begin{pmatrix} R_2 \\ I \end{pmatrix} = (s^t A' + e^t) \begin{pmatrix} R_2 \\ I \end{pmatrix} = s^t (G' - R_1) + e^t \begin{pmatrix} R_2 \\ I \end{pmatrix} \approx s^t G',$$ from which we can recover $s$ and then $e$.
Importantly, the "most-significant bits" of the entries of $s$ are zero because $s$ is short, so to recover $s$ from the "noisy" $s^t G'$, we don't need the "noisy" $s^t I_n$ subvector that is now missing due to omitting $I_n$ from $G$. If we were to use a non-identity invertible tag $H$, then we would need to recover $s$ from a noisy $(s^t H)G'$, which is trickier because $s^t H$ can have "large" entries. It's not clear to me whether this can be done efficiently in general.


How can I implement $\kappa\times OT_\kappa$?

You pick your favourite public-key based OT protocol. Usually these will allow you to input a choice bit and learn exactly one out of two $r$ bit values in return.
Then you input two random $r$-bit values into that protocol and use the $\kappa$-bit hashes as output. This is your $OT_\kappa$ protocol.
Next, you execute $\kappa$ (e.g. 128) instances of that protocol in parallel with independently random choice bits. This is what is usually done for these OT-extension protocols.
As for building a $OT_\kappa$ from $OT_1$s, you can indeed run $\kappa$ such protocols in parallel with the same choice bit (which is only immediately secure in a semi-honest model).


MPC and Secret Sharing in not Fully-Connected Network

Secure computation over incomplete networks has been the subject of several works in the past. However, as far as I am aware of, none of these works uses the model of rational cryptography, where the agents are modeled in a game-theoretic way as rational players rather than computationally-bounded machines.

The most classical setting of secure computation considers security with aborts (adversaries may prevent the completion of the protocol, but they cannot compromise security or correctness of the computation), with computational security guarantees. In this setting, it is relatively easy to see that secure computation over an incomplete but strongly connected network can be reduced to secure computation over a complete point-to-point network. Indeed, assuming for simplicity that a public-key setup has been made, each party will simply compile the complete point-to-point MPC protocol as follows: each time a party $A$ must sends a message $m$ to a party $B$, she encrypts $m$ with the public key of $B$, signs it to guarantee integrity and authenticity, and sends the message to all parties she is connected to. Each time $A$ receives a message for which she is not the target receiver, she broadcasts it back to the parties she is connected to (unless she already broadcasted this message in the past, of course). This guarantees that, unless a cheating party prevents a message from passing (which is equivalent to aborting and preventing completion of the protocol), the correct message will eventually securely reach it's target receiver, hence one can implement an arbitrary MPC protocol this way. The same strategy can be used to execute a key exchange over an incomplete network, removing the need for a public key infrastructure in the first place (but one must still be able to authenticate himself).

Now, there are many questions that the above naive solution does not address: can we get something more efficient? Especially, what if we are willing to assume a bit more than just "the network is strongly connected"? Much more efficient protocols are likely to exist on some more specific types of graphs. What if we want unconditional security (with honest majority)? What if we want to hide the topology of the network? What if we want fairness, or guaranteed output delivery? What if the structure of the graph is not fixed before the protocol, but determined dynamically?

Not all of these questions have been considered. What has been looked at in the literature includes (see also additional references in the linked papers):

Information-theoretic secure computation with private and reliable channels in an incomplete network was addressed in this paper.
The more specific case of secure aggregation over incomplete networks was addressed here.
This very cool recent paper addresses the challenging case of secure computation over an incomplete and dynamic network (whose connectivity is determined dynamically). I also suggest, for more references on MPC over incomplete network, that you look at their introduction; page 1 contains a bunch of references.
This recent paper provides further insights regarding the characterization of information-theoretic secure computation over incomplete networks.
Eventually, there has been a lot of work on topology hiding computation, where the goal is to securely compute a function over an incomplete graph, while at the same time hiding the topology of the graph. See e.g. 1, 2, 3, 4 and references therein.


Adding a number congruent to $0$ to ensure that the mod operation takes a constant number of instruction cycles

As the comment you quote notes:

  On some platforms, including Intel, the [modulo] operation can take a smaller number of cycles if the input is "small".

Is that really true, and what does that mean?  A bit of Googling led me to the Intel® 64 and IA-32 Architectures Optimization Reference Manual, which in table C-16 lists the throughput of the DIV instruction (which is used to compute both division and modulo) as "~20-26" cycles per instruction (~19-25 cycles on Ivy Bridge), with the following footnote:

  The throughput of “DIV/IDIV r32” varies with the number of significant digits in the input EDX:EAX and/or of the quotient of the division for a given size of significant bits in the divisor r32. The throughput decreases (increasing numerical value in cycles) with increasing number of significant bits in the input EDX:EAX or the output quotient. The latency of “DIV/IDIV r32” also varies with the significant bits of the input values. For a given set of input values, the latency is about the same as the throughput in cycles.

So what does that mean in plain English?

Integer division and modular reduction are not constant-time operations on Intel x86 CPUs.
The time taken to divide or reduce a number depends (mainly?) on the bit length of the number being divided or reduced.

Thus, the time needed to calculate x % y can leak information about the size of x.  However, we can minimize this leakage by instead calculating (x + c) % y, where c is a large constant multiple of y.  In particular, the constant c should be chosen so that:

the bit length of x + c is the same for all possible values of x,
the calculation of x + c cannot overflow for any possible value of x, and
of course, c needs to be divisible by the modulus y.

Depending on the range of possible x values, of course, it may not always be possible to find a constant c that would satisfy these requirements.

In the code you quote above, however, the constant 4294949760 appears to have been chosen as the largest value c that will not overflow a 32-bit unsigned register when added to any number 0 ≤ x < 214, and which is also an integer multiple of the possible moduli 40, 48, 64 and 128.  Given that 4294949760 ≥ 231, this also ensures that it satisfies the first condition: bitlength(4294949760 + x) = 32 for all 0 ≤ x < 214.


Double DES meet in the middle attack: number of candidate keys

My question is, where do we get the $2^{64}$ mentioned in the very first sentence?

There are a couple of equivalent ways of looking at the problem.

One way is to treat 2DES with an incorrect key as a completely random mapping; there are $2^{112}$ possible keys, and each incorrect key will map our one known plaintext block to a random ciphertext block; there are $2^{64}$ possible ciphertext blocks (of which 1 is the one which we know is valid); and hence each key will do the mapping correctly is $1 / 2^{64}$; hence the number of keys we expect to happen to get the mapping right is about $2^{112} / 2^{64}$ (as stated in the paragraph).

  So wouldn't the number of candidate keys be the number of elements of the intersection of these 2 sets?

That's another, equally valid way of looking at the problem.

If we treat DES (both encrypt and decrypt) with an incorrect key as a completely random mapping, then both the set of $2^{56}$ ciphertexts from the first level encryption, and the $2^{56}$ plaintexts from the second level decryption, are completely random.  There are $2^{64}$ plaintexts possible from the second level decryption, and so a specific block is a possible second level decryption with probability circa $2^{56}/2^{64} = 2^{-8}$.  There are $2^{56}$ ciphertexts from the first level, and each one happens to be a possible second level decryption with probability $2^{-8}$, and so the expected size of the intersection is, wait for it..., $2^{56} \cdot 2^{-8} = 2^{48}$.


why babai rounding technique does not work for finding closest vector using bad basis

The rounding algorithm, given $\mathbf{t=v+e}$ will output
\begin{equation}
\lfloor\mathbf{t}^t\cdot \mathbf{S}\rceil\cdot \mathbf{S}^{-1}=
\lfloor(\mathbf{v}^t + \mathbf{e}^t) \cdot \mathbf{S}\rceil\cdot \mathbf{S}^{-1}=
\mathbf{v}^t +\lfloor\mathbf{e}^t\cdot \mathbf{S}\rceil\cdot \mathbf{S}^{-1}
\end{equation}
where $\mathbf{v}$ is in the dual lattice. Now, the algorithm works correctly if $\lfloor\mathbf{e}^t\cdot \mathbf{S}\rceil$ becomes zero, which holds as long as both $\mathbf{e}$ and $\mathbf{s}_i$ are short enough (i.e., the basis is good enough)


Book ciphers are well understood and this seems like a fairly minor variation. Following Kerchoff's Principle we separate the key being the book and the arithmetic operator and numbers and the rest. Picking a random number for fourth position makes no difference in this regard. But even if we let that be a secret to it makes little difference. Humans are lousy at picking random numbers and this will be apparent.

Multuplying by a constant is also a really bad idea. It will be very quickly apparent all numbers in a certain position are a multiple of constant and will be devided by it.

Subtracting or adding a number from row or character number will also be apparent after collecting sufficient data by observing the skewed range. such an addition will be slightly harder regarding page number due to higher cardinality of page numbers but won't necessarily be an issue see next.

Humans doing a poor job picking random numbers. Many people who use book ciphers flip forward a bit from where they are or start reading from the start of the page. This means rare letters will require on average more skipping forward leading to some leakage.

Also the book itself may be selected from a limited set of books can make the book itself guessable.  Given a large library of online books brute forcing such a cipher isn't all that difficult.

If you do not want to mark the book making it physically obvious it is a cipher key it is difficult to prevent repetitions when randomly selecting characters.

If the book is considered a secret not chosen from a limited selection available at your local book store for instance and the person using it picks a random starting point in the book for each letter and seeks the next matching one and marks off each used letter to prevent duplicates then it is a fairly secure cipher even without the additions described.

In reality most book ciphers have been and will be broken.


$H(x) < D$ likely mean that $D$ is greater than the integer in range $[0,2^k-1]$ represented by the $k$-bit bitstring $H(x)$ in binary, per some convention. If we note the bits of that bitstring $b_0$ for the first/left one, and $b_{k-1}$ for the last/right one:

$\displaystyle\ \ \ D>\sum_{i=0}^{k-1}b_i\,2^{k-1-i}\ $ for big-endian, which thends to be the default convention; or

$\displaystyle\ \ \ D>\sum_{i=0}^{k-1}b_i\,2^k\ \ $ for little-endian.

If $H$ is secure in the random oracle model, and $x$ chosen without knowledge of $H$, then (for either convention) $H(x) < D$ holds with probability $\displaystyle{\max\left({D\over2^k},1\right)}$.