Is hashing a list of hashes safe? I have an arbitrary long list of hashes (e.g. git tree hashes), and I'm wondering by how much I am increasing the risk of hash collisions by condensing them into a single hash, like so:

import hashlib
...
rehash(list_of_hashes):
    return hashlib.sha224("".join(sorted(list_of_hashes))).hexdigest()

My feeling is that it doesn't increase the odds by an amount I need to worry about, but wouldn't mind confirmation by experts.

What you are describing is essentially the same things as a hash list. A hash list is a sequence of hashes over which another hash is calculated. Your scheme does the same thing after sorting. The sorting won't matter for the security of the scheme; it won't increase the chance of collisions.

Hash lists are also used for a well known structure called a Merkle tree, which allows for hashing data in parallel. Aggregating hashes using another hash is also performed in a meriad of protocols, including PKIX protocols (digital certificates, Cryptographic Message Syntax etc.). In those protocols the final hash is usually used within digital signature generation.


Montgomery Algorithm I'm trying to understand how it works and how to implement the algorithm described in
this paper. The paper shows a methods to compute a modular multiplication where it is used multiplier with a resolution smaller than output resolution. For example if I want to do a modular multiplication with 2 1024 bits numbers I can use 16 bits adders.

I've extracted the algorithm for simplicity :

$
S = 0\\
for\ i=0\  to\ (m-1)\ loop\\
\ \ \ \ (C,S^{(0)}) := x_i\cdot Y^{(0)}+S^{(0)}\\
\ \ \ \ if\ S^{(0)}_{0} = 1\ then\\
\ \ \ \ \ \ \ \ (C,S^{(0)}) := (C,S^{(0)}) + M^{(0)}\\
\ \ \ \ \ \ \ \ for\ j = 1\ to\ e-1\ loop\\
\ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} + M^{(j)} + S^{(j)}\\
\ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}_{w-1..1}) \\
\ \ \ \ \ \ \ \ end\ loop\\
\ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\\
\ \ \ \ else\\
\ \ \ \ \ \ \ \ for\ j = 1\ to\ e-1\ loop\\
\ \ \ \ \ \ \ \ \ \ \ \ (C,S^{(j)}) := C+ x_i \cdot Y^{(j)} +  S^{(j)}\\
\ \ \ \ \ \ \ \ \ \ \ \ S^{(j-1)} := (S_0^{(j)},S^{(j-1)}_{w-1..1}) \\
\ \ \ \ \ \ \ \ end\ loop\\
\ \ \ \ \ \ \ \ S^{(e-1)} := (C,S^{(e-1)}_{w-1..1})\\
\ \ \ \ end\ if\\
end\ loop\\
$

where I have :

$\\S$ is the result
$M$ is the module
$Y$ is the multiplicand
$X$ is the multiplier and $x_i$ is the single bit (e.g. $X = (x_n,...,x_1,x_0)$.
The superscript are the words vectors ( e.g. $M = (0,M^{e-1},...,M^1,M^0)$
$(A,B)$ is the concatenation of two bit vector.
$m$ is the operands width
$w$ is the width of chosen words
$e$ is the number of $w$ bits required to complete the vectors ( $e = \lceil(m+1)/w\rceil$

I don't understand what the authors mean with the variable $C$. It should be the carry, but the problem is that I don't understand what carry they are using, Is the carry of the previous addiction ?

P.S.
In the paper it's written that $C$ is in the range $[0,2]$ . Thus, $C$ is represented by 2 bits. The problem is that in the algorithm there is this step :

$S^{e-1} := (C,S^{e-1}_{w-1..1})$

It represents the concatenation of :

$C$ : $2$ bits.
$S^{e-1}_{w-1..1}$ : $w - 1$ bits.

So the concatenation is $w + 1$ bits and it shouldn't be possible. Where is my mistake ?

The confusion comes from the choice of representation. I'd a quick look to the referenced paper, where the autors use a 2-radix representation. Then you shoud initialise $e=\frac{m+15}{w}$ instead of $e=\frac{m+1}{w}$ as you use a 16 bit adder!
The best is to read again the seminal paper of P.L. Montgomery:http://web.itu.edu.tr/~orssi/dersler/cryptography/Montgomery.pdf

ANd this remak explain the additionnal word set to ZERO in the modulus.

The method introduced by Montgomery is clever and require a change or representation as explained in the paper. the method allows also to overlap mul and ReduC process.
I confirm also than C represent the carry which require 2 bits to be holded. The interest compared to the classical method, is that carry propagation is moving from right to left, exactly of the direction of scanning operand. This is the reason why the Mult-ReduC can be overlapped, and which is of great importance in hardware design.


Deterministic RSA blinding I have an implementation of the RSA private key operation in a context where I don't have access to an entropy source. I'd like to add blinding to it (both message and exponent), to make it resist some side channel attacks.

(The subsequent padding operation does have access to an entropy source. It's only the exponentiation operation that can't use an RNG.)

I can run a PRNG inside the RSA private operation if I want. My constraint is that rsa_private has to be deterministic: its operation can only depend on its inputs (message and private key).

Is it sensible to do blinding deterministically, i.e. use a PRNG that is seeded by the message and the key? And if so should it be seeded by message+key or key alone? Or does the blinding need to be unpredictable?

I'm interested in the answer for both CRT and straight $m^d$ implementations.

Alright, let's first agree on a few things:

The rsa_private operation is the operation requiring knowledge of the secret RSA key. This operation is required by one of the following processes:

RSA signature, to ensure authenticity and integrity of a given message in a way publicly verifiable
RSA decryption, to decrypt a message which was sent to you, encrypted with your public key,
more rarely, it might also be used to encrypt a message so that it can be decrypted by anybody knowing your public key. This latest usage is disputable since it provided nothing more than a signature.

In RSA, randomness is required at different stages:

When signing, with RSA-PSS (the provably secure RSA signature scheme), you'll need randomness in the PSS-encoding operation.
When encrypting, with RSA-OAEP (the provably secure RSA encryption scheme), you'll need randomness in the OAEP encoding operation.
When performing blinding on RSA operation, the blind is randomly generated.

Now, you're asking about how you could be generating your randomness without entropy, and you mentioned a PRNG, the key, and $m^d$, so I'll assume you only need randomness for RSA decryption, and to blind it.

Remark that it is not the same kind of properties that one would expect from
a PRNG used in a masking scheme and a PRNG used for keys generation. When you are masking something, the PRNG mainly requires uniform distribution and other such good statistical properties. But it does not necessarily require to be a cryptographically secure PRNG. This is due to the fact that all generated values are supposed to be a secret, so you mostly require a good initial entropy source... Which could contradict your current requirements.

In my opinion, generating your randomness out of (part of) your secret key, plus the message (typically by hashing the concatenation of (part of) your secret key together with the message), is providing you with a seed that an attacker could not possibly guess without knowing your private key, so there is no security risk there.

Furthermore by definition, the private key can be considered as a good entropy source, since its generation requires good entropy and the security of the RSA scheme crucially relies on the randomness used when generating the key pair.

The method of using (part of) the private key is actually already used by EdDSA for example to deterministically generate a secret nonce, whose disclosure would allow for private key material recovery.

Now, you asked:

  And if so should it be seeded by message+key or key alone? Or does the blinding need to be unpredictable?

And as I tried to explain, the private key can be considered as a good entropy source, but this is only a one-time entropy source, so if you simply seed your PRNG using the private key, and there is a way to reset the device so that it would get seeded again with that same private key, then there would be a way to get every new RSA operations to be conducted using the same random values, which actually means that you could not rely on your random values as being nonces, and the same mask would always get generated after $x$ calls to the just seeded PRNG...

One solution against this would have to be sure you can rely on a counter and seed your PRNG with the hash of your private key concatenated with that counter.
Finally, taking even more "pseudo-entropy" by also adding in the message value cannot hurt.

Fixed randomness certainly hurts, but the question is to which extent?

You didn't mentioned why and how you wanted to perform blinding, but let's say you are trying to protect against timings or power analysis (or such side-channel) attacks, and you are using blinding.

Now, it all depends on how you actually do the blinding, if you perform simple blinding by tacking a random $r$ value, computing $r^e\bmod n$ and then decrypting the message $m^e=c$ by doing $(r^ec)^d \bmod n$ and multiplying your result by $r^{-1} \bmod n$, then you really want to take a different $r$ for each computation, even of the same message, since otherwise, you would leak the secret value $d$, since the attacks target recovery of the exponent used.

Now, if you have another way to blind, which also blinds the exponent, it might work, but amongst those, the ones I'm aware of are blindings using the Euler's theorem, doing the same as the previous one, but taking also a random $s$ value and doing:
$(rc)^{d+s\cdot \phi(n)} \bmod n$ instead and multiplying the result by $r^{-1}$, but notice again that if both $r$ and $s$ can be fixed for a given message $m$, then an attack could recover $d+s\cdot \phi(n)$, which would allow him to decrypt anything as well, since $a^{s\cdot \phi(n)}= (a^s)^{\phi(n)}\equiv 1 \bmod n$, by Euler's theorem...
So in the end, you really want to have a different blind for each computation.

Notice that relying on a counter means that if an attacker is able to reset that counter, then the attacker can cause the PRNG to repeat itself, which brought us back to the problem of using fixed blinds... But this might not be a problem for you, depending on the fact whether the attacker is supposed to have access, or not, to the device.

By the way, since you mentioned those, attacks against both common $m^d$ and CRT implementations exist, see most notably:

  P. Kocher: Timing Attacks on Implementations of Diffie-Hellman, RSA,
  DSS and Other Systems. In: N. Koblitz (ed.): Crypto 1996, Springer,
  Lecture Notes in Computer Science 1109, Heidelberg 1996, 104–113.

  W. Schindler: A Timing Attack against RSA with the Chinese Remainder
  Theorem. In: Ç.K. Koç, C. Paar (eds.): Cryptographic Hardware and
  Embedded Systems — CHES 2000, Springer, Lecture Notes in Computer
  Science 1965, Berlin 2000, 110–125.

Finally, let me add a word regarding side-channels such as SPA and DPA: if you are using a vulnerable exponentiation algorithm (e.g. plain square and multiply, see maybe this paper for more info), SPA cannot be prevented using just masking, it depends more on your exponentiation algorithm. Timing attacks and DPA are both working if the attacker is able to gather enough traces which are correlated, so they should be defeated by using masking, as long as you avoid fixed masks.


What is insecure about this simple AES implementation? There are plenty of articles all over the Internet talking about how most people are dangerously bad at crypto, and most people new to the field often fall victim to common pitfalls.

I'm new to crypto, but I've spent hours researching this and I cannot for the life of of me seem to come up with something that could be insecure about the following implementation (barring a bug in the operating system, the programming language, etc.)

What's insecure about this?

Use Case: Storing files in a cloud environment and preventing anyone who gets access to those files from viewing them. I do not care about people knowing how many files I have, or what their sizes are, etc. I only want to protect the contents.

Implementation:

For each file, generate a random AES key and IV.
Encrypt the file using AES-CTR, and rename the file to a randomly generated filename.
Store the encrypted files in cloud environment.
Store a plaintext file locally that has an index of filenames, keys, and IVs.

Now, as long as nobody ever gets a copy of my local plaintext file, can I assume that the data stored in the cloud is secure?

Example Code

require 'openssl'

# Do the following for each file...

infile = "...input filename..."
outfile = "~/Dropbox/randomly_generated_name"

cipher = OpenSSL::Cipher::AES.new(128, :CTR)
cipher.encrypt
key = cipher.random_key
iv = cipher.random_iv

input = File.open(infile, 'rb')
output = File.open(outfile, 'wb')

while !input.eof? do
  chunk = input.read(100000)
  encrypted = cipher.update(chunk)
  output.write(encrypted)
end

input.close
output.close

store_locally_only = {
  infile: infile,
  outfile: outfile,
  key: key,
  iv: iv
}

File.open('~/local_only/private.txt', 'a') do |f|
  f.write(store_locally_only.to_json)
end

Now, clearly if my private.txt became compromised, this would give an attacker access to everything that was in my Dropbox.  But, assuming that this file as appropriately kept private, can I assume that the data that is stored in Dropbox is secure?

To be clear, I don't mean this post to be an "audit" of my simple code above. Rather, I am trying to understand something fundamental about crypto here. A lot of people say that it is "dangerously hard" to implement crypto. But this implementation seems so simple, that I am unable to think of what would compromise the data.

I think it is "dangerously hard" because there are things that might go wrong that you might be unaware of.

Below the list of things (not necessarily valid in your example) that might be the weak spot in the crypto:

is your random function random enough? If not it might be possible to predict the output
re-usage of things that should not be reused - keys, nounce etc.
timing attacks - does your code uses the same amount of time independently on where during the algorithm it fails or succeeds?
is there not side channel attack? - that can be used to determine the plaintext or part of the crypto

and the list is not complete.

I think in general the "bad at crypto" means that people are bad at implementing the algorithms and should not do it.

Use something that's there implemented by smarter people.
If you do it can still be misused (cases with re-using things that should not be reused or using not-random enough random numbers) but at least the implementation should be better and resistant to some attacks.


Reusing a one-time pad? I have an embedded device. It produces larges files (200 MB).
I want the device to encrypt the file before writing to disk, so I gave them all a 16-byte random key.

How can I transform the large file with the small key, with the least amount of CPU?

If I XOR the data with the 16byte key, its almost good enough. But it will show repeated patterns from which you can distract the key (for example if the input is 16 zeroes), but can I make it better without sacrificing on performance?

Use AES-128, the instruction set in most CPU's (AES-NI) speeds up the encryption and does not put to much load on your CPU. I would use CBC but there might be better mode operations for encrypting files. Also don't forget to use a MAC.

Using a one time pad (OTP) is nice but what you're doing is not an OTP it's more a Vigenère cipher. If you were to use OTP the key should be as long as the file which requires you to store a (approximately) 200MB key.

Thanks @CodesInChaos I missed the "I have an embedded device", but than it's not a CPU it's a MCU (most likely) even than, AES is designed to be fast on any platform so i would still give it a try, just see how much it takes i think you'll be surprised as to it's efficiency.

Take a look at the list of validated AES implementations, see if there's something which resembles your embedded device.


Prove that the following private-key encryption scheme is not CPA-secure Consider the following private-key encryption scheme : The shared key is k $\in$ {0,1}n. To encrypt the message m $\in$ {0,1}n, choose random r $\in$ {0,1}n and output $(r, F_r(k)\oplus \overline{m})$, where $F$ is a block cipher and $\overline{m}$ is the bit-wise compliment of m. Is this scheme CPA secure?

What is the importance of bit-wise compliment in this question?

Also, it does seem that the scheme is CPA secure because one is performing a $\oplus$ of a message string and a random string (it would change for every message as we pick a random r for each m)

If you choose $m = (1, \ldots, 1)_n$ then

$$(r, F_r(k) \oplus \overline{m}) = (r, F_r(k) \oplus (0, \ldots, 0)_n) = (r, F_r(k))$$

what reveals $k$.


Distinguishing two sets of pseudorandom values when their keys differ by one Suppose we use a pseudorandom function $PRF$ and a random key $k$ to generate a set of pseudorandom values:

$\forall i, 1\leq i \leq n:  w_i=PRF(k,i)$

Now, consider instead of picking a fresh key, we increment the key by one:$k'=k+1$. Then, we compute a set of pseudorandom values:

$\forall i, 1\leq i \leq n:  q_i=PRF(k',i)$

Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

Question: Are the set of $w_i$ values are computationally indistinguishable from the set of $q_i$ values?

No, that is not guaranteed by standard security notions.

AES for example is considered a secure PRP (and thus PRF up to a bound), but has related-key attacks. Granted, the known attacks have more complex key-dependence between a large number of keys, but still, in theory an otherwise secure PRF may be insecure if you see outputs for such related keys. They are only required to be secure with a randomly chosen key.


What is the ChainOfFools/CurveBall Attack on ECDSA on Windows 10 CryptoAPI What is the ChainOfFools/CurveBall Attack on ECDSA on Windows 10 CryptoAPI (Crypt32.dll)
Could someone provide details?

ChainOfFools (or Microsoft's Chain of Fools) or CurveBall is a vulnerability in Microsoft's X.509 certificate verification affecting certificate chains that use ECDSA at any point, discovery by NSA!1.
From Microsoft site for CVE-2020-0601

An attacker could exploit the vulnerability by using a spoofed code-signing certificate to sign a malicious executable, making it appear the file was from a trusted, legitimate source. The user would have no way of knowing the file was malicious because the digital signature would appear to be from a trusted provider.

From the CERT site

Any software, including third-party non-Microsoft software, that relies on the Windows CertGetCertificateChain() function to determine if an X.509 certificate can be traced to a trusted root CA may incorrectly determine the trustworthiness of a certificate chain.

Therefore, an attacker can create a valid certificate chain so that a malicious code can be trusted.
Details:
TLS often uses ECDSA to authenticate servers and clients. Windows code distribution often uses ECDSA for code-signing. The vulnerability affects certificate checking if ECDSA has been used at any point in the chain (code signed with ECDSA, or website authenticated with ECDSA, or a CA authenticated with ECDSA by a root CA, etc.).
Given an ECDSA signature, one can easily create a new private key that has the same public key matches if domain parameters are controllable.
The trick is simple, let begin with defining a curve over a finite field $\mathbb{F}_p$;
$$E:y^2 = x^3 + ax + b$$
Standards defines the parameters, $(p,a,b,G,n,h)$, where $G$ is the base point, $n$ is the order of $G$ and $h$ is the cofactor. See for example secp256k1.
Since we agree on the standard we all use the same parameters. Then one selects a private $k \in [1..n-1]$ and calculates the public key by scalar multiplication $[k]G$. So, your private key is a number, but, the public key is a point on the curve and protected by the EC discrete log.
The attack point:
What if the programmers/designers of a library forget to check the base point?
Now the attacker can create a new private key that has the same public key with a different base point as follows;
Let the target public key be $P$ with $P=[k]G$ of the private key $k$. Then the attacker chooses random key $k'$ and calculates their malicious base point $G'$ with
$$G' = [1/k']P$$ the $1/k=k^{-1}$ is computable since the inverse exists in the finite field $\mathbb{F}_p$ and can be computed by the extendedGCD.
Now, in the new curve where all parameters are the same as the previous except the base point, the public key is the same as the target key, but the private key is not.
Since we assumed that the library is not checking the base point, the attackers can exploit this vulnerability and spoof the Windows certificate chain and the website or signed code will appear as a legitimate source.

A Sage code can be found in Hacker News by zahllos.
One can test their system on https://curveballtest.com/ (no https!)

1 Or, they don't need anymore!


Construct rainbow table to break DES for a fixed plaintext I'm facing a project where I need to build a rainbow table to break DES for a fixed plaintext.
I've already collected information about Hellman, DP, rainbow table method. Finally, I chose the rainbow table approach. I've read about the topic “Rainbow table for DES with all-zero plaintext”.
Now, my consideration how to choose good parameter to obtain highest success rate.

The notations:

N: search space
m: number of chains
t: chain length
l: number of tables

Stopping matrix is $C = mt/N$. Success rate is $R = 1 - e^{-C\cdot l}$.
By Theorem 6, $C = (-\ln(1- R))/l < 2$.

So… I can calculate $l$ to obtain expected $R$, from $l$ I can derive $C$.
Now I´m wondering: can I simply choose $m$ and $t$ such that $mt/N = C$, or must it be dependent on something else?

Your formulas look somewhat strange to me, are you assuming perfect rainbow tables where you removed all collisions?
If you don't need a very high success rate, building perfect tables is feasible, but as you move up your success rate collisions become a real issue (even with multiple tables and or rainbow tables)
If you are not using perfect tables the math is more complicated.
You can choose m and t any way you like.
Also rainbow tables usually come instead of building multiple (distinguishing point) tables  (though you still can build several). In many cases it is simple and preferable to build one rainbow table.

You can choose m and t anyway you like but normally you choose m to be as big as your memory (or disk) and then choose t to be as high as you need for your success rate, or according to your table building budget.
for non-perfect tables table building is simply m*t, for perfect tables it can be much more (for high success rate).

So for high success rate you either pay a lot in table building throwing out colliding chains. Or you keep all the partially colliding and get an effective coverage of significantly less then m*t.


Deriving 2 shared secrets from one private key and 2 different public keys I have a key pair, say $(d, Q)$. I send my public key $Q$ to 2 different people. I also get their public keys $Q_1$ and $Q_2$. Now I can derive 2 shared secrets, $d*Q_1$ and $d*Q_2$. The 2 other people can also derive  secrets $d_1*Q$ and $d_2*Q$. Assuming all key pairs were generated from the same elliptic curve, is it safe to use both the shared secrets in the same session for 2-way communication?

Yes, you can use a (semi) static key pair for (Elliptic Curve) Diffie-Hellman. If you want to check for sure that you use ECDH correctly take a look at the NIST SP 56A which shows the various way that key agreement can be used. In this case you'd probably look for 6.2.2.2.

Note that you should check the public keys for validity. Furthermore, this describes a key agreement protocol. If the static public key can be trusted by the two other parties then the party holding the static key pair has been authenticated. You may require additional authentication for the other two parties. Finally, you probably want to use a MAC to validate that you've both generated the correct secret keys in your key agreement protocol rather than afterwards. This probably means that you need a KDF to derive the various session keys. You may want to use different keys for each direction of  communication as well.


Classification of attacks against lattices I'm interested about the cryptanalysis side of lattice-based cryptography, and was wondering whether there is a survey paper or something that gives some classification of attacks against lattices, current state-of-the-art in each category, and how they relate to one another. For example, I see on one side there is lattice basis reduction such as LLL and its variants, then there seems to be sieving attacks, enumeration attacks, and some other approaches. How do these approaches relate to one another?

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

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

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

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

While I haven't read the following thesis:

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


AES key equal to IV (CBC mode) Application uses AES in CBC mode with 128 bit key. In this implementation key is always same and is equal to IV.
Can attacker get the key or decrypt data? If he knows:

First and second blocks of plaintexts;
All blocks of ciphertexts.

The software mentioned above is malicious program, it encrypts all office files on user's computer. And I now attempt to help user get his data back. Reverse engineering of this program shows that key is unknown, but is always same and is equal to IV.

In this answer I'm assuming that a key is used to encrypt more than one message.

The first weakness is that CBC with fixed IV leaks if messages share a common prefix.
The second weakness is that it makes a padding oracle attack much more severe. Consider a device that knows the key and decrypts a ciphertext you send to it. While it won't tell you the plaintext, it'll leak if the padding was valid (e.g. via an error message or timing). Such a device acts as padding oracle.

For normal use of CBC with PKCS#7 padding and a known (variable or fixed) IV, such a padding oracle will allow an attacker to recover the message associated with plaintext, but it will not leak the key.

When using a fixed secret IV, it doesn't recover the plaintext of the first message block directly, rather it recovers $m_1 \oplus \mathrm{IV}$. When the attacker has access to several ciphertexts, this behaves like a many-time-pad thanks to the reused IV. Due to the redundancies of natural languages this should allow recovery of the IV given only a few ciphertexts.

If the key is reused as IV this IV recovery attack becomes a key recovery attack.

I don't expect either of these weaknesses to help a ransomware victim, since the first is only a minor leak and the second requires a padding oracle, which you probably won't have.


Properly storing an E-mail Password I'm creating a messaging application that will use an outlook account to send an email. However, I'm unsure about the proper steps to store the e-mail password on the user's computer. Suppose I had the following code:

SmtpClient SmtpServer = new SmtpClient("smtp.example.com");
var mail = new MailMessage();
mail.From = new MailAddress("you@example.com");
mail.To.Add("to@gmail.com");
mail.Subject = "Test Mail - 1";
mail.IsBodyHtml = true;
string htmlBody;
htmlBody = "Write some HTML code here";
mail.Body = htmlBody;
SmtpServer.Port = 587;
SmtpServer.UseDefaultCredentials = false;
SmtpServer.Credentials = new System.Net.NetworkCredential("you@example.com","pass");
SmtpServer.EnableSsl = true;
SmtpServer.Send(mail);

Obviously, I don't want "password" stored as a string inside my application. What would be the ideal/proper solution to storing a password on the user's machine  so I can read it into my application, and pass it to the NetworkCredential constructor?

I've done reading here, and here. The first link suggest storing it in a file or registry, not sure how to store it in a registry. How would I properly store it in a file?

Clarification:
This may have been a bit unclear from the above, but I want to allow some person, for which I set up an Outlook account, to send mails to other persons. So one may interpret this in that way that the created account "belongs" to that person, but I also know the password - for administration purposes and the user may know it.

I'm unsure about the proper steps to store the e-mail password on the user's computer.

There are two ways I would recommend (in tandem if possible).

First, some SMTP servers (like Google) allow you to create an Application Password.  This password has limited access (for instance just for email) and can't be used to change the users password.

Secondly, use .Net's built in capability to encrypt the web.config/app.config.  The nice part here is that the configuration sections can just be read by your application, it doesn't know they are encrypted or not, .Net takes care of it for you.

  This may have been a bit unclear from the above, but I want to allow some person, for which I set up an Outlook account, to send mails to other persons

If the application is sending an email from the computer Outlook is installed on, you may want to consider How to open Outlook new mail window.


TLS 1.3: HKDF-Expand In RFC5869 I found that the function of the HKDF-Expand on the input assumes the parameter $L$ which denotes length of output keying material in octets ($\leq 255*\text{Hash}_{Length}$), and then the $N$ is computed as $\operatorname{ceil}(L/\text{Hash}_\text{Length})$ and $L$ is a multiple of $\text{Hash}_\text{Length}$, i.e. the number of output blocks equals $N\in [1,..,255]$.

But when analyzing the use of this function in TLS 1.3 to form a key schedule, I see that the input of this function for $L$ parameter is Hash.length when calling the Derive-Secret function for each generated key:

DeriveSecret(EarlySecret, "ext binder" | "res binder", "") =
    HKDF-Expand-Label(EarlySecret, "ext binder" | "res binder" | Hash(""), Hash.length ) =
        HKDF-Expand(EarlySecret, "ext binder" | "res binder" | Hash(""), Hash.length)

i.e. $L$ = Hash.length and $N = 1$? And so for each key.

I'm sure that I'm wrong somewhere but I do not understand where.

As commented by Maarten Bodewes, derived secrects are not session keys. In TLS 1.3, a "derived secret" and a label are further fed into the HKDF.Expand function to generate the desired session/traffic key, secret nonce/IV, resumption key, etc. I think such an intermediate HKDF.Expand step makes a better key separation for security purpose, e.g., corrupting a traffic key intuitively leaks no information about a resumption key because they are not generated from the same "derived secret".

Btw, HKDF.Extract essentially converts a high-entropy input (not sampled from a uniform distribution), e.g., a DH result, to a fixed-length pseudorandom key, while HKDF.Expand takes a pseudorandom key and a label to generate a random string (which for example could be either a derived secret or a session key).


Exchanging key material between HSMs of different manufacturers In the future we may be setting up a system to secure a large number of symmetric (device) keys (a few million) by using HSMs. So, the keys themselves will be stored outside the HSM, but they will be stored encrypted by a key that resides in the HSM.
We will setup two such systems with HSMs potentially from different manufacturers.
One requirement is that it must be possible to exchange the keys from one system to the other.
So, is there a secure and standardized way to exchange key material between HSMs of different manufacturers?
If so, which standards are applicable here, and are they commonly implemented by HSM manufacturers?

No, there's no standardized way to exchange key material between HSM (and often not even between HSM of the same manufacturer, although manufacturers may provide a backup/restore or replication capability that works at least within the same model). As far as an HSM is concerned, the world is divided in two: inside and outside. What is outside is not trusted. From the point of view of HSM1, HSM2 is outside and therefore not trusted, so HSM1 won't give up its keys to HSM2.
Assuming that you keep a single copy of the wrapped application keys (plus their identical backups), both HSM need to have the same wrapping key. Either create that key outside the HSM and import it to both, or create that key inside one HSM, export it, and import it into the other HSM. After import, make sure to switch the key attributes to be non-exportable.
Even with a single HSM, you would need to have a copy of the wrapping key outside the HSM for backup purposes. This copy (or more precisely all the backup copies) must of course be stored securely. Depending on your security requirements, this could be a piece of paper stored in a safe, or key shares where several company officers are responsible for securing their own shares and K shares among N are necessary to reconstruct the key. As far as I know, there's no standard way to create these key shares, but one HSM may have this as a proprietary featue.


Using Euler's theorem.. how can I get appropriate x..? The question is this...

  $x^{29}\equiv4\pmod{91}$. Note that $91 = 7*13$. Compute an integer $x$.

Since 91 is not prime number, I know I need to use Euler's theorem, not Fermat's. So I get

  $a^{72} = 1 \bmod{91}$, $a \in Z_{91}^*$

I don't know what to do next...

This is RSA with $p=7, q=13$. First compute $d \equiv 29^{-1} \pmod {\varphi (pq)}$ and then $x \equiv 4^d \pmod{(pq)}$


Difference between MAC(key, msg) and SHA(key || msg) I know that SHA(key || msg) is vulnerable to string concatenation attack. However, what if we specified key bit-length and msg bit-length? For example, key bit-length is 256 bit and msg bit-length is 256 bit. If msg or key bit-length is longer than 256 then we simply don't do anything. In this situation, will there be any differences between SHA(key || msg) and MAC(key, msg)??

With the capacity of SHA-3[1] against length extension, It doesn't need HMAC where the key is used twice to build a secure MAC. Instead one can design with prepending the message with the key. Actually, NIST already standardized this into The KECCAK Message Authentication Code KMAC.

With the fixed key and message size, your scheme can be considered as keyed MAC. There is one drawback in your case, the message length prohibits MAC arbitrary messages.

Also, your scheme has a collision where $\operatorname{SHA}(key_1\mathbin\|message_1)=(key_2\mathbin\| message_2)$[2] i.e. the key is used as the message and message as the key ($key_2 = message_1$ and $key_1 = message_2$).

Stick to standards. With KMAC you can MAC arbitrary lengths and have desired output lengths with the help of the cSHAKE128 (XOF - Extendable Output Functions) and have domain separation and even you request different output sizes for the same input, the output will be different.

[1] One can use Blake2 and Skein, too. Those are also resist to length extension attacks

[2] Here we assume that SHA is not SHA-1 or SHA-0. Also note that the SHA-512/256, SHA-512/224, SHA-384 have resistance to length extension attacks. Those are designedNIST  after SHA3


Determine whether nonlinear boolean function is balanced or not Is there any way to check that a nonlinear boolean function is balanced or not?

I can't think any other way except to check all input variables.

If $$w_H(f)=\#\{x \in \{0,1\}^N:f(x)=1\}$$ denotes the Hamming weight of the truth table of the boolean function $f$ in $N$ variables, the function is balanced if and only if $w_H(f)=2^{N-1}.$

Equivalently, if we define the Walsh-Hadamard transform coefficient of $f$ as
$$
\widehat{f}(a)=\sum_{x\in \{0,1\}^N} (-1)^{f(x)+a\cdot x}, \quad a\in \{0,1\}^N,
$$
then a function $f$ is balanced if and only if $\widehat{f}(0)=0.$

There are some known constructions of nonlinear boolean functions that are balanced, for example you can find some recent constructions in the paper Construction of Balanced Boolean Functions with High Nonlinearity and Good Autocorrelation Properties by Tang, Zhang and Tang, available on the eprint server here.


Does there exist the method of projective coordinates for the computation of scalar multiplication for Koblitz curve? Although the computation for scalar multiplications for Koblitz curve can be efficiently executed by TNAF method, but it still need to compute the multiplicative inverse for each point addition.

Koblitz curves are still (convertible to) elliptic curves with a short Weierstrass equation.

Therefore you can use the standard projective / Jacobian coordinate systems as you'd use for more generic curves, though I think (variants of) Jacobian coordinates tend to perform best. All of these coordinate systems only require a single modular inversion at the end of the scalar multiplication, in an operation often called "rescaling".

If your curve is additionally of the form $y^2=x^3+b$ further optimizations seem to be possible using a special case of Jacobian coordinates.


Which algorithm to use for S/MIME I'm wondering if the algorithm 1.2.840.113549.1.1.1 (rsaEncryption) is still secure to use for S/MIME encryption. I'm afraid that the scheme is vulnerable against attacks against raw/textbook RSA.

I'm considering to change to 1.2.840.113549.1.1.7 (id-RSAES-OAEP) but with no insecurity of 1.2.840.113549.1.1.1 (rsaEncryption), I cannot push the change.

BTW, the ciphertext of the mail messages are also signed with RSASSA-PSS.

Thanks for any links and/or suggestions.

The RSA encryption that you seem to be using is specified in PKCS#1, I've linked to the latest version, 2.2:

rsaEncryption    OBJECT IDENTIFIER ::= { pkcs-1 1 }

where

pkcs-1    OBJECT IDENTIFIER ::= {
    iso(1) member-body(2) us(840) rsadsi(113549) pkcs(1) 1
}

with the description:

  The object identifier rsaEncryption (see Appendix A.1) identifies the
     RSAES-PKCS1-v1_5 encryption scheme.  The parameters field associated
     with this OID in a value of type AlgorithmIdentifier SHALL have a
     value of type NULL.  This is the same as in PKCS #1 v1.5.

So your application is using PKCS#1 v1.5 padding. Attacks on textbook/plain/raw RSA - which you mention in your comment - are therefore not possible.

PKCS#1 is secure for static text, but it may be vulnerable to the Bleichenbacher attack that uses a padding oracle to try and find the message - in this case undoubtedly the secret key that is used to encrypt the actual data.

However, you've indicated that your ciphertext is signed. If we assume that this signature is correctly verified (and you'd be amazed how many times it is not) then this attack is not possible.

Of course, signing the ciphertext also has drawbacks: the encryption is lost for the plaintext message. More importantly, the scheme is not protected against the removal of the signature or the replacement of signatures. So an adversary can try and show that the message is theirs by simply substituting his own signature.

Signature substitution sounds horrible, but it may not be a problem if only signatures are accepted from one or more specific, trusted parties. In that case substituting the signature will simply result in the message being rejected by the receiving party (who hopefully knows what to do when receiving such message).

Conclusion: I would deem the current scheme secure. The fact that RSA PSS is used for signing gives hope that the person creating the scheme knew what she was doing. There seems to be no pressing need to implement OAEP instead.


How the FHE encrypts a k-bit message just with one-bit encryption scheme? I'm reading "Fully Homomorphic Encryption over the Integers"——the first generation of FHE. However, this paper seems to detail a scheme to encrypt each bit in a message. I'm very confused about how to implement homomorphic encryption of the whole k-bits message. More specifically,

if I want to achieve homomorphic addition of ciphertexts, such as encryption(3)+encrpytion(3)=encrpytion(6), just using the one-bit FHE scheme seems insufficient.

My question is there any approach to implement that likes the function of carry bits. Or homomorphic encryption of boolean functions, which is capable of extending one-bit homomorphic arithmetic operations to k-bit homomorphic arithmetic operations.

Any references or answers will be much appreciated!

One-bit FHE schemes, as you call them, are actually sufficient to implement a full adder.

You just have to encrypt each bit of the messages, then use the homomorphic logic gates to execute the circuit that you want.

For instance, if you have 2-bit messages $a = (a_0, a_1)$ and $b = (b_0, b_1)$, just encrypt the four bits, obtaining $c_{a, i}$ and $c_{b, i}$ (for $i = 1, 2$), use the homomorphic logic xor gate to add two bits and logical and gate to obtain the carry, that is, representing XOR by + and AND by $\cdot$, we have

First bit of the result: $r_0 := c_{a,0} + c_{b,0}$ (thus, $r_0 $ encrypts $a_0$ XOR $b_0$)

First carry: $c_0 := c_{a,0} \cdot c_{b,0}$

Then, second bit of the result: $r_1 := c_{a,1} + c_{b,1} + c_0$.

Second carry: $c_1 := (c_{a,1} \cdot c_{b,1}) + (c_{a,1} \cdot c_0) + (c_{b,1} \cdot c_0)$

Third bit of the result: $r_2 := c_1$ (just use the last carry as the most-significant bit)

Therefore, the resulting message is $(r_0, r_1, r_2)$.

You may want to check the TFHE project. They implement several circuits homomorphically (in particular, in the tutorial that link, you can run a circuit that computes the maximum of two values).


How to implement GSW13 using Helib or SEAL? I want to implement the homomorphic encryption scheme proposed in GSW13, and make some changes to it, but seems that there is no library that has already been implemented it. Since this is a homomorphic encryption scheme based on LWE, both Helib and SEAL have implemented some other LWE-based homomorphic encryption algorithms. I want to ask if I can use one of these two libraries to generate the public and private keys in the form required in the GSW13? And would tell me based on these two libraries, how to implement the of GSW13？

A good resource for FHE implementations is found on Micciancio's website. Searching GSW on it points to FHEW/TFHE, although they are quite different than "standard FHE" schemes (they bootstrap after each gate in the circuit). They are implemented though.

Besides those, there are various libraries for lattice crypto (Palisade, Lol, NFLlib, all on the linked webpage) which may be useful to use in any given implementation as a starting point.


Exercise: recognizing Hawaiian plaintext I was given the following exercise to solve:

  The Hawaiian language consists of 12 letters. There are 7 consonants: HKLMNP and W  and there are five vowels: AEIO and U. In a word, no two consecutive letters can be consonants and all words end in a vowel. Suppose you are given, without spaces, a very long list of putative decrypts of a given cipher (where you know the plaintext is Hawaiian). Let’s say you have $2^{50}$ decrypts. The decrypts may only use the 12 letters. How would you analytically recognize the answer? Quantify how efficient your method would be - and how long a text you would require to be able to (probabilistically) differentiate between the correct answer and random “noise” (where you can assume that you don't read or speak Hawaiian)?

I don't know where to begin solving this. Any sense of direction would be great.

Let's assume that the incorrectly decrypted messages look like random sequences of letters.  That assumption might not be exactly correct, but for most modern ciphers it should be pretty close.  In any case, the mention of "random noise" in the assignment suggests that this is indeed the assumption that we're supposed to make.

According to the given rules of Hawaiian morphology, no word may contain two consonants in a row or end in a consonant.  This implies that the correct plaintext can never contain two consonants in a row.

In an incorrect plaintext, the probability of each letter being a consonant is 7 out of 12.  From this, you should be able to calculate (or at least approximate) the probability of two consonants appearing adjacent to each other in the incorrect plaintext as a function of its length.

Given this probability, you can then calculate the probability of all the $2^{50}-1$ incorrect plaintexts having at least one pair of adjacent consonants.  Then pick some reasonably high target probability (say, 0.9999) and calculate the minimum plaintext length needed to meet it.  (Of course, you really should give the full formula for the plaintext length needed to reject all the incorrect plaintexts with a given probability, so that the person reading your answer can choose a higher or lower target probability if they want.)


Hash system to generate same (specified) hash from multiple datasets? I have a hashed value $X$ and need to ensure that any of the data sets $D_1...D_n$ can be concatenated with a correctional value $C_1...C_n$ and passed into a hashing algorithm to result in the value of $X$. What I need is a way to figure out what $C_i$ should be in order to ensure that $Hash(D_i, C_i ) = X$. If I use a simple hash like addition or XOR then it'll be pretty easy, but is there any way to figure out $C_i$ for better hashing algorithms?

No (assuming by “better” you mean “cryptographically strong”). What you are trying to do is finding a pre-image of $X$ under the extra condition that $D_i$ must be a prefix of the pre-image. Cryptographic hash functions are designed to make finding pre-images computationally infeasible.


Why does 0x00 make bcrypt weaker? On the following site:

https://paragonie.com/blog/2015/04/secure-authentication-php-with-long-term-persistence

when talking about the dangers of using bcrypt it states:

  There is a nontrivial chance that one of the raw bytes in the hash
  will be 0x00. The sooner this byte appears in the string, the cost of
  finding a collision becomes exponentially cheaper.

I am not fully understanding what this means and how 0x00 would result in finding a collision sooner than any other hex digit. Can someone explain this more clearly to me. I also do not understand why sending it through base64_encode would make a difference as the password will still be the same and can be decoded with base64_decode.

Also, on this page it states that using base64_encode will get around the 72 character limit of bcrypt. However, if the bcrypt algorithm limits any input to 72 characters why wouldn't it also limit the base64_encoded string to 72 characters?

In many cases, 0x00 is treated as end of string. That is where the problem comes into play. So if I passed password\x00defgreallylongpassword into bcrypt, the password would be terminated after password due to the null byte. That is a very insecure password and can easily be found with a dictionary attack.

No one types null bytes into a password field, however. Where the blog post says this can occur in practice is if you first hash the password, then run it through bcrypt. There is a chance that the hash digest will have a null byte in it, which will cause the bcrypt code to truncate it.

The poster gets around this by suggesting that you base64 encode the hash of the password before feeding that to bcrypt. The base64 encoding will not have null bytes.

This hash then bcrypt construction has been proposed as a way around the 72 character limit of bcrypt. That said, I agree with this answer on our sister site. If you are using bcrypt for values that you expect might be larger than 72 characters, you are probably not using bcrypt for its intended purposes and should rethink what you are doing.


Multiple parties must encrypt and get the same result Hopefully this question is not too simple - I did some research but with encryption I really don't want to make a mistake.

Our scenario is that multiple groups need to encrypt a number and arrive at the same result.

This is because they want to use credit card numbers to search for documents, but we are only willing to store an encrypted version of the number as a search index.

I believe a one way hashing function of some sort would be best, salted somehow.

Would this be secure, given that:

We are storing a masked version of each number too (roughly half the number is visible, i.e. the non-personal details)
An attacker could have an account and therefore know their own plaintext

AES-256 was discussed as it's fairly standard in the banking industry but I don't know if it's appropriate here - we would be unable to use a random salt or initialisation vector.

It may be better to accept the full number as a search term and encrypt server side, but for various reasons I don't believe this will be possible.

Thanks.

Your approach is absolutely not secure.

The problem is mathematical, not technical. The search space is simply too small. There are only a finite possible number of values for an account number, and all an attacker has to do is try them all. If his output matches your stored value, he learns the account number. The technology choice of hashing with SHA-256 or encrypting with AES makes no difference.

Account numbers are 16 digits, so it looks like an attacker has to test $10^{16}$ possible values. To a specially crafted application running on a massively parallel processor like a graphics card, that's no longer a big number. (Machines capable of executing 348 billion hashes per second are now being built by hobbyists.) But account numbers  don't have that much uncertainty. Valid BIN numbers reduce the attackers job by a factor of a hundred thousand.  In your case you said you are keeping half the number visible (masking the other half), so the search space drops to $10^{8}$ possible tests.  I can also use the Luhn check digit to recover an additional hidden digit, meaning I only have to try $10^{7}$ possible numbers.

And I'm just making a guess here, based on the statement that you're revealing "roughly half" the number.  I assume you're revealing the last four digits, because you probably print those on your receipts and don't consider them secret.  And I assume you're revealing the first four digits, because they're the Bank Identification Number (BIN).  But BINs are actually six assigned digits, and given the first four I can probably determine the next two with a fairly high degree of certainty (there are far less than the 999,999 valid BINs suggested by the range).  So knowing 10 digits plus the Luhn algorithm gives me $10^{5}$ uncertain digits.  That's only a hundred thousand attempts, and I can spin through that many tests in a second on my PC without even invoking the graphics card!

The secure approach is to use a service to replace the account number with a non-mathematically-derived value, commonly called a token. Inside the secure service is where you would place the encrypted account number and perform your look-ups. An auto-generated sequence number is fine for this. Instead of giving each group the algorithm to look up an account number on their own, you grant them access to the service.

The service would need to be strongly protected against unauthenticated and unauthorized access, with audit logs tracing whoever is using it. If someone wants to run a million tests, at least you have the chance to detect them.

Also see the PCI Guidelines for advice on handling "multi-use tokens" which is this type of use.


ssh-keygen DH Primality Testing I'm pretty familiar with using ssh-keygen to create groups that go in the /etc/ssh/moduli file for the Diffie-Hellman Group Exchange in openssh.  Reading over the man page, it says "By default, each candidate will be subjected to 100 primality tests. This may be overridden using the -a option."  I'm making an educated guess that the tests being performed are some non-deterministic test for primality (Miller–Rabin?), although the man page doesn't seem to say.  Experimenting with that -a option shows that 4 is the lowest that ssh-keygen will accept as an argument for -a.

what I'm wondering what the chances are of getting a composite number (or a non-safe prime number, or some other problematic situation) with values like 4 or 100 for -a?  Is this on the order of a 1 in 100 risk, or 1 in a million risk?

Thank you.

In ssh-keygen.c of the OpenSSH source code, there is the following call:

        if (prime_test(in, out, rounds == 0 ? 100 : rounds,
            generator_wanted, checkpoint,
            start_lineno, lines_to_process) != 0)

...and a comment for the function prime_test says:

 * perform a Miller-Rabin primality test

Therefore, it does indeed use a Miller-Rabin test. One can show that for composite $n$, at least half of the possible random choices prove the compositeness of $n$ (in fact, there are even stronger bounds), hence the confidence in $n$'s primality after $k$ runs of that test is larger than $1-2^{-k}$. In the particular case $k=100$, the probability is (larger than) roughly $1-2^{-100}=0.999999999999999999999999999999$, which is a lot.


Soft question: What are examples of beautiful proofs in cryptography? These may include any proofs, reductions, constructions, etc. For example, simple solutions to problems which at first sight seem difficult. Elegant construction that hide deep mathematical concepts, but once presented are easy to use.

Anything which you deem elegant and clever.

Proofs with nice graphics are especially welcome.

(preferably ones that can fit reasonably into a StackExchange answer).

Theorem.  The ECB mode of a block cipher is distinguishable under chosen-plaintext attack with laughably high advantage.

Proof.


Implementation of MiMC over Edward curve I'm trying to use MiMC-hash function [1] over Edwards curve, in order acheive an hash function that output a point on Edwards curve.

However, in Section 5.1 ([1]), they state that $gcd(3,p-1)=1$, which is not valid the value $l$ (the order of the base point).

Is there any trick that I can use to achieve that?
(I was thinking about working on smaller field, but I struggle to put the result on the correct point on the elliptic curve).

Thanks.

[1] - https://eprint.iacr.org/2016/492.pdf

Using the MiMC-hash function won't actually give you a hash function that outputs a point on the Edwards curve. The MiMC-hash function is based on a sponge-construction that uses the MiMC-permutation internally and is configurable for any $l$-bit output. It is designed for applications that profit from a low number of multiplications such as multi-party computation, zero-knowledge proof systems or SNARKs.

It seems you just want a hash function that takes an arbitrary input and outputs a point on a specific curve. In that case and depending on your specific requirements you could look the "try-and-increment" method described in section 3.3 here or at the methods described in this work.


Why are elliptic curves over a field of characteristic 2 or 3 insecure? The following is a quotation from my cryptography course:

  Recent results on the discrete logarithm raise big concerns on the security of elliptic curves over a binary field.

What are these results? Also, is characteristic three safe?

There is no known subexponential-cost algorithm for computing discrete logs in elliptic curves over fields of small characteristic—barring standard generic algorithms on groups of smooth order, transfers to $\operatorname{GF}(2^n)$, etc.—but there seems to be exploitable structure that just hasn't been worked out yet.  The most recent survey seems to be from 2015:

  Stephen D. Galbraith and Pierrick Gaudry, ‘Recent progress on the elliptic curve discrete logarithm problem’, IACR Cryptology ePrint Archive: Report 2015/1022, 2015-10-22.

See in particular §10.2, ‘A subexponential algorithm for elliptic curves over $\mathbb F_{2^n}$?’, p. 18.


Is there a cryptographic approach to availability Background

Cryptography can be said to provide the tools used to fulfill the goals of information security.

The three pillars of information security are confidentiality, integrity, and availability.

For confidentiality, we have ciphers. The relevant security models here consider ciphertext-only, known-plaintext, chosen-plaintext, and chosen-ciphertext scenarios (IND-KPA, IND-CPA, IND-CCA, etc). On a finer-grained level, there are attacks such as linear/differential cryptanalysis, and resistance to them.

For integrity, we have MACS and digital signatures. The relevant security models here are UUF-KMA, SUF-KMA, EUF-KMA, UUF-CMA, SUF-CMA, EUF-CMA (see link for full explanation of terms)

The question

Are there analogous security models and goals for availability?

Basic approaches to availability include redundancy in various forms, such backups and distributing content among many machines. A blockchain provides some level of availability from a cryptographic approach.

But is there any approach that defines/proves resistance against a formal consideration of an adversaries powers and goals in the same way that there is for confidentiality and integrity?

Flooding.  Consider a node on the internet in conversation with a peer.  Anyone can send packets to the node, but only the peer knows the secret key to compute authenticators for the packets so that the node will accept them.

The maximum amount of memory on the node that an adversary on the network can waste at any given time is the number of packets in parallel that the node can process times the maximum size of a message that the node is willing to accept.  Design your protocol with small limits on packet sizes and you reduce this denial of service vector.

For example, TLS records are limited to $2^{14}$ bytes, or 16 KB.  However, TLS is layered inside a TCP stream rather than a packet protocol (unless we're talking DTLS, which by the way gave us Heartbleed).  So there's no way for a TLS receiver to drop a packet on the floor—forgery of a TCP segment will kill an entire TLS session.  Same with SSH.  Oops.  Lesson: put crypto at a packet layer, not at a stream layer inside a packet layer.
The amount of bandwidth still available to the peer is the total bandwidth going into the node minus the amount of bandwidth used by the adversary.  There's nothing particularly cryptographic in here, per se—it's just a matter of network or processing capacity.  And remember that a well-designed high-level denial of service flood is indistinguishable from a large number of legitimate users.

Erasure.
Consider an erasure channel: if a sender sends a packet, the recipient receives it with some probability $p$, or the channel eats it with some probability $1 - p$.  An erasure code, such as a Reed–Solomon code, is a method for encoding a message into $n$ packets so that any $k$ of them suffice to recover the message.  This raises the probability of transmission, at the cost of bandwidth in the channel.  But it also sets a lower bound on the number of packets that an adversary must block before they block a whole message—or, alternatively, sets a lower bound on the number of packets that must make it through for a message to go through, namely $k$ of $n$.

For example, Tahoe-LAFS splits files (‘messages’) into Reed–Solomon shares (‘packets’) to store on different servers.  If an adversary like the world's biggest paperclip maximizer (‘capitalism’) decides to erase a storage node, you can still recover your data from the other storage nodes you stored them on.  (Tahoe-LAFS also encrypts each file before erasure-coding it, and authenticates each share so the worst the adversary can do is erase a share—attempts at forgery will be detected and function like erasure.)

Proof-of-work.
In the Bitcoin network, the fraction of processing power that an adversary controls determines the adversary's success probability at double-spending.  Knock off a competitor, and you get a bigger fraction of processing power.  (Of course, someone might notice a double-spend in a fork.  So there may also be a high expected cost to attempting this attack.)

A little more broadly, the study of how much performance can be attained in a network when a certain fraction of nodes are malicious is the study of Byzantine fault tolerance.  Is this ‘cryptography’, per se?  I don't know—ask three Byzantine generals and you'll probably get three different answers.  But it's the formal field of study for questions like this, with goals and adversaries and true love and castle-storming.


Asymmetric format preserving encryption? I would like to encrypt a string asymmetrically.

I would like the ciphertext to be as short as as plaintext. (or shorter)

I've read about format preserving encryption functions - are there asymmetric variants of them?

Yes, in fact there is at least one length-preserving asymmetric encryption scheme. It's deterministic, though, so there are some security tradeoffs that come with it. It's described in the paper "Deterministic and Efficiently Searchable Encryption" by Boldyreva et al. Look for "RSA-DOAEP".


Unconditionally secure block cipher for a finite number of blocks I am wondering if someone can point me toward a block cipher that provides unconditional security for only a bounded number of encryptions.  For example, you can encrypt $h > 1$ length $n>1$ blocks with unconditional proof of security, but encrypting more than $h$ blocks will break the security of the whole system (or perhaps it can continue to remain secure, this matters less).
Does such a block cipher exist, and if so can you point me toward the relevant literature or implementations?  In particular, I am assuming that if the secret key can be represented with $d$ bits, then $hn > d$, so the cipher can encrypt more bits (with unconditional security) than was required for storing the key.

The PEANUT and WALNUT ciphers are an example of this (see also Vaudenay's decorrelation theory for the theory behind these ciphers). The idea is simple: take a provably secure construction, like the Luby-Rackoff scheme, and instantiate it with random functions that are identical to random up to $h$ invocations.
For example, if your block cipher works on $n=128$-bit blocks, it is easy to come up with a $64$-bit random function that is indistinguishable from random up to $h$ evaluations: a random polynomial of degree $h-1$ over $\mathbb{F}_{2^{64}}$. It takes $hn/2$ bits to represent such a polynomial. You cannot do better than this and remain information-theoretically secure.
Since with Luby-Rackoff you need $4$ rounds with an independent random function each, you need $4$ random polynomials as above to obtain a cipher that has an unconditional attack advantage bound
$$
\mathbf{Adv}^{\mathrm{sprp}}_E(q) \le \frac{q^2}{2^{64}} + \frac{q^2}{2^{128}}\,,
$$
provided the number of queries $q$ stays under the maximum $h$. Security completely breaks down after $h+1$ queries.
With some extra complications you can reduce this to a single random degree-$4h$ polynomial and $4$ Luby-Rackoff rounds.


Is there a need to encrypt data when send over https? I was monitoring web traffic from my Android mobile using Man in the middle proxy. I installed certificate signed from my server in my mobile and I could see all applications sending sensitive information like passwords as clear text.

I understand that SSL protocol takes care of establishing secure communication, but that eliminates any need to encrypt data? I could read all passwords sent by any application just by installing my certificate in the mobile.

Is there a need to encrypt data when send over https?

Maybe, but it would not be practical for widespread consumer use.

In order for this extra encryption to be effective against man-in-the-middle attacks, the client and server would already have had to agreed upon a pre shared secret out of band.


Smallest 256-bit security hash-based OTS? What is the smallest hash-based OTS in terms of the sum of the public key and signature which provides 256 bits of security?

I will just assume you mean 256-bit classical security as 256-bit post-quantum would be ridiculous. Then it would most likely be WOTS+ in the multi-target secure version described in this paper. The signature size depends on the value you choose for the Winternitz parameter $w$. For $w=16$ a signature contains 67 hash values (each of which should be 256bits in your case). As public key you can take the hash of all the chain ends (and the public seed) as done in the SPHINCS+ specification. Then your public key is two hashes (512 bit in your case). Key generation in this case costs ~67*16 short hashes and one hash over 67 hash values. Sign and verify for a given message add up to key generation time, i.e., they are both strictly upper bounded by these 67*16 + 1 hashes.

In theory, there is another scheme bei Bleichenbacher and Maurer which is slightly more efficient but according to current knowledge requires collision resistance and hence needs a bigger hash function output length.


Discrete log problem with modulus prime I am a bit confused on the hardness of the discrete logarithm problem. Does it become intractale only when it is mod n, where n is a large composite number  (Like RSA key). What about if it is mod a prime number p? what is the complexity and method for solving it? Can we reduce the problem of integer factorization to discrete log problem and vice versa?

The discrete logarithm problem is usually only considered in prime groups. And there $p-1$ has to have at least one large prime factor.

Composite moduli are usually used for RSA problem (related to factorization), quadratic residuosity or composite residuosity. The hardness of these assumptions depends on the fact that the order of the multiplicative groups are not known (the factorization can be calculated from this order directly).

In general, the discrete logarithm problem could be considered in composite groups, and there you would require the totient $\phi(n)$ to have at least one large prime factor. The reason for this is, that the order of the multiplicative group mod n is $\phi(n)$. In prime order groups this happens to be $p-1$.

The reason for this assumption are algorithms like Pohlig-Hellman and Index Calculus. If the multiplicative group order has only small factors, then the problem becomes much easier.


Schnorr signature using discrete logarithm / problem with python implementation For educational purposes (by purpose with small values for the prime order q), I tried to write a small Python implementation of the Schnorr signature described in the Wikipedia article https://en.wikipedia.org/wiki/Schnorr_signature

I implemented the following in python (Python 3.6)

from hashlib import sha256
from random import randint

def hashThis(r, M):
    hash=sha256();
    hash.update(str(r).encode());
    hash.update(M.encode());
    return int(hash.hexdigest(),16);

## Notation
# generator g
g = 2

# Prime q (for educational purpose I use explicitly a small prime number - for cryptographic purposes this would have to be much larger)
q = 2695139

## Key generation
#Private signing key x
x = 32991
# calculate public verification key y
y = pow(g, x, q)

## Signing
M = "This is the message"
k = randint(1, q - 1)
r = pow(g, k, q)
e = hashThis(r, M) % q # part 1 of signature
s = (k - (x * e)) % q # part 2 of signature

## Verification

rv = (pow(g, s, q) * pow (y, e, q)) % q
ev = hashThis(rv, M) % q

print ("e " + str(e) + " should equal ev " + str(ev))
# e 2241534 should equal ev 2462540

As you can see, e and ev should be equal - however, they are clarly not.

I don't know where the problem lies - do you have any ideas what I am doing wrong

Many thanks in advance

Beware, notice the $s$ is computed modulo $(q-1)$ (due to Fermat's little theorem).
You have to write $s = (k - (x * e)) \mod{ (q-1)}$.


Identify similar contents in encrypted data? Is it possible to compare two ciphertexts (two different encryption algorithms are used to create ciphertexts) to identify redundancy?

Not if the encryption algorithms work. And not even if it's the same encryption algorithm. This is a consequence of one of the properties required for an encryption algorithm to be considered secure: ciphertext indistinguishability under chosen ciphertext attack. If an adversary can send ciphertext 1 for decryption, and from that learns something about ciphertext 2 (such as a similarity in their corresponding plaintext), then this property is violated.


Is the 64-bit blocksize a fatal issue when encrypting TBs of data with Blowfish CBC? Crashplan uses 448-bit Blowfish to encrypt the data you send them. The mode used is CBC, keys are multiple use, and IVs are generated with SecureRandom from JCE. Keys are not derived from the password, but are generated randomly. MACs used are MD5 or SHA1.

The more I do research on Blowfish the more it sounds like the 64-bit block size is totally insufficient for the size of the volumes they will be backing up.

I've read that especially in certain modes (like CTR) it is totally insufficient for large streams of data, and can be distinguished from random data after only gigabytes? However, other stuff I've read seems to indicate this isn't an issue if properly implemented.

Would such an attack not apply to Crashplan's implementation?

With this sort of implementation does the 64-bit block size become an issue other than simply being distinguishable from random data after 'x' GB, or would there be greater issues if one were to encrypt say 10TB of data, such as plaintext leaks?

Keep in mind I'm using Crashplan's third option where I generated my own key which is supposedly never sent to Crashplan's servers and the client encrypts all data before sending to their servers. So I don't think transport is an issue? Correct me if I'm wrong.

Another question deals with the Blowfish weak key reflection attack, and is this something I should be worried about? Is there a relatively easy way to check if I'm using a weak key? Or does this just not apply to my situation?

I can make Crashplan backup to a folder on my PC and it seems to encrypt files the same way it would before sending to Crashplan's cloud. I could try to analyze data encrypted with my key if I actually knew what I was doing, but I don't. So, My final question is how would I begin to start analyzing this data if I wanted to try to crack my own stuff or find weaknesses in their implementation? What tools should I use? I'm interested in crypto and would like to learn more.

[This is a follow-up to a question I asked on Stack Overflow.]

I didn't find anything about the exact way Crashplan encrypts files, only that it uses Blowfish in CBC mode. The block size of Blowfish is 64 bit, so there are $2^{64}$ different input blocks and the same number of output blocks. All in all $147573953$ terabytes of different output data. The problem with this is the birthday attack. Summarized it says that the problems with too much encrypted data (for CBC mode) start at ca. $\sqrt{2^{n}} = 2^{\frac{n}{2}}$ (n denotes the block size in bit). For Blowfish we get approximate 34 gigabyte. You'r mentioned "TBs of data" are much more than this.
The accepted answer from "poncho" to the question "Importance of block size in CBC mode" shows why it is no good idea to encrypt much more than the mentioned limit with a single key. It would be a good idea to change the algorithm to a higher block size variant or change the key after ca. 34 gigabyte or even less.

To analyse the ciphertext of Crashplan you have to know how the program saves the encrypted data. Try to convert the saved file into the original output blocks of Blowfish and then look for equal blocks. As soon as you find two equal blocks you can use the attack in the answer of poncho mentioned earlier. If you know the plaintext block of one of the block (due to some patterns or something else) you can calculate the value of the other block.

How bad is this attack? Well, the attacker has to have good luck with finding equal blocks. The bigger the ciphertext, the higher the probability for equal blocks. After that the attacker has to know some patterns of the plaintext. Many identical or just similar files (like many pictures saved in PNG format) can help the attacker to exploit patterns. And that's only for the hardest attack someone could use, a Ciphertext-only attack (the enemy only knows the ciphertext, but nothing concrete about the plaintext). If the attacker has the ability to save his or her own files in your backup (like a employee maybe could do it) there's no way to prevent him or her from getting special patterns into your plaintext.

There's no publicly known way to break Blowfish. Even if your key is a weak key (or will be hashed into a weak key) it won't harm the encryption in any known way. The mentioned attacks only work for a reduced-round Blowfish.


Affine transformation in AES: Matrix representation I know that the affine transformation of the AES can be represented both as a polynomial evaluation over $\operatorname{GF}(2^8)$ and as a matrix-vector multiplication (see, e.g., p.212 C.4 of The Design of Rijndael for the polynomial representation and p.36 3.9 for the matrix-vector multiplication). I would like to know how this change of representation is done. In other words: given the polynomial representation (or maybe a slightly different polynomial), how can we come up with the matrix-vector representation? Is there some algorithm for this, or is the only way to do it just by "brute-forcing" all possibilites?

In literature there are 2 ways to show the affine transform for a given polynomial, and that depends on the location of the MSB in the input as a polynomial.

The polynomial representation of the full transformation, in the format of the original Rijndael paper, is:

$b(x) = a(x)(x^7 + x^6 + x^5 + x^4 + 1) + (x^7 + x^6 + x^2 + x) ~~mod~~ x^8 + 1$

Where $a(x)$ is the input polynomial, and $(x^7 + x^6 + x^5 + x^4 + 1)$ is the polynomial formula of the affine matrix. $(x^7 + x^6 + x^2 + x)$ is the 'vector' constant.

The original Rijndael paper and Wikipedia use the same representation of the affine transform matrix, so we will start there.

$$
 \begin{bmatrix}
y_0 \\
y_1 \\
y_2 \\
y_3 \\
y_4 \\
y_5 \\
y_6 \\
y_7 \\
 \end{bmatrix}=
 \begin{bmatrix}
1& 0& 0& 0& 1& 1& 1& 1 \\
1& 1& 0& 0& 0& 1& 1& 1 \\
1& 1& 1& 0& 0& 0& 1& 1 \\
1& 1& 1& 1& 0& 0& 0& 1 \\
1& 1& 1& 1& 1& 0& 0& 0 \\
0& 1& 1& 1& 1& 1& 0& 0 \\
0& 0& 1& 1& 1& 1& 1& 0 \\
0& 0& 0& 1& 1& 1& 1& 1 \\
 \end{bmatrix}
 \begin{bmatrix}
x_0 \\
x_1 \\
x_2 \\
x_3 \\
x_4 \\
x_5 \\
x_6 \\
x_7 \\
 \end{bmatrix}+
 \begin{bmatrix}
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
0 \\
 \end{bmatrix}$$

The rightmost column of the matrix top to bottom and the top row right to left is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial, since it is a rotational matrix. The vector constant top to bottom is the representation of the vector constant polynomial. Note $x_0$ is the LSB of the input.

The other representation is from The Design of Rijndael (page 36), to which you posted a link. You can see the matrix is the same, but rotated 180°. You can also see the input and output have their MSB locations flipped. Make note that addition and XOR in the field are the same.

$$
 \begin{bmatrix}
b_7 \\
b_6 \\
b_5 \\
b_4 \\
b_3 \\
b_2 \\
b_1 \\
b_0 \\
 \end{bmatrix}=
 \begin{bmatrix}
1& 1& 1& 1& 1& 0& 0& 0 \\
0& 1& 1& 1& 1& 1& 0& 0 \\
0& 0& 1& 1& 1& 1& 1& 0 \\
0& 0& 0& 1& 1& 1& 1& 1 \\
1& 0& 0& 0& 1& 1& 1& 1 \\
1& 1& 0& 0& 0& 1& 1& 1 \\
1& 1& 1& 0& 0& 0& 1& 1 \\
1& 1& 1& 1& 0& 0& 0& 1 \\
 \end{bmatrix}
 \begin{bmatrix}
a_7 \\
a_6 \\
a_5 \\
a_4 \\
a_3 \\
a_2 \\
a_1 \\
a_0 \\
 \end{bmatrix}+
 \begin{bmatrix}
0 \\
1 \\
1 \\
0 \\
0 \\
0 \\
1 \\
1 \\
 \end{bmatrix}$$

The bottom row of the matrix left to right and the first column bottom to top is the start representation of the affine transform polynomial, the other rows/columns are simply rotations of the polynomial. The vector constant bottom to top is the representation of the vector constant polynomial.


Lattice attacks against Multilinear Maps [CLT13] I am currently studying an article on a construction of Multilinear maps. There are some attacks on the scheme presented by the authors and I got stuck at the one in section 5.1.

I will try to summarize the ideas presented there and ask the questions in the end:

Consider the product of $n$ secret distinct primes $p_i$, publish $x_0 = \prod_{i=1}^n{p_i}$.
Given a set of $\tau$ integers $x_j \in Z_{x_0}$ such that $x_j \text{ mod } p_i = r_{i, j}g_i$ the goal is to recover (some of) the values $\textbf{r}_{i} := (r_{i, j}g_i)_{1\le j \le t}$

The attack works as follows: Compute the orthogonal lattice $L$ spanned by some subset $\textbf{x} = (x_j)_{1 \leq j \leq t}$ with $n \lt t \leq \tau$ and apply LLL algorithm on $L$. This results in a reduced basis $(u_1, \dots, u_t)$.

Now, because all vectors $\textbf{u} \in L$ are perpendicular to $\textbf{x}$, namely $\textbf{u} \cdot \textbf{x} = 0 \text{ mod } x_0$, reducing the expression modulo $p_i$ gives that  $\textbf{u} \cdot \textbf{r}_i = 0 \text{ mod } p_i$. Assuming that the product of norms of vectors $||\textbf u||$ $||\textbf r_i||$ is smaller than $||p_i||$ then that equation can be solved in $\mathbb{Z}$.

What I don't understand is:

The conclusion of authors that the vectors $(\textbf u_1, \dots, \textbf u_{t - n})$ resulted by LLL reduction on $L$ are perpendicular to $\textbf r_i$. If this is true, then computing $\textbf r_i$ can be done by Gaussian Elimination in $\mathbb{Z}$.
How does one get such samples $x_j$, namely encodings of zero on the level zero?

1. Why can't we find the vectors $\mathbf{r}_i$ by Gaussian Elimination?

The problem here is that $\mathbf{r}_i$ are small. You can use Gaussian Elimination to recover vectors orthogonal to $(\mathbf{u}_1, ..., \mathbf{u}_{t-n})$, but the vectors found will not be short vectors.

2. How to get encodings in level-zero?

Actually, one does not get encodings in level-zero. All the encodings are in level-one, i.e. multiplied by $z^{-1}$  (inverse modulo $x_0$).

However, this is irrelevant for the attack because the definition of the orthogonal lattice is:

$$L=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0 \}$$

Thus, considering encodings at level-one means that we have $\mathbf{x} \cdot z^{-1}$ instead of $\mathbf{x}$. Therefore, we are actually constructing the following lattice:

$$L'=\{ \mathbf{u} \in \mathbb{Z}_{x_0}^t : \mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \}$$

But since $\mathbf{u} \cdot \mathbf{x} \cdot z^{-1} = 0 \mod x_0 \Leftrightarrow \mathbf{u} \cdot \mathbf{x} = 0 \mod x_0$, it holds that $L = L'$.

Hence, having $t$ encodings at level-zero or $t$ encodings at level-one is equivalent in this attack.


Reason for squaring and not arbitrary exponentiation in Wesolowski and Pietrzak verifiable delay functions (VDFs) I'm working at understanding the Wesolowski and Pietrzak RSA group based VDFs (verifiable delay functions). These basically work by requiring the prover to do a bunch of repeated squaring within a semiprime group G of unknown order, and then computing a proof that a verifier can check without having to do the time consuming work of repeated squaring mod G. These can be used for proof of work, trustworthy randomness beacons, spam prevention, etc.
I'm curious as to why both rely on computing (g^(2^t) mod G) as the work to be done rather than just computing g to the power of some arbitrary huge exponent mod G. (The huge exponent could be generated by e.g. running a CSPRNG seeded by a known input.) In this case you could compute a proof of exponentiation for g^bignum mod G and supply that to the verifier.
Does the use of repeated squaring rather than some arbitrary exponent have any cryptographic significance? Is it just simpler? Just curious so I can understand why these choices were made.
Also curious about the generator (g). Any reason it needs to be a particular number, or should it just be something like 3? Maybe I didn't catch it but I didn't see that discussed.

Suppose I had an enormous exponent $B$. To compute $g^B\mod G$ (I'll omit "mod $ G$" from now on), I would use a square-and-multiply method: I would compute $g$, $g^2$, $g^4$,\dots, $g^{2^t}$, where $t$ is the bit-length of $B$, then multiply all $g^{2^i}$ for $i=1$ in the binary representation of $B$. Note that this involves, at most, $t$ squarings and $t$ multiplications (I'll assume squaring and multiplication take the same amount of time, which isn't exactly accurate but is good enough for this explanation), so the delay is at most time $2t$ times the time for a single square/multiplication.
However, the exact time is less clear; it will depend on the Hamming weight of G, how we store intermediate values, or whether we keep a running product of all $g^{2^i}$ that we have reached so far, etc. And note that we had to compute $g^{2^t}$ anyway to find $g^B$.
The proof of exponentiation for a big number shouldn't vary that much from the proof of repeated squaring. I'm also not sure the Pietrzak verification method works with arbitrary exponents (probably? but it will need some modification).
So basically, arbitrary large exponents should work, but it will be more complicated than just repeated squaring.
The generator cannot be an arbitrary number because it needs to change for every use. If the same generator were used in two different applications, someone could save all the values of $g^{2^t}$ and just look them up in memory the second time, and thus they would not have the required delay. The time-lock game in Definition 2 says that $g$ is uniformly random; the construction doesn't mention this but I think this is a basic assumption of all VDFs.


A question regarding relevance of vulnerability of MD5 when linking multiple records together I have been studying a Supreme Court case "IMS Health vs Sorrel".
In this case a Friend of Court brief filled by "Electronic Privacy Information Center" states that use of MD5 hash function to link multiple records together is suspect, since MD5 is broken.
I find this argument incorrect, the only use of MD5 (it is unknown whether it is salted or not) is to compute a hash to protect patient identity and not for signing purpose. Thus the usual arguments against use of MD5 do not apply.
Here is the quote from the brief http://epic.org/amicus/sorrell/EPIC_amicus_Sorrell_final.pdf

The first is the deidentification of the patient’s actual identity through a cryptographic technique known as “hashing.”
In ideal circumstances, a record containing the hashed representation of the patient’s actual identity could never be linked to the actual patient. But the cryptographic technique chosen to protect patient privacy in this matter has been suspect for at least 15 years, can now be broken using nothing more than an ordinary desktop computer, and is considered unsuitable for further use by the federal government.
Vlastimil Klima, Finding MD5 Collisions – A Toy For a Notebook (Mar. 5, 2005);9 Chad Dougherty, Vulnerability Note VU#836068: MD5 Vulnerable to Collision Attacks, United States Computer Emergency Readiness Team (Dec. 31, 2008).10 See generally, Wikipedia, “MD5,” (“. . .
it has been shown that MD5 is not collision resistant; as such, MD5 is not suitable for applications like SSL certificates or digital signatures that rely on this property. . . . The security of the MD5 hash function is severely compromised.”)11

If MD5 is used to hash "something like patient name or SSN or some unique personal identifier" in order to "ensure that a multiple prescriptions of the same patient (as identified by the personal identifier) are linked to each other, without revealing the identifier itself", then that solution is technically imperfect, but not for reasons related to weaknesses of MD5 highlighted in the question (there are better arguments in the legal memo itself, and some of the documents that it references).

Fact is, the risk of collisions with MD5 used in this way is negligible as far as the cryptographic community knows, even facing an adversary that deliberately attempts to create collisions. That's because the known weaknesses in MD5 currently only allow to create collisions between two artificially crafted data sets, not among a legitimate and an artificial data set, must less between two legitimate data sets. Thus MD5 collisions are a non-issue in that application, because they won't happen; and more importantly, the real issue is elsewhere.

The real issue (and what the legal memo is mostly about) is to protect the anonymity of patients, and that's something MD5, or any hash, is not designed to do, and does not. Knowing the input of the hash ("Patient name or SSN or some unique personal identifier"), it is possible to compute the output and check it against the hash to determine if a case/file belongs to that patient. Change MD5 to any better hash function like SHA-512, and that problem remains.

One option could be to use a MAC of patient info, with the key held by a trusted authority (in some cases that could be a Smart Card). That makes it impossible for a party with no access to the trusted authority to check if a file matches a patient id, unless she knows a file pertaining to that patient; further, access to the trusted authority can be logged, which is a deterrent against misuse. That's imperfect, and comes with a cost, and new risks (e.g. that patient info could be intercepted in transit to the trusted authority, or in the logs), thus I am not even sure this is preferable. But if we do use a MAC, we should use HMAC-SHA-512 rather than HMAC-MD5 (even though there is no known attack against HMAC-MD5; rationale is the same as for the car engineer, who won't use tires known to explode at high speed, even on a low-speed car when they would be safe, and save a little cost and energy).

Private Information Retrieval aims at solving the kind of issues the medical research community has. It works, but is a significant departure from existing practice. For pharmacies, some (not me) might advocate an intelligent tag that answer yes or no when asked if it is for a given patient, and reset after a number of no.


Dynamic Length Hash Function? Sorry if this is elementary, but is there such a thing as a dynamic length (output) hash function? Something that would be a fast way to calculate hashes and output different lengths of strings for the output.

This may give away some of the length of the message, and could be undesirable for many other reasons, but would possibly avoid collisions?

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

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

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

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

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


Does AES with whitening mode have the following property? This mode is that each time a random number $K$ is generated, you XOR it with plaintext $M$ and then pass the result to AES.

Since AES is a pseudo random permutation, does AES have the following property?

$$AES(M \oplus K) = AES(M) \oplus AES(K)$$

No. The AES permutation is not distributive over the XOR operation.

If it were true, this would violate the basic security construction of AES in the Chosen Plaintext Attack model (which is a good model we like to use when evaluating the security of a PRP): An adversary $A$ queries a black box with his own plaintext, trying to decide if the black box is outputting AES permutation of the input or a random one. Successfully guessing which one (AES or a real random permutation) the black box is performing is victory for $A$. So $A$ could issue a request to the AES encryption blackbox for X, Y, and X $\mathbin{\oplus}$ Y, and get back AES(k, X), AES(k, Y), and AES(k, X $\mathbin{\oplus}$ Y). Then he would check that AES(k, X $\mathbin{\oplus}$ Y) = AES(k, X) $\mathbin{\oplus}$ AES(k, Y). If it did, he would know (with negligible error) that he was working with AES and not a random permutation because a random permutation would certainly not have that property. Thus he would break AES under the CPA model with just 3 chosen messages.


How to convert d into 64bit limbs? Given a d value = -(10240/10241)

How would I convert this into 64 bit limbs?

I have to expand on this because of stackoverflow quality algorithm, I've tried using python to get the integer rep/hex rep, but it's not a whole number, so I'm a bit lost


How does TLS with PQC use key encapsulation? As there don't seem to be any PQC alternatives for Diffie-Hellman (DH / ECDH), DH must have been replaced by key encapsulation using an ephemeral key pair. However, since TLS 1.3 always performs ephmemeral key agreement during the handshake I think that it is not possible to directly replace DHE / ECDHE with key encapsulation.
Which changes have been made in the protocol for adjusting it for Post Quantum Cryptography during the testing phase, e.g. using liboqs? Does this alter the TLS specification significantly?

As there don't seem to be any PQC alternatives for Diffie-Hellman (DH / ECDH), DH must have been replaced by key encapsulation using an ephemeral key pair.

I don't believe that is correct; a postquantum Key Encapsulation Method (KEM) would appear to be the natural replacement for DH/ECDH within TLS.  In the KEM, one side (the client) produces a KEM public key, the other side (the server) produces a response, and they both generate a 'shared secret'; this is what TLS 1.3 needs.
Now, the server can't have a static key (because, unlike DH, the server response depends on the client public key).  On the other hand, TLS 1.3 currently doesn't assume that.
All of the NIST public encryption candidates can work like this; except for the ones that make it problematic by having huge key sizes, they all can fit within the current TLS 1.3 architecture.


How can I solve congruence modulo N? I am trying to solve congruences of the form
$$J_A \cdot a^e\equiv 1 \pmod n$$

where $n=pq$ for $p,q$ prime and $\gcd(e,\varphi(n))=\gcd(J_A,n)=1$

Solve for $a\in \mathbb{Z}$, in terms of $n,J_A$ and $e$.

I am using example from GQ signature scheme from the book Page 451.

Nota Bene: This is not a homework question. I am looking for a way to implement it.

$J_A \cdot a^e \: \equiv \: 1 \:\: \pmod{n} \;\;\;\;\; \iff \;\;\;\;\; a^e \: \equiv \;\; $$\operatorname{modinv}$$(J_A,\hspace{-0.02 in}n) \:\: \pmod{n}$

Since that is the RSA problem, the fastest known way to solve it is to factor $n$ which reveals $\lambda$$(n)$,

and then try $\;\;\; a \: = \: \operatorname{mod}\left(\hspace{-0.03 in}(\operatorname{modinv}(J_A,\hspace{-0.02 in}n))^{\operatorname{modinv}(e,\hspace{.02 in}\lambda(n))},n\hspace{-0.03 in}\right) \:\:\:\:$.


What is the difference between an encryption protocol and an encryption standard? What is the difference between an encryption protocol and an encryption standard?

Am I missing something here? Or are they in fact two different concepts altogether?

A protocol is a standard, in the sense that multiple parties agree to use it (as is required for a communication protocol). However a standard-standard is very widely used and has some kind of official backing. Examples of standard-standards would be Data Encryption Standard, Advanced Encryption Standard, and Internet Protocol.


How can we encrypt a file to be just readable (and not writable) after decryption? Is it possible to encrypt a file (e.g., a text document) such that when a user decrypts it, he/she be able to just read the file and not be able to change the content of the file?

I mean, the result of decryption be a read-only file. I think any modification can be detected using message authentication code. I am looking for a method to prevent the user from modifying the decrypted file.

A "file" is a convenient metaphor for a sequence of bits on a specific file system. Your copy of foo.bar is not the same as my copy of foo.bar, even if they contain the same data. And short of exploiting a bug in my system (illegal in many jurisdictions) there is no way for anyone else to dictate what I do with my copy of files. So in general, no, this is not possible if I have control over the system the file is on. Conversely, if you control the hardware, software and I/O devices of a system you can give me access to look at the contents of the file but not change it in any way.

However, if the goal is to preserve authenticity the solution is readily available: Use a hash-based cryptographic signature and ensure that anyone or anything that reads the resulting file verifies that the signature belongs to the right person.


Digital signature with collision Let's assume a digital signature scheme such that there's a probability of 0.2 for two random messages to have the same signature.

How can I exploit this sheme?

I'm having difficulties in finding an exploit since the messages has to be random.

Formally, a signature scheme is broken, as soon as you can generate a message-signature-pair that you were not given before.

Thus, generating a large bunch of pairs of (random) messages $(m_1,m_2)$, and requesting a signature for one $(m_1)$ of them  and verifying if the signature also verifies the other message is a strategy that will yield you a new message-signature-pair $(m_2,s_1)$ rather sooner than later.

Now if you want to make an impressive demonstration of what the above means, you could just generate a large bunch of end-entity X.509 certificates (only differing by the serial number?) and a large bunch of X.509 intermediate CA certificates. The signer will be the CA which only issues end-entitiy certificate by signing the hash of the certificate. Thus your messages become the hashes of the certificates (which are computationally indistinguishable from random strings) and rather sooner than later you'll get a signature for an EE certificate that also verifies for one of the intermediate CA certificates and thus you have successfully forged a (valid) intermediate CA certificate and can run havok with this one.