Using ECDH for encryption and decryption

Use crypto_box_curve25519xsalsa20poly1305 from libsodium/nacl.

How it works, roughly summarized with all details of encoding and coordinates omitted:

Alice and Bob have public keys $A = [a]G = \underbrace{G + \dotsb + G}_{\text{$a$ times}}$ and $B = [b]G$.
Here $G$ is the standard base point of Curve25519, $a$ is a secret 256-bit integer known only to Alice, and $b$ is a secret 256-bit integer known only to Bob.
When Alice wants to send the $n^{\mathit{th}}$ message $m_n$ to Bob, she sends the box $c_n = \operatorname{crypto\_box}(m_n, n, B, a)$ to Bob.  What this does is:

Computes the shared secret key $k = H([a]B) = H([a\cdot b]G)$, where $H$ is HSalsa20.
Uses $k$ as the key and $n$ as the nonce to authenticate and encrypt the message $m_n$ using crypto_secretbox_xsalsa20poly1305.

When Bob receives the alleged $n^{\mathit{th}}$ box $c'_n$, which may be $c_n$ or may have been modified in transit or otherwise forged, he opens it with $\operatorname{crypto\_box\_open}(c'_n, n, A, b)$—but he makes sure to immediately drop it on the floor if crypto_box_open fails, meaning that it was a forgery.  What this does is:

Computes the shared secret key $k = H([b]A) = H([a\cdot b]G)$.
Uses $k$ as the key and $n$ as the nonce to authenticate and decrypt the box $c_n$ using crypto_secretbox_xsalsa20poly1305_open.

In other words, crypto_box and crypto_box_open first do a static/static Diffie–Hellman key agreement, and then use the resulting key for an authenticated cipher.

Alice and Bob must never reuse any message number or nonce $n$ with a single pair of sender/receiver public keys or else the security will evaporate.  If the communication is bidirectional, i.e. if Alice and Bob both need to send messages to each other, you might have Alice choose even values for $n$ and Bob choose odd values.


What are the steps for decryption of RC4?

Your guess is correct. RC4 basically generates a very long key to fit your message. Encryption and decryption is simply xoring with the output of RC4 for that particular position in the key stream.

In general, most stream ciphers work that way. The complex part is that the algorithm should generate a very long key that is not susceptible to attack (the ideal being a one-time pad of the same length as the message).

So once you understand encryption using RC4, switch "plaintext" and "ciphertext" in the explanation to give you decryption.

edit: you probably know this already but it doesn't hurt to reiterate: don't use RC4.  It is not secure and can be broken.


What benefits do substitution boxes and permutation boxes offer in DES?

In general, the key length and number of rounds are the dominant factors in deciding cipher strength. But you need to consider how the rounds are constructed and how the key is used.

Substitution and permutation are the bread and butter of DES. That's literally all it is - substitution, permutation, and XOR.

Here is a diagram of the DES fiestel function for reference.

The DES substitution boxes ($S1$ through $S8$ in the diagram) are the only non-linear part of the cipher. Without them, the cipher would be nothing but XOR operations. It would be easy to come up with (relatively simple) linear equations relating the key, plaintext, and ciphertext bits.

The DES permutations ($E$ and $P$ in the diagram) propagate and distribute the bits of the previous output. Without these permutations, any small change in the plaintext/ciphertext would result in a small change in the resulting ciphertext/plaintext.

Suppose $E$ and $P$ don't exist and there are two plaintexts which are identical except for a difference in the first bit.

Since the difference is in the first bit, it will be fed into $S1$. $S1$ outputs 4 bits, so at most the first 4 bits will be different.

Repeat for the 2nd round. Since $S1$ takes the first 6 bits as input, those 4 bits go through $S1$ and output another 4-bit difference.

As you can see, after any number of rounds, the difference will still only be in the first 4 bits.

Because of the Feistel structure of DES where the left and right halves get swapped through the cipher, up to 8 ciphertext bits can be different: the first 4 bits in the left 32-bit half, and the first 4 bits in the right 32-bit half. Not only does a small change in the plaintext result in a small change in the ciphertext, the differences have locality. This makes differential cryptanalysis very easy to perform.

I hope that was the answer you were looking for.


Why/how is libsodium/nacl's cryptobox repudiable?

To take SEJPM's answer and be more explicit: Bob can also generate that ciphertext.

One of the conditions on nonrepudiation is that no one (other than Alice, assuming her private key wasn't leaked) could possible generate that message.  This doesn't hold here.  If Bob can decrypt the ciphertext, he knows Alice must have generated it (as Bob knows he didn't), however he can't prove it to anyone else.


Replay attack prevention under strict conditions

The standard solution would be to have the sender maintain a counter, and sending the value of that counter in each request (which is tied into the integrity check of the request).  The receiver would remember the largest counter value that he has received a valid request for, and a bitmap showing which of the N requests prior to that he has actually seen.  With 1kbyte of memory available on the receiver, you can have N=8000 or so, which means that we can do accurate replay detection, as long as we don't get a request that is older than 8000 requests previous to the most recent.  If we do get such a request, we'll reject it, even if it is a previously-unseen request.

See RFC6479 for details on one possible method of implementing this.

As for how HTTPS does replay detection, well, each TLS record has a sequence number associated with it.  Both sides maintain a copy of the counter, and it is included in the integrity check.  So, if someone were to replay an HTTPS record (adjusting the TCP sequence numbers, if they don't do that, the TCP stack will assume that it's a retransmission and ignore it), the TLS sequence number of the receiver won't be the same as the sequence number that the sender used, and so the integrity check will fail, and the record will be rejected (and the session will be shut down; TLS can't recover from these sorts of errors).


Why does WPA-PSK not use Diffie-Hellman key exchange?

As Thomas pointed out in his comment, in WPA-PSK the parties already have a shared secret (the pre-shared key), so there is no need to go through the step of Diffie-Hellman key-exchange -- unless you want perfect forward secrecy (PFS) (see update below).

In WPA, the client and the access point goes through a step known as the "4-way-handshake" to verify that the other party is in possession of the pre-shared key and to derive session keys for actual (encryption/authentication) usage. This step involves nonces from both sides, and some cryptographic computations, with the end result that 1) both parties can verify that the other party is in possession of the common secret and 2) they both have derived a shared session key which they will use for the actual encryption.

The picture below shows the steps in this process. The Supplicant is the client and the Authenticator is the access point. The PMK is the shared secret. In a typical home-user setup, the PMK is usually derived from a password using PBKDF (this password is what you normally punch in when connecting to a wireless network). The PTK is the derived key that they end up actually using for encryption.

UPDATE

As mentioned in the comments, the above does not actually answer why WPA-PSK does not use DH. However, before discussing that, let's clarify what DH has to offer over what's currently being used, and also why the use of pre-shared keys diminishes some of those advantages.
I claim that the one big advantage of using DH is that if offers perfect forward secrecy (PFS), while the ability to "separate" users from each other on the same WLAN is more debatable.

First we need to be clear about the kind of attacks we want -- and can -- be able to protect against.

Outsiders, i.e. attackers not knowing the PSK: If the PSK contains sufficient entropy (either drawn completely at random from a big key space or derived from a sufficiently long/complex password) and the PSK is kept safe and never leaked then DH does not offer anything over the current solution.
If, however, the PSK is either lost or derived from a weak password, then the current system is completely broken. The reason is that the session keys are completely derived from the PSK, hence anyone who knows this can decrypt all traffic. Even worse, since it does not offer PFS, an attacker can go back an decrypt all previous traffic as well. The use of DH would prevent this. Since in practice most home WLANs uses a weak password to derive the PSK, DH would indeed be an upgrade.
Insiders, i.e. attackers knowing the PSK: Now consider the scenario where the attacker knows the PSK. What could the handshake offer then? As mentioned above, with the current system the answer is nothing.  So what about DH? Assuming that in this scenario the PSK is only used to authenticate the DH exchange (say with a MAC), the DH would still offer security against a passive attacker, while nothing against an active attacker. Why? In the passive scenario, the attacker has to break the DH exchange which we assume is intractable. On the other hand, in the active scenario, the attacker can do a classic MitM attack, since he can forge valid handshake messages. Thus, under the typical conservative approach taken in formal security models, we would conclude that DH offers no security benefits over the current scheme since we always assume that the attacker is active. However, in practice, conducting an active MitM attack can sometimes be tricky to pull of. Thus, using DH significantly increase the cost and difficulty for the attacker. Since it forces him to be actively present during the hand shake, this also prevents large-scale passive snooping.

So to conclude, using DH would provide huge benefits in the sense of providing PFS. Also, it also provides some degree of protection of insider attacks, as long as the attacker stays passive.

So why was the 4WHS not designed to use DH?

Full disclosure:
this will just be speculation on my part, since I do not know the arguments that went in to the design decisions of the IEEE 802.1i standard.

I guess that at the time WPA (or more correctly IEEE 802.11 RSNA) was designed, the value of PFS was probably not fully appreciated. In hindsight of the NSA revelations, it is of course easy for us to understand its importance now, but at that time it might not have been so clear. Thus, if you are not required to have PFS, and you already have a PSK available to your protocol, then there is a very simple reason why DH would not be used: efficiency. Symmetric primitives are much much more efficient than public-key primitives, hence if you can get away with only using that, the choice is obvious.

*Incidentally, the IEEE 802.11 standard actually do support a DH-based key-exchange built on a password-based AKE called Dragonfly. However, this variant is only used when the network is in ad-hoc mode.


Forging a valid tag for an arbitrary message when you have some knowledge about the key

[Suppose] the adversary can predict the key with probability $\alpha$.  Can I say the adversary can forge a valid (message,tag) pair with probability $\alpha$?

It's not quite $\alpha$.  Write it out with the chain rule:

\begin{align*}
  \Pr[\text{forgery}]
  &= \Pr[\text{forgery} \mathbin\& \text{guessed key}]
     + \Pr[\text{forgery} \mathbin\& \text{didn't guess key}] \\
  &= \Pr[\text{forgery} \mid \text{guessed key}] \Pr[\text{guessed key}] \\
  &\qquad + \Pr[\text{forgery} \mid \text{didn't guess key}]
              \Pr[\text{didn't guess key}].
\end{align*}

Under your premise, $\Pr[\text{guessed key}] = \alpha$, so $\Pr[\text{didn't guess key}] = 1 - \alpha$.

Exercise: Figure out what $\Pr[\text{forgery} \mid \text{guessed key}]$ and $\Pr[\text{forgery} \mid \text{didn't guess key}]$ are.  Hint: Model HMAC-SHA256 as a uniform random function.  What's the probability any two prescribed inputs $m \ne m'$ collide under a uniform random function?  (Then add a term at the end for the distinguishing advantage of the adversary against HMAC-SHA256.)


What is the lightweight key exchange protocol of choice?

I would personally use triple Diffie-Hellman, which is used often in secure instant-messaging protocols but unfortunately not very well-known beyond that. Essentially, both parties have a long-term identity DH keypair, which they must securely share beforehand (through some CA system, manual fingerprint confirmation like SSH, etc). In each session, both parties also generate an ephemeral DH keypair.

Both parties send their identity and ephemeral public keys to each other, and do this:

DH1 = DH(their_identity_public_key, our_ephemeral_private_key)
DH2 = DH(their_ephemeral_public_key, our_identity_private_key)
DH3 = DH(their_ephemeral_public_key, our_ephemeral_private_key)
SK = KDF(DH1 || DH2 || DH3)

This derives a shared secret that they can use with symmetric encryption etc like TLS (don't forget to derive different keys for the two directions, and to use authenticated encryption!)

Triple DH provides both security and authentication against active attackers, as long as both parties know (a hash of) the other's identity public key beforehand. It also has the following desirable properties:

Forward secrecy: the ephemeral keypairs are thrown away after the session is done, so even stealing the long-term keypairs in the future cannot compromise recorded past sessions
Simplicity: the scheme's security relies entirely on that of one primitive: Diffie-Hellman, and by simply plugging in different functions for DH you can use variants like X25519, NIST-standardized ECDHE, classical DH, etc. There is also no need to maintain multiple keys; only the identity key needs to be kept around and kept secret.
Deniability: this is a property that most protocols do not have: although the key exchange is authenticated to the two parties, after it happens the two ends cannot present cryptographic proof that the session ever happened, since both parties can forge a convincing transcript of messages. (For a non-deniable protocol, see ECDSA-signed ECDHE, very commonly in used in TLS. It uses Diffie-Hellman and has forward secrecy, but signing the key-exchange messages with an ECDSA key destroys deniability)


Advantages of using 64-bit word size over 32-bit word size

The main reason of using 64-bit word size over 32-bit word size is speed, on CPUs that manipulate words sequentially. Doubling the word size can hope to about double the number of elementary bitwise operations performed in a given amount of time, on a 64-bit CPU like one using the AMD64 instruction set.

As an aside, for constant number of words in the internal state of a an algorithm (like a hash), the number of bits in the state is twice as large, which can improve the cryptographic resistance (if other conditions apply; in particular, at least twice as many bit operations); and allows a larger result.

Accordingly, for large input, SHA-512 is typically faster than SHA-256 on the same 64-bit CPU, even though SHA-512 uses 25% more rounds, and has a state with twice more bits, making it arguably safer.

Update per comment: word size has no direct impact on security. As an illustration, it is possible to reformulate SHA-512 as using 32-bit words, with identical result thus security; compilers for 32-bit CPUs do this automatically.


No, in general using a CRC in this way is not secure. A CRC is not designed to be used against adversaries, it is used to detect random bit changes to the data it is protecting (as well as the CRC itself). A CRC of 16 bit will certainly not be as secure as an 8 byte MAC value, that was designed to protect against such attacks. Without additional measures a 16 bit CRC would be pretty easy to brute force.

Note that there are many arguments against authenticate-then-encrypt. One of the reasons that it may be less secure is that it allows attacks on the block cipher mode of operation. In this case the ciphertext may be vulnerable to padding oracle attacks.


How to change hash checksum of a text file without changing the contents in the file

Hash functions are deterministic, same input same output. Without a modification, you cannot change the result.

The hash of a file is used at least for the integrity check. If you were able to change it without modification the integrity check will have problems.

Note: as mentioned by Ella Rose in the comments if a keyed-hash message authentication code HMAC is used then changing the key will result in a different hash-based message authentication code.


Chosen plain text and chosen ciphertext definitions clarification

The idea behind these models is to model an adversaries capabilities. To get reliable security the worst case for a capability is modelled. Let's start with chosen plaintext attacks (CPA):

In this game the adversary is given access to an encryption oracle. This models the case where an attacker knows (parts of) the message. For example, the British knew during WWII that German messages will always end with "Heil Hitler" and this was what allowed them to break their encryption. Now, as I said we always want to model the worst case, so let's assume the adversary knows the whole plaintext. For a good encryption scheme this should not give him any advantage. Besides, there might be some messages that are more beneficial to an attacker than others. A good encryption scheme should also be secure in this case. So, that's why we allow the attacker to chose the messages which are encrypted. Thereby we can make sure that even for the most beneficial message the adversary can not break the scheme.

In some cases the above might already be enough. However, sometimes it might be the case that the adversary can learn the plaintexts for some ciphertexts. For example, the decrypted values might be output by an application which the adversary can somehow access or they influence the behaviour of an application which can be observed. Hence, we might also want to cover this case. This leads to the stronger notion of security against chosen ciphertext attacks (CCA). To model the above we give the adversary access to a decryption oracle. The motivation behind allowing the adversary to decrypt arbitrary ciphertexts is the same as above, i.e. modelling the worst case.

These notions define something we call a learning phase. It models what an adversary might be able to learn about the used encryption scheme and the used keys. However, the goal of the adversary is to attack a ciphertext for which he does not know the plaintext, yet. And of course it is about a ciphertext for which he was unable to learn the plaintext from one of the above "side-channels". This is normally modelled in one of two ways.
Either in terms of semantic security which says that an adversary can learn nothing about a plaintext given its ciphertext, or in terms of indistinguishability of ciphertexts (IND). Luckily, these two notions are equivalent and I will not talk anymore about semantic security as it is more complicated to explain the details.

In the case of IND, the adversary is allowed to choose two different messages. One of the two messages is chosen at random and the adversary will receive back the encryption of it. Now the goal of the adversary is to tell which message's encryption he received. As I said before, we want to model the case where the adversary is unable to learn something about the plaintext from a side channel. Hence, he is not allowed to ask its decryption oracle for the decryption of this plaintext.


Hasse's bound tells that the order $n$ of [that is, number of elements in] an Elliptic Curve group is about the same as the order $p$ of the underlying field [note: $x$ and $y$ coordinates are elements of the field, points $(x,y)$ are elements of the group].
For every $x$ in the field with $(x,y)$ in the group, there is exactly one other point in the group with the same $x$: $(x,-y)$.
Therefore, about one value of $x$ in the field out of two is such that there exist $y$ in the field with $(x,y)$ [and $(x,-y)$] in the group. Like, if you have $n$ nuts and $p$ persons, with $n\approx p$, and you give two nuts to each person, then only about half the persons get a nut.
Therefore, $f$ as defined in the question is not uniform in the field, for it only reaches about half of the field elements.


Indeed FIPS 140-2 requires a module to validate itself, and this has no security benefit.
In order for a code integrity check to have a security benefit, both the code that performs the verification and the data that it uses (hash value for a hash, MAC value and secret key for a MAC, public key for a signature) need to be integrity-protected (and with a MAC, the key also needs to be confidentiality-protected). Since the verification code is part of the module, the code integrity verification does not provide any security benefit. It guarantees the module's integrity under the assumption that the module's integrity is not breached.
As far as I know, this started as a requirement for hardware modules, which had to perform some kind of self-test that would typically fail if the physical integrity of the module was compromised. Basically, a physical tamper detection mechanism: make sure that the keys are unusable if the box has been opened. This doesn't translate to software well, but the requirement has been kept and has evolved to require cryptography, partly due to inertia and partly due to the illusory wish that something should be done.
An integrity (or authenticity) check is useful when the module that performs the check is better-protected than the module that is checked. For example, some devices boot from ROM (as in, physical ROM, which can only be modified by completely taking the device apart), which then transfers control to updatable, physically exposed storage (such as a hard disk or flash memory). If the ROM contains signature verification code and a root public key, and the ROM code verifies the integrity or authenticity of the external storage before transferring control to it, there is a real security benefit: it can ensure that the device will only run trusted code. Depending on who you ask, this is called secure boot or trusted boot. There is often a chain of secure boot, from ROM to firmware bootloader to operating system bootloader to operating system kernel to user land utilities. This chain relies on physical integrity protection for the first element, and cryptography to extend trust to subsequent elements.
Some security standards that are applicable to a specific kind of device (for example a PC, a smartphone, a smartcard, etc.) have specific requirements on secure boot. But FIPS 140 is too generic for that.
So treat the FIPS 140 integrity check as a compliance requirement, not as a security requirement. It's one of the many hoops through which you need to jump. Fiddle with your operating system's low-level interfaces to figure out how to read code in memory before any dynamic linking or randomization takes place. Calculate the expected MAC value and store it somewhere that isn't part of the verification (because it's infeasible to find $v$ such that $\mathsf{MAC}(m) = v$ and $v$ is a substring of $m$). Arrange for your code's initialization sequence to verify the MAC of the code against the reference value stored next to it. It's part of the cost of getting a FIPS stamp.


Implementation of a side channel attack?

I wish I had such homeworks when I studied, mine implied pen and papers only, sadly.

You have to get your hands dirty there. This means that you have to code something which will, as said by Ruggero in his comment:

determine the length by trying random password of different lengths and timing the time your program will take to return
determine the actual password thanks to the fact that the time needed by the program to return is a direct function of the edit distance between the actual password and the string you used as input.

The difficult part for 2. is that there is some noise added to the computation because of that random_time variable. This means that the nearer to the actual password you'll get, the more noise you'll obtain.

In order to counter this, however, you may rely on statistical analysis since you may run that program many time with the same input. So you'll have a mean deviation of only 4.5, which means that when you run a few times the same input, you'll get a Gaussian repartition with a mean value equal to roughly 4.5 plus the actual value of the difference between the inputed characters and the actual characters.

This would be the theoretical approach, I guess...

In your case because the usleep will take 0.01 seconds times the differences plus the random_wait... On average, when provided with the valid password, it'll take around 0.045 seconds.

So you may want to try to do so:
 - determine the length
 - benchmark the mean time with a all-zero string of that length (running it a few times, like 20-30 times should be good enough given the resolution of the wait time)
 - benchmark the mean difference to the previous computed mean time when changing only one characters of the input string at a time, do so for each position in the input string
 - compute the actual password thanks to all of that information, by trying to minimize the edit distance between your input and the actual password. (Eventually this may just allow you to narrow down the range of possible password to an amount which is easily bruteforced... but I think you can manage the noise added by random_time easily thanks to only a few trials with the same input and should get the right result.)

Here are a few other thing you may also try to, if you dislike having to wait so long at each execution of your binary:

if you have a crackme and you can run it on your device, and can do whatever you want, you may try to tamper with the usleep to get it to simply print its current value (maybe using a custom usleep implementation through a LD_PRELOAD trick ?) and then use the above method.
if you cannot tamper with its execution, you may try to count the number of instruction it's running and kill it when it passes a threshold and try with another input, this may be the quickest way to recover the password, instead of using the time it takes, you can use the number of instructions executed. This is possible using for example pintools, they even provide an example of such a counter.
more generally, reverse engineering and/or patching the crackme may help you.

PS: In the end, I'm not sure this question is really about cryptography or side-channels... But I don't really know where it may belong to.


Size of Key Material of TLS_DHE_RSA_WITH_AES_256_CBC_SHA

TLS_DHE_RSA_WITH_AES_256_CBC_SHA is

256-bit AES encryption
SHA-1 message authentication
Ephemeral Diffie-Hellman key exchange
Signed with an RSA certificate

We can find the answer in rfc5246

                        Key      IV   Block
Cipher        Type    Material  Size  Size
------------  ------  --------  ----  -----
NULL          Stream      0       0    N/A
RC4_128       Stream     16       0    N/A
3DES_EDE_CBC  Block      24       8      8
AES_128_CBC   Block      16      16     16
AES_256_CBC   Block      32      16     16

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

Note 1: the values in bytes.
Note 2: This mode is archaic and exist in TLS since TLS1.0. You should stick to TLS 1.3 which has huge cleanup and has only 5 cipher suites and all use Authenticated Encryption with Associated Data (AEAD).


What are the implications of quantum collision search algorithms like Ambainis for collision-resistant hash functions?

The query complexity, i.e. the number of times the machine evaluates the function as a black box, may be $O(2^{n/3})$, but that's not the only cost of an algorithm: the size of the machine and how long you have to run it figure in too.

So far, there are no implications of quantum algorithms for security parameters of collision-resistant hash functions.  Classical algorithms are still the cheapest algorithms for generic collision-finding, and would remain so even if Grover-capable quantum computers had the decency to merely exist.

The original Brassard–Høyer–Tapp algorithm[1] precomputes $H(x_1), H(x_2), \dots, H(x_{2^{n/3}})$ and stores them in a table $C$; then it applies Grover to find a preimage of 1 under the function $f(y) = [H(y) \in C]$, which reveals a collision in $H$.

Even if the communication costs for table lookup were zero (which seems unrealistic), this costs $O(2^{n/3})$ space, and the algorithm is expected to take $O(2^{n/3})$ oracle evaluations before finding a preimage under $f$ of 1, for a total of $O(2^{n/3})$ evaluations of $H$, and a total area*time cost of $O(2^{2n/3})$—far greater than the $O(2^{n/2})$ area*time cost of standard classical algorithms like the van Oorschot and Wiener collision search algorithm based on parallel $\rho$[2].

Variants of the algorithm have been proposed, but so far none of them has beaten the $O(2^{n/2})$ cost of the best classical algorithms in any plausible cost model even if qubit operations are no more expensive than bit operations—and most of them are much more expensive in any plausible cost model[3].  See here for an overview of some of the proposed algorithms and of problems in the cost models, and for broader context.

The Ambainis algorithm[4] takes a slightly different approach of a quantum random walk to find a repetition if there is one among a sequence of $M$ elements in $O(M^{2/3})$ time, which can be converted to an algorithm for finding a collision in an $m$-bit-to-$n$-bit function in $O(2^{m/3})$ queries.  But it also requires maintaining a data structure holding all $O(M^{2/3})$ queries throughout the algorithm.  So the area*time cost for a collision search based on it is $O(2^{2m/3})$, which remains far beyond the $O(2^{n/2})$ cost of classical collision search for any input size $m$ that gives a collision in $n$-bit outputs with nonnegligible probability.  What Czajkowski et al. describe[5] is a generic way to apply it to a sponge with $c$-bit capacity producing an $n$-bit output costing $O(\min\{2^{2c/3}, 2^{2n/3}\})$, which is essentially what you would expect.

And since the query complexity of a generic quantum collision search has a lower bound[6] of $\Omega((2^n/r)^{1/3})$ if $r$ is an upper bound on the number of colliding preimages, unless there are dramatic breakthroughs in storage costs it seems unlikely that this situation will change any time soon.


How is the message digest related to Signatures and Encryption?

First of all, yes, the message digest is the hash of the message.

Secondly, do not mix things up. You are talking about public key encryption and signature. Let's redefine them to make sure we have everything right.

Alice and Bob got pairs of key ($A_{pub}$, $A_{priv}$), ($B_{pub}$, $B_{priv}$). Alice knows $B_{pub}$ and Bob knows $A_{pub}$.

Alice wants to send a message $m$ to Bob $\implies$ She encrypts it with $B_{pub}$.
Alice wants to prove to Bob that it was she who sent the message $\implies$ She signs it with her private key $A_{priv}$.

How does the message digest appear in all that ? Continue reading.

Problem: signing and encryption using RSA (standard procedure) is slow. How to speed up the process ?

Alice encrypts the message with a symmetric cipher (AES) using a random generated key $K_{sym}$. Then, encrypt $K_{sym}$ with the $B_{pub}$.
Alice does not sign the message, she signs the message digest. Smaller therefore faster.

All this together ? Here are the steps :

Alice hashes the message $m$ $\implies$ she gets the message digest.$H(m) \to MD$.
Alice signs $MD$ with her private key.
$E_{A_{priv}}(MD) \to Sig$.
Alice generates a random key for the symmetric encryption.
$rdm() \to K_{sym}$
Alice encrypts the message and the signature with a symmetric cypher.
$E_{K_{sym}}(m\|Sig) \to c$
Alice encrypts the symmetric key with Bob's public key.
$E_{B_{pub}}(K_{Sym}) \to K_{cipher}$
Alice sends $(c,K_{cipher})$ to Bob.

Remark: It is a good practice to have 2 pairs of keys : one for encryption, one for signatures.


How to derive a 4096 bit or 8192 bit RSA private key from a (BIP39) mnemonic seed?

As it was already pointed out in a comment by @corpsfini, you could use a PRNG to generate pseude-random numbers from the seed. Then you would check whether they are primes using some probabilistic primality test.

In spirit the same procedure is implemented in this github repo you might find useful.


This seems to me to be less secure...

Do you have a plausible adversary that can break AES-128?  AES-128 is believed (to the best of knowledge) to require $O(2^{128})$ operations (unless someone has a Quantum Computer, in which can it takes $O(2^{64})$ Quantum operations, which might not be any more practical).  For a reference, if an attacker has designed a chip with 1 million cores, and each core can test 1 billion keys per second, and he has 1 billion such chips, it'll still expected to take 4 million years before he happens to stumble across the correct key.  Do you have an adversary who can devote considerably more resources to this task than my rather extreme example?

And, if AES-128 is secure from any plausible adversary you can have, how can you say it is 'less secure'?

In addition, if you're not using some sort of MAC, that means that you are open to adversaries who can modify your data; attackers can cause all sorts of mischief (including deducing the decryption in some cases) by doing that.  That is a practical concern; IMHO, it far outweighs any concern about Space Aliens who could break AES-128.

Now, I have not reviewed Fernet; it could be that they got some details wrong (such as not selecting IVs correctly).  However, we know there are issues if you don't do integrity checking on your ciphertext.


The big O notations describes the complexity when $N$ approaching infinity, it is not a formula giving you exact running time for all $N$.

Roughly, let $f(N)$ be the function for the running time of the algorithm, the big O notation says that there exists $n$ and a constant $c$ such that
 $f(N)<c\cdot (\log N)^2(\log\log N)(\log\log\log N)$ for all $N>n$.


Simple secret key encryption with PyNaCl

It's not really a cryptography question, but I think the decryption would go better if you read the data from infile first (box works on strings of data, not filenames), so

with open(infile, 'r') as in_file:
    encrypted = in_file.read()

and later:

decrypted = box.decrypt(encrypted)

where the nonce before it can go, as it is not used (the encrypted data contains the generated salt from encrypting).

Also the quotes on "outfile" can go. It's a variable.


How to find collisions in a secret-prefix Merkle–Damgård given an adversary that can choose the IV?

Algorithm C would give you the answer directly, except it needs an IV to start off with, and you don't initially know that.  Here's some hints:

The IV you give algorithm C needn't be the secret IV $K$; instead, it can be the intermediate state of some message
So, how could you use your access to function $F_K$ to find the intermediate state in some message?


Which is the better way of generating a salt string?

Neither. The RAND function in method 1 isn't cryptographically random; the GUID generation is only random with version 4, and isn't guaranteed to be of cryptographic quality.


Why would someone prove security in the real-ideal model instead of Universal Composibility framework?

Try to prove something non-trivial using the universal composability framework and you will quickly understand why few people use it.

EDIT: Snide remarks aside, it is pretty widely acknowledge that universal composability is really hard to use in papers. It's even hard to typeset - I've seen proofs with UC functionalities that don't fit on a single page! A colleague of mine has said that proving non-trivial things using UC is like writing a web server in assembly language.

Aside from the practical difficulty of writing proofs with it, there's a more fundamental difference between UC and the real-ideal paradigm: the latter has an intuitive philosophical appeal that comports with the way people think about security. The former doesn't have the same "interpretability" IMO.


Example of not computationally indistinguishable

The usual way of proving that two distributions are distinguishable is by devising an attack such as the one you mentioned. Finding an attack may not be easy or even doable. In general, you should assume that two distributions are distinguishable unless you can prove otherwise. To prove indistinguishability, you can often use the technique of reduction to map the distributions in question to other ones that are known to be indistinguishable from random.


In W-OTS, could you XOR all public keys?

If I understand you correctly, you're proposing that we have a number of one-time-signatures (which, with the corresponding messages, hash to the corresponding public keys), and then we produce the xor of all the public keys.  Then, the receiver would validate all those signatures together (by computing the corresponding public keys, xor them together, and seeing if the result is the published xor).

If so, it doesn't work; an adversary could put together a forgery, that is, a series of messages and signatures that would evaluate to that same xor.  How he would do so is straight-forward; he would generate a series of messages and random signatures; he would then find the corresponding public keys.  Then, he would find a subset of those public keys that would xor to the published value - this can be done by solving a set of linear equations.  That subset would be the forgery.


What's the functional difference between fountain codes and polynomial secret sharing?

Consider what happens when we construct Shamir's secret sharing scheme for a secret $s$ and a reconstruction threshold $t=4$.  Our polynomial will be of degree $t - 1$ with $a_i$ being random coefficients:

$$
f(x) = s + a_1x + a_2x^2 + a_3x^3
$$

The shares for the $n$ players are given by $f(1), f(2), \dots f(n)$.  Any $t \ge 4$ of the players can reconstruct the polynomial $f(x)$ and can  recover the secret as $s = f(0)$, but any $t < 4$ of the players do not have enough information and thus learn nothing about the secret $s$.

We can use this exact same technique as a fountain code through nothing more than a change in perspective.  Instead of a secret $s$, we have a message $m$:

$$
g(x) = m + a_1x + a_2x^2 + a_3x^3
$$

And instead of giving each player $n$ the share $f(n)$, we broadcast a series of blocks $g(1), g(2), \dots$ to the players.  Once a player has received $t \ge 4$ message blocks, they have enough information to reconstruct the polynomial $g(x)$ and can recover the original message as $m = g(0)$.  By choosing a large enough finite field, it is possible to generate a very large number of unique message blocks.

Practical fountain codes are usually based on low-density parity codes for reasons of efficiency, but I hope this example helps to show that in many ways error-correcting codes and secret-sharing schemes are merely two interpretations of the same underlying concept.


Shannon's paper Prediction and Entropy of Printed English details  the experiment to determine the entropy of English.
Without getting into too much detail, it's only really proper to talk about the entropy of a source of information. You can estimate the entropy given a sample of the source's output and it's fair to say that Shannon's method gives an estimate for the upper bound. A more sophisticated experiment would give a lower estimate for the upper bound.
Another way to arrive at an upper bound would be to look at the results of a competition to compress a portion of wikipedia which shows that 100M of English can be compressed into 16M.

I'm reminded of a similar scheme I read about which relied on a long stream of publicly available bits derived in this case from digitizing a picture of the surface of the moon. I can't find the reference but I'm sure it would be relevant, although of purely academic interest.

There are no practical schemes that I am aware of which use your idea or anything similar. You would have to ask yourself what security guarantees you're trying to achieve and whether this really is the best way of obtaining them. I believe that it should always be preferable to implement your system using established cryptographic primitives in the prescribed fashion.


Carol generates a NIZK proof common reference string and a statistically binding commitment

to a formal description of $M$. $\:$ Carol sends both of those to both Alice and Bob, and additionally

sends the associated decommit string to Alice. $\;\;$ For each message $m$ in $M$, Alice calculates
the proof of $\:m\in M\:$ and encrypts it along with $m$ before sending the ciphertext to Bob.

After decrypting, Bob can then verify that $\:m\in M\:$ by verifying the NIZK proof.


Classification of attacks against lattices

You're describing methods of solving LWE via reduction to SVP. In particular:

Sieving and Enumeration are methods of solving exact SVP
Basis reduction is a method of solving approximate SVP

There are additionally ways of solving LWE directly (the classic example is the Arora-Ge attack, which works when the noise distribution is too concentrated).

Daniele Micciancio has a webpage on lattice cryptography where you can see some discussion of this/links to papers.

While I haven't read the following thesis:

Michael Walter's thesis has sections on both enumeration and basis reduction.
Rachel Player's thesis seems to include include a summary of direct attacks on LWE, and a section of lattice basis reduction.


Can not use big prime number for pair of key of RSA Algorithm

Although it is theoretical possible to create two large primes and use that to establish the private and public key, there are real issues doing so. First of all, let's check how big a modulus you need, as that defines the size of the two primes.

Let's assume color, and use the RGB color space without gamma, each color having 8 bits of color depth. That means each pixel uses 3 bytes. So your bitmap takes $64 \cdot 64 \cdot 3 \cdot 8 = 98304$ bits. That's excluding overhead of both the image as well as the overhead required for the padding required for secure RSA encryption (both of which may be insignificant with these kind of values).

This requires you to find two primes of half the number of bits to create secure RSA, assuming that you use the regular RSA and not multi-prime RSA. Unfortunately, even a modern CPU can take time to calculate an 8K-bit modulus. The problem is that each prime number is now close to 49152 bits. The density of primes is much smaller for such large spaces. Furthermore, doing primality testing on that kind of values will take a lot of time. So the time to find the primes $p$ and $q$ grows very rapidly (a factor of 12 to 16 for each additional bit). So the time to generate a key pair that size is prohibitively large (and depends on chance as well).

Just type in openssl genrsa 98304 on your computer to use it as a heater.

So key pair generation is a huge issue at these key sizes. Performing any modular exponentiation with these kind of exponents and modulus sizes will be a lesser-but-still-significant issue as well. Many cryptographic libraries will have maximum key sizes for these reasons (and others, such as limiting testing, memory usage etc.).

So what can you do? Well: you can simply split up your plaintext into blocks and encrypt each with RSA. This will still be slow and will expand your ciphertext significantly compared to the plaintext image size, as padding the blocks is required.

What most cryptographers do is to pair the RSA algorithm with a symmetric cipher such as AES. In that case you can generate a random AES key and use that to encrypt the image (using a secure mode of operation). Then the AES key itself can be encrypted using the RSA public key. This kind of scheme is called a hybrid cryptosystem.


How can fully homomorphic encryption ever be secure?

Interpreting the question

Firstly, I should state that I interpreted

  "Since this is a FHE scheme that allows arbitrary computation, the cloud service builds a full-text search function on the ciphertext and starts querying E(M) to check for partial matches or even full equality of M"

to mean something equivalent to

  "What if the cloud service uses the homomorphic properties of the ciphertexts to evaluate a search algorithm which outputs True if the searched substring is contained in the message, or alternatively outputs the matched substring, or returns any arbitrary information about the message. Why can't they abuse this feature to find the message?"

I mention this up front because there appears to be confusion about what exactly the question is asking. This answer will assume that the unspecified homomorphic encryption scheme fulfills its promise of data confidentiality, which for a fully homomorphic scheme, includes evaluating arbitrary circuits while revealing nothing of the plaintext value without evaluating the decryption circuit. Obviously, this does not extend to constants introduced during the evaluation that are created by the service provider via the public key (which they only know because they created the ciphertext).

Answer

With homomorphic encryption, the data is confidential to everyone but the key holder. Anyone can manipulate ciphertexts and evaluate functions on them, but they cannot decrypt the ciphertexts to obtain the result.

What part of FHE prevents the cloud service from doing this?

So the answer is that nothing prevents the cloud service provider from computing a search on the encrypted data - it may compute the search, but it cannot decrypt and view the result of the search. This is because the output of the circuit that is computed is also a ciphertext. The cloud service provider may compute any circuit it wants (assuming the scheme supports it), but the output will always be a bunch of random noise as far the cloud service provider is concerned.


Why does rsyncrypto require a public key during decryption?

For completeness / posterity / future inquisitors, this is the response I got when I asked on the mailing list. I have also included it below because links sometimes break.

  No, you're not missing anything. This requirement is not,
  algorithmically, necessary.

  When you're decrypting with the symmetric key available, rsyncrypto uses
  the public key in order to know how much of the file's header to skip.
  In other words, all it actually needs from your public key is how many
  bits it is. Since the first part of the file is the symmetric key,
  encrypted using the private key, the key's length is needed in order to
  know how much to skip.

  Of course, in retrospect, I could have stored that information inside
  the symmetric key file, and made the usage simpler. I'm hoping to, some
  day, get around to working on rsyncrypto again, and this will definitely
  go there.

  Unfortunately, rsyncrypto's current file format makes it impossible to
  encrypt using a stream algorithm. Since this is a kinda important
  change, the changes planned for rsyncrypto 2.0 are breaking changes. As
  that's the case, I will not do another breaking change (changing the
  format of the symmetric key file) for so little gain.

  If this restriction is a problem for the deployment type you are
  planning, you can simply generate some random public key for the
  decryption machine. So long as it is the same length as the original
  encryption key, everything should work fine.

  Shachar


Achieving 256-bit encryption strength with PBKDF2 - HMAC-SHA1

As others have pointed out, you are never going to get more strength out of it than you put into it; you are just going to make it so the attacker has to go after the password instead of brute forcing the key.  And because nobody would try to brute force a 128 bit key, stretching to 256 bits isn't going to do any good. The attacker will go after the password. (I'm assuming that the salt is not secret.)

However, there is still a good reason to move from SHA1 to SHA256 for deriving a 256 bit key with PBKDF2. There is a bug in the design of PBKDF2. If you extract 256 bits from PBKDF2-HMAC-SHA1 then the attacker can go after the first 128 bits using only half of the hash compressions that you did to generate it.

This shouldn't be a problem where the attacker needs the entire 256 bits as in your usage, but there are cases where this does give a 1 bit advantage to the attacker.

So I would strongly recommend that you use HMAC-SHA256 as your PRF in PBKDF2 when deriving a 256 bit key.


Is there an advantage to using a hash in combination with a key-derivation function?

There is no advantage. A password-based KDF already behaves a lot like a hash function.

There is no weakness to pre-hashing a password if you use a proper hash function.

If the probability of a hash collision is small then hashing does not reduce a cracker's search space.

However, if the hash had a 16-bit output, then you would have a problem. A cracker would just guess-and-check each 16-bit KDF input, skipping prehashing, rather than guess-and-check different passwords.

On the other hand, if you use SHA-512 then you are not reducing a password cracker's search space. Hash functions aren't truly one-to-one functions, but we can safely say we have never hashed two distinct inputs that have the same SHA-512 output. You would expect humanity to have to hash around $2^{256}$ different messages  (give or take slightly on that exponent) before it becomes probable that we would have two messages collide by chance. (That $2^{256}$ makes astronomically large numbers look infinitesimal by comparison.)

Until we generate that many distinct passwords we can get away with approximating the relationship between prehashed "passwords" and pre-prehashed passwords as a one-to-one mapping. That makes the prehashed password basically equivalent to the user's password. (Just in a different format.)

Guessing random 256-bit strings isn't a shortcut or a smart strategy. It still makes sense to guess and check plausible passwords by brute force. Again, the cracker's search space isn't reduced, so there is should be no impact on security.

Note that I said a hash with a low collision probability would be safe (but still pointless). You don't actually need collision resistance. If you used SHA-1 instead, that collision attack wouldn't necessarily have any impact on security. In most real world scenarios that would just mean a user could use more than one password to login to the same account or decrypt the same files. User chosen passwords or randomly generated passwords still won't result in SHA-1 collisions in non-adversial settings.

Aside: The security of password hashes and KDFs in general don't  rely on collision resistance. You just need a function that is preimage resistant and that does not have any biases that reveal information about inputs. (Actually, for KDFs at least, biased output in general.)

A hash that wasn't preimage resistant would not work for user authentication. (A hacker could find a password that hashes to the same value. It wouldn't matter to him whether it was the same as the original password.)

A hash with biases might make a password cracker's search easier.

Password based KDFs like Argon2 utilize hash algorithms with these requirements.

Finally there are two scenarios where prehashing passwords might help. Just not for reasons based in cryptography.

First, there might be quirks in a KDF or password hash. For example, there might be a length limit on the password (as in bcrypt). Prehashing transforms the user input into a fixed length bit string.

Bcrypt has several issues related to user input. If you had to use bcrypt it would be a good idea to prehash a user's password with a 256-bit hash and encode the output using base64. That results in a pure ASCII string with no stray null characters that's small enough to be used with existing bcrypt implementations. (You should still use Argon2 because it's much better for password hashing.)

Second, you may opt for the client to prehash users' passwords before sending them to the server. Web applications typically receive the user's plaintext password, whether they use HTTP or HTTPS. Sending a hash of the password is not a substitute for encryption (because eavesdroppers can just send the same hash without ever requiring someone to log in with the actual password), but it potentially obscures the user's actual password.

If the user's password is weak then the server can guess the original just the same as any other password cracker would. If a password is inhumanly strong then the server won't ever know the user's actual password.

(Although that's unrealistic. If passwords are assumed to be that strong then there isn't the need to use a dedicated password hashing algorithm instead of an inexpensive hash. It's likely better to do client-side password stretching for non-web-applications if the server shouldn't be trusted with actual passwords. Or use an alternative authentication method.)


If a cryptanalytic breakthrough is made, what process should be followed?

Well, first off, the question doesn't arise that often in practice.  People do find cryptographical weaknesses; however, generally they are purely of theoretical interest, or if they could be used in a real attack, it may take quite a while before someone figures out how to use it.  As an example of the second case, Ms. Wang announced an efficient way to create MD5 collisions; this is a severe break of the MD5 security properties, but it took people quite a while to figure out how to translate that into being able to obtain a bogus certificate (by asking for an innocuous one from a CA).

On the other hand, it does happen on occasion; one example that springs to mind is WEP and the key recovery attack.

Now, in my opinion, the ethical thing to try to do is to get people to stop using the broken protocol, and switch to something which doesn't have known weaknesses.  However, in practice, that appears to be difficult.  Once they have a system in place, quite a lot of people are loathe to update it.  In addition, when cryptographical hardware is involved, sometimes the fix involves hardware modification, and so updating things would involve real money (rather than just a software update).  One example of someone ignoring an announced attack would be the TJX credit card breach; this attack was done using the WEP key recovery attack that was announced 5+ years earlier.

So, what should we do?  Well, I don't see any good options.  Not publishing the result doesn't appear to work (we leave the weaknesses in place for the blackhats to find and exploit).  Publishing the result does mean that some will update, but others won't bother.  Publishing the fact that we have a result will generally mean that you won't be taken seriously (unless you're already a cryptographical Big Name), and the blackhats will be alerted that there is a weakness.

My personal feeling is that publishing the result is the "least worse".

[Hmmmm, we're supposed to avoid statements based on opinions; for a question about ethics like this, I don't see how I can avoid it]


Can I use a one time pad key twice with random plaintext?

Yes, encrypting two different random "plain texts" with the same "pad" is indistinguishable from using two different random one time pads for encrypting the same plain text. You get perfect secrecy in the latter case, so you will get corresponding secrecy in the former case as well.

However, usually there is a functional difference between the key and the plain text that the above argument doesn't account for. More precisely, the recipient will usually "do things" with the plain text once decrypted, and in that respect the above argument might fail.

For instance, if the random messages are symmetric encryption keys for a cipher that is vulnerable to a related key attack, it is obviously not safe to transport those messages encrypted with a reused pad.


Does it mean though that I sign many different messages, or do I sign one message, which, if its longer than 256bit, will be split into two parts and the 2nd part will be signed with the 2nd private key?

You can sign many ($2^h$) different messages; it does what just about any other signature algorithm does; it hashes the initial message, and then signs the hash.  If you're using SHA-256 or SHAKE-128 as your hash function, then this hash is 256 bits, which is what is signed by a single WOTS+ private key.
Now, XMSS is a bit different than most other signature schemes; it stirs in some unpredictable data at the front of the message when it computes this hash (and includes this unpredictable message in with the signature) - it does this to prevent collision attacks from working (an adversary who picks the message to be signed cannot predict this unpredictable data, hence he cannot pregenerate a collision) - it does this because everywhere else, XMSS depends on the (second) preimage resistance of the hash function, and it would be a shame if it made a stronger security assumption on the hash function for the initial message hash.

What is the maximal length of the message?

If you're using SHA-256, this would be not quite $2^{61}$ bytes; if you're using SHAKE-128, there is no upper bound.


XSL on serpent and rijndael - which is most affected?

First, from a direct witness of the events (i.e. myself): Serpent was indeed felt as "too slow" when compared with Rijndael, by a factor of 2 to 3. The performance of Rijndael was not the best there was on a PC (RC6 was faster) but it wasn't abysmal on any platform, especially 8-bit smartcard (contrary to, say, RC6). Serpent performance was consistently lower than Rijndael's. See this page for benchmarks of the AES candidates on various software platforms at the time of the competition.

XSL attacks were discovered in 2002, hence after the choice of Rijndael as the AES; therefore, they could not have been a parameter in the choice.

In their paper, Courtois and Pierprzyk "show" that AES (i.e. Rijndael) with a 256-bit key, and Serpent with a 192-bit or 256-bit key, are "broken", which means that the attack ought to recover the key with less work than the CPU needed to evaluate the block cipher $2^{256}$ times (resp. $2^{192}$). They certainly did not go below $2^{128}$, so the break is only theoretical and unverifiable. That's part of the problem, too: the analysis is based on a number of probabilistic assumptions on an equation-solving algorithm in a situation where it is out of the question to actually run it on existing hardware. So XSL attacks are an effective break only insofar as their description is intellectually convincing. Don Coppersmith has publicly expressed that he was not convinced. And when Coppersmith says that your research stinks, it is time to worry.

Anyway, that an algorithm can be represented as a set of multivariate polynomial equations is not the key issue: any algorithm which can be implemented as a circuit is amenable to such a representation (e.g. because a NAND of $x$ and $y$ is equal to $1+xy$, when computing modulo 2, and every boolean operator can be built out of NAND gates). Generally speaking, solving a set of multivariate polynomial equations is hard. Courtois and Pieprzyk argue that the specific structure of the equations in the case of Rijndael and Serpent can be exploited into running a dedicated variant of Shamir's re-linearization solving algorithm fast enough to be considered, academically speaking, as a "break".

The interesting part in XSL attacks is that resistance grows with the number of rounds, but not exponentially, contrary to more mundane differential or linear cryptanalysis. The bad part of XSL is that most cryptographers do not believe that it works as advertised, or at all. On the other hands, most think that Serpent is a more "conservative" design than AES, with a correspondingly "higher" security margin (but there is no really scientific way of quantifying such a "margin" so these are really all fuzzy feelings).

On the matter of attacks of debatable success, you could consider cache timing attacks, which are not an issue with the algorithm per se, but with its implementation. At least that attack could be demonstrated in lab conditions (the debate being whether the lab conditions have any similarity with whatever could occur in the field). Serpent is "naturally" immune to such attacks, because the normal implementations on software platforms will not use any table at all.


In your particular case the order of the point divides $p-1$, this means that the embedding degree of your curve is 1.

You should be able to apply the MOV attack to transfer your instance of ECDLP into an instance of DLP over $\mathbb{F}_{p}^*$. This would allow you to use the Index Calculus to solve your problem.

As the Index Calculus is subexponential, it would improve the required time for your attack compared to a generic discrete logarithm attack on the elliptic curve (as the Rho or the BSGS).

To perform the MOV attack you should first find a point $R$ of order $n$ which is not a multiple of $P$. This should be easy given your curve. Proceed in the following way:

Randomly generate a point $R$ on the curve
Find its order
Most likely it will be of the form $a*n$, if not goto step 1
$R = [a]R$ will have order $n$

Then perform the Weil pairing of $P$ and $Q$ as:
$$
\begin{eqnarray}
w_1 &=& e(P, R)  \\
w_2 &=& e(Q, R) = e(kP, R) = e(P, R)^k
\end{eqnarray}
$$

If $w_1 = 1$ then goto step 1. Otherwise solve the DLP by finding the $k$ of $w_2 = w_1{^k}$ in $\mathbb{F}_{p}^*$ using Index Calculus.

The returned $k$ will be the $k$ you are looking for (the one of $Q=[k]P$)

This answer by Samuel Neves, which I've used to write this answer, links to Sage code to compute the pairing and has more details.

Edit: Thanks Maarten for finding the goto issue.


How long brute force AES-128 at 24 bits of key

I have an Intel(R) Core(TM) i7-7700HQ CPU @ 2.80GHz. Intel I7 has around 10 generations to speak of. The result cannot be accurate without providing the actual referenced Intel I7.
Here is the method;
Run openssl speed -evp aes-128-cbc command. That will give you the metric.
My CPUs output:
aes-128-cbc for 3s on 16 size blocks: 144516288 aes-128-cbc's in 3.00s,
that is $144516288 = 2^{27.1066568628459}$. Therefore 1 seconds is more than enough.
\begin{array}{|c|r|r|} \hline
2^i & \text{seconds} & \text{years} \\ \hline
2^{30} & 22.29 & 0.0000007\\ \hline
2^{40} & 22824.65 & 0.0007\\ \hline
2^{50} & 23372450.03 & 0.74\\ \hline
2^{60} & 23933388835.87 & 758.92\\ \hline
\vdots & \vdots & \vdots \\ \hline
2^{128} & 7.06388957874987e30 & 2.23994469138441e23\\ \hline
\end{array}
The below code ( tested in SageMath )
SecondsInADay = 86400
SecondsInAYear = 31536000
TotalCBCin3Sec = 144516288 #your CPU time from openssl speed -evp aes-128-cbc
power = (30,40,50,60,128)

for i in power:
    print('seconds for 2^{%d} =' % (i),end="")
    print(((2^i *3.0)/TotalCBCin3Sec).str(no_sci=2))
for i in power:
    print('years for 2^{%d}   =' % (i),end="")
    print(((2^i *3.0)/TotalCBCin3Sec/SecondsInAYear).str(no_sci=2))


How do “modes of operation” with block ciphers like (eg) DES work?

The block cipher itself is used as a black box for any mode of operation. The internal design - including if the block cipher uses a Feistel network - is completely tranparent to the mode of operation.

The only thing that matters for the mode of operation is the block size of the block cipher. This, together with any usage limitations, limits the applicability of the block cipher for certain modes of operation. (Tripple) DES is less useful for modes of operation such as CTR and unusable for GCM which requires a 128 bit block size.

Note that the block cipher is basically a configuration parameter for the mode of operation. The block cipher itself doesn't use a mode of operation - it is being used by one.


In AES Keyschedule : Infer all round keys and cipher key from last round key

For AES-128, it's easy (that is, so easy that there are hardware AES implementations that, in decrypt mode, just store the last round key, and derive all the other subkeys, including the first one, on the fly).

Let us treat the expanded key as a series of 32 bit words $w[0], w[1], w[2], w[3], ..., w[40], w[41], w[42], w[43]$, there $w[0], w[1], w[2], w[3]$ are the 128 bit AES key, and $w[40], w[41], w[42], w[43]$ is the last round key.

Then, the key expansion process is defined as $w[i] = w[i-4] \oplus F_i(w[i-1])$, where $F_i$ is a simple function that involves possibly sending the inputs through the sbox, and xoring in the round constant.  Starting with $w[0], w[1], w[2], w[3]$, this allows us to efficiently compute the rest of the $w$ array.

So, if we rewrite this as $w[j] = w[j+4] \oplus F_{j+4}(w[j+3])$ (which we get by setting $j = i-4$ and rearranging), then, starting with $w[40], w[41], w[42], w[43]$, we can compute $w[39]$ using this formula, and then work our way backwards through the key schedule, ending with the initial values.

For AES-192 and AES-256, it's actually pretty similar, except that you need more information than the last round key (which makes sense; there are only 128 last round key bits; not enough information to recover the full 192 or 256 bit key).  However, if you have the last 6 $w$ elements (for AES-192), or last 8 elements (for AES-256), the same logic works.


Multi User limited Time Encryption of big Datasets

I'd start by dividing the read, write, and replicate roles into 3 keys. Tahoe-LAFS does this using "semiprivate" keys, each no larger than an EC curve point. I.e. Using ed25519, these keys would all be 32-bytes. The write key implies read, and the read key implies the replicate/verification key.

Once these keys have been revealed to someone, they cannot be revoked. To implement revocation, we need an additional authority that may be revoked, such as Macaroons. Macaroons support both delegation (sharing) and provisioning (with additional restrictions). These restrictions may reference clocks, or limit the functions the user may call (I.e. to read, write, append, truncate, delete, ..), or query out to external services to either check if the credential is still valid (revocation) or to check if the message is approved by the authority (configurable filters).

You cannot force a user to delete any ciphertexts, keys/credentials, nor plaintexts. You can revoke credentials to limit the distribution of ciphertexts. You don't need to rotate the encryption key so long that your adversary cannot also obtain the ciphertext (a revoked user cannot).

If your trusted server is allowed to read the user's data, then you don't need encryption at all (aside from session transports) as you only care about the authority to access. If the users can create new documents, then you'll likely prefer to lock the server (and you, the administrator) out of the user' personal data.


According to the definition on Wikipedia, both are valid uses of the term "one time pad" - "each bit or character of the plaintext is encrypted by combining it with the corresponding bit or character from the pad using modular addition." - that is: e=(d+p)%m, where e=encrypted data, d=decrypted data (input), p=pad, m is the number of possible values in e, d, and p (which must be the same). % is modulus - divide (d+p) by m, but take the remainder.

The most common implementation is the XOR method, which is the above calculation using m=2 (since 1 bit has two different possible values). A byte-by-byte solution would be equally valid, with m=256. letter by letter (m=26) is fine PROVIDED only encrypted data is sent - if you use this but send punctuation, capitals, newlines, and spaces unencrypted (or encrypted as a separate character set, then this is no longer secure (it will leak data - e.g. word lengths, and position and likely candidates for proper nouns, etc.).

Remember also, the pad needs to be really, really random, and of the same length (at least) as the message. It can never be reused. If the pad is English text, it is very insecure.


Assume that there are $2^{50}$ keys out there. Then calculating one of these keys by chance is $2^{50} \over 2^{255}$ for each calculation or a chance of one in $2^{205}$. Now say that you generate $2^{64}$ keys then you'd still only have a chance of one out of $2^{91}$ of hitting the right key.

Note that making sure that you hit a key would however require $2^{50}$ tests, and knowledge of $2^{50}$ operations by the public key of course. To test a single key the situation is significantly worse, the chance of finding it after
$2^{64}$ tries is only one out of $2^{191}$.

Chances of hitting the right key increase somewhat if you make sure you make sure that you don't generate the same key again. For instance you could start at a specific value and then simply test each following value. But that won't increase your chances by much and the calculation is too hairy to do here.

This is always what cryptography relies on: that you cannot just guess the private key. There is no cryptosystem to protect against that. And there doesn't need to be because the chance of generating a matching private key is negligible.

And think about it, I could guess the value of a coin as well. There is no protection against that either.

Note that a chance of one in $2^{91}$ is one in 2475880078570760549798248448 or one in 2 octillion 475 septillion 880 sextillion 78 quintillion 570 quadrillion 760 trillion 549 billion 798 million 248 thousand 448 (using the short scale).


The number of rounds does not directly influence security; it depends at least as much on the complexity of those rounds. That said, it is possible to use the percentage of rounds for which there are attacks as an indication on how much crypt-analysis has advanced (disregarding those attacks that are worse than brute force, of course).

One tricky thing with this is memory usage; many attacks are still better than the time-complexity of brute force, but have impossible memory requirements. I don't think there is any objective way to weigh memory-complexity and time-complexity.

Another thing to notice is that these attacks are far from practical; you can possibly see them as indication if other / more advanced attacks are possible. Of course, if this is true cannot be predicted, but for sure some attacks are more likely to be "extended" than others as well.

Still, with that said, for Serpent-128 it seems that 11 out of 32 rounds have been shown to be weak in an attack. For AES-128 there is the biclique attack on the full cipher. This attack however only brings down the attack complexity to $2^{126.1}$; having a complex attack that has a smaller than 4 times advantage over a brute force attacks doesn't say much. Otherwise, there are attacks for at least 7 rounds out of the 10 used for AES-128 (the other key sizes use a larger number of rounds).

So in that sense Serpent should be considered to be much more secure than AES; $\frac{11}{32} \ll \frac{7}{11}$ after all. AES is however also more than twice as efficient. In that sense Serpent with 16 rather than 32 rounds would probably have fared better at the competition. However, that's just for the minimum key sizes. If you look at AES-256 then you would have all the security you may need (9 out of 14 rounds or $2^{254.3}$ for the biclique attack) - and still be faster than even Serpent-128. And that's without hardware acceleration. Note that I've disregarded related key attacks on AES-256 in this scenario.

The notion on Serpent that "It is build like a tank" (Cryptography Engineering: Design Principles and Practical Applications) still seems to hold. Note that there haven't been many breakthroughs on either cipher in the last couple of years; research seems to have moved on.


Password-based cipher with fast encryption

One approach that you might consider is a puzzle; this is something where the decryptor must do some searching to find the result.

Here is one simple example: suppose the encryptor takes the password, and selects $N$ random bits; he concatenates the two and SHA-256 hashes the result.  He then takes the first 128 bits of the hash, places that in the ciphertext, and then uses the other 128 bits to AES encrypt the secret; that's the rest of the ciphertext.

He then discards the original $N$ bits he selected.

To decrypt this, we have to search for the $N$ random bits that were selected; to do that, we have to compute an average of $2^{N-1}$ hashes, which is fairly slow.  Once we have selected the correct set of random bits, it's easy to recognize it (by comparing that hash with the initial part of the hash in the ciphertext); we can then decrypt the message.

You can select $N$ to taste; perhaps 24 if you want decryption to take maybe a second; perhaps 32 if you want to make it more expensive.

There are tweaks you can do to this approach:

Use multiple levels of puzzles, to reduce the chance that decryption might be done quickly (by stumbling on the answer early)
Use something other than SHA-256 (which is fairly GPU friendly).

However, I don't see how this approach could be made that resistant to a large multi-CPU attack...

If it is important to mimimize the variation in the decryption time, one idea would be to arrange the puzzles in parallel rather than serial.  That is, we select $k$ distinct random values of $n$ bits each, and compute the $k$ values:

$$h_i = \text{Hash}( \text{Password} || r_i )$$

and expose $z$ bits of each (for some $z$ somewhat larger than $n$).

Then, we compute a final hash $\text{Hash}( h_0, h_1, ..., h_{k-1}$, expose 128 bits of that (and use the other 128 bits as the actual key).

To decrypt, someone would need to compute $\text{Hash}( \text{Password} || x )$ for various values of $x$, and see if that matches any of the partially revealed $h_i$ values.  The decrypter will need all $k$ of them, and hence will need to try almost all $2^n$ possible values of $x$.

As an example, for $\text{Hash} = \text{SHA-256}$, $n = 28$ (a single for of my test machine can perform $2^{28}$ SHA-256 hashes per minute), $z=32$ and $k = 10$, then this would yield a decryption with about 10% variation, with 56 bytes of overhead...


For WinRar, how long should a password be to make up for a lack of complexity?

how long do you recommend a password or phrase to be when using
  WinRar?

This very much depends on how you choose your passwords. The "right" answer can be anything from 11 characters to 200 characters.

So assuming fgrieu's research is correct (it usually is), the PBKDF uses at least $2^{15}$ rounds of hashing, giving us effectively 15 bits of security "for free". Now with the target being 100-bit security (which is reasonably secure for most intents and purposes), this leaves 85-bits to go. Now assuming you use the full ASCII-Range and good cryptographic randomness, this is about 11 bytes, or 11 characters. However assuming humans being humans, you will get much less randomness from short passwords. A conservative estimate would be 40 characters (with a bit more than 2 bits of entropy per character) and a more aggressive estimate would be 16 characters (assuming nearly fully random pick from upper- and lower-case latin letters).


Finding collisions for the DES F-function

If S is a DES S-box, for a given "output", S(input) = output has exctly 4 solutions for "input", or "collisions". You can then find collisions for F by concatenating collisions for each S-box.
You can start with setting an output for F and then look for all possible "inputs" for each of the 8 S-boxes on the 4 relevant bits of the output of F.


Attack on DSA with signatures made with k, k+1, k+2

You got three equations with two unknowns ($k$ and $x$). You only need two signatures to solve the private key $x$:

$s_1k \equiv h_1 + xr_1 \pmod q$
$s_2k + s_2 \equiv h_2 + xr_2 \pmod q$

This might be solved using Gaussian elimination. Step 1:

$s_1k/r_1 \equiv h_1/r_1 + x \pmod q$  - Divide 0.1 by $r_1$
$s_2k + s_2 - s_1kr_2/r_1 \equiv h_2 - h_1r_2/r_1 \pmod q$ - Subtract 1.1 times $r_2$ from 0.2

Step 2:

$x \equiv s_1k/r_1 - h_1/r_1 \pmod q$ - Swap terms of 1.1
$k \equiv (h_2 - s_2 - h_1r_2/r_1)/(s_2 - s_1r_2/r_1) \pmod q$ - Divide 1.1 by $s_2 - s_1r_2/r_1$

Step 3:

$x \equiv s_1((h_2 - s_2 - h_1r_2/r_1)/(s_2 - s_1r_2/r_1))/r_1 - h_1/r_1 \pmod q$ - substitute $k$ in 2.1 for right expression of 2.2


Is RSA encryption with a private key the same as signature generation?

Short answer

No, RSA encryption with a private key is not the same as RSA signature generation. RSA encryption can only be performed with an RSA public key according to the RSA standard.

The terms Raw RSA or textbook RSA are often used to indicate RSA without a padding scheme. Raw RSA simply consists of modular exponentiation. Raw RSA is vulnerable to many cryptographic attacks and is not safe for general use.

Sources of confusion

It is often mentioned that signing is equivalent to RSA encrypting (the hash over) the message using the private key. This is only true if you disregard the required padding mechanism. The RSA padding mechanisms are different for encryption and signing.

Another reason why the two can be confused is that the public key is often identified with the ASN.1 OID for RSA encryption: 1.2.840.113549.1.1.1 or {iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) pkcs-1(1) rsaEncryption(1)}. This is for instance often the case within X.509 certificates. This OID is however generally used as a generic pointer to the PKCS#1 specifications; the unfortunate name is tied to the history of the X.509 and RSA specifications.

A deeper look into padding schemes

The PKCS#1 RSA Cryptography Specifications clearly define different schemes for RSA encryption and RSA signature generation.

The older PKCS#1 v1.5 standard contains two padding schemes that are often simply referred to as PKCS#1 v1.5. The padding for these encryption and signature schemes are however quite different, which is reflected by their official names RSAES-PKCS1-v1_5 and RSASSA-PKCS1-v1_5 - the first one is an Encryption Scheme (ES) and the other one is for Signature Scheme with Appendix (SSA).

Fortunately the confusion that arises from two padding schemes with the same name is not present for the newer OAEP encryption - which uses RSAES-OAEP padding - and PSS signature generation schemes - which uses RSASSA-PSS padding. So the name of the padding for encryption and signature generation is different even though they rely on the same mechanism (called a mask generation function or MGF with one implementation: MGF1).

The actual modular exponentiation is mathematically the same for RSA encryption with a public key and RSA signature generation using the private key. This is easily verified by looking at the last part of paragraph 5.2 [emphasis mine]:

  The main mathematical operation in each primitive is
     exponentiation, as in the encryption and decryption primitives of
     Section 5.1.  RSASP1 and RSAVP1 are the same as RSADP and RSAEP
     except for the names of their input and output arguments; they are
     distinguished as they are intended for different purposes.

In general, a signature created by performing RSA encryption will fail if the other party correctly implemented the verification method.

However, some software libraries actually perform RSA padding for signature generation if the private key is used for encryption. One possible reason for this is SSL/TLS; versions of TLS up to v1.2 used a "signature" created from an MD5 hash concatenated with a SHA-1 hash. Such a scheme is often not compatible with the signature generation methods provided by RSA implementations, hence they rely on the RSA encryption routine to magically do the right thing.

RSA implementation notes

A lot of implementations do not allow encryption with a private key. Trying to simulate signature generation using private keys is often not possible. Implementations of public key operations often assume a small public exponent. Furthermore, they will generally not apply the Chinese Remainder Theorem that is used to speed up private key operations.

Note that public keys do not require protection against information leakage, while private keys should be kept secure at all times. Hence RSA encryption implementations - when programmed to be used with a public key - may not contain protection against side channel attacks, possibly exposing the private key to an attacker that is able to apply a side channel attack.


Yes.  Discrete-log based cryptosystems (e.g., El Gamal) have a similar property.  It's "multiply", not "add", but that's just because that's the group operation for discrete-log based cryptosystems.

More generally, I suggest you look at threshold cryptography.  Threshold public-key cryptosystems are a class of systems that can achieve the sort of thing you mention.


How to guarantee every plaintext is in a rainbow table?

You could, but generating such a table may get prohibitively expensive. It may also prevent other optimizations, like merged chain removal.

If you had a data structure keeping track of the whole dictionary, you could tick off each entry when you add it to a chain at any point, then start each chain from an entry not already used. However, in the cases where you'd use a rainbow table, rather than a simple hash table, you may not be able to store all that. The extra space usage is proportional to the chain length.

Alternatively, if you already have a table with e.g. 99% probability, you could iterate over all the inputs, see if they are in the table, then add chains starting with those that are not. This should require relatively little extra space, but increases the number of hash function invocations by a factor of about $l^2$, where $l$ is the chain length, since you need about that many hash iterations for each input to check if they are in the table.

Once you had such a table, it wouldn't necessarily be that much more costly to use, except by virtue of being larger.


The Keccak submission says:

  From the security claim in [12], a PRF constructed using HMAC shall resist a distinguishing attack that requires much fewer than $2^{c/2}$ queries and significantly less computation than a pre-image attack.

Here, $c$ denotes the capacity of the sponge, i.e. the effective size of the internal state in bits.

Since HMAC is a deterministic iterated MAC (in particular, it does not use a nonce), it is always vulnerable to a generic birthday-based existential forgery attack requiring on the order of $2^{c/2}$ MAC queries (Preneel & Oorschot, 1999).

Thus, the claimed security level of HMAC-SHA3 is the same as the overall maximum attainable security level for HMAC, or any other deterministic iterated MAC construction, with the same effective internal state size.


Given a scenario, e.g. my Dropbox was hacked, and the hacker has access to my EncFS encrypted texts, and probably the history of it as well. Is that what was mentioned as "two or more snapshots" and "different times"?

Whether it applies depends on how the storage system would work. As far as I can tell, EncFS itself has no backup/versioning capability. Assuming that is the case, a storage system which supports history could implement it in one of two ways:

Do the versioning on top of EncFS. So the versioning system itself is stored in the encrypted filesystem.
Do it on a level below EncFS. So different versions of the filesystem exist.

In the former case, an attacker who only gained access to the system once could not see two copies of the ciphertext. In the latter they could.

In the real world, it is possible both would be used. E.g. if versioning is done on top of EncFS, but whole system backups are also stored. An attacker who got access to backups would be in a better position to break the encryption.

However, the audit details several weaknesses that even an attacker who only got access to a single snapshot could exploit, so I would disagree with the conclusion you quoted. For example, an attacker could punch holes in files without being noticed, and if the filesystem was large enough could find IV collisions leaking information on plaintext.

  Is EncFS good for online storage services?

I would argue that it is not. It is probably better than nothing and if only passive attackers need to be protected against it may even be secure. However, even the README points to some more modern alternatives. (Without saying EncFS is insecure or anything.)


With CBC mode the initialization vector is referred to as IV, because it is not nonce. There are ways to construct nonce so that it does not meet the needs of CBC mode. Random IV is one generation choice which is usually fine.
Nonce can also be a counter, which is not ok here.

Definitions

Nonce means number used once.
IV means initialization vector.

CBC mode security

For security of CBC mode (SemCPA in this case), it is necessary that the IV is unpredictable, prior use of IV. However, once IV is used, the value does not need to be kept secret.

One way to generate IV is to generate random numbers. For the CBC IV size (128 bits)  it is extremely rare to get IV value which is same than one of the previously used *IV*s. In addition, random numbers are by definition unpredictable.

Such IV values are nonce as well, as the numbers are used only once (with high probability unless the number of encryptions with the same key is very large).

However, there are also other ways to generate nonce. Once of common ways to generate nonce is to use increasing numbers (increment with 1 or use linear feedback shift register). Such approach fullfils the necessary requirements for nonce, but fails to meet needs (unpredictability) of IV for CBC mode.
(In Rogaway's paper, "Random IV" is used for Random IV generation and "nonce IV" for these other ways of generating nonce.)

The Rogaway's paper is concerned investigating the security provided by AES usual block cipher modes of operation if they have been implemented as defined in papers by NIST. NIST SP 800-38A is concerned with CBC, CFB, OFB and ECB modes.
NIST SP 800-38A (Appendix C) suggests two ways to generate IV for CBC mode, Random IV and nonce-based scheme using forward cipher function ($C = E_K^R(P)$) to generate IVs.

This paper by Rogaway points out that the nonce-based scheme using forward cipher function does not provide intended security.

Random IV

When using Random IV's, remember that if you generate $2^{64}$ IV's, there is around 50% possibility that not all IVs are unique. For this reason, you need to make sure that the amount of encryptions with single key is not too large.

And... If the random number generator is not a good one, then unpredictability can be violated. So generally you should make sure that a cryptographically secure RNG is used for IV's.


You have 10, 12, and 14 rounds respectively; however, they are not linear increments depending on the key schedule.  For AES-192, you have 8 different values and you have 7 values for AES-256.  The RCON value only changes with every round for AES-128.
The RCON value (in hardware) is generated by a register that is 8-bits and increments every round. It wraps around with the count, and left alone for encryption, you'd get:
0: 00000001
1: 00000010
2: 00000100
3: 00001000
4: 00010000
5: 00100000
6: 01000000
7: 10000000
8: 00011011
9: 00110110
10: 01101100
11: 11011000
12: 10101011
13: 01001101
14: 10011010

This is not what you'll actually use, but it's necessary to have a complete discussion.  In the above list, for AES-128, you'd start at round 0, and the final round, 9 (the 10th round), you will have 0x36.
For AES-192 and AES-256, you end up skipping constants due to the key schedule.  For AES-192:
0: 00000001
1: 00000001
2: 00000001
3: 00000010
4: 00000100
5: 00000100
6: 00001000
7: 00010000
8: 00010000
9: 00100000
10: 01000000
11: 01000000
12: 10000000

For AES-256:
0: 00000001
1: 00000001
2: 00000001
3: 00000001
4: 00000010
5: 00000010
6: 00000100
7: 00000100
8: 00001000
9: 00001000
10: 00010000
11: 00010000
12: 00100000
13: 00100000
14: 01000000

You can implement this in many ways. The naive approach that you'd have in class, but is easy to follow (also, FPGAs would do this generally):

The way that I generally do it (note, this is encryption, you move tap 4 for decryption):

The clock control increments the value.


How to detect changes in data while preserving confidentiality (under constraints)?

I'm going to try to make a handwavy argument that this problem doesn't have any great solution.  Criticisms are welcome!  A major assumption here is that my definitions are general enough to cover any possible solution to your problem.

Suppose there exists a scheme consisting of three deterministic algorithms $\operatorname{Broadcast}(X, Y)$, $\operatorname{CompareX}(B_1, B_2)$ and $\operatorname{CompareY}(B_1, B_2)$.  $\operatorname{Broadcast}$ is run by party $A$ and accepts $X$ and $Y$, outputting some "broadcast" value $B$.  $\operatorname{CompareX}$ and $\operatorname{CompareY}$ compare two broadcast values to determine if they were generated from the same $X$ or $Y$ values, respectively, and output $0$ when matching or $1$ when different.

Suppose a broadcast value $B_0$ is received by the attacker, who wishes to determine the secret value $Y$ from which it was generated.  The attacker can use the public algorithms $\operatorname{Broadcast}$ and $\operatorname{CompareY}$ to brute force the $Y$ value as follows:

Choose some arbitrary fixed value $x$ for use as an input to $\operatorname{Broadcast}$.
For each $y$ where $y$ is a guess for $Y$, call $\operatorname{CompareY}(\operatorname{Broadcast}(x, y), B_0)$.  Halt and output $y$ iff $\operatorname{CompareY}$ outputs $0$.

This suggests the option of making $\operatorname{Broadcast}$ or $\operatorname{CompareY}$ slow.  Consider the following scheme:

$\operatorname{Broadcast}(X,Y) = (X, \operatorname{PBKDF}(Y))$, where $\operatorname{PBKDF}$ is a password-based KDF such as scrypt, but using a fixed salt.
$\operatorname{CompareX}$ and $\operatorname{CompareY}$ are simply an equality check on the appropriate field.

If $S$ (the set of possible $Y$ values) is large and $\operatorname{PBKDF}$ is sufficiently slow, this might afford a modest level of security.


What is the length field in SHA-512 padding?

In $\text{SHA-512}$ the size of the blocks is 1024 bit. The last block must contain:

the rest of data in message (mod 1024).
some filling (padding)
the last 128 bits as length

If the message is 1919 bit length:

Calculate the size of the data in the last block:
$1919 \mod 1024 = 895$
Add the size of length field(128 bit) to the last block size(895 bit), $128 + 895 = 1023$
See that we have to add 1 bit as padding to the last block to became 1024 bit

The answer will be:

size of padding field = 1 bit
data of padding field = 1
data of length field = 1919 as an unsigned 128-bit big endian integer 0x0000000000000000000000000000077F


Montgomery Powering Ladder and Side Channel Attacks: Is it practically (im-)possible to analyze where intermediate values are stored?

Each bit of the exponent decides where intermediate results are stored.

Not necessarily.

One approach is to use a primitive known as a (constant access) conditional swap.  This primitive takes the values R and S, and swaps them if the bit in the exponent is 1, and leaves them alone if they are 0.  Naturally, this is done with constant accesses (even if the bit is 0, you still read and write R and S) and constant time; it's pretty straight-forward to implement (and is considerably quicker than the Bignum operations the rest of the algorithm uses)

With this primitive, the pseudocode looks like:

CSWAP R, S
R <- R*S
S <- S*S
CSWAP R, S

If the exponent bit is 0, we can ignore the CSWAP's, and this is exactly the Montgomery Ladder 'bit 0' logic.

If the exponent bit is 1, then we effectively do this logic:

R' = S, S' = R   /* First CSWAP */
R' <- R'*S'
S' <- S'*S'
R = S', S = R'   /* Second CSWAP */

Renaming variables, this simplifies to:

S <- S*R
R <- R*R

Which is the 'bit 1' Montgomery logic (as * is commutative).

Hence, we've implemented both sides of the ladder with constant memory accesses.

If we write out the full ladder, we'll see that there are adjacent CSWAPs based on different bits of the exponent; it's obvious how those could be combined to further simplify things.


Can two elliptic curve point multiplications have a same resulted point?

Yes, it is possible, but only if $a, b$ differ by a multiple of the order of the point $G$.

When we perform elliptic curve cryptography, we select a curve and a point $G$ where the order is a large prime (typically, circa the field size).  When we select a random multiplier, we most often select a random one uniformly between 1 and $\operatorname{order}(G)-1$; if both $a, b$ were selected that way, then the only way for $aG = bG$ would be if $a=b$


In cryptography, we often assimilate bitstrings to integers. Unless otherwise specified, that is per big-endian binary, where a bitstring $S$ of $n$ bits $b_0,b_1,\ldots b_{n-2},b_{n-1}$ is assimilated to integer $s$ with
$$s=\sum_{i=0}^{n-1}b_i\,2^{n-1-i}$$
E.g. bitstring 00010001 (which is 8-bit) is assimilated to integer $16+1=17$. Bitstring 0000000000010001 (which is 16-bit) and bitstring 10001 (which is 5-bit) also are assimilated to integer $17$. Note that for some purposes like hashing, we can't assimilate these bitstrings, even though they are assimilated to the same integer.
$H(x)<2^{n-k}$ compares $H(x)$, which is a bitstring (or perhaps a bytestring for a programmer), to $2^{n-k}$, which is an integer (an element of $\mathbb Z\,$). Some kind of transformation is needed. This is a sure sign that in the question, $H(x)<2^{n-k}$ must be read as:

the integer assimilated to the bitsring $H(x)$ is less than the integer $2^{n-k}$.

Note: In the circumstance it's also OK to assume little-endian binary, which uses the simpler $s=\displaystyle\sum_{i=0}^{n-1}b_i\,2^i$, but one should first get convinced this won't change the result.

There are several things wrong with stating

the size of the hashed $x$ is always going to be $n$ bytes, and $(n\text{ bytes }< 2^{n-k})$ is always true for any positive integer $k$.

If the question considered the size of "the size of the hashed $x$", it would be written $|H(x)|<2^{n-k}$, rather than $H(x)<2^{n-k}$.
Even with the statement understood as $|H(x)|<2^{n-k}$, the argument given would be wrong, with a counterexample the choice of $k=n$.
Cryptographers measure size of bitstrings and integers in bits (not bytes) unless otherwise stated. BTW, the bit size of non-negative integer $s$ is $\bigl\lceil\log_2(s+1)\bigr\rceil$, or equivalently the size of the smallest bitstring assimilated to $s$ (equivalently per big-endian or little-endian binary).


Without more details, I can't be certain what's going on with your implementation.  However, here is one thing that can certainly cause it to fail sometimes if $n$ is composite: the ECDSA verifier needs to compute $s^{-1} \bmod n$ (where $s$ is effectively a random number between 1 and $n-1$).  If $n$ is composite, then $s$ might not be relatively prime to $n$; if it is not, then $s^{-1}$ won't exist (because there's no number $t$ such that $s \cdot t = 1 \mod n$).  If this happens during the verification, then either your modular inversion routine (which computes $s^{-1} \bmod n$) will fail, or it will claim to succeed, and return some incorrect value (which will cause later calculations to fail).

If the order of your generator is composite, you'll run into a second problem; it'll be easier to break.  ECDSA can be broken if you can solve the 'discrete log' problem; that is, given the generator $G$ and a point $Q$, you can compute the value $d$ such that $Q = dG$.  Now, if the order of the generator $G$ is composite (say, $pq$), then an attacker could compute $pG$, $qG$, $pQ$, $qQ$, and solve these two discrete log problems $pQ = d_p(pG)$ and $qQ = d_q(qG)$, and given the values $d_p, d_q$, reconstruct $d$.  Solving these two discrete log problems would be considerably easier than solving the single discrete log problem (because the orders of the points involved are smaller); and hence we've just made things easier for the attacker.

Because generators with composite order can cause the verify to fail, and because they're cryptographically weaker, we always use generators with prime order.


Is there a standard, or widely accepted convention, for magic constants in crypto software?

If you just need a constant to begin your algorithm, and the value of that constant isn't important, why not have a widely known convention to always use the digits of Pi or Phi or other well known constant?

Why not use all zeros or all ones then? Why not use what user provided us with?

There is a joke: Good thing about standards is that we have so many to choose from.

Often there are some values that are supposed to have specific properties, like being prime numbers. Then you have to use CSPRNG with that constant. Why not use this CSPRNG, why not that one. This one is simple, this one is more secure, this is newer, this is more well-established etc.

In short: because they are used in widely different settings, and we usually have some vague requirements:

Sometimes it has to be of any length and secure (DH safe prime generation)
Sometimes it has to be of any length and just simple constant (HMAC)
Sometimes it has to be specific length and have high entropy (AES)
Sometimes it has to be fairly independent from another constant we used somewhere else

Last requirement is probably worst. There might be interference from two different algorithms that happen to use same constant, and since you have one standard you increase such possibility.

Even if you managed to fulfill that somehow, some values are supposed to have high entropy, and some can be plain anything. Making them meaningful decreases speed your algorithm will work on.

All that and you gain that 1% extra security that nobody did plant bug in algorithm. Sadly IMO this doesn't give us much and prevents smart designs that are faster while retaining security.