How difficult is it to practically detect a forgery in a cryptosystem? If the encryption key that you use doesn't correspond to the decryption key used by the crypto system, it is assumed that it will not be possible to decrypt the message or you'll know that there has been some mischief.
I wanted to know how will one know that the decrypted text is not correct? My point is that whether the decryption was successful or not can be checked by seeing if the either the decrypted text is same as what we expected it to be or follows the syntax of the language in which it was expected. Otherwise you will defintiely get SOME decrypted string. So how does a computer know that the decrypted string was not correct? Is it left to the programmer to check the correctness of the output?

Confidentiality does not imply authenticity.  Many common ciphers are trivially malleable—an attacker that doesn't know the key can nevertheless modify ciphertexts in ways that cause predictable changes to the plaintext.  Authenticated encryption solves this problem.

  I wanted to know how will one know that the decrypted text is not correct? My point is that whether the decryption was successful or not can be checked by seeing if the either the decrypted text is same as what we expected it to be or follows the syntax of the language in which it was expected.

There is no general criterion to be had here.  If the attacker has partial information about the plaintext (e.g., the language or protocol, the application that sends the message, the context in which the message was sent, etc.), they may be able to leverage this to produce an undetectable forgery.

Keep in mind that most encrypted data is not read by humans, but rather processed by computers, or as I like to call them, "error multiplication machines."  Attackers don't have to fool a human, only a computer—a fairly stupid machine that may act in very literal and potentially catastrophic manners when given unanticipated input, and which will happily do the wrong thing over and over and over.


Is reverse NTRU still secure? I'm currently prototyping something with the NTRU encryption scheme but I wish to use it in "reverse" -- distribute private keys so anyone can decrypt, but keep the public keys secret and thus only allow certain entities to create new messages. Is NTRU still secure under such a scheme? It seems from the literature that chosen-ciphertext attacks using decryption oracles (which essentially every entity would have) have had some success in breaking traditional NTRU. In general, does knowledge of the private key give us any information about the public key?

No, this system is not secure. Knowledge of the private key immediately gives enough of the public key that we can immediately encrypt an arbitrary message.

The NTRU decryption key includes a polynomial $f$; the encryption key is essentially $f^{-1}g$, where $g$ is a polynomial with coefficients in the set $(0, p, -p)$.  Anyone with the private key can immediately compute $f^{-1}$; while they won't be able to recover the value $g$ (that's not actually referenced within the private key), what the attacker could do is just pick a legal $g$, and then use that to encrypt any message he wants (as no one else with the decryption key will be able to determine that's not the current $g$ value. It won't be the same key as the legitimate encryptor; however it will be accepted by anyone with the decryption key.  Alternatively, he can just get any known text signed by the correct encryption key; that'll give him enough information to recover the correct $g$.

It sounds like what you want is a signature method; that is, a way where someone with the private key can 'sign' a message, and anyone with the public key can verify that signature (but cannot generate their own signatures).  There are lots of signature methods known; some proposed methods are based on NTRU, but the unbroken ones are fairly new; I'd personally wait for cryptanalytic results against them, but if you have your heart set on an NTRU-based method, you can look at this paper.  That would certainly be more secure than what you're doing now.


How can I protect against the failure of a block or symmetric cipher? Can I protect against the failure of a block or symmetric cipher by chaining different techniques together?  If so what implementation details should I be aware of?

Are some combination of ciphers better or worse than others?

In my case I'm not concerned about the CPU expense, but am more concerned about defending against unintentional programming errors or malicious crypto implementation (in hardware or software).

Unintentional programming errors can be defeated by extensively checking your code against test vectors before releasing it (or better yet, create a self-test routine). Note that this doesn't protect against a malicious attacker circumventing your self-test and inserting his backdoor at runtime, obviously.

Of course, there aren't any test vectors for cipher combos, but you can always create your own by running reference code (presumably, by the cipher designers or some authority like NIST).

As for malicious crypto implementations, there really is no way to know without sifting through the implementation line by line and verifying that nothing that shouldn't be there is, like a socket call to some random IP in a crypto library would probably raise a few eyebrows.

And as for crypto hardware, I think this has come up before a few times - if you can't trust your hardware cryptographic provider, it's game over already. Of course, if you're into that kind of stuff, you could recover the firmware and study it and check it for malicious code, but in general it's more or less a black box that you have to trust.

Your question seems to relate more to the correctness of the implementation (i.e. "getting the right answer") than of how to detect backdoors in crypto code.

  Are some combination of ciphers better or worse than others?

When it comes to ensuring your code doesn't screw up and works fine, it doesn't matter, because of the all-or-nothing property of cryptographic primitives. It doesn't matter if your code screws up a single bit at the beginning, at the end, or at the middle - the result will be garbage in any case (or most of the time - if you are using keystream encryption this may not be true if your key schedule is correct).


Order of target group in bilinear pairing Consider a bilinear pairing $e:G_1×G_2→G_T$, and $p^2q^2$ be the order of $G_1$ and $G_2$, where $p$ and $q$ are prime integers.

Suppose that $g_1$ and $g_2$ are generators of $G_1$ and $G_2$ respectively, and $a$ is a random integer. What is the output of $e(g_1^p, g_2^a)$? Is it equal to $(g_t)^{ap}$?

What is the order of the result? Is it equal to $pq^2$?

I know usually in the pairing cryptography the order of groups is set to a prime integer, but, i just want to know what happens if the order is a composite integer $p^2q^2$.

I find it. The output is $e(g_1^p,g_2^a)=(g_t)^{ap}$. https://eprint.iacr.org/2013/812.pdf


Question about the key in RC4 I am planning to develop a more secure version of the RC4 algorithm. Since I´m not an encryption expert, I´ld like you to help me find answers to the following questions:

Does the value of the key array(T) have to be in this range [0-255]? If the answer is “yes”, could you please explain why?
Why did they use s[t] to generate the key and not the key array which is defined as t array in RC4?

Output = S[(S[i] + S[j]) mod N];

Does the value of the key array(T) have to be in this range [0-255] if yes could you please specify why?

Yes. RC4 operates on bytes. There are 256 possible values for an 8 bit (1 byte) number, that range from 0 to 255. RC4 treats the key as an array of bytes, so every entry in the key array is by definition in the range 0 to 255.

  Why did they use s[t] to generate the key and not the key array which is defined as t array in RC4?

Without seeing the RC4 code you are referring to, it is hard to tell what you mean. $S$ is a keyed permutation (where the key is $T$) of the bytes in the range 0-255. The T array may not contain all bytes since it is generated by the user. So, in order to make it so that the values output as the keystream can be the entire range of byte values, they have to use $S$ instead of $T$.

  I want to develop the RC4 algorithm to be more secure

Bruce Schneier once noted: "Again, I repeat the saying I've heard came from inside the NSA: 'Attacks always get better; they never get worse.'"

The most recent news on an RC4 attack had this to say: "The researchers said the only reliable countermeasure is to stop using RC4 altogether." (emphasis added)

A number of attacks on RC4 have been published in recent years, and, they are only getting better. A lot of folks are removing RC4 completely from older systems.

Important
I want to point something out that I hope you don't skip over. Any sort of system designed these days should be designed in such a way that it is not cipher specific. In other words, if you really want your system to be "more secure", you should design it in such a way that it can theoretically support any cipher. That way, if one cipher gets broken, your system can easily adapt to a new one that isn't broken. If you are willing to share more details about your system, I think we can help you design it in such a way that this is possible. Likely that will mean using existing standards, or only slightly modifying a standard to fit your needs.


Why does the Secure Remote Protocol have resistance of dictionary attack? Assume that Eeve who masquerades as a legitimate host and convinces Carol to
make an authentication attempt. (Carol wants to handshake with Steve – a host)

Thus, Eve can get values $A = g^a, M1 = H(A,B',K')$

For a guessing password $P'$, Eve can calculate the following :

$x' = H(s,P') \rightarrow v' = g^{x'}$ (Eve can get random string $s$ in previous run)
$S' = (A(v')^u )^b = (g^a \times g^{ux'} )^b = g^{(ab +bux')}$
$K' = H(S')$.

If Carol's proof of key and Eve's are matched, the password guessed is correct. Hence, If the correct password of Carol is in Eve's dictionary, Eve can get the password.

I read “Thomas Wu, The Secure Remote Password Protocol”… but that paper tells me SRP is safe against dictionary attack.

What am I missing?

The property of SRP is that:

If the attacker is a passive listener to an exchange between a client and a server, he learns nothing about the shared password
If the attacker is a participant in the exchange with either a client or a server with the password (or modifies the exchange between the client and the server), the attacker learns nothing except for the validity of one password.

What you point out is that, if the attacker mimics the server, he can check on a single guess to the password.  There is a similar attack if the attacker mimics the client; he takes this guess at the password, and runs through the protocol with his guess; if he succeeds, his guess was correct.

Why do we accept such a vulnerability?  It's because it is inevitable given the assumptions.  For any protocol whose sole authentication is based on a shared password, the attacker could always take his guess at the password, and run the protocol with someone with the valid password.  If it succeeds, his guess was right.

Now, why is this vulnerability considered acceptable?  Well, if the attacker's dictionary contained one million entries, then this would require one million exchanges with someone.  This is considerably more costly then being able to do one (or several) exchanges, take the results, and then use a GPU farm (or botnet) to attack it offline.


Why does the EdDSA use a 2b-bit hash function? The EdDSA signature of a message $M$ under key $k$ is created as:

Define $r=H(h_b,....,h_{2b−1},M)\in\{0,1,...,2^{2b}−1\}$.

Define $R=rB$.

Define $S=(r+H(\underline R,\underline A,M)s)\bmod\ell$.

Output $(\underline R,\underline S)$ as signature (where $\underline S$ is the $b$-bit little-endian encoding of $S$).
My question is: why does it use of $2b$-bit hash function? What will happen if we use of $b$-bit hash function in the above equations? The $r$ in 1 has $2b$-bit, but it computes the $R=rB$ in 2 and $S$ in 3 at the $\ell$ module. Note that $\ell$ has $b$-bit. Why don't we use the hash function with $b$-bit output? Is there any security problem with this?

Why does EdDSA use of $2b$-bit hash function?

It insures $r\bmod\ell$ is almost uniformly distributed in $\{0,1,\ldots\ell-1\}$. That's explained at the end of the section on Pseudorandom generation of $r$, which also explains $H$ of $b+61$-bit would be enough for this purpose.

Is there any security problem with this?

Update: I know no I'm told there's is actually a purely cryptographic attack if we reduce $H$ to $b$-bit. It

leaks the private key to lattice or FFT algorithms on relatively small numbers of signatures, with Howgrave–Graham/Smart or Bleichenbacher. The setting is very weak: you just need to get a decently large number of signatures on distinct messages, not even chosen messages, and—bam—the private key falls out. In the Minerva attack, there was a separate side channel giving additional information about the per-signature secrets even if they were uniformly distributed; this enabled the adversary to do rejection sampling to give a nonuniform distribution for the lattice attack.  With b-bit secrets reduced modulo the curve order, the distribution is already nonuniform enough for the lattice attack.

Turns out that a less-than-uniform modulo $\ell$ not only invalidate the security argument, it allows an attack! It also (and more badly) affects ECDSA, and there was precedents as explained earlier in the section on Pseudorandom generation of $r$ of Bernstein's paper.


How can i predict the next number of a long sequence of seemingly random numbers? How can I accurately predict the next random number between 1 and 999, given past results. I have no knowledge of the PRNG or algorithm used.

How can I predict the next number of a long sequence of seemingly random numbers? Can I do it by hand, or should I use some kind of software to help find patterns from long strings of data?

This sounds like a lot of work.

I would break this down into parts.  First, I would try to identify the random number generator being used.  From that, my goal would be to determine the starting seed, which would let me accurately predict future results based on past results.

I'd start with the NIST Random Number Generation statistical tests    In them, they offer 15 statistical tests for a random number generator.  I'd run the sample data through this battery of tests to see if it's actually random or not.  Important: if the tests reveal it is random, that could be evidence that a cryptographically secure random number generator was used to produce them.  I would stop searching as I would consider the problem unsolvable at that point.

I'd then test each of the random number generators that the original source might have used, such as rand(), and see if they reveal a pattern similar to that output of the mystery algorithm.

Once a potential random number generator is identified, I'd turn to published papers to see what kinds of analysis and reversals are known for it.


iOS Data Protection: What is the Input of the LFSR? Every time a file on the data partition is created, Data Protection creates a new 256-bit
  key (the “per-file” key) and gives it to the hardware AES engine, which uses the key to
  encrypt the file as it is written to flash memory using AES CBC mode. The initialization
  vector (IV) is the output of a linear feedback shift register (LFSR) calculated with the
  block offset into the file, encrypted with the SHA-1 hash of the per-file key.

Regarding the iOS-Security whitepaper (excerpt from pg. 8) when a file is written to the data partition a AES-Key is created which is used by the AES engine to encrypt the file using the AES-CBC mode. AES-CBC does need an initialization vector which is the output of a linear feedback shift register.

What is the exact input of the LFSR?
What exactly does "block offset" mean?

Does it work like this:

  encrypt(LFSR(block-offset),SHA-1(perfile-key)) ---> result stored
  inside the files meta data

According to this source, which looked at it in detail, and they also implemented tools to do it, it works as follows (roughly):

Every protected file has a metadata entry that contains its encrypted per-file key, and this per-file key is encrypted with its corresponding class key; the metadata also contains information about the protection class of the file. The metadata field itself is also encrypted, with the EMF-key. The file data itself is encrypted only with the per-file key, and the IV is implicit, i.e. not part of that data (quoting from this followup on iOS 5):

  To compute the IV for a block in a file data fork, the input to the IV
  generator is now the block offset in the file fork (instead of the
  block LBA on iOS 4), and the resulting IV is then encrypted (AES128)
  with the "IV-key" to give the actual IV. The "IV-key" is unique
  per-file and computed using the following formula:

  IV-key = SHA1(filekey)[:16]

This is probably to ensure that if different file-system blocks in a file are identical (maybe blocks of 0) the IV's used for those blocks are entirely different (they used to be just the block LBA on iOS 4 fed through an LSFR). The IV generator (from the block offset) is still the same LSFR though (and its source can be found among the mentioned tools).


Are there any elliptic curve asymmetric encryption algorithms? RSA offers the functionality of encrypting (short messages, or symmetric keys) with a public key, and decrypting with a private key.  However, RSA key generation is extremely expensive, especially for 2048-bit+ keys. Is there an algorithm which employs elliptic curve cryptography,  fast asymmetric encryption, fast key generation, and small keys sizes?

As already mentioned in a previous comment, ECIES (a hybrid encryption scheme) is typically the way to go when implementing
asymmetric encryption on elliptic curves, as it is standardized. It provides chosen ciphertext security (IND-CCA).

But as you are looking for "pure" public key encryption schemes, here we go:

ElGamal can not only be implemented in (prime order $q$ subgroups of) $\mathbb{Z}_p^*$ for prime $p$, but equally
on elliptic curve groups. It provides chosen plaintext security (IND-CPA).

Furthermore, there are various ElGamal-type schemes I want to mention:

Cramer-Shoup is an ElGamal variant that provides IND-CCA security.
If you work in a pairing friendly elliptic curve setting,
it may be the case that in the group in which you are using the encryption scheme the decisional Diffie-Hellman (DDH) problem
is easy. In such a case ElGamal is insecure as it's security relies on the DDH. Here, you can use Linear-encryption, which in contrast to ElGamal relies on the decision linear (DLIN) assumption and stays secure even if the DDH is easy and is also IND-CPA secure.
There is also a IND-CCA secure Cramer-Shoup version of linear encryption (but that's rather of theoretical interest).
Furthermore, recently I encountered another variant of linear encryption, denoted as linear combination encryption (unfortunately, behind a paywall) which provides IND-CPA security and relies on the decision linear combination (DLC) assumption. It can also be used in groups where the DDH may be easy (however, this scheme is rather esoteric and seems to be tailored to the constructed group signature scheme and the proofs respectively).

The most efficient one of these schemes is the standard ElGamal version.


Key generation in Digital Signature Algorithm In DSA, one needs to generate two primes $p$ and $q$ such that $q$ is $256$-bit and $p$ is $3072$-bit and $p-1$ is a multiple of $q$.

Question: How to generate such $p$ and $q$.

Attempt: First, use a random number generator to generate $256$-bit number, say $q$. Then test whether it is a prime. If it is not, generate again until a prime is obtained.

After that, generate a random number $\alpha$ such that $\alpha$ is $(3072-256)=2816$ bits and $\alpha q +1$. Test whether $\alpha q+1$ is prime. If it is not, then generate $\alpha$ again. If yes, then we are done as we have two primes $p$ and $q$ which satisfy the conditions above.

Does the key generation above work?

As the comments are quite spot-on, I shall just reproduce them and say that you should just follow the relevant standard which is FIPS 186-4 appendix A.1, which expands upon your intuition.

  The exact algorithm for generating the primes is specified in the DSS
  NIST FIPS 186-4 [(PDF)]  –
  Henrick Hellström

and

  One issue with the proposed algorithm is that the p generated will
  often be 3071- bit rather than 3072-bit, a stated requirement. Also,
  as pointed by Henrick Hellström, if you want DSA per the U.S.
  Department of Commerce's book, then appendix A.1 [(PDF)] is a
  must; also, following that procedure ensures the parameters are not
  cooked in some way; p and q essentially become
  nothing-up-my-sleeve. – fgrieu


Is an invulnerable code possible (including brute force attack)? If I double encrypted a text with for example AES wouldn't it be invulnerable to bruteforce attacks due to the computer not knowing when it has reached the plain text?

Plain text->1st layer of encryption->2nd layer->output

No, If we assume that the mythical computer can brute force the multiple AES encryptions and there are many ciphertexts available which are encrypted under the same key and their corresponding plaintext are not random.

The brute-force code can keep track of the meaningful plaintexts for each ciphertext and finally can perform an intersection of possible key candidates to find the key.

Yes, If the plaintexts don't contain any meaningful information to distinguish them from random then there will be no possibility. So at least a distinguisher is required.


Why is ciphertext from low entropy plaintext not compressible? This comes following a discussion with a colleague.

My plaintext file plain consists of a about 100,000 lines of "all work and
no play...". It's size is: 2.2 MB.
Compressed it is: 5.4kB
I encrypt the original:

openssl aes-128-cbc -in plain -out plain.ENC

plain.ENC is marginally bigger than the original, which I would expect.
I compress the encrypted copy: gzip plain.ENC. But I observe that the
compressed copy is now marginally larger than plain.ENC.

Assuming the entropy of the original file is on the order of ~1000-10000 bits, why is the corresponding ciphertext incompressable? My intuitive notion of the entropy of a string is the minimal number of bits required to produce that string. If the string is the 3 MB long cipher text, it was generated with a 1000-bit entropy string encrypted with an AES implementation (probably no more than a few thousand bits), as well as a few-hundred bit key. Intuitively, to me, the entropy of the cipher text should be no more than the sum of the entropies of the strings and procedures that generate it.

So, my question is: Is my intuitive notion completely wrong? If we extended the low-entropy file to be orders of magnitude larger, would we begin to observe compressibility in the ciphertext?

Well, your definition of entropy is known as Kolmogorov complexity, and it's not so much that it is incorrect, as it is that it is inapplicable to what gzip does.

For example, the value $\pi$ can also be generated by a short program; however, if you attempt to compress a 2.2Mbyte sample of the binary expansion, you'll also find that gzip will also not be able to compress it.

What we can tell from that is that gzip doesn't actually do a good job of estimating the Kolmogorov complexity.  Now, this is not actually a major criticism of gzip; it is actually impossible to write a program that computes it (!).

Instead of attempting to wrestle with Kolmogorov complexity, what gzip (and every other compression algorithm out there) relies on to compress the data is heuristics. That is, it has a model of redundancies that appear in real plaintexts (such as repeated substrings), and is able to take advantage of those redundancies to shorten the length.  Now, if that model corresponds to the text it is given, gzip can compress quite well; if the model doesn't correspond (and both the encrypted text and the binary expansion of $\pi$ fall in this camp), it can't compress at all.

And, no, encrypting more data would not make the result any more compressible.


Diffie-Hellman in Https: How are prime numbers picked? I am trying to understand https, as I understand https uses the Diffie–Hellman method for keys exchange and then AES for encryption.

But Diffie–Hellman needs two prime numbers, where do these come from?

TLS generally uses the DH groups specified in RFC7919.  The RFC selects the modulii it specifies so that $(p-1)/2$ is also prime (and so the value $g$ is selects generates a large prime subgroup) - those primes have a number of other nice practical properties.

In TLS 1.2, the client could specify its own group, however that is not greatly encouraged (both because the client might get it wrong, and because it makes it difficult for the server to do validity checking).

In TLS 1.3, they removed the option to specify your own group, and so the groups in RFC7919 (or an elliptic curve group or a private group) is your only option.


Measuring entropy for a ciphertext only attack When bruteforcing a password (e.g. the common attacks on DES), where you have ciphertext only, you need a way to assess whether a decrypted plaintext is the right one.  I believe the EFF DES machine does this by checking if the chars are printable.  Of course, this only works for ASCII files, not things like images.

I'd like to measure the entropy (observed 0th order byte level) and see if it's above a threshold that can be attributed to randomness.

Is that a good method?
Is there another well known method?
Where can I find tables that indicate given a randomly generated message of size X, there's p probability that it's entropy would be < ? (These types of tables are used, for instance, in chi-squared testing)

In response to D.W:
I have 5 ciphertexts all of 1 KB and no information about them.  I was able to decrypt one by dictionary attack; it is plaintext ASCII.  I imagine the others are also.  If that were the case, it's easy to automatically distinguish valid decrypts from nonvalid (check that all chars are printable, not < 0x20 or > 0x80).  Of course, the others might not be ASCII files, but until I try, I have no way of knowing.

But, I'm interested in this method in general.  For instance, when looking at a sample output of an unknown cryptosystem, it would be a good way to assess if there are any obvious statistical problems.  Or, when reverse engineering binary applications, and looking at data, and trying to assess if it's binary data or encrypted.  I also find the question mathematically of interest even aside from applications.

Well, from your previous questions, I'm assuming that your writing a utility to brute-force decrypt a password protected file (encrypted with a certain encryption utility), and you're looking for a way to determine whether your trial decryption is plausible.

Normally, when an attacker attempts to decrypt something, he has some idea about what it is (why else is he investing the effort), and even if that guess doesn't give him an entire plaintext block, he partial information about what it is (be it an IP packet or a Word document) will help him recognize it.

Thomas states that the usual assumption is that you do have a full plaintext block; that may be the assumption you make when you're designing a cipher (actually, you assume the attacker has a lot more than that), but that's not always true for all attackers (for example, yourself).

Your suggestion (run a Chi-Squared test on the byte frequencies to see if it is consistent with the bytes being generated randomly (with the idea that decrypting the data with the wrong key will end up with random looking plaintext) isn't a bad idea; whether it is the right idea depends a great deal on whether it will actually pick up the plaintext (without the sensitivity needing to be so high that you are deluged with false hits).  This is a real concern; I suspect that (say) ZIP files have fairly even byte distributions; the Chi-Squared test would be hard pressed to identify those).

Hence, my suggestion would be to rely on a series of tests, each designed to pick up a particular file format (as well as a general purpose test that has a shot at recognizing file formats you didn't anticipate).

Some ideas for these tests might be:

Checking if the MSbits of the bytes are mostly the same.  This will catch anything in a text format (and yes, a Chi-Squared test would also catch it, but you'd need to decrypt a lot more data to run that test)
Check to see if the start of the is consistent with a specific file format (for example, check the magic number that appears in a ZIP file header or a JPEG file header).

Your Chi-Squared based test is a decent general purpose test, which has a good shot at picking up most file formats that aren't heavily compresssed.  If I were doing this, I'd pick a simpler but related characteristic (such as "is there a byte value that occurs more than N times"); I have no good feel as to which would work better in practice.


What are the public key and output sizes for the four remaining PQC KEM candidates? Currently there are only 4 direct candidates left that provide KEM. Generally performance seems to be "OK" for those candidates. However, the key and encapsulated key sizes (i.e. the output size of the algorithm) may require some interesting tweaks in the protocols.
I could not directly find these sizes on the Internet, so are they known (for the different levels of security required by the NIST competition)?
The round 3 candidates are:

Classic McEliece
CRYSTALS-KYBER
NTRU
SABER

I'm only interested in the sizes of the dynamic values in minimum number of bits as well as any encoded sizes - if an encoding has been specified. Domain parameters - assuming that they are static - may be excluded from the calculation.

Throughout this answer the following conventions are used:

CT = Ciphertext or transmitted output of the encapsulation algorithm
PK = Public key or transmitted output of the key generation algorithm
Cat 1 / 3 / 5 = NIST security categories with the following specification:

Any  attack  that  breaks  the  relevant  security  definition  must  require  computational resources comparable to or greater than those required for key search on a block cipher with a 128/192/256-bit key

The following table gives you the tools to calculate the desired sizes from the given parameter sets - wherever I could figure out the relevant formulas from the supporting documentation PDF.

Scheme
PK size
CT size
Additional Notes

Classic McEliece
$mt\lceil k/8\rceil$
$\lceil mt/8\rceil+\lceil\ell/8\rceil$
$k=n-mt,\ell=256$

Kyber
$12kn/8+32$
$d_ukn/8+d_vn/8$

NTRU
$\lceil(n-1)\log_2q/8\rceil$
$\lceil(n-1)\log_2q/8\rceil$

SABER
?
?
Sizes pre-computed

Unfortunately the SABER documentation was rather unclear on how the sizes are computed (it appears they want one to infer them from the sizes of the packed objects). Fortunately the relevant sizes are already precomputed in a table in their paper.
For NTRU there were two models of computation given, for the sake of comparability I have chosen the weaker ("local") model of computation as the other one didn't have a single named parameter set with category 5 security.
The following table uses the above formulas to compute the sizes for the smallest specified parameter sets that satisfy a given security category as assigned in the supporting documentation of the submission.

Scheme
Cat1 CT
Cat1 PK
Cat3 CT
Cat3 PK
Cat5 CT
Cat5 PK

Classic McEliece
128B
261,120B
188B
524,160B
240B
1,044,992B

Kyber
768B
800B
1,088B
1,184B
1,568B
1,568B

NTRU
699B
699B
930B
930B
1,230B
1,230B

SABER
736B
672B
1,088B
992B
1,472B
1,312B


Bad custom encryption I hope you can help me understand the issue. I know creating my own encryption is not a thing which you should do, but I did this simple "encryption" a long time ago and discussed it with my teacher. He said that it is weak and should not be used in production, but he couldn't really explain why (or at least I didn't get it). Maybe one of you will be kind enough to help me.

The fundamental concept is to create an "endless" hash that is used to encrypt the whole plain text. I implemented the algorithm like:

A pre-shared secret and the plaintext are entered by the user
A hash is created from the secret
The plaintext is split into blocks with the size of the length of the hash
Each byte of the 1. block is aggregated to the according to byte of the hash (1. byte of block + 1. byte of hash = 1. byte of encrypted block, 2. byte of block + 2. byte of hash = 2. byte of encrypted block etc)
If there are more blocks to encrypt a new hash is generated from the last encrypted block + the last plain text block. This hash is used for encrypting the next plain text block (like step 4). This process repeats until all blocks are encrypted.
Last but not least all encrypted blocks are merged back again to one

As far as I understand, it should be secure as long as I use a secure hashing algorithm. Please help me understand why I am wrong.

You find a javascript implementation and example HTML page here: https://github.com/EdwardTivrusky/codebook

From the way I understand your question, your encryption scheme works as follows:

For a message consisting of $\ell$ blocks $m=m_1\|\dots\| m_\ell$ and a key $k$ the ciphertext $c=c_1\|\dots\| c_\ell$ is computed as
$c_1:=m_1\oplus H(k)$ and $c_i:=m_i\oplus H(c_{i-1},m_{i-1})$ for $2\le i \le \ell$.

This scheme has several problems. First of all it's deterministic and therefore cannot be CPA secure, the basic minimum we generally require of an encryption
 scheme.

But it gets worse. In any standard definition of security, it is assumed that the attacker can choose, or at least know, parts of the plaintext. In your scheme, if the attacker knows the $n^{\text{th}}$ plaintext block $m_n$, they can compute $H(c_n,m_n)$ and thereby reveal the next plaintext block (and by extension the rest of the message).


Why is a proxy needed in proxy re-encryption? Context

Here's the usual proxy re-encryption scenario:

Alice, with key pair $(pk_a, sk_a)$ encrypts a message $m$, producing $c = encrypt(pk_a, m)$
Alice saves $c$ on an untrusted storge provider (Dropbox, IPFS, etc..)
Bob, with the key pair $(pk_b, sk_b)$ asks Alice to access $c$
Alice generates $re_{a\rightarrow b} = rekey(sk_a, pk_b)$, which she sends to a proxy
That proxy re-encrypts $c$ in $c' = reencrypt(re_{a\rightarrow b}, c)$
Bob can now download $c'$ and obtain the plaintext $m = decrypt(sk_b, c')$

Question

Why do we need a proxy? Can't Bob re-encrypt $c$ into $c'$ by himself?
From what I've understood, the only role of the proxy is to re-encrypt $c$ and nothing more.

In other words: can Bob and the proxy be the same person/device?

Further details

If Alice sends $re_{a\rightarrow b}$ to Bob via e-mail, or by letting it be publicly accessible (i.e. storing it on IPFS), Bob should be able to re-encrypt $c$ into $c'$ by himself, provided he has the right software to do so on his device.

What I'm also interested in is uderstanding whether there are any advantages for the re-encryption step being performed by a proxy and not by the recipient himslef. I can't think of a scenario where Bob may be forced to rely on a proxy.

If Bob has the re-encryption key from Alice, then he can re-encrypt all Alice's ciphertexts stored online and then decrypt these messages. This is not good because Alice may only want to reveal some small subset of messages to Bob but not all. Similar things happen if Alice knows Bob's re-encryption key. Furthermore, the proxy is also not fully trusted, i.e., knowing Alice and Bob's re-encryption keys is not enough for the proxy to decrypt the online ciphertexts either (because it does not know Alice and Bob's private keys). On the other hand, if the proxy and, say, Bob collude, then they can decrypt all Alice's ciphertexts.


What is the security strength of McEliece variants? Please help me understand the security strength of McEliece variants prepared for Round 3.
I looked at the specifications - https://classic.mceliece.org/nist/mceliece-20201010.pdf - it doesn't have the security strength information - normally other algorithms submitted to NIST usually carry that information in the specification that they submit.
ISARA implementation of Classic McEliece - "6960119" variant is 128 bits?  and "8192128" variant 256 bits? Probably based on  https://classic.mceliece.org/nist/mceliece-20190331.pdf (though this specification does not talk about the security strength)
What about the other variants submitted for Round 3? How about the NIST Level for these variants?
https://en.wikipedia.org/wiki/McEliece_cryptosystem says 80 bits of security for some of the variants. The description further says "In its round 3 submissions to the NIST post-quantum standardization the highest level of security, level 5 is given for parameter sets 6688128, 6960119, and 8192128. "
How about the other variants what is their security level?

Further search at this Round 3 Official Comment Newsgroup - found here
https://csrc.nist.gov/CSRC/media/Projects/post-quantum-cryptography/documents/round-3/official-comments/Classic-McEliece-round3-official-comment.pdf
https://groups.google.com/a/list.nist.gov/g/pqc-forum/c/EiwxGnfQgec?pli=1
OP (Kirk Fleming) sets up these estimates

mceliece-3488-064   143
mceliece-4608-096   207
mceliece-6688-128   272
mceliece-6960-119   272
mceliece-8192-128   272

DJ Bernstein (from the submitters - the Classic McEliece team) doesn't appear to be too enthusiastic about those security strength bits.


Are there groups where the computational Diffie Hellman problem is easy but the discrete log problem is hard? I know that there are elliptic curve groups, used in pairing-based cryptography, where the decisional Diffie Hellman problem (ie. given $g$, $g^a$, $g^b$ and $c$, determine if $c = g^{ab}$ is easy but the computational Diffie Hellman problem (given $g$, $g^a$ and $g^b$, find $g^{ab}$) is hard, and I know that if you can solve the discrete log problem (given $g$ and $g^a$ find $a$) you can do both.

But are there groups where you can fairly easily do the Computational Diffie Hellman problem but it's hard to find a discrete log?

There are some known groups in which computational Diffie-Hellman assumption is equivalent to discrete logarithm problem. Besides, It has been shown that the equivalence holds "when a small amount of extra information depending on the group order is provided". Furthermore, those extra informations has been computed for certain elliptic curve groups used in real cryptographic applications. Later the reduction has been tightened.

The whole progress in researches shows that although there is no full proof for the equivalence but there are some evidences which lead to the believe that there might not be any groups in which computational Diffie-Hellman is easy but discrete logarithm problem is hard.


Question About ECC Primitives (GnuPG) In version 2.1, GnuPG featured primitives that use elliptic curves. For encryption, one option was ECDH, which confused me. I thought ECDH was for key agreement, not public key encryption. How does GnuPG utilize a key agreement scheme for enciphering files/messages?

https://tools.ietf.org/html/rfc6637#section-8

  Elliptic Curve Cryptography (ECC) in OpenPGP

  ...

  EC DH Algorithm (ECDH)

  The method is a combination of an ECC Diffie-Hellman method to
  establish a shared secret, a key derivation method to process the
  shared secret into a derived key, and a key wrapping method that uses
  the derived key to protect a session key used to encrypt a message.

  The One-Pass Diffie-Hellman method C(1, 1, ECC CDH) [NIST-SP800-56A]
  MUST be implemented with the following restrictions: the ECC CDH
  primitive employed by this method is modified to always assume the
  cofactor as 1, the KDF specified in Section 7 is used, and the KDF
  parameters specified below are used.

  ...

  The key wrapping method is described in [RFC3394].  KDF produces a
  symmetric key that is used as a key-encryption key (KEK) as specified
  in [RFC3394].  Refer to Section 13 for the details regarding the
  choice of the KEK algorithm, which SHOULD be one of three AES
  algorithms.  Key wrapping and unwrapping is performed with the
  default initial value of [RFC3394].

  ...


How to choose the size of the IV in AES-GCM? In The Galois/Counter Mode of Operation (GCM) by McGrew and Vega (PDF) it's stated that:

  An initialization vector IV , that can have any number of bits between
  $1$ and $2^{64}$. For a fixed value of the key, each IV value must be
  distinct, but need not have equal lengths. 96-bit IV values can be
  processed mor e efficiently, so that length is recommended for
  situations in which efficiency is critical.

But how to choose the IV's size and how - if so - it affects the security of the algorithm?

But how to choose the IV's size and how - if so - it affects the
  security of the algorithm?

You really want to give 96-bit IVs to GCM (pad them if neccessary).

If you pick any IV size but 96-bit, GCM's polynomial hashing function GHASH is invoked to get the IV size down to 128-bit. This means that you basically apply a PRF on your IV, which means that there's a decent chance of hitting a collision if you use about $2^{64}$ IVs which will allow for a key-recovery attack on GCM and allows you to forge ciphertexts (numbers corrected by poncho).

NIST SP800-38D (PDF) has further treatment on the security considerations (especially with regards to IV sizes) in section 8. Furthermore it is the specific recommendation of NIST to use a 96-bit IV (section 5.2.1.1, found by Maarten):

  For IVs, it is recommended that implementation restrict support to the
  length  of 96 bits, to promote interoperability, efficiency, and
  simplicity of design.


security amplification Reading some papers on security amplification of weak-PRP written by Stefano Tessaro, I noticed the use of notion "epsilon-PRP" and the notion of "security amplification". These notions, in conjunction with the statement

  We consequently call a primitive satisfying this assumption an epsilon-PRP: Clearly, AES is much more likely to be a 0.99-PRP, rather than a fully-secure PRP.

from Tesaro-Security Amplification for the Cascade of Arbitrarily Weak PRPs:
Tight Bounds via the Interactive Hardcore Lemma confused me.

Can anybody explain when security of PRP is higher, for epsilon very close to 1? Security amplification of cascade of PRP's occur when resulting epsilon is greater than every epsilon of basic PRP?

As D.W. said, your questions are not very clear. I interpret your first question as asking how the security of an $\epsilon$-PRP varies with $\epsilon$. The answer to this is quite clear from Tessaro's introduction: $\epsilon=0$ corresponds to the standard definition of PRP (also called fully-secure PRP in the paper). As $\epsilon$ grows, the security weakens. If you push to $\epsilon=1$ (which is not permited by the definition), there is no security left.

So the highlighted sentence in your question means that the assumption that AES is very weakly secure (0.99-PRP) is much weaker (and thus more likely) than the assumption that AES is fully secure.

Concerning your second question: The problem solved in the paper is to show that a cascade of $\epsilon$-PRPs with independent keys becomes more and more secure as the number of ciphers in the cascade grows. For $\epsilon\geq 1/2$, this was unknown from previous papers.


Discrete logarithm problem particularly hard for Schnorr groups? The Wikipedia article on Discrete Logarithm just states without source:

  In some cases (e.g. large prime order subgroups of groups ($\mathbb{Z}_p)^×$) there is not only no efficient algorithm known for the worst case, but the average-case complexity can be shown to be about as hard as the worst case using random self-reducibility.

To my understanding "large prime order subgroups of groups ($\mathbb{Z}_p)^×$" are also known as Schnorr groups. But apparently not everybody calls them that (?).

So where would I find a (citable) proof that the discrete logarithm problem is (assumed to be) hard for elements of a Schnorr group?

This is probably related to Why does Schnorr's Digital Signature scheme necessitate two prime numbers?, which would be my next question. The answer given there may be correct but also without a citable source...

I do not know an exact citable source.

However the rationale is roughly the following:

The Decisional Diffie-Hellman Problem (DDHP) is not hard in $\mathbb{Z}_p^*$ since the Legendre symbol leaks the parity of the discrete log (DLOG) [1 section 5.1.2, 2]. You can use this fact to build an efficient algorithm to distinguish between Diffie-Hellman and non Diffie Hellman tuples [3 section 6.6].
Another reason is the existence of the Pohlig - Hellman Algorithm [1].

Note that the semantic security of the ElGamal cryptosystem rests on the DDHP problem, which is believed to be easier than the DLOG problem.

References:

[1]Cryptography: Theory and Practice by Douglas Stinson

[2] Finding $x$'s parity in the discrete log problem

[3] https://crypto.di.uoa.gr/class/Kryptographia/Semeioseis_files/Cryptograph_Primitives_and_Protocols.pdf


Converting a pre-image resistant hash to second pre-image resistant I am looking for some standard conversion from any hash function $f$, which has pre-image resistance, to another hash function with second preimage resistance. Is there such a standard conversion?

Yes.  I believe this is the standard conversion.

(That link is to the paper "Universal One-Way Hash Functions via Inaccessible Entropy".)


What are other good attack examples that use the hash collision? When we consider the security of a cryptographic hash function with $n$ bit output we simply say that it must have at least $\mathcal{O}(2^{n/2})$-time security against the (generic) collision attack due to the birthday attack / paradox.
When we talk about the attacks from an educative perspective one needs to demonstrate good examples of the usage of the collision attack.
One attack example from Wikipedia based on the hash-and-sign paradigm

The usual attack scenario goes like this:

Mallory creates two different documents A and B that have an identical hash value, i.e., a collision. Mallory seeks to deceive Bob into accepting document B, ostensibly from Alice.
Mallory sends document A to Alice, who agrees to what the document says, signs its hash, and sends the signature to Mallory.
Mallory attaches the signature from document A to document B.
Mallory then sends the signature and document B to Bob, claiming that Alice signed B. Because the digital signature matches document B's hash, Bob's software is unable to detect the substitution.

Another one From Our site: Squeamish Ossifrage answer

I make three versions of a software package:

the good one does what it is advertised to do which is something useful
the bad one does something harmful noisily, like uploading credit card data to a bad place
the sneaky one does something harmful quietly, like slowly making your screen look blurrier and blurrier over the course of a month, or silently disabling disk encryption

There's a sneaky catch: the good one and the sneaky one collide under MD5, but the bad one does not.

and, in short, goes like this the bad one detected due to an incorrect hash but the sneaky one survives since it has a hash collision with the good one.
What are other good attack examples that use the hash collision?

Collisions are a generic tool in many attacks beyond hashes. Examples:

Attack of double encryption $C=E_{(K_1,K_2)}(P)=E_{K_2}(E_{K_1}(P))$ given a few (say 2) plaintext/ciphertext pairs $(P_i,C_i)$, which basically finds a collision between $F(K_1)=(E_{K_1}(P_1),E_{K_1}(P_2))$ and $G(K_2)=(D_{K_2}(C_1),D_{K_2}(C_2))$.
Discrete logarithm, in Baby-Step/Giant-Step and it-s memory-lean variant Pollard's rho. Basically these solve $x[G]=A$ in some group (noted additively) with generator $G$ by finding a collision between $y[G]$ and $z[G]+A$ with $y$ and $z$ from disjoint sets, then get $x=y-z$ modulo the group order.
Integer factorization, using a different Pollard's rho.

The reduction of the effort from $O(n)$ to $O(\sqrt n)$ characteristic of collision search, combined with the possibility of parallel collision search on independent machines with little memory*, is what makes these methods attractive. For 1, and 2 in the case of a generic group, this is the best known method.

* See Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications, in Journal of Cryptology, 1999.


What are I2OSP & OS2IP in RSA PKCS#1? I started working with RSA two weeks ago. But I couldn't really understand how exactly I2OSP & OS2IP are working. I am using some open source for signature verification through RSA PSS algorithm.

I am trying to generate "EM" from a signature of length 256 bytes, public modulus $n$ (256 bytes) and exponent $e$ (0x10001). But I am not getting the expected output ("EM"). So I started debugging code.

Can someone clearly explain what OS2IP & I2OSP do?

I2OSP and OS2IP mean Integer to Octet Stream Primitive and Octet Stream to Integer Primitive. There is an often used play on words here: "two" (2) has almost the same pronunciation as "to". The word "octet" simply means 8-bit "byte" and that "stream" can be replaced with "array". So these are conversion functions between integers to byte arrays.

The I2OSP function simply represents an integer in a statically sized byte array. For this it requires two inputs: the integer itself and the required size of the byte array. If the integer "doesn't fit" then an error is produced.

The integer is encoded as an unsigned big endian (network order) number, prefixing leading zero bits and bytes at the left hand side until the size is reached.

So lets take a look at some examples with output size of 2 octets with the integer (in decimals) on the left and octets  / bytes at the right (in hexadecimals, separated by colons):

   -1  ->  error
    0  ->  00:00
    1  ->  00:01
  255  ->  00:FF
  256  ->  01:00
65535  ->  FF:FF
65536  ->  error

So any integer will be represented with the same number of bytes, and each number will have a unique (or canonical) representation.

This function is used to make sure that signatures and encrypted values for a specific key size will also be represented in the same way, using the same number of bytes. For instance in RSA - for which these functions are defined - the size of the signature and ciphertext is always the same as the key size (or: modulus size) in bytes.

The size of the array used for RSA is the minimum size of the modulus encoded using I2OSP. The size of the modulus in bits is the same as the key size. So signatures for RSA with a 2047 bit key size (generally not used) and 2048 bit key size will both be 256 bytes in size.

The error conditions of I2OSP should never happen for RSA / PKCS#1 as all calculations will result in a number smaller than the modulus. So the number will fit - by definition - in an array that can also hold the modulus.

The encoding returned by I2OSP is specific to RSA instead of specific to the internal number representation within a language / runtime / operating system / CPU architecture. This means that the byte encoding of the signature is portable across the different runtimes.

OS2IP will do the exact reverse. It's usually easier to implement as languages/runtimes generally simply skip leading zeros when converting integers from bytes. You must however make sure that the bytes are interpreted as an unsigned big endian value.

For little endian machines it may be required to reverse the order of bytes. It could also be required to add a 00 valued byte at the most significant location. Otherwise the number may be interpreted as a (two-complement) signed value, which may result in a negative value.

Often I2OSP is programmed the way it is described in the PKCS#1 specifications. This however is a rather mathematical description of the encoding. Generally integers are already represented in a way that is largely compatible with the description of I2OSP, which means that some copying and resizing (and possibly reversing for little endian systems) is all that is required. For instance, check my implementation for Java here.


RSA decryption with small exponent - no "public keys" I have an unusual scenario where an RSA key pair is being used to protect the confidentiality of data in transit. The encryption exponent, the decryption exponent and the modulus are all kept secret between the two systems (i.e. there is no "public key").  The decryption exponent is 65537. Appropriate padding for RSA encryption is being used when encrypting.

Does the small decryption exponent create a vulnerability in this case?

Actually, someone who gets two plaintext/ciphertext pairs (after padding; randomized padding foils this attack), and guesses the small exponent can recover the modulus, allowing him to decrypt other ciphertexts.

The relation between plaintext, ciphertext and modulus is:

$$C^e \equiv P \pmod N$$

or

$$C^e - P = kN$$

for some integer $k$.  Hence, if we have two such plaintext/ciphertext pairs $P_1, C_1, P_2, C_2$, the attacker could compute

$$\gcd( C_1^e - P_1, C_2^e - P_2 )$$

and that is likely to be a small multiple of $N$; the actual value of $N$ (which has no small factors) is easy to derive from that.

On the other hand, if everything is kept secret and shared between the two parties, is there any reason you don't go with (say) AES and a shared secret key?


8-bit CFB in DES and AES - error propagation I have two questions for an assignment that I need to answer in relation to Error Propagation in 8-bit CFB mode for AES and DES encryption. The questions are as follows:

If there is an error in transmitted ciphertext block C1, how many plaintext blocks will be corrupted when the file is decrypted for 8-bit CFB-DES?
If there is an error in transmitted ciphertext block C1, how many corrupted plaintext blocks when 8-bit CFB-AES is used?

For question 1 I know the answer is 9 characters, as P1 will be affected and so will the following 8 characters (Avalanche effect). But why, when using AES, will 17 bits be affected, ie. P1 and the following 16 characters? I tested this encryption using openssl -AES-256-CFB8 and -DES-CFB8 on Linux Ubuntu.

17 bytes are affected in AES mode, not 17 bits. This is because the block size of AES is 16 bytes instead of 8 bytes for DES.

When you change the ciphertext it directly affects the bits that are at the same location of the plaintext, plus the time it takes to get out of the shift register, which is the size of the block size of the cryptographic primitive, i.e. 8 bytes for DES and 16 bytes for AES.

The question is however how many blocks are affected, not how many bytes. Note that the block size of CFB will be set to 1 bit, not the block size of the underlying block cipher. CFB is a stream mode after all.

So you could say that 9 * 8 = 72 blocks are affected for DES or indeed 17 * 8 = 136 for AES. This is probably not what is meant by the teacher, you're better off guessing 2 blocks for both or 9 for DES and 17 for AES. Also see the explanation by SEJPM here.

The nice thing about CFB8 mode is that if you drop or insert a byte that it will re-synchronize. What it won't do is to only flip those plaintext bits that are changed in the ciphertext, such as CTR mode does.

Nowadays we're not that interested anymore. We tend to catch transmission errors in a lower layer and then only decrypt if the entire ciphertext is available, preferably using authenticated encryption to catch any changes to the ciphertext (deliberate or otherwise).

Note also that CFB8 mode is terribly expensive; it requires a block encrypt for each byte that is transmitted, both for encrypting as decrypting.


Does two-factor authentication require one time use of one of the factors? Do we need one of the factors of two factor authentication to be one-time use?

TOTP and password are considered two factor authentication, but does smart card and password also count as two-factor authentication?

No.

The factors are:

something you know (for instance a password);
something you have (for instance a device containing a key for TOTP generation)
something that you are (for instance a fingerprint).

TOTP is not a factor in itself, it is a scheme that can be used to prove that you have the key / device).

There are however other ways of testing that you have something. If you bring a special amulet as "something that you have" then I could simply have a look at it after all. One time use is therefore not required.


To understand a fact related to padding in MD5 I'm trying to understand the padding process of MD5
from this link.
In that paper in Section 3.1, I found the following description of padding:

The message is "padded" (extended) so that its length (in bits) is
congruent to $448$, modulo $512$. That is, the message is extended so
that it is just $64$ bits shy of being a multiple of $512$ bits long.
Padding is always performed, even if the length of the message is
already congruent to $448$, modulo $512$.

I have tried to understand the sentence "That is, the message is extended so that it is just $64$ bits shy of being a multiple of $512$ bits long." with my utmost effort. But I've failed.
Could anyone clarify that sentence?

Let's say our message is b bits long. When we're done padding it, it should look like this:

P = [  Message   |     Padding     |  Message length ]
    |<- b  bits->|<-- ??? bits --->|<--- 64 bits --->|

Where the message length is just b encoded as a 64-bit integer, and the middle padding section looks like this:

Padding = 1 0 0 0 0 ... 0 0 0 0 0

(Those are actual 1 and 0 bits).

So how many zero bits do we include in the padding? Enough to make P a multiple of 512 bits long (so 512 bits, 1024 bits, 1536 bits, etc.). This allows us to break P up into a complete number of 512-bit chunks for the next step.

For example, let's say the message is 128 bits long (16 bytes). We need 64 bits for the message length. That brings us to 192 bits. In order to get to a multiple of 512 bits, we'll need to add 512 - 192 = 320 bits of padding: a single one followed by 319 zeroes:

P = [  Message   |     Padding     |  Message length ]
    |<-128 bits->|<-- 320 bits --->|<--- 64 bits --->|

Note that the first two sections take up 128 + 320 = 448 bits. In general, once we break the message up into 512-bit blocks, the last block will contain 64 bits for the message length and 512 - 64 = 448 bits for the end of the message and the padding combined. This is where the 448 number in the RFC comes from.


Is double SHA-256 the best choice for Bitcoin? So I was just curious.
I really look up to Blockchain technology and I have read that Bitcoin uses double SHA-256 for hashing.
( from what I understood, double sha256 is essentially $\operatorname{SHA-256}(\operatorname{SHA256}(value))$ ).
Is double SHA-256 better than SHA-512 or any other hashing algorithm that bitcoin could use? Or maybe there are other alternatives that could bring some benefits over the double SHA-256 for bitcoin?

Since the initial release of Bitcoin is  9 January 2009,  the designer had these NIST hash functions (NIST-FIPS 180-4) as available options: SHA-1( 1995), SHA-256 (2001), SHA-512 (2001), and some more.
The main difference between SHA-256 and SHA-512 is the target CPU. SHA-256 is designed for 32-bit CPUs and SHA-512 is designed for 64-bit CPUs. That makes a huge difference in the target CPUs.
One can argue that the designer wanted protection against the length extension attacks. However, SHA-512/256, which has the same pre-image, secondary-preimage, and collision resistance as SHA256, is secure against length extension attacks. Though not officially available at that time, simply trimming the 256 bit from the output of SHA-512 is the countermeasure. The knowledge was there since SHA-384 (2001) was available and it is trimmed from SHA-512 with different initial values for domain seperation *.
The obvious choice can be considered as the speed. SHA512, according to the Blake2 site, is 50% faster than SHA-256. SHA-1 is 2-times faster than SHA-256. However, the output size of SHA-1 is 160 bit and can be considered small for security during 2009 and for the mining space.
Another parameter for the choice of 256-bit is that Bitcoin used ECDSA-SHA-256 signatures. The obvious choice for hashing the message is using SHA-256.
Therefore, we can conclude that the designer didn't want fast mining, compatible with the ECDSA-SHA-256 signature so choose the $\operatorname{SHA-256}$ and, to prevent length extension attacks, selected double hashing. The double hashing is invented by Ferguson and Schneier in their book Practical Cryptography to countermeasure against length extension attacks.

As a side note, double-hashing doesn't prevent collision attacks since any collision $\operatorname{SHA256}(x)=\operatorname{SHA256}(y)$ is also a collision for  $$\operatorname{SHA256}(\operatorname{SHA256}(x))=\operatorname{SHA256}(\operatorname{SHA256}(y)).$$

*In academics, the first occurence the trimming as a countermeasure againt the length extension attack goes back to 1995


Authenticating with a document Hope you're having a nice day.

I need to implement an authentication system between a "document" (it's not exactly a document, but an object without any computing capacity, only able to store information) and a computer. The document will have some sort of information stored there by the computer, and then it will be given to an user and kept away from the computer. When the computer detects the document again, it will identify its possessor as the user to whom it was given to and authenticate it.

However, the computer isn't assumed secure, so I need the information stored there to don't be enough to replicate the document and to let us know if the computer has been modified.

On the one hand, I would like to know if the implementation I was thinking to use would be insecure: I was thinking of using RSA; I'll store the private key in the document and the public in the computer. Then, for authenticating, I'll encrypt and decrypt a random number less than N (the modulo) and see if it results the original one. This will be right, wouldn't it?

On the other hand, I would like to know if there is some research done about this topic and if there are any papers developing it. I've tried to search it by myself, but I don't know how to describe precisely without needing quite a long text. Is there any term for this type of security?

Please, don't hesitate to ask me more details in case I haven't explained myself very well. Thank you so much in advance for your help.

Your idea seems secure, but it is more complicated than it needs to be.

If you only need to know if the "secure information" in the document matches some public information (stored on an insecure computer), it is enough to calculate a preimage resistant hash of the document (e.g. SHA-256). The document needs only to be unguessable, like a 256-bit random number.

Note that there are practical problems here, which may lead to side channel attacks. For example, doing anything on a general purpose computer usually involves a chance that the memory you are using hits the swap on the disk, unless you use something like mlock.

You would need to carefully consider which parts of the computer you consider secure and what kind of attacks may be possible.


Does hashing an encrypted message suffer from any drawbacks? I am working on this problem where the set up is like this:

There are three hosts: A, B and C. A wants to send a message to C which passes through B. At A the message is hashed, the hash is padded to the message and then the message + hash is encrypted and sent to B. B wants to check for message integrity for which it decrypts the message, extracts the hash and then verifies.

I have proposed an alternative. My point is that we should encrypt the message at A and then compute the hash of this encrypted message. Then we should send the encrypted message +hash. The advantage is that at B the message need not be decrypted. B can verify the hash on the encrypted message itself.

Is there some problem with my proposed strategy?

Your scheme is of course insecure against any active attacks. B or another man-in-the-middle can just change the data and then calculate a new hash. This is why you need a MAC instead of a hash. And it depends on the method of encryption / hash if hash-then-encrypt is safe.

If anybody proposes such schemes you should try and use an authenticated cipher such as GCM. That will however still leave you vulnerable to protocol errors, so while you're at it: use TLS.


Why FHE only needs support for addition and multiplication For example, given $E(m_1)$ and $E(m_2)$ to the cloud. How does it calculate $E(m{_1}^{m_2})$?

Is it related to the claim that any computable function can be represented as a circuit containing or xor (additive) and and (multiplicative) gates?

If so, what's the approach?

Yes, it is related and they don't need only addition and multiplication. If you know from the electronics the Functional completeness;

  In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression

What operation is suitable for functional completeness is fine. However, addition and multiplication are common since many mathematical structures have it. Besides, there are others,for example; there is a partial FHE that only supports x-or.

It is a similar idea in FHE and you can build almost any circuits. The basic problem is the semantic security which prevents the direct comparison of ciphertexts. You compare in a different way.

Also, if you look at TFHE: Fast Fully Homomorphic Encryption over the Torus yo can see the supported boolean operations;

  The library supports the homomorphic evaluation of the 10 binary gates (And, Or, Xor, Nand, Nor, etc…), as well as the negation and the Mux gate. Each binary gate takes about 13 milliseconds single-core time to evaluate, which improves [DM15] by a factor 53, and the mux gate takes about 26 CPU-ms.

To calculate $E(m_1^{m_2})$? is really depend on the scheme. But basically you cannot use $E(m_1^{m_2}) = E(m_1) E(m_1) \dots E(m_1)$ since it will reveal your $m_2$. You need at least the repatings squaring method to hide the actual value.

With square-and-multiply you can at least hide the actual value of the power, not the size. let convert the below code into bit based FHE;

Let b be the “base” of the power, let p be the exponent.
Let r = the multiplicative identity (e.g.: 1).
Let s = b.
While p > 0 do:
    if p is odd
        let r = r * s.  // The "multiply"
    Let s = s * s       // The "square"
    Let p = p / 2 //(throw out the remainder).
The result is r

FHE version ( I keep $b=m_1$ and $p=m_2$);

While C(p,0) do:
    r =(r*s∗ S)+(r∗S′)
    Let s = s * s
    Let p = p >> 1
The result is r

in this code C(p,0) is the comparator as in Representing a function as FHE circuit. The multiply is performed by the if condition 'S' keep the value of p is odd. Since it is semantically secure we apply multiplication by the bit for if and it's inverse for the else case.

As you can see from this circuit this will only release the number of bits in $m_2$

In Short: We can build almost any circuit, however, some circuits may reveal some information that either sensitive or not depending on the problem


Which bitlevel operations must a fully homorphic crypto system support? My question is:
If I want to develop an turing complete programming language (for example some kind of assembly language) on top of a homomorphic encryption system, which bitlevel operations does this encryption system need to support so we can carry out all sorts of functions?

Bonus question: What operations is a usual CPU capable of carrying out at the lowest level? Because if you look at the number of operations in the x86 assembly language it seems obvious not all of them are supported a the lowest hardware level.

Any set of functionally complete operations should be sufficient. As SEJPM says in his comment this could be simply the NAND operation as it is complete on its own. Thus a good test to see if the supported set of operations is complete is to check if you can use them to evaluate the NAND operation.

AFAIK many FHE schemes supporting Boolean operations are built to support the AND and XOR operations. These are actually not complete on their own as you also need an operation that outputs the constant 1 (in order to implement the NOT operation together with XOR). This, however, is easily achieved in FHE as you can simply use the public key to encrypt the value 1.


Safe Elliptic curves of prime order according to "safecurves" I am currently trying to implement a cryptographic scheme. For this purpose I need a group of prime order in which the discrete logarithm problem is hard.

For now, I have been using a subgroup of prime order q over the Integers mod p, where p=2q+1, p prime, q prime. (p about 2048-4096 bits) The parameters for the groups are based on the primes given in RFC3526.

I would like to also try the scheme over elliptic curves. I'm aware of https://safecurves.cr.yp.to which lists and classifies a lot of different curves. However the information of whether the curve is of prime order is missing there. I've tried some of the popular curves like Curve25519 with Sagemath, however e. g. Curve25519 appears not to be of prime order, only the NIST curve (which have uncertain seed origin) are working.

So my question is basically: Are there any 'safe' and well-established elliptic curves of prime order? (If the answer is yes then where to find them? And if the answer is no, then why not and what's so special about the NIST curves then).

Thanks for your help in advance. I'm quite new to the topic, please don't hesitate asking if anything is unclear.

Are there any 'safe' and well-established elliptic curves of prime order?

Depends on what you mean by 'safe'.  If you use Dan Bernstein's definition of "safe curve", no; the curves they list as safe are Edwards curve, which always have a point of order 2 (and hence can't be of prime order).

As for proposed curves that are of prime order, there's the NIST curves that you know about, there's the Brainpool curves, and there are the Weierstrass flavor of the NUMS curves.  Whether they are 'well-established' is questionable; they each certainly have their proponents.

Also, it's not clear that you really need a prime order curve. The multiplicative group $Z^*_p$ you're using isn't of prime order either, you manage to work in a prime order subgroup.  The elliptic curves we use for cryptography have large prime order subgroups (to make the discrete log program hard), perhaps you can use the same trick to use, say, Curve25519.


Analysis of Repeatedly Enciphered Plaintext using Same Algorithm / Key? Please forgive the impracticality of this question, but I'm curious about the behaviors of encryption algorithms applied to their own output.

Suppose I have an encryption algorithm E and (using the same key(s)) I repeatedly encrypt its output for a given plaintext: E(E(E(E(...E(plaintext)

Would a modern encryption algorithm, such as some variant of AES, display any kind of cycling with respect to its output for arbitrarily long compositions of itself?  Is there some known number of compositions where the final output is itself the plaintext?

Eventually, it will cycle, but it'll almost certainly take far longer than your lifetime to do so.

If that sounds too flip, here's the mathematics.  Assuming AES is secure, then the probability it will revisit the original plaintext after at most r repeated encryptions is just r/2128.  (This follows from a standard fact about the cycle structure of a random permutation.)  For the values of r that can realistically arise in practice, this probability is negligible: less than the chances of getting hit by lightning, twice.

Is there some known number r such that r repeated encryptions are guaranteed to bring you back to the plaintext you started with?  Yes, for instance: r = (2128)!, i.e., 2128 factorial.  Or, r =  lcm(1, 2, 3, ..., 2128) also works.   However, this is a stupendously, ridiculously large number.  So it's completely irrelevant in practice.

Bottom line. If you've got a secure block cipher, you don't need to worry about cycling.  It's not an issue.  It just ain't gonna happen.


How does wNAF work with prime finite fields? According to wikipedia, in the precomputation step of the w-ary non-adjacent form (wNAF) point multiplication method you do $d \bmod 2$ and, later, $d \gets \frac{d}2$.

The mod operation doesn't make a lot of sense in the context of a prime finite field since division over a finite field doesn't produce a remainder. Rather, it's the numerator multiplied by the modulo inverse of the denominator. But I guess in this context it can probably just be taken to be the same thing as "is d odd".

But what about $d \gets \frac{d}2$? Outside of the context of prime finite fields that would normally be the same thing as right bit shifting by 1 but in the context of a binary field idk that dividing by two is the same thing as right bit shifting by one. It could be "multiply d by the modulo inverse of 2".

The fact that the while loop is doing while (d > 0) do kinda makes me think it's doing bit shifting but idk.

Any ideas?

The scalar is a scalar, it is not uncommon to view it in $\mathbb{Z}$ instead of in a field defined by the order of the curve/point (note:it does never make sense to view it in a binary field).

So $d\mod2$ becomes the least significant bit of $d$ and $\frac{d}{2}$ becomes the same thing as $floor(\frac{d}{2})$ which is the same thing as a right shift by 1.


Why does Apple use One-Pass Diffie-Hellman for file encryption? I was reading the iOS Security Guide (snapshot) and stumbled upon the following file protection class on page 15:

(NSFileProtectionCompleteUnlessOpen): Some files may need to be written while the device is locked. A good example of this is a mail attachment downloading in the background. This behavior is achieved by using asymmetric elliptic curve cryptography (ECDH over Curve25519). The usual per-file key is protected by a key derived using One-Pass Diffie-Hellman Key Agreement as described in NIST SP 800-56A.
The ephemeral public key for the agreement is stored alongside the wrapped per-file key. The KDF is Concatenation Key Derivation Function (Approved Alternative 1) as described in 5.8.1 of NIST SP 800-56A. AlgorithmID is omitted. PartyUInfo and PartyVInfo are the ephemeral and static public keys, respectively. SHA-256 is used as the hashing function. As soon as the file is closed, the per-file key is wiped from memory. To open the file again, the shared secret is re-created using the Protected Unless Open class’s private key and the file’s ephemeral public key, which are used to unwrap the per-file key that is then used to decrypt the file.

Here the document explains that ECDH key exchange is used, but gives no explanation as to why it is needed at all.
It would be more obvious if there was some kind of network between two parties involved, but in this case the only network I can think of is the communication channel between the CPU and the Secure Enclave.
I guess that the answer lies in the "One-Pass Diffie-Hellman Key Agreement" scheme described in §6.2.2.2 of the NIST SP 800-56A (snapshot) document and how it is different from "normal" Diffie-Hellman, but the document goes straight into details that are rather hard to digest.

If you have a look in the introductory paragraph of Section 6.2.2 of the NIST SP 800-56A document, you will find an explanation of how the one-pass key-agreement protocol is supposed to work.

If I understand the description you are quoting correctly, some public ECDH key corresponding to a static ECDH key pair is used to encrypt files while the device is locked, because the actual symmetric encryption key is only available when the device is unlocked. Furthermore, each file gets encrypted with a separate per-file key. This is where the one-pass key-agreement comes into play. In particular, one uses it to derive a per-file key, which is in turn used to encrypt the actual file (one has different keys per file since the ephemeral keys are freshly chosen for each file). Then, as soon as the device gets unlocked one can use the static secret key corresponding to the ECDH key pair to obtain the per-file key using the key agreement protocol and then store/encrypt the file as it would have been stored/encrypted if the device would have been unlocked in the first place.


How would you explain this very simple add/modulo asymetric encryption? I am working on a presentation aimed at developers without a strong mathematical background (like me). I would like to explain how asymetric encryption works with an non-fully-secure but working example.
I found one on Stackoverflow based on addition and modulo :

given a range from 1 to M
given a and b where a+b = M
a is the public key, b is the private key
x is the clear data (just a number)
y is the encrypted data
y = (x + a) mod M
x = (y + b) mod M

Example :

M=10, a=3, b=7, x=4
y = (4+3) mod 10 = 7
(7 + 7) mod 10 = 4

Vilain knows the algorithm and a, y, M.
We suppose Vilain cannot guess b from a.
Reverse modulo has multiple results :

4 mod 3 = 1
7 mod 3 = 1
13 mod 3 = 1

Meaning Vilain cannot easyly find

x+a

from

(x+a) mod M

Even this is really simple, and I "feel" the modulo "wrap-around" I could not find anyway to explain WHY this works :

y = (x + a) mod M
x = (y + b) mod M

Does anyone could try to explain it to me ?

If you were to plot the numbers 0-M on a straight horizontal line in increasing order from left to right, your message would become a point on that line. When you apply the key, it moves the message over $a$ spaces to the right. The modulo operator means that if your message goes too far off the right side of the line, then it wraps back around to the left side of the line.

If you were to apply the key $a$ again, your ciphertext message would move over another $a$ spaces to the right, which, assuming an appropriate modulus, implies that the result will not line up with the original plaintext message.

With this in mind, if you were move the ciphertext message instead $b$ spaces forward, you would end up back at the original message.

If you wanted to use $a$ as a symmetric key, you would instead perform modular subtraction on the ciphertext using $a$. Basically, symmetric decryption "reverses" the transformation, while in the case of asymmetric encryption, the  ciphertext is decrypted by going forward, as opposed to going backwards. This is what enables us to build public key encryption from non-invertible functions - we do not invert the transformation, we design it such that "going forward" (in a particular way) happens to "line up" and result in the original message.

Other operations can be used to create this asymmetric effect, usually employing a modulus. As mentioned by @poncho in the comments, multiplication is often used as a way to demonstrate "asymmetric crypto", but it should be noted neither addition nor multiplication is "strong enough", typically: modular exponentiation is what is used in practice to achieve the effect.

Here are some simple diagrams using your example. We'll start with a number line:

-----0-----1-----2-----3-----4-----5-----6-----7-----8-----9-----10-----

Setting $a$ at 3:

-----0-----1-----2-----a-----4-----5-----6-----7-----8-----9-----10-----

After we add $x$ (which is 4) to $a$ (which is 3); Since $a$ has been encrypted, we shall refer to the ciphertext as $b$ (as you did), which now has the value of $7$; The addition moves the value to the right on the number line:

                                   +x
                       +-----------------------+
                       |                       v
-----0-----1-----2-----a-----4-----5-----6-----b-----8-----9-----10-----

If we were to add $x$ to our ciphertext again, we would end up at $1$ ($11 \bmod 10 = 1$)

                                                           +x
... -------+                                   +------------------ ...
           v                                   |
-----0-----1-----2-----3-----4-----5-----6-----b-----8-----9-----10-----

This obviously leads to incorrect decryption. To decrypt correctly, we can add the corresponding private key $y=6$ ($x + y = 10$) to make the ciphertext "go forward" to the correct plaintext, remembering to wrap around when we get to the end of the number line:

                                                         +y
... -------------------+                       +------------------ ...
                       v                       |
-----0-----1-----2-----3-----4-----5-----6-----b-----8-----9-----10-----

Remark: here $10$ and $0$ are the same number (because $\mod 10$) !


How would P=BPP affect zero knowledge proofs? If there were a proof to show that P=BPP, how would this affect zero knowledge proofs and the fiat-shamir heuristic for Turing an interactive proof into a non-interactive proof?

It would not affect this at all. Note that under reasonable complexity hardness assumptions, it holds that P=BPP. So, even though we don't know how to prove this unconditionally (and in fact seem far away from doing so), it is what we assume to be correct.

I am not sure why you would think that this would affect the Fiat-Shamir heuristic. Even if P=BPP it doesn't mean that randomness has no role. In particular, you cannot sample a distribution deterministically. P=BPP relates to the ability to decide a language, not sample distributions. In particular, the necessity of randomness for zero knowledge holds, even if P=BPP.


KDF based on X9.63 vs. NIST SP800-108 What is the difference between KDF based on NIST SP800-108 vs. the older one in ANSI X9.63? When should one be selected over the other? Thanks.

The ANSI X9.63 uses SHA-1 for Key Derivation Function:

  Ingredients: The key derivation function employs the hash function SHA-1 specified in Section 5.6.2

NIST SP800-108 uses PRFs:

  This Section defines several families of key derivation functions that use PRFs.

First look at their dates;

1998 : ANSI X9.63
2009 : NIST SP800-108

And, SHA-1 is no longer recomended. So you should prefer NIST SP800-108

There are two other reasons for not to use SHA-1:

SHA-1 is shattered, you can also read these two articles:

Does “Shattered” actually show SHA-1-signed certificates are “unsafe”?
After Google's collision attack, is RSA-SHA1 signature still safe?.

Reaching $2^{80}$ for the generic birthday attack is not that far since the Bitcoin miners reached $\approx2^{92}$ for SHA256 hashes per year in 06 Agust 2019.
Also, SHA-256 is approximately 2.2 times slower than SHA-1 on hashcat 2080Ti

Note: Depending on your case, there is also password-based key derivations; as PBKDF2


Can a Feistel network have more than two halves, widening the block width? Just to help   form this question, this is a Feistel network:-

To me this looks like:-

Why does the generic architecture have to have two halves?  We already have asymmetry in some variants.  As I understand it, the principal security comes from a secure permutation within the round function. All that happens outside of the round function is simple xor and swapping halves.

Could it have more than two halves then? Say five like the bread?  Or perhaps it has to be an even number of plaits /halves, so say four? Or ten? Yes it would mean more rounds to ensure good mixing of halves and be secure, but that's doable. So for example, with six halves of 64 bits each, would you have a 384 bit cipher?  Is there some intrinsic reason why this wouldn't work?

There are designs called generalised unbalanced feistel networks which do exactly this.

See the paper by Schneier and Kelsey here. The CAST cipher, an AES competition entry was an early example.

The article on cryptowiki gives a brief summary here

Here is an example:


Guess 100 bits of md5 hash I found the following challenge on a wargames site:

A 16 byte string is randomly generated and hashed with md5 => HashRandom

Next, the following happens in an infinite loop:

user is prompted for a 16 byte input
input is hashed => HashUser
HashUser is compared with HashRandom and the number of matching bits is displayed

The goal is to get at least 100 matching bits.

A couple of observations:

The initial random string is generated using lowercase/uppercase characters, numbers and characters like .,"...
usually, for any user input string like AAAAAAAAAAAAAAAA I get between 50 and 70 matching bits

To get a better understanding on what happens behind the scenes, I did some reading on md5 and Wang's attack ( http://merlot.usc.edu/csac-f06/papers/Wang05a.pdf ) + other papers related to it. Based on that, here are some notes:

My input will look like this (UI - user input - bytes I can control):

m0  - 0xUIUIUIUI
m1  - 0xUIUIUIUI
m2  - 0xUIUIUIUI
m3  - 0xUIUIUIUI
m4  - 0x00000080 - initial padding with 1 + 0's
m5  - 0x00000000
m6  - 0x00000000
m7  - 0x00000000
m8  - 0x00000000
m9  - 0x00000000
m10 - 0x00000000
m11 - 0x00000000
m12 - 0x00000000
m13 - 0x00000000
m14 - 0x00000000
m15 - 0x00000080 - input size - 128 bits - 16 bytes

Wang talks about a differential attack used to generate messages that collide under md5. I read that hoping it would give me some hints, however it can't really be applied for this challenge. The method described uses two 512 bit input blocks per message. It also imposes restrictions on bytes I can't control.
The only breakthrough I had with this is the ability to control the hash function after the first round (however, this is trivial and I don't think it can help me)
Because I can get the matching number of bits for how many strings I want, I can get an idea on how the hash of the random generated string looks like. Since I only need 100 bits, I don't need the hash to mach 100%. Basically, if I can control half of the hash (64 bits), with some luck I can get 36 other random bits to match.
On the fourth round of the md5 algorithm, the 63rd operation (so right before the final value is calculated) involves m2 (which I control):

Q63 = Q62 + Q59 + I (Q62, Q61, Q60) + m2 + 0x2ad7d2bb) <<< 15

Q63 will also have an effect on Q64.

This might allow me to intervene on the last 64 bits of the hash function; however, any change on m2 will impact the way in which Q63 and Q64 are calculated so I'm not sure if this can help.

Any ideas or suggested reading that could point me in the right direction? (GPU + brute force is the last thing on the list - I'm hoping there's another way to do it)

A 3 minute running time on my laptop (running Java) already gave me a bit string where 99 bits are identical. It might be that you're overthinking this.

This sounds like a classical proof of work that you're supposed to do. As it is unlikely that there are any shortcuts I guess you'll have to break it brute-force. And as is it a gaming site, the faster GPU probably wins.

MD5 still has pre-image resistance of over $2^{123}$, with the specific attack mentioned here. You won't get far with just finding collisions as the pre-image seems to be (unknown) and given.

Just computing on a laptop gives, comparing with a hash of all zero's:

100 : 00000000000000000000000625b4aa69 -> 0740a0a42a0074920018000008308212

only just over 26,000,000,000 (16 billion for the US, 16 milliard for the rest of us) hashes required; the hexadecimal representation of the value as 16 byte integer is used as input.

Took some time but nothing major, unoptimized, single threaded Java code, running on a downclocked i7 laptop. On a fast machine with semi-optimized, multi-threaded code expect a 16 times improvement minimum.


Security of GCM if Implemented with Stream Cipher instead of Block Cipher Can GCM be implemented with a stream cipher instead of a block cipher? If no, then what security flaw does it have?

If yes, then which possibility from below two is better in terms of security? In terms of speed, option ONE seems better as Stream cipher will be initialized only once in it (assume the input data consists of n blocks{0,1,2...n-1} where each block is of 128 bits).

Generate an output stream of length $n+1$ blocks $\{0,1,2,3....n\}$ from stream cipher using single key and single IV. Then  XOR the $n$ blocks $\{1,2,3...n\}$ of this output stream with $n$ blocks of plaintext to create ciphertext. Multiply ciphertext blocks together(as in GCM, shown as $\operatorname{mult}_H$ in figure below) and XOR the result with $1^{st}$ block  (0) of output stream to make AUTH_TAG.
Generate an output stream of length $n+1$ blocks $\{0,1,2,3....n\}$ from stream cipher, where each block is generated with incremental IV (like Counter) but same key. Then XOR the $n$ blocks $\{1,2,3...n\}$ of this output stream with $n$ blocks of plaintext to create ciphertext. Multiply ciphertext blocks together(as in GCM, shown as $\operatorname{mult}_H$ in figure below) and XOR the result with $1^{st}$ block (0) of output stream to make AUTH_TAG.

In AES/GCM, every use of AES can be expressed in terms of AES-CTR:

From the initial IV (12 bytes + counter initialized at 1), a sequence of $n+16$ bytes is generated, for a source plaintext of $n$ bytes; the first $16$ bytes are the block XORed with the GHASH output to produce the authentication tag.
The GHASH key ($h$) is obtained as the encryption of an all-zero block; this is equivalent to AES-CTR encryption of an all-zero value with an IV+counter equal to zero.

In fact, it is highly possible and even sensible to implement GCM out of an exclusively CTR implementation of AES (see my GCM code for an example).

Since AES-CTR is supposed to be a strong stream cipher, indistinguishable from a random source, we can replace it with another stream cipher, and things should still be fine in terms of security (i.e. it won't be made worse). In details, this would mean the following:

The stream cipher works over a key $K$ and a 16-byte IV.
The stream cipher would be invoked over an all-zero IV to produce $h$ (16 bytes).
The stream cipher would also be invoked, with the same key, but an IV made of the nonce (12 bytes) + the value 1 (over 4 bytes) to generate $n+16$ bytes, for the XOR with the authentication tag and the data encryption itself.

With this description, we see that AES-CTR is actually a bit lousy with regards to IV management. The specific details of IV construction are meant to avoid nonce reuse; AES-CTR for a run of $k$ blocks "burns up" $k$ successive nonces. This is the reason why counter starts at $1$ for the block to be XORed with the GHASH output, and $2$ for the data itself: that way, the values cannot collide with the all-zero block for $h$. Use of a secure stream cipher in lieu of AES might possibly relax such constraints, and in fact be more secure than GCM(*).

Of course, this raises the question of why you would do that. The GHASH part of GCM is usually the problematic one when it comes to implementation, not the AES. GHASH is very fast on hardware platforms that have dedicated opcodes (x86 with AES-NI, POWER8...) but these platform also provide an AES hardware implementation that outperforms software-based stream ciphers. In practice, you would probably be better off with Poly1305, which is commonly used in combination with the stream cipher ChaCha20, as described in RFC 7539.

(*) With the usual caveat that something can be "more secure" than AES/GCM only insofar as AES/GCM is less than ideally secure, but it is currently unbroken. We still have a few academic misgivings related to the relatively short IV, in that random 96-bit IV have a not completely impossible probability of collision.


Practicality of a certain hash function Consider the following hash function:
$$(V\cdot A + V\cdot B)^2 \bmod C$$
$A, B,$ and $C$ are large primes. $V$ is the value to be hashed and is guaranteed to contain at least as many bits as the largest prime.
Ostensibly, this should provide an excellent level of collision resistance.
Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

The obvious weakness when one sees a square is
$$(a)^{2} = (-a)^{2},$$ This is not a problem in the Rabin Cryptosystem since it requires an additional mechanism to resolve the message from possible 4 candidates. Here, however, this is can cause a direct collision.
Also, as noted by fgrieu, the calculation of the square root is not hard in the prime case by the Tonelli-Shanks. This algorithm work for prime $p$ and generalized for $p^k$, too.

Now assuming that the primes in question are large enough, computing the reverse should be unfeasible. Correct?

Take
$$h = (V\cdot A + V \cdot B)^2 = V^2(A+B)^2 \bmod C $$ So there is no reason for $A$ and $B$ to be a prime. Since it is not a keyed hash, we should know all values, like $A,B,C$ then
$$V^2 = \frac{h}{(A+B)^2} \bmod C$$ this has two solutions in the range $[0,C{-1}]$ and infinitely many solutions in the $\mathbf{Z}$. We can find these first two with the Tonelli-Shanks and the rest with modular arithmetic.
Therefore, one-can find pre-images, secondary pre-images, and collisions very easily. Remember in the pre-image attack we don't need to find the actual value $V$, and any value $V'$ that produces the given hash value $h$ will be enough for this attack to be successful.
Not even close to being a secure hash function at all.


How does one associate the actual identity of a person or organization with a decentralized ID? In SSI (Self-Sovereign Identity), anyone can generate their own DID (Decentralized ID). No authority or authorization is needed to create one. Since a public key pair is associated with DID, the person can prove the ownership by using the private key. DID document, which includes DID, is stored in a blockchain that prevents illegal manipulation. In some materials on the web, they call this decentralized PKI. This is a little confusing because I always associated PKI with certificates issued by CAs. In SSI, how do people verify that the given DID is Alice's DID? Furthermore, how do people verify that the given DID is the Issuer's DID (for example, a university that issues verifiable credentials of a diploma)? Do we need some other mechanism (perhaps centralized PKI to prove this DID is Alice's DID to the issuer before requesting her diploma)? What is the main reason we no longer need certificates when using public keys?

A certificate is a document containing a public key, identity information associated with that key, a signature, and information about what entity created the signature. A self-signed certificate is any certificate where the signature was created by the same entity that has the private key of the certificate. A DID is just a self-signed certificate.
By using their private key to sign a challenge the DID holder can verify to others that they possess that private key, and thus are the same entity as they were when the DID was created and added to the blockchain. Nothing about the blockchain ensures that the identity information is correct, of course, only that it hasn't changed. That step has to be done independently. In your example, the university could publish their DID on their web site.
You might note that this doesn't get rid of certificates, it just calls self-signed certificates DIDs.