Perform calculation on encrypted numbers

No, that can't be done. There is no way that "Server performs haversine geolocation calculation over list of available active rides and figures out the best possible match along with the distance" but can't find driver's locations.

Worse, even if the server is trusted to internally know the location data, if it puts no limit to creating fake users and telling them what's the closest user, that allows to extract the location of any real user with arbitrary precision, by dichotomic search. That argument can be used to derive a rigorous proof of the above impossibility (sketch: there's nothing to stop a rogue server to use whatever computation it can make without implementing the necessary limitations).

Additionally, there is a possible inconsistency in "Driver has his private key on device and shares the location in encrypted format": the two things have no clear relationship. Fact is, it is never useful to encrypt with one's own asymmetric key, for only self could decipher. Remotely similar possibilities making sense include

Driver signs his/her location using his/her private key; that does not make the location confidential.
Driver encrypts his/her location with the server's public key.
Driver encrypts his/her location with public keys of some other users.

Note: variants of the last two involve establishing a symmetric key using the driver's asymmetric key, and using the symmetric key for encryption (perhaps authenticated), but that makes no functional change.

In the trusted server scenario, it is possible that users sign their location data with their private key and encrypt it with the server's public key; that keeps the location data from directly leaking to other users, and makes it necessary to use complicity of registered users to find a user's location. Further, the ability of a registered user to submit wildly different locations in a short period of time can be limited by the server. That's clearly feasible, including replacing the server by some secure "black box"; an HSM could do that.

Using Fully Homomorphic Encryption, it is theoretically possible that a non-trusted entity performs the distance calculation (including haversine), and I'm ready to admit it is possible to find the identity of the closest neighbor in encrypted form. But I see little point in that, for in the end deciphering distance and identity requires a trusted party / private key. Also, I'm afraid that, if security is required, the best FHE has to offer now would make computations slow (unbearably so for the encrypted identity).


How to generate a list of unique random strings?

There are three general solutions to the non-duplicate random number problem:

If you want a few numbers from a large range then pick one and reject it if it is a duplicate. If the range is large, then this won't cause too many repeated attempts.
If you want a lot of numbers from a small range, then set out all the numbers in an array and shuffle the array. The Fisher-Yates algorithm is standard for array shuffling. Take the random numbers in sequence from the shuffled array.
If you want a lot of numbers from a large range then use an appropriately sized encryption algorithm. E.g. for 64 bit numbers use DES and encrypt 0, 1, 2, 3, ... in sequence. The output is guaranteed unique because encryption is reversible. The Hasty Pudding Cipher can be set for any convenient range of numbers.


TLS_NULL_WITH_NULL_NULL the protection against replay, swapping and
  filtering is guaranteed?

No. The NULL-cipher suite makes no guarantees at all and it is explicitely forbidden in the RFC that two parties negotiate this cipher suite, the only reason for its existence is to run the handshake protocol.

  Because I have seen that the MAC uses a sequence number, so maybe this
  is used against replay.

The TLS record layer indeed does use a sequence number which is covered by the MAC authentication to prevent reordering attacks.

  If I do not calculate the MAC our TLS fragments are vulnerable to
  replay, swapping and filtering?

Yes, if you don't use a MAC of some kind (either application layer or transport layer) you have no guarantees regarding authenticity / integrity of the data and thus are prone to such attacks.

  Or the fact that we are using a reliable transmission protocol avoid
  that [...]?

TLS usually runs over TCP or a similar relieable protocol, but it is not a requirement. And note especially that such "reliable" protocols are only designed to protect from network errors, such as random transmission. They are not designed to survive a malicious / targeted attack which is why we have cryptographic transport protocols like TLS.


No, this is not the same thing as Diffie-Hellman key agreement.

What happens here is that the server authenticates itself by being able to RSA decrypt the pre-master-secret. If the server is able to do that it is possible to perform (H)MAC operations using the derived session key.

A problem with this scheme is that the encrypted pre-master secret can be stored by the attacker - together with the rest of the TLS session. The attacker can then try and find the private key value. Once that is found all the data of that particular session and all other sessions protected with the private key can be decrypted.

DHE_ and ECDHE_ ciphersuites work differently. The key pairs are generated on the fly; i.e. the key pairs are ephemeral (the E in DHE). Both client and server establish a session key. The server (or the client and server) then authenticate by performing signature-generation (for authentication). This has the advantage that each session needs to be attacked separately. This is known as (perfect) forward secrecy.

The server's random is a value that does not need to be protected. It is used as derivation data for generating the master_secret from the pre_master_secret. If it wasn't present then the key would not be dependent on a random source of the server. This is a problem if the client's random number generator is not secure (enough). The pre-master secret on the other hand needs to be kept secret.

Note that the server cannot send an encrypted value to the client as the client is not authenticated at that time.


Proving that a scheme is $\epsilon$-perfectly secret

There is no mistake.
Just prefix your work with the observation that any scheme is secure for $\epsilon\ge 1/2$ because all probabilities are less than or equal to 1.
Then consider the case $0<\epsilon<1/2$. Repeat your argument, then note that $2(1-\epsilon)>1$ and so $\epsilon/2(1-\epsilon)<\epsilon$.


Practical attack on md5 hashing algorithm?

Passwords, $p$, when only secured with a hash function $H$ on the database as $H(p)$ for login systems, is vulnerable to finding pre-image or secondary pre-image attacks.

Secondary pre-image : given $ H(p)$ find $p' \neq p$ s.t  $H(p)=H(p')$.

The famous rainbow tables are generated to more effectively find the pre-image or secondary pre-images. To countermeasure the rainbow tables, salt is one of the solutions.

As I can see from your problem there is a salt and these prevent the rainbow attacks.

As a result, you cannot benefit from the salts.

The only choice is the brute force.

And as you noted;

AWS p3.x16 has the power of 450GH/s.


How are AEAD, GCM, CBC, Poly1305, EtM, MtE and E&M related?

I do not know how they are related to each other.

EtM, MtE and E&M are generic constructions that take pairs of schemes that satisfy weaker security notions (chosen-plaintext security and unforgeability) and turn them into AEAD-secure schemes.
GCM is a construction that takes a 128-bit block cipher and turns it into - an AEAD-secure scheme and internally uses something like EtM for that.
CBC is one construction that takes a block cipher and turns it into something that is suitable for the encryption part of the EtM, MtE and E&M schemes (though it is admittedly not easy to do this right in face of padding / timing attacks).
Poly1305 is a one-time MAC (that is a MAC that is only secure when used at most once for a given key) which can be paired up with e.g. a block cipher (to generate one-time keys from nonces) to become a regular MAC suitable for the MAC part in EtM, MtE and E&M schemes.

  What does OpenSSL use by default?

Apparently OpenSSL will default to using either AES-GCM or ChaCha20-Poly1305 for symmetric encryption

  Which are supported?

TLS 1.3 abandoned the concept of these generic compositions so you will only find complete AEAD schemes to be specified as ciphersuite.


Are TLS 1.2 AES-CBC and AES-GCM Authenticated Encryption ciphersuites?

When can I consider a ciphersuite an Authenticated Encryption?

To cite from Wikipedia: Authenticated Encryption:

  Authenticated encryption  ... is a form of encryption which simultaneously provides confidentiality, integrity, and authenticity assurances on the data.

Note the focus on simultaneously.

  Is AES-CBC in TLS 1.2 an Authenticated Encryption (it uses MAC-then-Encrypt construction).

Since the authentication tag in the form of MAC is added before and not during encryption it can not be considered authenticated encryption. This allows the padding oracle attacks because this means that the authentication tag can only be verified after decryption.


Do hash functions for digital signatures need to be preimage resistant?

A hash function which isn't preimage resistent is also not collision resistance.
If I hash a large random message and apply the preimage algorithm I'm extremely unlikely to get the same message I started with, thus finding a collision.
Collision resistance is critical for a hash used in a signature. As you can create forged signatures. Even though you need a bit more in order to forge meaningful messages, such as exploiting internal state collision to make extensions collide and utilize formats like pdf or postscript.


What exactly is the contents of the LDAP userSMIMECertificate attribute?

tl;dr
The userSMIMECertificate attribute must hold a signed S/MIME message.
To create the contents for userSMIMECertificate, sign an email message with an empty message body, then remove all mail headers except for those describing the signature attachment.
The result should look similar to this (signature only):
Content-Disposition: attachment;
    filename=smime.p7s
Content-Type: application/pkcs7-signature;
    name=smime.p7s
Content-Transfer-Encoding: base64

MIAGCSqGSIb3DQEHAqCAMIACAQExCzAJBgUrDgMCGgUAMIAGCSqGSIb3DQEHAQAAoIIEQTCCBD0w
ggMloAMCAQICAQIwDQYJKoZIhvcNAQELBQAwgbYxGjAYBgNVBAMMEXNhdmlnbmFubyBDRVJULWky
MSUwIwYDVQQKDBxzYXZpZ25hbm8gc29mdHdhcmUgc29sdXRpb25zMR4wHAYDVQQLDBVDZXJ0aWZp
[...and so on...]
wtIEojI4gYW+wg/50/viPjxisPIPm3dEJbM+CN5gnySH9HwAAAAAAAA=

or like this (multipart message):
MIME-Version: 1.0
Content-Type: multipart/signed;
    protocol="application/x-pkcs7-signature";
    micalg=SHA1;
    boundary="----=_NextPart_000_003C_01D7312D.9474A240"

This is a multipart message in MIME format.

------=_NextPart_000_003C_01D7312D.9474A240
Content-Type: text/plain;
    charset="us-ascii"
Content-Transfer-Encoding: 7bit

This contents part may be empty or not and will be ignored.

------=_NextPart_000_003C_01D7312D.9474A240
Content-Disposition: attachment;
    filename=smime.p7s
Content-Type: application/pkcs7-signature;
    name=smime.p7s
Content-Transfer-Encoding: base64

MIAGCSqGSIb3DQEHAqCAMIACAQExDzANBglghkgBZQMEAgEFADCABgkqhkiG9w0BBwEAAKCCCDUw
ggQDMIIC66ADAgECAgRK+N2BMA0GCSqGSIb3DQEBCwUAMIHAMSMwIQYDVQQDDBpzYXZpZ25hbm8g
[...]
E3toHxuZzFrZMnMobwmt1nbAwNodpSsAAAAAAAA=

------=_NextPart_000_003C_01D7312D.9474A240--

This format can be created manually by signing an empty message using an email client, then saving that email in text format and removing the unwanted headers in an editor.
To create this format with openssl, use:
openssl smime -sign -in empty.txt -text -out userSMIMEcertificate.txt -signer mycert.pem -certfile intermediatecerts.pem

where mycert.pem is the signer's private certificate including its key and intermediatecerts.pem are any additional certificates that should be included. Add -inkey mykey.pem if the key is separate rather than included in the private certificate.
Note that, in order to sign the message, the certificate owner's private key is required.

Background Details
Format
The userSMIMECertificate is designed to hold a signed message that is signed using the user's email certificate. Additionally, it can and it should also contain the other certificates needed for chaining and verifying the user certificate. It's also designed to provide details about the encryption algorithms which are supported and preferred by the email client.
The userSMIMECertificate LDAP attribute is defined in RFC 2798: Definition of the inetOrgPerson LDAP Object Class as

A PKCS#7 [RFC2315] SignedData, where the content that is signed is
ignored by consumers of userSMIMECertificate values.

The format is based on RFC 2315: PKCS #7: Cryptographic Message Syntax. I find this RFC hard to understand, but fortunately, there is another document RFC 4134: Examples of S/MIME Messages that exhibits an example in chapter 4.9 S/MIME application/pkcs7-mime Signed Message.
As we can see there, it is an S/MIME signed email as created by any email client when sending a signed (but not encrypted) email.
According to this, it's not even necessary to remove any headers, but I recommend it for improved compatibility.
Purpose
In a quote from an original discussion with the creators of the userSMIMECertificate LDAP attribute, one of the authors explains:

Now we come to the question of why we felt we needed a new directory attribute for S/MIME certificates. I was told by our directory engineers that the existing userCertificate attribute was defined as a single raw certificate. That leaves no place to store the other certificates needed for chaining, and no place to store the algorithm capabilities. We had an existing package available to us that could contain both the certificates and the capabilities. That package is an S/MIME signed message.
The format of the userSMIMECertificate attribute is an S/MIME signed message with a zero length body. It contains the user's entire certificate chain and the signed attribute that describes their algorithm capabilities.

There is also a draft about the format to publish the data in userSMIMECertificate that provides some insight, but it has expired in 2001, and there doesn't seem to be successor to it.
Practical Notes
Weak Support
Most email clients seem not to understand a userSMIMECertificate that holds a PKCS#7 signed message. They do understand DER encoded certificates in this attribute. I'm planning to create a compatibility table but haven't yet.
Removed Headers
My above recommendation to remove all headers so only the signature is left is made because I have otherwise experienced problems with some clients, but I don't remember which. The actual definition does not require such modifications.
Algorithm Capabilities
One of the ideas for userSMIMECertificate was that the PKCS#7 data can include the owner's encryption capabilities (i.e. which ciphers they support). That way the encrypting client can select the best encryption cipher supported by both the sender and recipient of the email.
However, in extensive testing I've learned that in practice, only some (older) email clients provide such capabilities. My guess is that this feature has become obsolete by the fact that nowadays users are not confined to using only one email client all the time. Therefore, including one client's capabilities would be useless at best and might even lead to problems with the other client(s).


Yao's Garbled circuit: Does Bob ever see the circuit?

That summary, on which you are basing your understanding, seems bogus to me. Clearly the same $K_i^b$ values are being used as one-time pad keys, but are being used more than once. This is a major red flag.

Here's an even simpler attack: if you XOR together all 4 ciphertexts $X_s^{i,j}$ you will get $\Delta = K_k^0 \oplus K_k^1$. Since the functionality of the construction ensures that Bob will learn at least one of the values $K_k^v$, he can learn the other via $K_k^{1-v} = \Delta \oplus K_k^v$. As you point out, learning both wire labels is a violation of the privacy property.

While it is possible to use something like one-time pad for garbled circuits (see for example this paper of Kolesnikov), it requires much more care, and is not typically used in practice.

Better to think of a garbled gate as a random permutation of the following 4 ciphertexts:

$ \qquad \textsf{Enc}_{A_0,B_0}(C_0), \quad \textsf{Enc}_{A_0,B_1}(C_0), \quad \textsf{Enc}_{A_1,B_0}(C_0), \quad \textsf{Enc}_{A_1,B_1}(C_1)$

where $\textsf{Enc}$ is a legitimate encryption scheme.
(I like to use $A_0,A_1$ as wire labels on the left input wire, $B_0,B_1$ for wire labels on the right input wire, and $C_0,C_1$ for output wire labels)
In particular, knowing $Y$ and $\textsf{Enc}_K(Y)$ shouldn't allow you to solve for $K$ as it does in one-time pad.

To answer your bigger question about hiding the circuit. It is not required that the circuit be hidden from Bob. The standard setting of two-party computation has the parties first agreeing on a function to compute. The inputs to the function are to be hidden, but not the function itself. Furthermore, most practical garbled circuit constructions use the "Free XOR" optimization, and this requires Bob to behave differently for XOR gates vs AND gates (hence he must know the type of each gate).


Encrypting AES cipher text with fully homomorphic encryption

No, this won't happen. You can't change the order of operations. For that to happen, you'd have to homomorphically compute the decryption function of AES on the encrypted ciphertext c'.


Is it possible to create a 128-bit UUID from a weak entropy source?

The entropy will never go higher than the amount you put in. So if you require 128 - 4 = 124 bits and you input 32 bits, you can rest assured that the amount left is at most 32 bits. It's really that simple. And in that case, there is a high likelihood of collisions due to the birthday bound.
Now generally you will likely not find dupes during regular use, but an adversary may simply try and see if a collision can be made. In that case all bets are off, because in the end the RNG is simply not cryptographically secure.
I'd also be concerned about the entropy source. If it is 32 bits taken from the system clock then it is really not entropy at all, to name just one common option.

Try and avoid generating UID's at the client side entirely.
If this is really something you require then there is subtle crypto now for JavaScript in browsers, use that cryptographically secure random number generator instead. Beware of dragons though: "There is no minimum degree of entropy mandated by the Web Cryptography specification." ... this might especially be an issue on non-standard / embedded browsers.


meaning of Reduce f modulo the order of the base point G

First a preliminary: a base point $G$ on an elliptic curve generates a group of points on the curve such that every point in that group can be written as $dG$ ($d$ times $G$) where $d$ is an integer. This group is also cyclic in that for a certain value $q > 1$ we have that $qG = \mathcal{O}$, where $\mathcal{O}$ is the identity element, known as the point at infinity. This value $q$ is known as the group order. Reducing $f$ modulo $q$ is equivalent to calculating the remainder of dividing $f$ by $q$.

For standardized elliptic curves you won't need to calculate the group order yourself, it's usually included with the rest of the curve parameters.


Are these emerging threats against AES affecting your designs?

No, an attack on AES-128 requiring $2^{126.1}$ computations and $2^{88}$ bytes of known plaintext is not a concern. Brute-force guessing of keys (e.g., using the AES-NI instructions you mentioned) will succeed in $2^{127}$ computations on average and requires negligible known plaintext. Part of why key lengths are selected conservatively is precisely to ensure a safety margin which renders these tiny differences insignificant.

What the paper presents is an interesting method of analyzing block ciphers using a technique developed for analyzing hash functions. That this novel cryptanalysis technique fails to improve on brute force by even a full bit confirms the fundamental soundness and resiliency of AES's design.

Still, this technique is new and the paper explores multiple approaches to applying it. Cryptographers will be watching with interest to see if anyone goes farther with it, either through refinement or in combination with other cryptanalytic techniques.

Edit: In other discussion it was pointed out that this attack succeeds with probability 1, so an apples-to-apples comparison would be with worst-case brute force at $2^{128}$. It would be an exceedingly unlucky attacker who actually paid worst-case cost! A comparison of the typical scenario seems more relevant. The average-case for this AES-attack is probably a bit better than $2^{126.1}$, but it's not obvious from the paper. Still, the difference seems likely to be under a couple of bits (for now), while brute force retains its overriding advantage of not requiring $2^{88}$ data.

Of course one can build a weak protocol (or use a non-weak protocol in a weak way) on top of AES-128. WPA2-PSK can usually broken quite easily, because the pre-shared key is derived from a user-given password, which can be brute-forced in a short time. Even changing to an algorithm with a 10000-bit key would not help, if this key is derived from a weak password.


AES encryption takes more time to decrypt than encrypt

As the commenters have said, it is impossible to answer without many more details about your particular implementation, but here is some background on Rijndael (pronounced 'rain-doll') that might help. Rijndael is the family of ciphers on which AES is based. AES is defined as Rijndael[1] with a block size of 128 bits and key lengths of 128, 192 and 256 bits.
Back in 1999, when the winner of the AES had not been chosen yet, Bruce Schneier published a paper[2] on performance of the proposed ciphers. The Pentium Pro CPU was a high end processor back then. On page seven of his report he states:

Rijndael is another variant of Square: a fast cipher that works very well across all platforms. It boasts a clean mathematical structure involving only table lookup and XOR operations. Although the encryption and decryption algorithms are not exactly identical, their general structure and performance are virtually indistinguishable.
Rijndael’s assembly language on both the Pentium and Pentium Pro processors is about 300 clocks per block. Unlike RC6 and Mars, there are no known CPU platforms (8-bit or 32-bit) on which Rijndael’s relative performance would be unduly negatively affected or on which timing attacks would be possible.

According to this, one of the algorithm's advantages is its resistance to timing attacks. This would definitely have been a factor in the decision to select Rijndael as the current AES.
Later, though, discussing performance on 8-bit smart cards, which I read as computing platforms with very restricted resources, he says about Rijndael:

Perhaps the only negative comment about Rijndael on smart cards is that the performance numbers in the paper do not include a decryption function. Including decryption would increase the code size somewhat (probably between 512 and 1024 bytes), and decryption speed would be slower (possibly twice as slow) than encryption speed due to the coefficients of the inverse MDS matrix.

Again, without details about your implementation, it is impossible to know what the cause of the discrepancy is. There is strong evidence pointing to the fact that encryption and decryption for a given key should take about the same time, but the Arduino UNO has an 8-bit RISC processor and even though it has 2K of memory, it can only consume it 8 bits at a time. You could be experiencing the same theoretical problem Schneier described.
[1] https://en.wikipedia.org/wiki/Advanced_Encryption_Standard - Check the section called Description of the cipher.
[2] https://www.schneier.com/paper-aes-performance.pdf


In the ROCA paper the authors define an integer $M$ (which they call a primorial) as follows:

$$M = \prod_{i=1}^{n} P_i = 2 * 3 * ... * P_n$$

Said another way, $M$ is the product of the first $n$ primes. What the authors observed is that the factors of a vulnerable RSA modulus $N$ have the following form:

$$p = k*M + (65537^a \text{ mod } M)$$

The $65537 (= \mathtt{0x10001})$ might look a little odd hardcoded, but it's a common choice for the public exponent of an RSA key as it has a low hamming weight and thus allows some speed gains in common public key operations.

In the case you are interested in, where $|N| = 512$ bits, we have $n = 39$ and thus $|M| = 219$ bits. Since the size of the prime factors of $N$ is $\frac{|N|}{2} = 256$ bits this implies:

$$|k| = \frac{|N|}{2} - |M| = 256 - 219 = 37$$
$$|a| = \mathbb{log}_{2}(\mathbb{order}_M(65537)) = 62$$

So to generate a vulnerable $512$ bit RSA public key do the following:

Randomly sample a $62$ bit value $a'$ and a $37$ bit value $k'$.
Compute $p' = k'*M + (65537^{a'} \text{ mod } M)$.
Check that $p'$ is prime, if yes it is one of your factors $p$, if not go back to step 1.
Sample another prime $q$ using steps 1-3.

Your vulnerable RSA public key $(N, e) = (p*q, 65537)$.

On to the attack. If $M$ is known, our prime factor $p$ now only has $|k| + |a| = 37 + 62 = 99$ bits of entropy rather than the $256$ bits of entropy that it should. This is not good. The "naive" ROCA attack works in the following way:

Select a guess for the value of $a$ and compute $65537^{a} \text{ mod } M$.
Given $65537^{a} \text{ mod } M$ and the relationship $p = k*M + (65537^a \text{ mod } M)$ use Coppersmith's Algorithm to recover $k$.
Compute $p$ using the recovered $k$ and check if $N \text{ mod } p = 0$. If so, $p$ is a factor of $N$. If not,go back to step 1. and select the next guess for $a$.

The time complexity for this attack is $\mathcal{O}(2^{|a|}) = \mathcal{O}(2^{62})$ since in the worst case we have to check every possible value of $a$. Note that the search space of $a$ is the size of the group that $65537$ generates $\text{ mod } M$.

Now I said "naive" ROCA attack above because the authors optimize this attack by finding a value $M'$ such that the following relationship still holds:

$$p = k*M' + (65537^a \text{ mod } M')$$

But they find $M'$ in such a way that the size of the group $65537$ generates $\text{ mod } M'$ is much smaller than $\text{ mod }M$. Thus the search space for $a$ is also much smaller, and ends up bringing the time complexity down to $\mathcal{O}(2^{20})$. The actual process for finding $M'$ is rather involved, if you'd like to know the details I'd suggest diving into the paper.


What algorithm for AES key wrapping to choose in an embedded environment

AES with ECB and CBC mode

AES-ECB could well directly leak information, especially if it is used over multiple keys. The start of the private values within an encoded key are likely not precisely on a block boundary, so looking for repetition of blocks may for instance indicate that a key contains a smaller private exponent value than other keys. This will not likely leak enough information for a break, but telling auditors that parts of the key may be leaked is not recommended.

AES-CBC can be used, but it doesn't offer any integrity protection. Furthermore, it is vulnerable to padding oracle attacks and will directly leak data if the IV is predictable (distinguishable from random by an attacker). You may directly leak information about the RSA components if the IV is set to a static value for the same reason as for AES-ECB. Both will require some kind of padding, and a description on how to unpad (PKCS#11 often simply uses the encoding of the RSA key itself for that). This makes it perfectly valid to use zero padding.

Unfortunately many HSM's use ECB or CBC with a zero based IV to wrap keys. I'm not sure that those cryptographers were thinking at the time. Not recommended.

The AES-KW mode

AES-KW seems to be mainly concerned with symmetric keys and will probably not be very efficient for RSA keys. It requires input that is a multiple of the block size so just like ECB and CBC it will require padding. Otherwise it will be more secure than ECB and CBC. Still, AES-KW is probably not a good idea.

The AES-(GCM-)SIV mode

Static IV or SIV mode was specifically created with unique input messages in mind. As each RSA private key is (or should be) different from the next, SIV mode is especially useful for key wrapping; it is one of the stated goals for SIV.

Most cryptographers here will probably choose AES in SIV mode for encryption. This mode does expand the wrapped key compared to an unwrapped key, but it doesn't require an IV, and it protects the integrity of the key to boot. It also doesn't require padding, so that the expansion is just the authentication tag size (which doubles as the static-IV).

AES-GCM-SIV is a useful, fast alternative to SIV mode. It is probably a good idea to keep the authentication tag / IV size to 128 bits, especially when using GCM mode. Probably you don't need the GCM speedup for RSA key encryption, so normal SIV mode might be a better choice, if available.

One thing that slightly irks me is that the SIV is usually placed in front of the wrapped key. This makes in-place encryption impossible. However, the mode is just as secure if you place the SIV at the end (but that breaks compatibility with the description).

Unfortunately, I think that the order of availability is the exact reverse to the security provided by the various modes.


Honest Verifier Zero-Knowledge Game for Sigma Protocols

This question requires clarifications regarding the definition of special computational Honest-Verifier-Zero-Knowledge (Special cHVZK) as introduced in the linked material by Boneh and Shoup:

  Can the adversary generate the challenge c of the transcript in Special cHVZK?

No, because this is meant to be a definition for a version of honest-verifier zero-knowledge, therefore challenges must be uniformly random and cannot be chosen by the adversary.

  Can the adversary ask the transcript for polynomially many challenge instead of just one?

Well, that is the definition. If you allow the adversary to ask transcripts of polynomially many challenges, then it is easy to see that you will end up with an equivalent definition. So in theory, you could allow the adversary to ask the transcript of polynomially-many challenges.


Currently, I’m hashing (SHA2) a few extracted bytes I collect from a CSRNG to create keys for AES encryption/decryption. Is that wrong?

Depends on what you mean by "a few"; if you mean 16 or more, then yes, that is likely to be secure.  However, if you mean, say, 4, then that is Very Bad.

The reason is that the hash function doesn't do magic; if you use only 4 bytes of CSRNG output, and then compute:

$$Key := SHA256( \text{CSRNG Output} )$$

then what an attacker can do is exhaustive search over all 4 bytes of possible CSRNG output, compute the corresponding keys, and test them; there are only $2^{32}$ possibilities; a single laptop is likely to be able to go through all of them in perhaps an hour.

  But I could also skip SHA2 and extract more random bytes from the CSRNG until I’ve got enough bytes for a key. Is that a better idea?

Well, you'll likely need that many bytes of CSRNG output to form a secure AES key anyways; once you have that many, the SHA256 doesn't add anything.

  Or is SHA2 not one of those hashes that might make things less random?

No, SHA2 is not likely to be a weak hash function.  However, the problem is that SHA2 doesn't make things more random -- if there are only $2^{32}$ possible inputs to SHA2, there are only $2^{32}$ possible outputs.  It might make things look more random, but that's not what we care about.


Why is a hash of blocks - with index - weaker than hashing the entire thing?

Ok, here's a hint as to why this construct has essentially no cryptographical strength.

By using Gaussian Elimination, we can solve the below problem in $O(n^3)$ time (that is, very fast):

Given a target value $T$ and $n$ values $v_1, v_2, ..., v_n$ what bit vector $b_1, b_2, ..., b_n$ makes this happen:

$$\bigoplus_{i=1}^n b_i \cdot v_i = T$$

where $\cdot$ is multiplication (so $0 \cdot v_i = $ and $1 \cdot v_i = v_i$), and $\bigoplus$ is the exclusive-or.

If we were given a value $S$, how can the above observation be used to craft a message, that, when hashed by the method in question, generates the value $S$?

Further hint: suppose we were to arbitrarily select $n$ pairs of messages blocks $(m_1, m'_1)$, $(m_2, m'_2)$..., $(m_n, m'_n)$, and we set:

$u_i = Hash(m_i||i)$

$v_i = Hash(m_i||i) \oplus Hash(m'_i||i)$

$T = S \oplus \bigoplus_{i=1}^n u_i$

And we use Gaussian Elimination to find the bit vector $b_1, ... b_n$ with:

$$\bigoplus_{i=1}^n b_i \cdot v_i = T$$

How can we use the $v_i$ values to directly deduce the message that hashes to $S$?

(Practical note: often, there will be no such bit vector that satisfies the equation; this can be handled by including a few extra message block pairs (and hence $v_i$ values).


From context, it appears $\langle A,B \rangle$ simply denotes (some value unambiguously encoding) the pair of values $A$ and $B$.

In general, when discussing high-level protocols, no specific encoding for such pairs (or more complex tuples of values) is specified.  It is simply assumed that we can unambiguously store and transmit such structured data somehow, but the specific manner in which this is done is considered an implementation detail.

Of course, an interoperability standard may indeed need to specify such an encoding, especially if such data structures are to be processed by cryptographic primitives that are defined as operating on (bit or byte) strings, with the expectation that independent evaluations of the primitive on the same structure should yield the same canonical output.  Some standard encoding schemes include e.g. csexps or the various ASN.1 encodings, although it's also common for specific interoperability standards to specify their own custom encoding schemes.

Note that, even if $A$ and $B$ are both strings, the pair $\langle A,B \rangle$ can not generally be unambiguously encoded merely by concatenating $A$ and $B$ together, since concatenation may introduce ambiguity when the length of the strings being concatenated is not fixed.  For a simple example, $10 \,||\, 1 = 101 = 1 \,||\, 01$.  That said, if the length of either $A$ or $B$ (or both) is fixed, then $A \,||\, B$ can indeed be a valid unambiguous encoding of $\langle A,B \rangle$.


I have a question about multiplication of two points belong to elliptic curve. I know every think about adding and scalar multiplication but not about multiplication of two points.

Actually, when the paper talks about 'multiplying' two points, it's talking about what we more conventionally call 'point addition'; and hence what they call "g to the power to t1", we conventionally call "multiply the point g by the integer t1, that is, g added to itself t1 times".

It's not clear why they decided to refer to the elliptic curve as a multiplicative group and not an additive one.  Their paper is from 2006; I had thought that, by that time, the additive convention was fairly prevalent.  One possibility is that they looked at the convention of $\mathbb{G}_2$.  The group $\mathbb{G}_2$ has an operation which is multiplication over a finite field (at least with any pairing operation you'd actually use), and hence is always written multiplicatively.  Perhaps they decided to write the operations in $\mathbb{G}_1$ (the elliptic curve group) to be consistent with it.


$\displaystyle \text{cycles per byte} = \frac{\text{cycles per second}}{\text{bytes per second}} = \frac{2.1 ~ \text{GHz}}{4.3 ~ \text{MiB}} = \frac{2.1 \times 10^9}{4.3 \times 1024^2} \approx 466 ~ \text{cpb}$

Of course this may be way off because processors are complex beasts these days, and may not work at their full potential all the time, and the calculations may very well be reordered, optimized, or vectorized.

So it's a little better than raw speed in that it is not dependent of processor clock speed but it is still quite dependent on the underlying hardware details. It is a decent measure of cryptographic performance.


Proving an encrypted message contains (but does not 100% consist of) a plain-text message?

A fundamental theorem of cryptography (Goldreich, Micali and Wigderson 1986) states that any NP statement can be proven in zero knowledge. So, the answer is yes. For any polynomial-time combination of $X$ and $Y$ into $Z$, it is possible to prove that $Q$ contains $X$ in zero knowledge.

Note that the general zero knowledge will not be practically efficient since it requires a Karp reduction. However, depending on the combination and the public-key scheme, it may be possible to do this very efficiently. El Gamal specifically is very amenable to efficient zero knowledge, but it depends on the combination you mean.


Are there any simple and yet secure encryption algorithms?

A simple block cipher would be Threefish (p. 11-13). It's a bit more complicated than RC4 or RC5 yet doesn't drive you insane with seemingly random design choices. It is presumably secure and was designed by experts but has not yet been reviewed extensively, so it shouldn't be used in sensitive applications yet (consider it an exercise).

You'll be able to implement the key schedule and the encryption/decryption functions, and if you use the PDF I linked above, it will be an excellent exercise in following a specification.

If anything, it's the technical details surrounding the implementations that can take you forever to fix, such as endianness concerns in particular (this isn't too much of a hassle for block ciphers but it did get in my way a few times when implementing hash functions).

PS: same name lol


What does it mean if second half of 8-char string encrypted in 3DES is always identical?

DES has a block size of 8 bytes. Two blocks therefore come to 16 bytes.

It looks like Adbobe were encrypting passwords using two blocks of 3-DES in ECB mode.

Because all these passwords are eight bytes long, the second block is empty and is just filled with zeros. The second block gets started at all because of the string-terminating NUL character at the position 9 of the password. The character that the rest of the block is padded with is also NUL. Because we're in ECB mode, this block encrypts to the same value each time.

That's why all these passwords have the same eight trailing bytes: ioxG6CatHBw==. This is just the sequence of bytes you get when you encrypt 64 zero bits using their key.


Discrete logarithm key sizes for very short term usage

If:

You're okay with the encrypted information being easily decrypted after the session
You have a guarantee that the session won't be very long
You use random and unpredictable safe primes $p$ every session

I think it should, theoretically, be okay to use slightly smaller bit lengths for $p$.

That said, in practice it is probably a bad idea, and it's better to use ECC as @CurveEnthusiast mentioned. Generating safe DH primes is non-trivial, judging by how many implementations screw it up. And in the case of smaller groups, it is absolutely crucial that you generate random and unpredictable safe primes for every session (otherwise, someone can simply do a large amount of precomputation on the group, and crack connections using that group very, very quickly -- see Logjam).

What is your threat model? How much computing power does your attacker have at his disposal?

For reference, the authors of the Logjam attack in 2015 cracked several 512 bit groups in a week. They estimated that this could be optimized by a factor of 3, and they deliberately spent more time on precomputation. How fast do you think a state actor could break a 512 bit key exchange? It's not inconceivable to think that with a huge amount of computation power, and some very clever optimizations, a state-level adversary could do it in a few hours.

In short, it's not worth the risk. You run a big risk of improperly generating the weaker DH groups. You run another big risk of reusing the weaker DH groups, or having them be predictable, thereby opening yourself up to precomputation attacks.

Try ECC curves instead, and see if they don't alleviate your time/power consumption issues.


Recovering state of modified RC4 key scheduling algorithm

The algorithm you describe seems to have a class of special states (similar to the Finney states of RC4) consisting of the states such that $i = j$ and $k_x \bmod L = 1$, where $x := k_i \bmod L$.

If we are at a state that belongs to this class at the beginning of the loop, the effect of the loop will be simply to swap $k_i$ and $k_{i+1}$ and to increment both $i$ and $j$ by one.  Thus, as long as we also have $x \notin \{k, k+1\}$, the state at the next iteration of the loop will also belong to this class of special states.

In particular, consider what happens if, before the algorithm, we have $k_0 = L-1$ and $k_{L-1} = 1$.  Then the initial state $i = j = 0$ belongs to the special class described above, and this will continue to hold almost to the end of the algorithm.  The second to last iteration, where $i = L-2$, does take us out of the class, leaving us with $i = j = x = k_x = L-1$, but this just causes the last two elements of the array $k$ to be swapped a second time on the last iteration, leaving us with $k_{L-2} = L-1$ and $k_{L-1} = 1$.

Meanwhile, all the other elements of the array, between the $L-1$ at the beginning and the $1$ at the end, just get shifted down by one position as the $L-1$ element bubbles up past them.  Thus, from an initial array $$(L-1, a, b, c, \dotsc, y, z, 1) \tag{1}$$ we end up with the final state $$(a, b, c, \dotsc, y, z, L-1, 1) \tag{2}$$ regardless of the values of the unknown elements $a, b, c, \dotsc, y, z$.  Conversely, to end up in any final state of the form given in $(2)$ above, it suffices to start with the corresponding initial state $(1)$.

(The same trick works also for loops terminating at some $i = C < L-1$, except that the initial $L-1$ element then ends up at $k_{C+1}$ rather than at $k_{L-2}$.)

In fact, I just wrote a little program to test this.  Here's a sample run with $L = 10$, one line per iteration, starting with eight random values bracketed between $L-1 = 9$ and $1$:

k = (9, 144, 165, 42, 43, 56, 231, 72, 53, 1), i = 0, j = 0
k = (144, 9, 165, 42, 43, 56, 231, 72, 53, 1), i = 1, j = 1
k = (144, 165, 9, 42, 43, 56, 231, 72, 53, 1), i = 2, j = 2
k = (144, 165, 42, 9, 43, 56, 231, 72, 53, 1), i = 3, j = 3
k = (144, 165, 42, 43, 9, 56, 231, 72, 53, 1), i = 4, j = 4
k = (144, 165, 42, 43, 56, 9, 231, 72, 53, 1), i = 5, j = 5
k = (144, 165, 42, 43, 56, 231, 9, 72, 53, 1), i = 6, j = 6
k = (144, 165, 42, 43, 56, 231, 72, 9, 53, 1), i = 7, j = 7
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), i = 8, j = 8
k = (144, 165, 42, 43, 56, 231, 72, 53, 1, 9), i = 9, j = 9
k = (144, 165, 42, 43, 56, 231, 72, 53, 9, 1), j = 8, end of loop


Assuming you posted correctly, your second file has the base64 body of the claimed PEM format as a single line, not broken/folded into lines of 64 chars (max) as required. See RFC 7468 section 2 near the end. Some software is lax about this (including, usefully, openssl asn1parse !) but not all. I wonder if you got these switched, because OpenSSL commandline (and library) always writes PEM with linebreaks as required -- although IME it may write Unix-style linebreaks (LF only) on Windows, and if you open such a file in some Windows programs like notepad it may ignore/discard the LF and treat it as one huge line while e.g. wordpad (or type or more) displays it correctly.


Can the OpenSSL random number generator be considered cryptographically secure?

Can the openSSL random number generator be considered cryptographically secure?

Yes.

  Does it impact the quality of randomness to use a broken cryptographic hash such as MD5 for random number generation?

Not as far as we know. The question you link does, in fact, cover this topic adequately. To quote it to answer your question:

  And actually, collisions in a PRNG output are nothing to be feared. You would expect these to occur naturally (but infrequently) as you produce the output. Random numbers repeat sometimes. What's important is that again given a long sequence of output, we can't at the moment discover the input sequence and therefore the generator's internal state.

This CSPRNG is, with modern (2019) hardware, secure, with there being a very minimal risk to the RNG being predictable.


Aumasson et al. Showed that ChaCha6  can be attacked with time complexity $2^{139}$ and ChaCha7 with $2^{248}$.
Shi et al. gave an attack based on second-order differential with $2^{136}$ for ChaCha6 and $2^{246.5}$ for ChaCha7.
Maitra, chosen IV cryptoanalysis and the time complexity of the attack showed that it can be reduced to $2^{239}$ for ChaCha7.
Choudhuri and Maitra concluded ChaCha12 are
sufficient for 256-bit keys against differential cryptanalysis using a hybrid model of non-linear round functions and linear approximation...

\begin{array} {|l|l|}
\hline
Attack & Evaluation \\
\hline
\text{Differential Analysis }      &                    \text{No attack found}\\
\text{Rotational Cryptanalysis}     &                   \text{No attack found}\\
\text{Boomerang Attack}        &                        \text{No attack found}  \\
\text{Linear Cryptanalysis}      &                      \text{No attack found}\\
\text{Distinguishing Attack}     &                      \text{No attack found}\\
\text{Guess and Determine Analysis}       &             \text{No attack found}\\
\text{Time-Memory-Data Tradeoff Attack }   &            \text{Protected}\\
\text{Practically ChaCha Algebraic Attack}   &          \text{No attack found} \\
\text{Attacks on Initialization Process}    &           \text{No attack found}\\
\text{Single Power Analysis }           &               \text{Protected}\\
\text{Practically Difference Power Analysis }    &      \text{Protected Practically}\\
\text{Cache Timing Attack}         &                    \text{No attack found}\\
\text{Fault Injection Analysis }   &                    \text{Protected Practically}\\
\hline
\end{array}
The above table and results come from KDDI Research, Inc

simple power attack; though the rotation is vulnerable to power attack, they propose masking as a countermeasure.
differential power analysis; they demonstrated that adversary can get all keys except $k_1$ which can be found in $2^{32}$, proposed masking as a countermeasure.
Fault Injection Attack; they claim that the initial matrix $X$ or
matrix $X^{(20)}$ will be output if injection is performed on the addition.

A countermeasure against this sort of attacks is to separate variables; that is, distinct variables store the inputs and output of the addition. Consider an addition $z \leftarrow x+y$. The addition returns the initial value of variable z even if the addition is skipped. Thus, the adversary can get neither the value of variables $x$ and $y$. Algorithm 9 shows the implementation using countermeasure based on variable separation.
We should note that variable separation in source-code level does not work

They include all attacks upto 2017 in their document. I couldn't find one in 2018.


You can use a similar method like VeraCrypt. Also, you can use a better Key derivation alternative like Argon2id. Argon2id is the combined version of Argon2d, data-dependent, and Argon2i data-independent modes.
For the encryption

Get/force a good password from user and use it with Argonid with application/usage dependent domain separation
$$k = \operatorname{Argon2i}(passwd\|app)$$

Use $k$ for $\operatorname{AES-GCM}$ encryption of the file with a random or counter-based generated nonce;
$$(c,tag)\operatorname{AES-GCM-128}(k, nonce)$$

Store the $(nonce\mathbin\|c\mathbin\|tag)$

Also encrypt a small text with the $k$ $$check = \operatorname{AES-ENC}(k,\text{"myData"})$$

Store this $check$, too.

Delete the $k$ from the memory.

For the decryption;

Get the password from user and use $k' = Argon2i(passwd\|app)$
Decrypt the $check$ with the $k'$ $$check' = \operatorname{AES-DEC}(k',\text{"myData"})$$
If the plaintext is $\text{"myData"}$ then $k'=k$ ans start to use it, else warn the user.

Other methods;

you can test the password like the usual password-based login systems.

you can generate a random key for the message and encrypt this key with the key derived from the user's passwords. Prepend the message to check the validity of the password.

Is this correct/incorrect password for file encryption scheme secure?

There is no need to derive $k_2$ since it will be public. And, though it will be secure, you are giving direct testing for the attackers.


Timing attack on RSA as used by CryptoLocker?

No, it's not possible to recover the private RSA key; not with a timing attack, not with a debugger, not with any technical means.  There isn't enough information on the victim's computer.
The timing attack you describe requires timing the decryption operation, which could reveal the decryption key.  But the malware isn't ever decrypting anything, it's just encrypting the victim's data.  The malware doesn't even have the decryption key until after you pay the ransom.
All a timing attack could tell you about RSA keys during encryption is the encryption key, but that's just the public key that your machine's virus retrieves from their server.  The whole point of asymmetric encryption security is to separate encryption secrets from decryption secrets.
EDIT
I reread your question more carefully, and I now understand that you're asking if it's possible to attack the criminal's server, not the client-side malware.  Yes, servers can obviously be attacked.  And yes, side-channel attacks are one of the many potential tools that could be used to attack it.  But the thief doesn't operate just one server, he's operating a large farm of them; the client-side malware simply keeps testing for servers until it finds one that responds.  In order to recover your own data, you would need to identify the correct server containing your key, hack into it, and exfiltrate all the data from it before he wipes all the stored private keys (either in response to the attack or because you didn't pay him in time.)  Even if such an attack was successful, it will do little to help with future attacks as each private key is reportedly generated on request.


Statistics on the frequency of usage of RSA key public exponents

I couldn't find any references to any statistics, however:

All Fermat primes $${3, 5, 17, 257, 65537, 4294967297, 18446744073709551617, … }$$ could be used while regarding the use a proper padding scheme. There is no known weakness for any short or long public exponent for RSA, as long as the public exponent is "correct" (i.e. relatively prime to p-1 for all primes p which divide the modulus).

So why is $ e = 65537$ used most commonly?

Using $e=65537$ (or higher) in RSA is an extra precaution against a variety of attacks that are possible when bad message padding is used. But it's not too large so that it would greatly impact performance speed ($e = 3$ is around 8x faster than $e = 65537$).

So in short: $e = 65537$ is most commonly used as a comprimise, because it's reasonably fast and secure.

Related answers for more details:

Impacts of not using RSA exponent of 65537, answer by fgrieu
Should RSA public exponent be only in {3, 5, 17, 257 or 65537} due to security considerations?, answer by Thomas Pornin


This post answers my first questions: RC4 Keystream Reconstruction

Because I integrate others informations to this problem.

The RC4 algorithm has some well-known vulnerabilities but it is not completely moldy. So, if I understand correctly, finding the initial encryption key even with the clear text is difficult (Principaly in this case, no reset rc4, key lenght, ...).

On the other hand I understand that I work on a similar challenge.

I have to decrypt a file of the same type: INTEL Hex Format

So, Drop-N routine or not, if I know the plaintext I know the associated XOR key.


Statement $a > c$
could be proved as $a - c - 1 = b_1^2 + b_2^2 + b_3^2 + b_4^2$.
According to Lagrange theorem,
a 4-tuple of integers exists for any non-negative integer such that it equals to the sum of squares.
This kind of proof was suggested by Helger Lipmaa (On diophantine complexity and statistical zero-knowledge arguments. ASIACRYPT 2003).
Proving statements about integers (not finite field elements) committed with Okamoto-Fujisaki commitment scheme, is doable
with a group of order hidden from Prover.

Scenario described previously looks somewhat like a Zcash JoinSplit (section 1.2 High-level Overview).


You should not just "pick the highest frequency character and assume it should be E" because it will probably fail most of the time, except if your ciphertext is really long.

If your alphabet is small enough (usually either 26 or 255), it would be wiser to try all the possibilities for each group, and to check if the output looks like real english (printable chars, correct frequency, etc). It will be almost as fast, and you'll be way more confident in your result.


Meaning of the $m$ power of a modular world

The notation $(Z_{26})^m$ means the $m$-fold cartesian product of $Z_{26}$.  This is a set whose elements are all tuples of length $m$ with components in $Z_{26}$.  For example, $(Z_2)^2$ means the set of tuples (0,0), (0,1), (1,0), (1,1), where $Z_2$ alone is taken to mean the set of integers modulo 2, i.e. 0 or 1.  In this context, you can read $(Z_{26})^m$ as the set of strings that are $m$ English letters long.

(Beware: Sometimes $Z$ means the center of a group, not the integers, so I prefer to write the unambiguous $\mathbb Z$.  Sometimes $Z_p$ or $\mathbb Z_p$ means the $p$-adic integers, so I prefer to write $\mathbb Z/p\mathbb Z$ which is the unambiguous quotient of $\mathbb Z$ by the ideal $p\mathbb Z$, i.e. the integers modulo $p$.  But in this case context suggests that $Z_{26}$ means the set of integers modulo 26, corresponding to the English alphabet.)


Security is clearly broken if there is a polynomial-length period with non-negligible probability (where by this I mean if a random point falls in a cycle with a poly-length period with non-negligible probability). In order to find a preimage, just go forward until you get back to the starting point, keeping the previous value each time.


Can we have single hash function both for data integrity and key derivation function?

I'll answer the question in the context of the most common application of KDFs - Password-Based Key Derivation Functions (ex PBKDF2) which take a relatively low-entropy string and derive a key from it. As opposed to Key-Based KDFs which take something that's already a strong key and change its length.

Hashes and PBKDFs are designed for different things. Yes, they are both hash functions with all the usual collision resistance, pre-image resistance, etc, but:

General-purpose hash functions want to be fast to have efficient implementations in software and hardware. This greatly reduces the runtime costs and latency of TLS servers, embedded devices doing TLS, hashing large files, etc.
PBKDFs want to be slow to make it as frustrating / expensive as possible to perform brute-force attacks on the password or master key.

SHA2 makes a terrible PBKDF because it's way too fast. PBKDF2 makes a terrible hash function because it's way too slow.

Many key derivation functions use regular hash functions internally.

For example, if you take a look at the PBKDF1/2 spec in RFC 2898, you'll notice:

  5.1 PBKDF1

  PBKDF1 applies a hash function, which shall be MD2 [6], MD5 [19] or
     SHA-1 [18], to derive keys.

and

  5.2 PBKDF2

  PBKDF2 applies a pseudorandom function (see Appendix B.1 for an
     example) to derive keys.

And the example referenced in Appendix B.1 is to use HMAC-SHA-1 as the underlying pseudorandom function.

Related question on security.SE:

What's the advantage of using PBKDF2 vs SHA256 to generate an AES encryption key from a passphrase?


Why does SSH authentication protocol send a challenge message instead of using digital signature to verify client

The server sending an encrypted challenge has a few advantages over the signature-based method you described:
1) It is more efficient for the client in the case that authentication is rejected outright.
If the server doesn't recognize the client's public key, there's no reason to have the client waste time and energy generating a signature.
2) It is more secure from the server's perspective since the challenge is, for all intents and purposes, completely unique per connection.
The server is not just trying to verify that the person who signed the message has the private key but that the client it is connected to is the one who signed the message.  So a signature would need to be of data that could not have been stolen from a separate communication (either with this server or another one).
3) It also helps protect the client's private key from clever attacks.
As described in section 3.4.2.2 of the O'Reilly book on SSH:

The client receives the challenge and decrypts it with the corresponding private key. It then combines the challenge with the session identifier, hashes the result with MD5, and returns the hash value to the server as its response to the challenge. The session identifier is mixed in to bind the authenticator to the current session, protecting against replay attacks taking advantage of weak or compromised random-number generation in creating the challenge.
The hashing operation is there to prevent misuse of the client's private key via the protocol, including a chosen-plaintext attack. If the client simply returns the decrypted challenge instead, a corrupt server can present any data encrypted with the client's public key, and the unsuspecting client dutifully decrypts and returns it. It might be the data-encryption key for an enciphered email message the attacker intercepted. Also, remember that with RSA, "decrypting" some data with the private key is actually the same operation as "signing" it. So the server can supply chosen, unencrypted data to the client as a "challenge," to be signed with the client's private key -- perhaps a document saying, "OWAH TAGU SIAM" or something even more nefarious.

4) A signature based method, implemented properly, would still require the same number of steps, due to the logic in (2).
That is, because the server wants to be sure that it the client has the private key, even in a signature based method it would be best for the server to send a random challenge and have that signed, making the process look very similar but without the benefits described above.


Problems with calculating inverse of finite field $GF(2^8)$ of AES

Let $g(x) = (x^8+x^4+x^3+x+1)$ and $p(x) = (x^7+x+1)$
The GCD is correct and it is $1$ as the last non zero remainders.
\begin{align}
(x^8+x^4+x^3+x+1) &= (x^7+x+1)(x) + \color{blue}{(x^4+x^3+x^2+1)}\\
(x^7+x+1) &= (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}\\
(x^4+x^3+x^2+1) &= (x^3+x^2+x)\color{red}{(x)} + 1\\
\end{align}
Now collect back to find to reach Bézout's identity $$a(x)g(x) + b(x)p(x) = d(x)$$ where $d(x)$ is the $\gcd(p(x),g(x))$
and we want to keep $g(x) $ and $p(x)$

begin from the last equation ( the last one that has non-zero remainder)
$$(x^4+x^3+x^2+1) =  (x^3+x^2+x) \color{red}{(x)} + 1$$  change to  (in $GF(2)$ we have $-1=1$)
$$1 = (x^4+x^3+x^2+1) + (x^3+x^2+x)  \color{red}{(x)}$$

Now substitute $\color{red}{(x)}$ from the previous
$$(x^7+x+1) = (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)} + \color{red}{(x)}$$
that is
$$\color{red}{(x)} = p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}$$
now substitute
\begin{align}
1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)\big[(p(x) + (x^3+x^2+1)\color{blue}{(x^4+x^3+x^2+1)}\big]\\
  1 &= \color{blue}{(x^4+x^3+x^2+1)}) + (x^3+x^2+x)p(x) + (x^6 + x^2 + x)\color{blue}{(x^4+x^3+x^2+1)})\\
1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1)\color{blue}{(x^4+x^3+x^2+1)})\\
\end{align}

Now substitute $\color{blue}{(x^4+x^3+x^2+1)}$ from the first equation
$$g(x) = p(x)(x) + \color{blue}{(x^4+x^3+x^2+1)}$$
$$\color{blue}{(x^4+x^3+x^2+1)} = p(x)(x) + g(x)$$
\begin{align}
1 &= (x^3+x^2+x)p(x) + (x^6 + x^2 + x +1) \big[p(x)(x) + g(x)\big]\\
1 &= (x^3+x^2+x)p(x) + (x^7 + x^3 + x^2 + x) p(x) + (x^6 + x^2 + x+1) g(x))\\
1 &= (x^7 ) p(x) + (x^6 + x^2 + x) g(x))\\
\end{align}
Now that modulo $g(x)$ of both sides
$$1 = (x^7 ) p(x) $$ and this implies inverse of $p(x)^{-1} = x^7$

Note: for the field calculations I've used a Sagemath code as below, and this can be used for AES calculations.
#Base field
R.<y> = PolynomialRing(GF(2), 'y')

#Defining polynomial
G = y^8+y^4+y^3+y+1

#The field extension
S.<x> = QuotientRing(R, R.ideal(G))
S.is_field()

#this is zero
X = x^8+x^4+x^3+x+1
print(X)

#GCD
print(X.gcd(x^7+x+1))
#to find and inverse use the 1/
1/(x^7+x+1)
#field calculations
(x^3+x^2+1)* (x^4+x^3+x^2+1) + (x)


Why do some block cipher modes of operation only use encryption while others use both encryption and decryption?

That is the general idea of it yes.

Some modes of operation (eg CTR) work in such a way that only known values are ever encrypted, forming a stream of pseudo-random data that is then combined with the plaintext by a keyless reversible operation (often xor) to form the ciphertext.

Other modes (eg CBC) directly encrypt secret (ie plaintext) values, meaning decryption is required to find out what the secret value was.

One of the biggest advantages of a scheme that does not require decryption is that it can be implemented in hardware with reduced footprint (ie it's smaller).  Moreover, for block ciphers such as AES it can often be easier to implement efficient encryption than decryption because the internal coefficients have been optimized for this direction.


For the complete picture, as was pointed out, you should use the final RFC, not drafts. There are two relevant RFC here:

RFC 7539 describes the stream cipher ChaCha20, the MAC algorithm Poly1305, and an Authenticated Encryption with Associated Data mode that combines ChaCha20 and Poly1305 in a safe way (in particular, it uses ChaCha20 to provide the secret values needed by Poly1305).
RFC 7905 describes TLS cipher suites that rely on the AEAD construction described in RFC 7539; that RFC explains how the associated data and nonce are built in the context of TLS.

In RFC 7539, section 2.6, there are some explanations about the nonce. The nonce must have length exactly 96 bits (12 bytes); however, the following text appears:

The protocol will specify a 96-bit or 64-bit nonce.  This MUST be
unique per invocation with the same key, so it MUST NOT be
randomly generated.  A counter is a good way to implement this,
but other methods, such as a Linear Feedback Shift Register (LFSR)
are also acceptable.  ChaCha20 as specified here requires a 96-bit
nonce.  So if the provided nonce is only 64-bit, then the first 32
bits of the nonce will be set to a constant number.  This will
usually be zero, but for protocols with multiple senders it may be
different for each sender, but should be the same for all
invocations of the function with the same key by a particular
sender.

This is why the test vector in RFC 7539, section 2.8.2, shows this:

IV:
000  40 41 42 43 44 45 46 47                          @ABCDEFG

32-bit fixed-common part:
000  07 00 00 00

These are a 64-bit IV and a 32-bit "fixed-common part", which are meant to be assembled (concatenated) into the 96-bit value that the algorithm requires.

However, if you look at RFC 7905, you will see that what happens in TLS is something a bit different:

AEAD_CHACHA20_POLY1305 requires a 96-bit nonce, which is formed as
follows:

1.  The 64-bit record sequence number is serialized as an 8-byte,
    big-endian value and padded on the left with four 0x00 bytes.

2.  The padded sequence number is XORed with the client_write_IV
    (when the client is sending) or server_write_IV (when the server
    is sending).

In other words, a full 96-bit (12 bytes) value is generated from the handshake, and the record sequence number is XORed into the last 8 bytes. An alternative design, more in line with the method explained in RFC 7539, would have been to concatenate a 32-bit (4 bytes) value generated during the handshake with the 64-bit (8 bytes) record counter. However, the RFC 7905 designers found it fit to use the XOR method, which can be argued to make nonce reuse between distinct TLS connections even less probable (not that it would matter much, since distinct TLS connections also use distinct encryption keys).


Algebraic relationship between Original Key and Sub Key of DES

Laurie Brown and Jeniffer Seberry (see paper here performed a comprehensive analysis of the key schedule of DES, published in AUSCRYPT90 (conference series which later on turned into ASIACRYPT), and suggested some changes to strengthen the key schedule.

This is a good starting point to start hunting citations, and see what else has been done since then.


How to find 64 collisions for a hash value?

As far as I understand, you are trying to find $M_1...M_6$ so that $H(M_0||M_1||...||M_6) = h$ for any of 64 preset values of $M_0$. This implies a collision attack on $H$, which in the case of SHA-1 has not yet been accomplished in practice (though it is probably close).

Specifically, you would need a chosen prefix collision. We have such attacks for MD5 (see e.g. the links from this answer), assuming you have enough freedom in the size/choice of $M_i$. However, there is still a ways to go before it could be accomplished for SHA-1.


If we know $e$, then it's easy.

If don't have to know the factors, but it does make it easier - as fgrieu pointed out, either $(p-1)/2$ or $(q-1)/2$ will appear as one of the prime factors, that will allow us to immediately recover $p, q$

Once we have that, then we know that we want:

$$y^{p_0} \equiv 1 \pmod p$$
$$y^{p_0} \equiv 1 \pmod q$$

If we have $y \equiv 4 \pmod p$ (or any other quadratic residue) and $p_0 = (p-1)/2$ (which is prime), then we satisfy the first equation.

If we have $y \equiv 1 \pmod q$, then we satisfy the second equation.

It's easy to find a $y$ that meets both modulii (as $p, q$ are relatively prime) using the Chinese Remainder Theorem, and so that's our answer.


Generate a list of unique coupon codes in a format of your choice.
Print them out prior to the meeting /event/ ceremony. Like lottery tickets.
Hand them out to attendees, one for each kid. At the end I guess.
Each kid then later enters the coupon code into a website to confirm attendance.
Repeat prior to the next event...

There's a question here regarding preparation of coupons.  Just formulate your generation algorithm carefully to avoid BUMH0LEs.


Is it acceptable to write the nonce to the encrypted file during AES-256 GCM?

The IV of encryption schemes can be made public without damaging the security of the encryption, so there shouldn't be any issues with prepending it to the encrypted file.

The difference between IVs and Nonces was already explained by @SEJPM in the comments. Note that in the case of GCM, you do need to make sure that you do not re-use the IV with the same encryption key, as AES-GCM works (I'm simplifying here) by using the IV as a counter and encrypting successive counter values to generate a key stream, which is then XOR'd onto the plaintext to encrypt it (like the regular CTR-Mode). This means that if you re-use the IV and key, you will generate the same keystream again and allow more efficient attacks on the encryption (think key-reuse for one-time-pads, with the added bonus that you can also create forged messages that will pass the authenticity check of GCM, as @SEJPM points out in the comments).

You only need to add Additional Authenticated Data (AAD) if you have additional data you want to verify. An example would be to add the filename of the encrypted file as AAD if you want to be sure that the file cannot be renamed and still be decrypted. But this is highly situational, and you definitely don't need to use it.


The term "truncated polynomials" shouldn't really be used in relation to NTRU. A truncated polynomial is, strictly speaking, a polynomial with terms of order N or more discarded. NTRU instead uses polynomials mod $X^N-1$. So, for example, if $N=3$, then $x^2+1 * x^2+1$ = $x^4+2x^2+1$. Truncated this is simply $2x^2+1$. Reduced mod $X^3-1$, it's $2x^2 + x + 1$.


There's no practical limit to password or salt length you can use with PBKDF2.

Theoretical limit, however, is determined by the hash function used by PBKDF2: under the hood, it uses $HMAC(Password, Salt || Counter)$, which in turn will translates to a series of hash function calls:

$K_0 = H(Password)$ (assuming password is longer than hash block)
$HMAC = H((K_0 \oplus opad) || H((K_0 \oplus ipad) || Salt))$

If we assume a very long password and/or salt, then two hash function calls can potentially "overflow": $H(Password)$ and $H((K_0 \oplus ipad) || Salt)$. To avoid such "overflow" $Password$ must be smaller than maximum input size supported by the hash function, and $Salt$ must be shorter than maximum input length minus block size of the function.

TO give some perspective and show why this doesn't really matters in real world, maximum input length for e.g. SHA-1 is $2^{64}-1$ bits or $2^{61}-1$ bytes. Block size of SHA-1 is 64 bytes, so maximum $Salt$ size will be $2^{61}-65$ bytes.


What is the viability of a hybrid vigenere cipher?

You could obscure the frequency using a block-cipher or stream-cipher or use a code-book substitution, then maybe use Vigenere Cipher on it, but if you really want your scheme to be secure, then your underlying substitution must be secure enough. In that case using secure block or steam encryption itself is enough. The second level Vigenere encryption is just a burden, and also a possible backdoor (might lead to lazy people reusing keys, leading to vulnerabilities).

Besides, frequency analysis is its major weakness, but not its only weakness.

Pretending your underlying substitution is weak:

Consider Kasiski examination: If you use a code-book substitution for randomisation (not ideal) or a block-cipher in ECB-mode (which you mustn't) then use a Vigenere key as big as the block, then it is easily vulnerable to this attack. It is still vulnerable if you use a key of a different length. The next step is to break the substitution.

Now consider Key Elimination: Just XOR two consecutive blocks of Vigenere key size, the you get the XOR of the two blocks of plaintext. Now you could break it by finding patterns to guess two possible plaintexts from the first level substitution. It is actually easy if you use something weak.

Pretending your underlying substitution is secure:

If you use a stream cipher, then it is the same as combining the Vigenere key with the pseudorandom keystream, which is not only useless, but could lead to pattern finding as the repetition of the Vigenere key pattern in the PRNG keystream.

Otherwise, just stick to something secure. It would be better, more secure and efficient if you use a stream-cipher with PRNGs like AES-CTR, which is blazing fast and secure.

When could you actually make it secure:

Use the Vigenere Cipher only, but as One-Time-Pad.
Use Vigenere Cipher for a Key Whitening process, where you will have to re-substitute with some block algorithm.


Do I need to use a MAC with asymmetric encryption?

Yes, (asymmetric) encrypt-then-sign would provide the same properties as (symmetric) encrypt-then-mac. It would provide integrity and authenticity of the ciphertext.

It is however possible for another person to re-sign the encrypted message if encrypt-then-sign is used. This is a problem when other parties are trusted within the same network. Note as well that it won't necessarily provide integrity and authenticity of the plaintext if another party creates the ciphertext. For this reason sign-then-encrypt is often used instead of encrypt-then-sign.

As the use cases for symmetric and asymmetric encryption would be different there are differences on how to implement encrypt-then-sign. The most important difference is of course that although the session keys are kept by both parties in the case of symmetric encryption. With asymmetric encryption the private key for signing is normally different than the one used for decryption (if more than one party is involved). The private key(s) of a party would be used for signature generation and decryption and the public keys would be used for signature verification and decryption. So you'd have a pretty different key management scheme.

Attacks on symmetric block modes of operations such as padding oracle attacks don't translate directly to attacks on asymmetric primitives. But often the same kind of issues can be found. There is, for instance, a padding oracle attack on PKCS#1 v1.5 encoding for encryption (Bleichenbacher attack). So although not identical, the same kind of issues can creep up.

With asymmetric encryption a hybrid cryptosystem is normally defined. You could use e.g. RSA OAEP and an authenticated symmetric cipher together to maintain confidentiality and integrity. In that case a signature may not be required to maintain integrity and confidentiality. You'd still need a signature of course for authenticity. This construction could be used for sign-then-encrypt (as noted in the second section of this answer).

Beware that using PKCS#1 v1.5 padding and / or CBC mode of operation can be vulnerable to plaintext & padding oracle attacks, so you don't want to use those algorithms for sign-then-encrypt unless you're certain that those kind of attacks are infeasible (which they generally are when using in place encryption / decryption such as file encryption).

  However, assuming that Bob also knows the public key of Alice, Alice could simply sign the data being sent using an appropriate asymmetric signature algorithm. To me, this seems equivalent to using a MAC. Is my understanding correct?

It is. Bob doesn't just need to know the public key though, he needs to trust the public key. But this assumes that you only accept signatures generated by one private key.

  Furthermore, do the vulnerabilities that require MACs with symmetric cryptography even affect asymmetric cryptography?

Yes, they may. But this statement is too broad to be answered with a yes or no. There are certainly different attacks possible on symmetric and asymmetric primitives (that don't easily translate from one system to the other).


Different keys for clients but 1 key on server

Simple solution (with symmetric encryption):

Assign each device an ID (probably already present)
Store a master key on the server
Use a KDF on the master key and the device ID to generate the key for the device. Then you only need the device ID on the device, and the server can re-create that key as required with the master key and the device ID. Of course the device ID has to be transmitting at the connection phase.
If you want to change keys for the devices, you will also need some random input to the KDF, which also has to be stored for each device ID.

That way each device has its own key, and the server can reconstruct all keys just from his one master key. However, this way the devices have no shared keys and cannot communicate with each other. For that you would either need some sort of public key infrastructure, or you could apply an IBE scheme to your devices, where the server holds the master key. However, public key encryption is quite a bit less efficient than symmetric encryption and hashing, so that you have to check the limitations of your devices.


How can I generate a good password from a SHA512 hash?

So your idea is to effectively turn the password authentication into a key-based authentication by deriving the machine passwords from a single random key stored elsewhere. Assuming key storage is secure (probably encrypted with a strong password), this is sound.

It would be better to just use the asymmetric key-based authentication built into most remote access tools (like ssh), so that you don't mess up anything by rolling your own crypto. But if you need to use password authentication, your idea is not insecure either.

Actually generating the password / passphrase from a SHA-512 hash (or any seed material), it's a fairly mechanical process:

Choose the alphabet (or dictionary). For passwords you might use hex or base64, for passphrases any conveniently sized dictionary will do.
Choose the bit-strength. 128 bits is sufficient, but may result in quite long passwords. OTOH, there's no use making it longer than input entropy.
Consume the input bits to generate characters/words until you have a sufficiently long password. With a hashed input like SHA-512 you can just use the first bits from either end, with a non-mixed seed you should probably hash it first (with a strong password hash if entropy is low).


You could try Ajtai's hash function:

What is Ajtai's hash function?
Given a matrix $A \hookleftarrow U(\mathbb{Z}_q^{n \times m})$ and a column vector $\vec{m} \in \mathbb{Z}_d^m$, the hash of the message $\vec{m}$ is given by
$H(\vec{m}) = A\vec{m} \mod q$

If you're not comfortable with linear algebra (and perhaps lattices too) it might be more challenging to implement than something like SHA256.
As for the efficiency, that depends on your definition of "efficient". I doubt it will compete with something like SHA256/SHA512/BLAKE2 for speed; But to be fair, few algorithms will beat BLAKE2.
Note
You will need to take extra care to ensure that the implementation functions in constant time. With bitwise operations, this is significantly easier to accomplish, which is one motivation to use them.


What is Deterministic Authenticated Encryption?

Deterministic authenticated encryption indeed provides authenticity and it doesn't require a nonce or IV. In that sense it doesn't provide CPA security as identical messages would result in identical ciphertext.

Authentication however doesn't really have to do with CPA security. It is about ensuring that the ciphertext was created by a specific party holding the secret key. In other words it provides authenticity of the ciphertext (and therefore plaintext). Furthermore it ensures that the integrity of the plaintext after decryption (and possibly the ciphertext before decryption) is maintained; i.e. that the ciphertext wasn't altered by an attacker or damaged somehow. If not the verification of the authentication tag will fail.

DAE differs with ECB in the sense that ECB doesn't provide authenticity or integrity of the ciphertext (if multiple blocks of plaintext are encrypted anyway). Furthermore ECB mode leaks information if identical plaintext blocks are encrypted. SIV mode on the other hand calculates an IV using the entire input. Even if just a single bit of plaintext is different the entire ciphertext will be indistinguishable from ciphertexts created from previous plaintexts.

This matters if you for instance wrap a large set of keys that do not encode to fully randomized blocks of data. Take for instance an RSA private CRT key, which consists of many numbers. Usually these are encoded, including the public modulus. It could well be that the same block contains only one byte of a private value. If you have many of those blocks then you will find duplicates, leaking information about the RSA private key. Horrible practices such as wrapping RSA keys using only ECB or CBC (using a zero-valued IV) are pretty wide spread.


How to implement 1-out-of-n OT from 1-out-of-2 OT?

Approach 1

The simplest way of doing this is for the receiver, with choice $j \in \{1,\dots,n\}$, to input $1$ in the $j$-th 1-out-of-2 OT and $0$ elsewhere. The sender, with input $(x_1, \dots, x_n)$, inputs $(0,x_i)$ in the $i$-th OT.

Approach 2

An alternative protocol (that just came out of a discussion with a colleague, and seems to be actively secure) is for the sender to sample $n$ random strings $r_1,\dots,r_n$. Now run $n$ 1-out-of-2 OTs where the sender inputs:

$$
\begin{aligned}
(r_1, \,& x_1) \\
(r_2, \,& r_1 \oplus x_2) \\
(r_3, \,& r_1 \oplus r_2 \oplus x_3) \\
&\vdots \\
(r_n, \,& r_1 \oplus r_2 \oplus r_3 \oplus \dots \oplus r_{n-1} \oplus x_n) \\
\end{aligned}
$$

Now, it should be easy to see how the receiver gets the right choice. The advantage here is that a cheating receiver cannot easily learn any other choices, as each $x_i$ is masked by a fresh random value.

(Caveat: I've only thought very briefly about this and am not 100% sure about its active security)

Approach 3 (using $\log n$ OTs)

Naor and Pinkas gave a protocol using just $\log_2 n$ 1-out-of-2 OTs on $k$-bit strings (for security parameter $k$).
The sender inputs $\log{n}$ random pairs of strings to the 1-out-of-2 OTs, and the receiver inputs their choice represented as $\log n$ bits.

Now for each $i \in \{1,\dots,n\}$, let $b_1^i b_2^i \cdots b_{\log n}^i$ denote the bits of $i$. The $i$-th sender's string is defined as

$$x_i = H(s^1_{b_1^i}\|\cdots\|s^{\log n}_{b_{\log n^i}})$$

where $s^j_0,s^j_1$ are the random strings used in the $j$-th 1-out-of-2 OT.
This gets a 1-out-of-$n$ OT on random strings, which can be easily converted to chosen strings by sending the XOR.

(Note that the Naor-Pinkas protocol used a PRF, but if $H$ is modelled as a random oracle then this works too)


Is F_k_1(x) \xor F_k_2(x) a pseudorandom function?

The simplest way to show something like this would be to take advantage of the triangle inequality with a hybrid argument:
$$
\Delta(A, B) \le \Delta(A, C) + \Delta(C, B)\,,
$$
where $C$ is some intermediate construction.

In this case, you begin with $F_{k_1}(x) \oplus F_{k_2}(x)$, where $k_1$ and $k_2$ are sampled independently and uniformly at random. We can replace $F_{k_1}$ by a truly random function $f_1$, and now we have
$$
f_1(x) \oplus F_{k_2}\,,
$$
and the distance from the original construction is the distance from $F_{k_1}$ to $f_1$ which is, by definition, $\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1}}(D_1)$ for some distinguisher $D_1$ that makes $q$ queries to $F_{k_1}$ and has runtime $t$.

Doing the same for $F_{k_2}$, we have
$$
f_1(x) \oplus f_2(x)\,
$$
adding the distance $\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_2}}(D_2)$ similarly as before. Since the xor of two uniformly random strings is just as uniform as a single one, we can move to the random function
$$
f_3(x)\,,
$$
without any degradation in advantage. The total advantage is the sum of all these steps:
$$
\mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1,k_2}}(D) \le \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_1}}(D_1) + \mathrm{Adv}^{\mathrm{PRF}}_{F_{k_2}}(D_2) + 0\,.
$$


Diffie–Hellman key exchange, why it's hard to break it?

The straight-forward method you outlined doesn't work, because $G^a$ is not monotonic in $a$; we can have $G^{r_a} < G^a$ even though $r_a > a$.  This happens because we're working modulo $n$, rather than doing exponentiation in the real numbers or integers.

For example, if we have $n=101$ and $G=2$ (for a toy example), then we have:

$$G^8 = 54 > G^{10} = 14$$

even though $8 < 10$

In fact, a practical method for doing probabilistic [1] evaluation of whether $a < b$ given $G^a \bmod n, G^b \bmod n$ (for the values of $n$ we actually use in cryptography) would be of great interest (and would essentially break all crypto based on modular exponentation)

[1] By probabilistic evaluation, I mean that the method doesn't have to give us the correct answer in all cases; it would be sufficient if it was correct with some probability somewhat more than 0.5


With byte aligned data, bit padding allows the padding oracle attack. Every message has to end in a 0x80 byte followed by any number of zero bytes. You can iterate one byte at a time just like with many other byte paddings.

If you allowed plaintexts that are not a full number of bytes long, the attack wouldn't be possible. (Every plaintext that didn't end in a full block of zeros would decode, so no attack.) However, most real world encryption uses byte aligned data.


Why $f(x)=x^e$ is a bijection i.f.f $e\in{\mathbf{Z^*_{\phi(N)}}}$?

The correct form is:
The integer $a \mod Z_n$ has multiplicative inverse iff $gcd(n,a)=1$

Here, you are working on exponents, so you must consider the modulo as $\phi(n)$ not $n$.

Therefore, here you can find the inverse of $e$ iff $gcd(e, \phi(e))=1$. This guarantees that you be able to find the inverse of $e$ using extended Euclidean algorithm.


Can an Enigma-style cipher of sufficient complexity be considered secure today?

Yes, if you are willing to throw enough resources at it. Only the most fatally flawed schemes cannot be rescued (in practical terms) given enough additional computation. Since you are even willing to enhance the rotor complexity, you could actually use it to implement a modern algorithm exactly. The ability for a rotor to advance "forward a different number each time" makes it sound like quite a programmable architecture.

But why would you want to? (other than it being a cool project of course) What you would end up with would certainly be many times less efficient than a modern cipher running on modern hardware. Additionally, an attacker who was able to develop custom hardware (FPGAs or ASICs) would likely have access to a far more efficient implementation than the defender.


Can this key revocation scheme using hierarchical deterministic keys work?

One problem I can foresee with such a scheme is that when you know a parent extended public key and any non-hardened private key descending from it, you can easily compute the parent extended private key.

This is true because non-hardened public keys are of the form :

  I = HMAC-SHA512(Key = cpar, Data = serP(point(kpar)) || ser32(i))
  then you split I into two 32-byte sequences, IL and IR
  and the child key ki is: parse256(IL) + kpar (mod n)
  the chain code ci is IR, which is part of the extended public key
  and finally you can compute the child public key either by computing point(parse256(IL)) + Kpar
  or by computing point(ki), both are equivalent

So, as you can see, the child private key is the parent private key plus 256 bits of the computed HMAC-SHA512 using the chaincode of the parent private key (which is not a secret) as the HMAC key and, importantly, hashing the public key that corresponds to the extended parent private key along with the child key index.

This basically means that an attacker stealing a non-hardened private key (which you would then like to revoke using the parent private key to authenticate with the registry) could see the extended public key you used to authenticate with the registry if this is public, and from there derive the parent private key you've used to authenticate with the server.

Now, the attacker and the registry both can derive the child public key from the extended parent public key using:

  I = HMAC-SHA512(Key = cpar, Data = serP(Kpar) || ser32(i))
  then split I into two 32-byte sequences, IL and IR
  The child key Ki is point(parse256(IL)) + Kpar, just like above.

But that also means that the attacker can compute the index value "parse256(IL)" and subtract it to the child non-hardened private key (which she stole) to recover the parent private key:

  kpar = ki - parse256(IL) (mod n)

thus effectively allowing the attacker to revoke herself all other child keys derived from that parent key on the registry.

A way around it might be to say that when you register on the registry, for each child key, you register a different parent public key (which would be a hardened key), and that this key can then be used to revoke that child key, but only that child key...

I'm not convinced this eases the pain compared to having a certificate to sign your keys and allowing you to revoke them à la PGP, but with this method at least you're using only HD keys, as you seem to want.

So, in the end, this could work from what I can tell, as long as you take care to handle this caveat correctly.


Does a trace of SSL packets provide a proof of data authenticity?

To complete what @CodesInChaos explains:

If the server has a RSA key in a certificate which is suitable for encryption, then anybody can forge a completely fake conversation without the server being involved at all. In the SSL/TLS protocol, when using a "RSA" cipher suite, the client generates the random "pre-master secret" which it then encrypts with the server's public key; the server merely decrypts it. The attacker then just has to play the roles of both client and server, and speak with himself. In a normal SSL/TLS situation, outsider cannot fathom the SSL connection because they only observe the encrypted pre-master secret; but our envisioned attacker chose the pre-master secret, so he knows it perfectly. The same reasoning applies to the case of a server with a Diffie-Hellman certificate (but who does that anyway ?).
If the server key is not suitable for encryption, but for signatures (e.g. it is a DSA or ECDSA key, or it is a RSA key but the server's certificate contains a Key Usage extension which restricts it to signatures only), then the attacker must "prime" the attack by contacting the server once. With the "DHE" cipher suites, the server generates an ephemeral Diffie-Hellman key pair, signs the public key, and sends it to the client. Once the attacker has a nice signed DH public key from the server, he can use it to build fake SSL connections (as many as he wishes).

The problem is a bit more interesting in the other direction: the server recording a SSL/TLS connection with certificate-based client authentication, and wanting to use it as a proof. The signature computed by the client happens during the initial handshake, and everything which is sent afterwards is encrypted and MACed with the agreed-upon symmetric key, which both client and server know, so the server could fake it at will. However, what the client signs is a hash of all preceding handshake messages, which includes the server's certificate, and also the client random and server random. An interesting point is that the first four bytes of the "client random" are not random at all; they are supposed to encode the current time, with second accuracy.

Therefore, by recording the handshake messages of a SSL connection with certificate-based client authentication, one obtains a proof that the client did connect to a specific server, and even at what time the connection happened (note that the time is relative to how well the client system clock is adjusted; I have encountered personal computers which were off by several years, to the blissful ignorance of their owners). Of course, it says nothing about the data which was exchanged afterwards.

(Whether this "proof" would have any legal value is another, quite distinct subject; I am only talking about the cryptographic half of the problem.)


Montgomery multiplication without final subtraction

Brett just asked & answered this question : Confused about final subtraction of modulus in Montgomery Multiplication, during modular exponentiation

You should increase $R$ exponent by $2$.
If you use $n=1024$ , increase it to be $$n=1024 + 2 = 1026.$$
Recalculate the pre-compute $R'$, based on the new exponent.
$$R' = 2^{(2\cdot 1026)} \bmod(M).$$


The problem with CBC-MAC for variable-length messages is that CBC-MAC applied to a one-block message essentially amounts to an oracle for evaluating the block cipher at values of the adversary's choice. And that oracle allows an adversary to break the scheme.

Consider first CMAC restricted to messages that consist of a whole number of blocks. Then the difference between CMAC and CBC-MAC is that CMAC xors the final block with a secret value - you could call it a tweak - (carefully) derived from the key before applying the block cipher. This ensures that the final block is treated differently from the other blocks, which in turn means that the adversary no longer has an oracle for evaluating the block cipher at values of his choice.

To make CMAC work for messages that do not consist of a whole number of blocks, CMAC (carefully) derives a second secret value. CMAC first pads the message so that it contains a whole number of blocks, then the second secret is xored with the final (padded) block before the block cipher is applied.

This extra complication could be avoided by always padding the message, but by not doing that, CMAC saves a block cipher evaluation for a significant fraction of all possible messages.

The secret values are derived by applying the block cipher to the all-zero block and then shifting the bit values (sometimes xoring bits into the low-order bits to get a finite field multiplication).


Most efficient way to crack a monoalphabetic substitution cipher with spacing intact

Since you know where the word boundaries are, you can use word frequency analysis (either alone or combined with normal letter frequency analysis).

For example, in English text, the most common three-letter word is normally "the".  Identifying it gives you the encryptions of three very common letters, and also some useful hints about the grammatical structure of the plaintext.  Meanwhile, a single-letter word occurring several times in the middle of normal text (i.e. not close to other single letters, not always after the same preceding word) is very likely either "a" or "I", either of which gives you one more common letter.

Also, once you've identified "the", you can look for other short words that begin with the same letters. A four-letter word beginning with "the" is probably "they", "them" or possibly "then". If it begins with "th" but the next letter isn't "e", it's most likely "that" or "than" (and you'll know which, because you know what "t" encrypts to). Once you know what ciphertext letter stands for "a", you can start looking for three-letter words that begin with it, such as "and", "any", "all" and "are". Knowing a few other ciphertext/plaintext letter pairs will let you tell those apart.  ("All" is easy to recognize anyway, because the last two letters are the same.)

Finally, once you've managed to determine the encryptions of a few common plaintext letters, you can start pattern matching longer words containing those letters with a dictionary.  For example, "enQRSTtiUn" (where uppercase letter stand for yet unknown ciphertext letters) is almost certainly "encryption", while "XYtheXYtZQW" (note the repeating ciphertext letters!) most likely stands for "mathematics".

To make this easier,  you may want to write a simple program (in whatever programming language you prefer) that reads a list of possible plaintext words (e.g. from any commonly available English word list) and one or more partially decrypted ciphertext words like above, and prints out all possible matches between them.


OTP Scheme where only one party can generate the OTP, but both parties can verify it's validity

I'm looking for an OTP scheme between two parties where both parties can verify the validity of an OTP, but only one party can generate it.

The obvious way to do this is for one party (Alice) to select the one-time password and send the hash of that password to the other party (Bob).  Then, Bob can verify that Alice has the correct password (as Alice actually sends it), but Bob himself cannot generate it.

If Alice and Bob need to do this $n$ times based on the same exchanged key, then what Alice can do is select the base key, and hash that $n$ times, that is, compute $H^n(\text{base key}) = \underbrace {H(H(H(…H(\text{base key})))))}_{n \text{ times}}$, and send that to Bob.  Then, to authenticate the first time, she would send $H^{n-1}(\text{base key})$, which Bob can verify with his copy of the base key (but could not compute beforehand).  To authenticate the second time, she would send $H^{n-2}(\text{base key})$, and keep on doing this up to $n$ times.