Signing and verifying message consisting of several parts Given a message $m$ that consists of several parts. we want to be able to verify individual parts or a combination thereof.

The simplest solution is independently signing each part. But since asymmetric signatures are relatively expensive to compute and verify, that might not be the most efficient approach.

Is there an efficient and faster alternative approach for this problem?

The standard way to do this is with a hash list.  That is, you would hash each of the messages $m_i$ to produce a hash $h_i = H(m_i)$, and then combine all the hashes and hash them to obtain a master hash $h = H(h_0 \| h_1 \| h_2 \| \dots \| h_n)$.  Finally, you can e.g. digitally sign the master hash to prove that the hash, and by extension all the messages, were sent by you.

(You can, of course, also use a keyed MAC instead of a hash for this, if you want.)

Hash lists can also be generalized into hash trees.  For very large numbers of messages, hash trees are potentially more efficient, since they can let you verify the integrity of an individual message without having to load and hash together all the intermediate hashes $h_i$.  They're also more efficient to update, if your messages may sometimes change.  (That said, if your messages don't change, and you know you're going to want to verify all of them anyway, a simple hash list will have somewhat less overhead than a more complex hash tree.)

Of course, you could also just simply hash the whole combined message $m = (m_0, m_1, \dotsc, m_n)$ at once, without bothering with hash lists or trees.  But the advantage of hash lists or trees is that they let you verify the individual message parts without loading and hashing the whole combined message.


HMAC Secure Key Exchange? Within RFC 2104 section 3 there is discussion around keys (below). How are these keys agreed upon/distributed? Practically speaking is asymmetric crypto a requirement to "bootstrap" and distribute keys?

  "Keys need to be chosen at random (or using a cryptographically strong
  pseudo-random generator seeded with a random seed), and periodically
  refreshed.  (Current attacks do not indicate a specific recommended
  frequency for key changes as these attacks are practically infeasible.
  However, periodic key refreshment is a fundamental security practice
  that helps against potential weaknesses of the function and keys, and
  limits the damage of an exposed key.)"

How are these keys agreed upon/distributed? Practically speaking is asymmetric crypto a requirement to "bootstrap" and distribute keys?

The answers to those questions are beyond the scope of the RFC. So, it depends on the context in which HMAC is being used. The keys can be agreed upon/distributed in any secure manner. The RFC doesn't care. It could be via asymmetric crypto, it could be in person, it could be via carrier pigeon (if that is considered secure in your threat model).


SHA3 hexadecimal paddig odd length string Section B2 of FIPS-202 specification describes the Hexadecimal Form of Padding Bits which is basically the translation of the bit padding 0110*1. However at the beginning they suppose that the message is "byte-aligned, i.e., len(M) = 8m", so what should I do if it is not (ex when the length is odd)?
In section B1 they also suppose the hexadecimal string to be 2m long, but what if it's odd?
If we have "abcd" we pad with ||060*80 so that the first line of the Keccak's state is
$[00\ ..\ 00\ 06\ cd\ ab]$ and that's ok.
However if we have "abc" and we do the same we end up with abc||060*80 that gives a state whose first line is $[00\ ..\ 00\ 06\ c0\ ab]$ which is not the right pad.
I also tried to add just 60*80 and then swap the 6 with the last element of the original string so
\begin{equation*}
  ab\,c  \rightarrow ab\,c6\,0*80 \rightarrow ab\,6c\,0*80 \rightarrow [00 \ ..\ 00\ 00\ 6c\ ab]
\end{equation*}
but this also gives wrong hash compared to SHA3 calculator online. So what is the right way to do it?

The bid padding of KECCAK family
Actually, the padding is defined bit based in section 5.2 for the general case;
Algorithm 9: pad10*1(x, m)

Input:
positive integer x;
non-negative integer m.

Output:
string P such that m + len(P) is a positive multiple of x.

Steps:
    1. Let j = (– m – 2) mod x.
    2. Return P = 1 || 0^j|| 1.

and also noted as
Therefore this at least a 2-bit padding. If the message size $m \bmod r = \{0,-1\}$ then a new block will be required.
The $x$ is set as $x = r (rate)$

The suffix and padding for $\operatorname{SHA3-224}$
The Keccak uses domain separation for SHA3, rawShake, and Shake series. For SHA3-x the message is first suffixed with 01 then the padding is applied (section 6.1);
$$M||\underbrace{01}_{suffix}||\underbrace{10^*1}_{padding bits}$$
$$\operatorname{SHA3-224}(M) = \operatorname{KECCAK}[448] (M || 01, 224);$$
In this case, the minimum added bits is 4, 2 from the suffix, and at least 2 from the padding.
byte padding fix for odd hex numbered messages.

but to do a bit of padding I first need to convert the input from hex to binary. To do so I could use Algorithm 10 in section B1 but this works only with hex string of even length so it cannot be used so that's why I'm asking for detail about the hex padding

Since the encoding trans $\texttt{abc||060*80}$ to $[80\ ..\ 00\ 06\ c0\ ab]$ the obvious solutions is using $\texttt{ab6c||0*80}$ and this will be translate to $[80\ ..\ 00\ 00\ 6c\ ab]$ as required.
The confusion come from the fact that the NIST defines the message as

message A bit string of any length that is the input to a SHA-3 function.

So the bit padding is naturally applied to a bit string. For the hex valued string, it must be converted Algorithm 10: h2b(H, n) but the document implicitly defines the byte padding as before the conversion. after the conversion it is still the bit padding.

Note: the $\phantom{a}^*$ represents the Kleene star simply means zero or more.


what are the advatanges and disavantages of the digital signature algorithms for JWT? I am using a Java JWT library jose4j.
There is a list of digital signatures algorithms which can be used.

HMAC using SHA-2
RSASSA-PKCS1-V1_5 Digital Signatures with with SHA-2
Elliptic Curve Digital Signatures (ECDSA) with SHA-2
RSASSA-PSS Digital Signatures with SHA-2

I tried to understand what the advantages/disadvantages of the algorithms are but Google searches of "HMAC vs RSASSA-PKCS1-V1_5" did not return results.

What are the pros/cons of these algorithms?

My answer is not original, as I am simply summing up information from different questions already solved in this site. Nevertheless, I thought it could be interesting to collect everything in one answer.

The first thing you have to know is to differentiate between a digital signature and a message authentication code (MAC). In this case, HMAC is a MAC and the rest (RSA and ECDSA) are digital signatures.

This answer to a previous question gives you an excellent overview of the different characteristics of both categories. As you can see, the main difference between HMAC and conventional digital signatures are:

HMAC uses symmetric keys (so both parties have to share a common secret), while Digital Signatures use asymmetric keys (i.e., public key crypto, so the prover uses a secret key, and the verifier uses an associated public key). This also has implications regarding performance, since symmetric crypto is usually much faster.
Digital Signatures provide non-repudiation of origin, while HMAC don't.

That is the first differential factor between them. Now, we could focus on the difference among digital signatures schemes:

RSASSA-PKCS1-V1_5 Digital Signatures with with SHA-2
Elliptic Curve Digital Signatures (ECDSA) with SHA-2
RSASSA-PSS Digital Signatures with SHA-2

In this case, the main differences are not about functionality, but about the underlying mathematical primitives, namely RSA vs Elliptic Curves. This also has been covered before. To sum up, the implications are mainly centered on performance, size of keys, implementations, etc.

Finally, this other answer covers the difference between RSASSA-PSS and RSASSA-PKCS1-V1_5. To sum up, the difference is mainly of theoretical interest, concerning the proof of security.


monoalphabetic substitution perfect secrecy I have this question that I'm trying to answer:

  Consider a monoalphabetic substitution cipher applied to plaintexts
   consisting of just a single letter. That is, $$M = \{0, 1, . . . ,
 25\}$$ The keyspace $K$ is the set of all permutations of $M$. (As
   usual, we identify the letter $A, . . . , Z$ with this set of
   integers.) Show that this is perfectly secret.

I understand that to show perfect secrecy it suffices to show that $|K|\ge |M|$. I'm just not understanding how to answer this question. Would it make sense to say $K = \{0, 1, ..., 25\}\Rightarrow |K|\ge |M|$?

IF $K$ is randomly chosen (and well distributed over the key space with size 26! - the total number of possible permutations) then each $C$ (ciphertext letter) is also equally likely. An attacker may choose any $K$ but it is impossible to gain any advantage by that; each message $M$ is still as likely as before.

Basically this scheme is a one-time-pad using a per-character permutation rather than XOR as often used.

As indicated by the first IF, what's missing is the requirement that the choice of $K$ is perfectly random. Generally we try and proof ciphers correct by looking at the set $\operatorname{Gen}, \operatorname{E}, \operatorname{D}$. The $\operatorname{Gen}$ is missing from the question.


Is CBC still better than ECB if the key and a large part of the texts are random? I am doing protection for my software, which involves storing a part of the crucial algorithm inside a smart-card based dongle. I will supply the input to the dongle, and I will expect the output of the dongle to be correct. If it's not then I know something is wrong.

The idea is that

First a random key is generated
Then I will encrypt my input using this random key, with ECB/CBC algorithm ( to be determined)
Then I will store both the key and the encrypted input in a random, much larger input stream. The position and the size of the key and encrypted input are indicated in the first two bytes of the input stream.
Once the input stream is passed to the dongle, the dongle will read out the key and the encrypted input and do necessary decryption, and then do the computation, and the output passed out.
The output will be encrypted again with the same (passed-in random) key, before passed out of the dongle.
The software side will then check the received output and decrypt accordingly.

Due to the nature of the protection, the hacker can only know the input/output stream to/from the dongle. He can't know what I do in the software, so he won't be able to tell what is the random key, and the encrypted input, and also the position and the size of the key and encrypted input.

I am thinking whether to use ECB/CBC for encryption algorithm. I am aware that ECB is less secure in general because if you encrypt two messages which has two blocks of plaintexts in common, then with ECB mode the corresponding ciphertext blocks will be the same. But in my case, even if my raw input is the same, what the hacker sees looks quite random because

The key is random
Both the key and the encrypted input are stored in random input streams.
The actual, meaningful unencrypted input size is quite small compared to the random input streams that the hacker has accessed to, less than 64 bytes ( 8 blocks). So there isn't too much of same text for the hacker to guess ( not sure about this point)

Also, both of the ECB/CBC contains only one secret key, and the only way how CBC "improves" over ECB is that it applies a random initial vector on the inputs, but I think this "improvement" can be nullified by random key/much bigger random input stream, no?

So I wonder whether CBC really improves over ECB in this case, and whether is there any need to use CBC or not.

After observing many transactions the ECB will likely break. The random data is not likely to repeat. Any repeating cipher blocks will be from the data revealing both the location in cipher stream and the fact the matching plain text was the same in both messages.
Encrypting only the small message with CBC and a random IV will be faster and more secure.


Is AES reducible to an NP-complete problem? Is breaking AES NP-hard?  Can the security of AES be reduced to a NP-complete problem?

If it is reducible, what does the reduction look like?
If it is not reducible, why do we assume it is secure?

There are some complexity-theoretic reasons to believe that cryptography can't be based on NP-completeness. For one example, see this paper by Akavia et al. Basically it all boils down to the mismatch between average-case hardness required for cryptography, and worst-case hardness required for NP-hardness. Moreover, many (most? all?) hard algebraic problems which serve as the basis for cryptography are in NP $\cap$ co-NP (for one such example, consider factoring). Such problems cannot be NP-complete unless NP = co-NP. You can see more discussion in this stackoverflow thread.

Finally, AES is a finite-domain function. It is invertible / distinguishable from a random permutation in (large but) constant time. The definitions of P, NP, etc., refer to asymptotic behavior -- that is, as the input size grows to infinity. Because of the algebraic structure of AES, it is probably possible to define a "generalized AES" for infinitely many key lengths (though there are many semi-arbitrary choices to be made). We could then ask about the asymptotic behavior of such a generalized AES. I'm not sure if anyone has done so.


Does the DES s-box only provide confusion, or does it also provide an avalanche effect? In DES, does the s-box provide an avalanche effect or does it only provide confusion in the ciphertext?

Well it goes a long way towards it.  If you simply consider an S box on it's own, you'll virtually have the avalanche effect across it.  Even with a randomly permuted one.  This is just a function of the input /output non linearity.

The 100% avalanche effect is brought on by DES' S box in conjunction with other components such as permutations and xor operators on the outputs of these, as in the points where the 48 bit subkeys are mixed in.  The number of rounds is also important. Generally, there is  a relationship between the width of the S boxes, the number of adjacent s boxes and the number of rounds. It's entirely possible that without enough rounds, you might only get  say 90% of avalanche effect.

It's easier to describe the avalanche effect itself, rather than the required steps to provide it.  That's why testing is crucial to confirm that a primitive has it.  You can have a pretty good suspicion that a construct might exhibit avalanche effect, but you won't be able to confirm it without testing.

S-Box Modifications and Their Effect in DES-like Encryption Systems is a good article on the DES S boxes and messing with them. Specifically look to section 4.2 regarding DES box 5.


Decrypt SHA1 Base64 Hash After spending a good hour searching I came across an article that explained that you can't reverse a hash value. How true is this? I need to reverse a base64 encoded Sha-1 email address but I can't seem to find a way without knowing what function was used to hash. Or is there an easier way of going about this?

You can very easily Base64-decode a string.
SHA-1 was designed to prevent people from inverting it. It approximates a one-way function.

See here for more. If it could be simply inverted, it would provide no information security.

Your only feasible option is brute-force search.


Encryption in SET protocol I have a rough idea of what is symmetric and asymmetric encryption, but I can't apply the idea to the SET protocol (Secure Electronic Transaction
Specification), so how the symmetric and asymmetric encryption are used in the SET protocol? Also I want to know more about the Preq messages.

how the symmetric and asymmetric encryption are used in the SET protocol?

As per section 3.2 (which goes into further detail) of the SET specification here:
Symmetric Encryption

SET will rely on cryptography to ensure message confidentiality. In SET, message data will
be encrypted using a randomly generated symmetric encryption key. This key, in turn, will
be encrypted using the message recipient’s public key. This is referred to as the “digital
envelope” of the message and is sent to the recipient along with the encrypted message itself.
After receiving the digital envelope, the recipient decrypts it using his or her private key to
obtain the randomly generated symmetric key and then uses the symmetric key to unlock the
original message.

Asymmetric Encryption

SET uses a distinct public/private key pair to create the digital signature. Thus, each SET
participant will possess two asymmetric key pairs: a “key exchange” pair, which is used in
the process of encryption and decryption, and a “signature” pair for the creation and
verification of digital signatures. Note that the roles of the public and private keys are
reversed in the digital signature process where the private key is used to encrypt (sign) and
the public key is used to decrypt (verify the signature).

You can find even more detailed information in the Formal Protocol Definition here which also goes into some detail on PReq messages (on PDF page 84).


Concatenating a hash function for generating one hash for multiple files Assuming we use SHA256 as hash function. In practice you see that a Merkle tree is used to concatenating multiple hashes together to one single root hash.

A Merkle tree is a binary tree which always takes two SHA256 hashes and concatenate them in a recursive manner.

My question: Is it insecure to hash more than two hashes together? Say for example you want to create a unique hash of a folder structure. Each folder can contain an huge amount of files which are separately hashed. If we now concatenate the hashes in a sorted way:

SHA256(concatenate(sort(SHA256(file 0), SHA256(file 1), SHA256(file 2), [...], SHA256(file n-1))))

Does this increase the risk of a collision?

Explanation: You can imagine that an attacker wants to prove that a file was part of the hashes (through the root hash) which it was not. So he can choose n-2 hashes freely and try to calculate the root hash (collision). Does this (dramatically) increasing the chance of a collision?

I can not find precise information about that online. My stomach feeling points me to the birthday problem. And kind of the existence of a Merkle trees is pointing in the same direction. Or am I wrong? I would be really happy for any hint. Thanks!

Assuming the hash is collision-resistant (which SHA-256 is believed to be), the proposed practice of hashing the concatenation of a sorted list of hash of files is demonstrably secure against collision (argument: a collision in the final result implies a collision in the last step or/and for some file); so is the practice of hierarchically hashing a binary tree. There's no meaningful difference in security (arguably, accidental collision is more likely in the later; but that's immaterial).

Notice that the proposed practice will give the same hash if files are reordered (which clearly is intentional), or if the content of two files is exchanged while they keep their name (which could be a serious security issue: two packages with the same hash, and the same filenames, can do entirely different things when run).


random number generator and seed I'm working with openssl cryptographic libraries, I'm new to all these cryptographic stuffs and slowly I'm learning all these. I have a doubt regarding random number generator, I'm using RAND_pseudo_bytes() for generating a pseudo random number. I'm providing a seed to it with my required entropy. But my doubt is if we provide same seed twice, will the random number generator generate the same random number ?

I recommend against using RAND_pseudo_bytes(). OpenSSL's CPRNG does not provide better pseudo-random numbers than /dev/urandom but it is much harder to use right. It has a couple of known flaws, for example it doesn't handle fork() very well. The standard PRNG is not very well designed, too. The FIPS mode PRNG is a bit better, though.

/dev/urandom (Linux, BSD, Solaris) are about as fast as RAND_pseudo_bytes(). You don't have to take care of seeding, fork hooks, thread locks and other stuff that makes the PRNG hard to use. You can just read as many bytes from /dev/urandom as you need. Windows has CryptGenRandom().

No matter what some people or documents say: ignore /dev/random. /dev/urandom is fine for everything you are going to do.


Using PBKDF2 twice with different argument order I'm pretty sure this is a really bad approach (in theory), but one of my clients is doing this and I was wondering… How bad it is to perform pbkdf-2 in this way (with 2000 iterations)?

a = PBKDF2(x, y)
b = PBKDF2(y, x)

x is the username (password in pbkdf2)
y is the password (salt in pbkdf2)
2000 iterations

a is then used for some authentication in the system and "b" is used for encryption.
a and x are also stored and therefore known.

Is it subject to some class of attacks or is it just a really bad crypto nightmare which is only subject to brute-force attacks?

EDIT 1:

More specifically: a is used as key to retrieve user data from the DB (thus, a is sent to server), data is returned and partially encrypted. You need b to decrypt what you get.

EDIT 2:

Let's say that an attacker gets access to the database where these hashes are stored. What kind of attacks could he perpetrate?

Is it subject to some class of attacks or is it just a really bad crypto nightmare which is only subject to brute-force attacks?

You are calculating PBKDF2 twice, which takes twice as long. An attacker doing a brute force or dictionary attack only needs to calculate one of them to verify his guesses.

That means you are making attacks twice as easy as they would be if you used PBKDF2 only once with twice the iterations, then used e.g. HKDF to quickly derive two keys.

Actually, if you use 128-bit keys and SHA-256 in PBKDF2, you can just split the output.

  More specifically: a is used as key to retrieve user data from the DB (thus, a is sent to server), data is returned and partially encrypted. You need b to decrypt what you get.

If $a$ is sent in the clear, an eavesdropper can use it for a brute force or dictionary attack, which would also find $b$. 2000 iterations of PBKDF2 doesn't make a password invulnerable to such attacks, although it obviously helps.

  Let's say that an attacker gets access to the database where these hashes are stored. What kind of attacks could he perpetrate?

Brute force and dictionary attacks, probably no easier than if only $b$ was known, but like I wrote above, twice as easy as if a better key derivation system was used.

Like the other answer mentions, if someone used their username as a password, that would be immediately visible as $a=b$, so no searching would be needed. However, that would be one of the first guesses in any case, so it probably isn't a big deal.


A mathematical explanation of the DES encryption system I need a mathematical explanation of what does the DES encryption system really do.

This means I need more explanation than the one that offers FIPS, which is more an explanation for computer specialists.

Among other things, I want to know where do these permutation tables come from:
$$IP\\
\newcommand\T{\Rule{0pt}{1em}{.3em}}
\begin{array}{|c|c|c|c|c|c|c|c|}
\hline
  58 \T & 50 \T & 42 \T & 34 \T & 26 \T & 18 \T & 10 \T &  2 \\\hline
  60 \T & 52 \T & 44 \T & 36 \T & 28 \T & 20 \T & 12 \T &  4 \\\hline
  62 \T & 54 \T & 46 \T & 38 \T & 30 \T & 22 \T & 14 \T &  6 \\\hline
  64 \T & 56 \T & 48 \T & 40 \T & 32 \T & 24 \T & 16 \T &  8 \\\hline
  57 \T & 49 \T & 41 \T & 33 \T & 25 \T & 17 \T &  9 \T &  1 \\\hline
  59 \T & 51 \T & 43 \T & 35 \T & 27 \T & 19 \T & 11 \T &  3 \\\hline
  61 \T & 53 \T & 45 \T & 37 \T & 29 \T & 21 \T & 13 \T &  5 \\\hline
  63 \T & 55 \T & 47 \T & 39 \T & 31 \T & 23 \T & 15 \T &  7 \\\hline
\end{array}
$$

I know this kind of encryption systems have a lot to do with the mathematical concept of a field.

So I would like to know if someones has a PDF or any other real mathematical explanation of the DES encryption system.

The DES standard (FIPS 46-3) is actually a rather straightforward description of DES. It tells with precision and detail where each bit goes. It is a specification for implementers (who can be thought as "computer specialists" but anybody who wants to learn about DES should be able to understand that specification). What FIPS 46-3 does not tell is why DES was designed that way. If you want more mathematics, you can have a look at the Handbook of Applied Cryptography (free download !), in particular chapter 7, which goes over the case of DES.

For the initial and final permutations (called "IP" in FIPS 46-3), they were defined not for security (they are fixed, key-less permutations which anyone can readily invert), but to ease implementations in hardware contexts of the 1970s' era: they make it easier to make an hardware implementation which plugs on an 8-bit bus. See this question for some details.

There is nothing about fields in DES. It is all bit-by-bit manipulations; to some extent you could say that a bit is a value in GF(2), the field with two elements (0 and 1), but that's quite stretching it.


What cipher algorithm is this routine using? I transfered a code routine from Java to Python:

import base64
import hashlib

class Cipher(object):

    def __init__(self, key):
        self.key = key

    def decrypt(self, message):
        message = base64.b64decode(message)
        message = bytearray(message)
        a1 = self.make_table()
        results = range(len(message))
        j = k = 0
        for i in range(len(message)):
            k = 0xFF & k + 1
            j = 0xFF & j + (0xFF & a1[k])
            a1[j], a1[k] = a1[k], a1[j]
            n = 0xFF & (0xFF & a1[k]) + (0xFF & a1[j])
            results[i] = message[i] ^ a1[n]
        return bytearray(results)

    def make_table(self):
        key = hashlib.md5(self.key).hexdigest()
        key = bytearray(key)
        results = range(256)
        m = 0
        k = 0
        for i in range(256):
            k = 0xFF & k + ((0xFF & key[m])) + (0xFF & results[i])
            results[i], results[k] = results[k], results[i]
            m = (m + 1) % len(key)
        return results

I'd like to know what algorithm is this code using? so I can refactor it to better Python code. thanks!

Normally, questions like this are considered off-topic; however, in this case, I can give a quick answer -- it's RC4


Is ISAAC Cipher Cryptographically Secure? http://en.wikipedia.org/wiki/ISAAC_(cipher)

This question was asked before but the answers seem vague, and I want to know about ISAAC specifically, not ISAAC+.

It seems some cryptanalysis was performed on it and the only seemingly major drawback to security is that some initial rounds may be biased (although on the official website, looking at the implementations the author of ISAAC purposefully skips the first round).

Also, is there anything unique to seeding this cipher? Can I not just pass it any securely generate random seed?

It somewhat depends how you define “secure“, but as far as I know, it has not been broken yet.

Potential attacks and/or weaknesses:

Brute force to find 256-bit key.
~ Obvious.
Paul and Preneel (2006) published an alleged distinguishing attack using $2^{17}$ bytes of output
~ Turned out to be an attack on a cipher different from ISAAC.
Aumasson (2006) labelled various states of ISAAC as "weak."
~ Pointing to weaknesses, but no statements of any attack.

Therefore, I would categorize it to be cryptographically secure indeed. Yet, we have to remember that ISAAC didn’t get as much attention as (for example) AES did. So there may well be weaknesses that have not yet been found and/or published. But looking at what is known, it should be safe. (ISAAC+ would be more recommendable though, as it fixes some weaknesses pointed out by Aumasson).

As to seeding: a securely generated random seed should indeed suffice, as long as it is generated cryptographically secure.


Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG? If $F$ a PRF, and we construct $G$ using $F$ in the following way:
$$G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$$
where $|s|= n$.

Is $G$ then a PRG? If so how can I prove this? If not how can $G(s)$ be distinguished from a random $r$? And what if $n+1 <$ range of $F_s$? or it could be for any $n > |s|$.

Consider the following game:

I assume certain familiarity with the definitions of Katz and Lindell book (this is exercise 3.14 in the book). In particular, $O$ is denoting an oracle. It can be either a random function oracle (if $b = 0$) or the output of a random function $F_s$ (if $b = 1$). What you do essentially in your distinguisher is query this oracle $l(n)$ times. This is a generalization with respect to your setting. Instead of $n$ one can write an arbitrary polynomial $l(n)$ since the involved algorithms are PPT.

In any case, note that when you gather all the $b_i$ you get $y = G(s)$ or $y$ uniformly distributed in $n \cdot l(n)$. This is because the independent concatenation of uniformly distributed bits is uniformly distributed (?). So, indeed what you have in the last part is a distinguisher for the PRG game.

If you assume that $G$ is not a PRG then we can use an attack $A$ that has non-negligible probability $|P[WIN_{PRG}] - \frac 1 2|$. Then, we realize that one wins in the game PRF if and only if one wins in the PRG game (case distinction on $b$). Therefore, $|P[WIN_{PRF}] - \frac 1 2| = |P[WIN_{PRG}] - \frac 1 2|$ is non-negligible, but this contradicts the definition of PRF.


Secure way to Tally Votes I want to find a secure and efficient way to tally votes.

Say we have N ~ 10000 voters. Each one can vote for candidate 1, candidate 0, or both. But no one can vote more than once. The groups who voted for 1 or 0 want to tally their votes.

Is there a way to tally votes that is fast and cryptographically secure? Perhaps a zero knowledge proof or a ring signature? Thanks!

Yes it is possible, check out the CGS voting protocol: A Secure and Optimally Efficient Multi-Authority Election Scheme. In this voting scheme, each voter encrypts their vote $v \in \{0,1\}$ with Elgamal encryption: ${\it ctxt} = (g^vg^{xy}, g^y)$ under public key $(g, g^x)$. At this point anyone can compute the aggregate of all votes as the componentwise product of all ballots: $(g^{\sum v_i}, g^{x\sum y_i}, g^{\sum y_i})$ and the authorities (who jointly hold the secret key $x$ matching the public key) decrypt this ciphertext.

In order to make this protocol secure against malicious voters, the voters are required to provide a zero-knowledge proof the their encryption is an encryption of 1 or 0 but of nothing else. This is accomplished using the CDS '94 technique, which allows you to compose simple zero-knowledge proofs using (among other access structures) "and" and "or" type predicates. Specifically, the zero-knowledge proof says "this ciphertext is an encryption of 1 OR this ciphertext is an encryption of 0".

In your case, a voter's ballot should consist of two ciphertexts so that they can be tallied independently across voters leading to a tally for each candidate. Accordingly, there should be two "this ciphertext encrypts 0 or 1" proofs.

You do need a way to collect all these encrypted ballots. Voting schemes usually assume the existence of a public append-only bulletin board available to everybody. If access to the bulletin board logs your identity, then you can use those logs to identify double voters and count only their most recent ballot. An alternative is to assume that each voter has a public / private key pair associated to a digital signature scheme. They then sign their votes, and the talliers make sure not to count votes twice that are signed by the same public key.


Attack on textbook RSA with small messages We learned in class that if Alice wants to send a small message $m$, such that $m < N^{\frac{1}{e}}$, so we can break the system using $e$-th square of $m^e$.

But what if Alice knows this flaw and decides to sent $2^{100}\cdot m$ as her message. Is an attacker can still break the system (I assume that the attacker knows that Alice sent $2^{100}\cdot m$)?

The attacker sees $E(2^{100}\cdot m) = (2^{100} \cdot m)^e \,(N) = 2^{100e} \cdot m^e \,(N)$. The attacker can compute $A = 2^{100e} \,(N)$ from public parameters, so he can also compute $A^{-1} \,(N)$ (if not he would already have a factor of $N$). So he then knows $m^e \,(N) = E(2^{100}\cdot m) \cdot A^{-1} \,(N)$ and you can apply the previous attack. This abuses the homeomorphic property of RSA.


Cryptographically Secure Hash Algorithm with Very Specific Property First of all, I apologize if this is a stupid question, but I don't have any background in cryptography.

I'm looking for a secure hash algorithm $H$ with the property $H(K_1+n)\oplus H(K_2+n)=H(K_1\oplus K_2 + n)$.  Would it be feasible to implement a hash algorithm like this, and could a hash algorithm even be secure if it had this property?  If not, would a hash algorithm with the property $H(K_1\oplus n)\oplus H(K_2 \oplus n)\oplus H(K_3\oplus n)=H(K_1\oplus K_2\oplus K_3\oplus n)$ be any better?

Thanks in advance for any comments.

No such function with either property would meet the requirements of a secure hash function; either of those properties would make it easy to find preimages, that is, given a value $H(x)$, you can find a value $y$ with $H(y) = H(x)$.

First off, I assume that $n$ is a constant for the hash function; if we were to assume that the first property holds for any $n$, then it is easy to see that the only function that has that property is $H(x)=0$ for all $x$.

To find a preimage of a function with the first property, we would compute the hashes:

$$H(1 + n)$$
$$H(2 + n)$$
$$H(4 + n)$$
$$H(8 + n)$$
$$...$$
$$H(2^k + n)$$

Then, when given a value $H(x)$, we use Gaussian Elimination to find a subset of the above list ${a, b, c, ..., z}$ with $H(a + n) \oplus H(b + n) \oplus H(c + n) \oplus ... \oplus H(z+n) = H(x)$
Then, because of the property, we know that $H(a \oplus b \oplus c \oplus ... \oplus z + n) = H(x)$.

With a function with the second property, it is only slightly trickier.  In that case, we would compute the list:

$$H(1 + n) \oplus H(0 + n)$$
$$H(2 + n) \oplus H(0 + n)$$
$$H(4 + n) \oplus H(0 + n)$$
$$H(8 + n) \oplus H(0 + n)$$
$$...$$
$$H(2^k + n) \oplus H(0 + n)$$

and proceed as previously.


Encrypted String length in c# I am using AES encryption in my application. I used 3 types of encryption AES-128,AES-192, AES-256 keysize. When I encrypt with different keysize(128 or 192 or 256) with the same text, the encrypted string length is same for all keysize(128 and 192 and 256) whereas encrypted characters only differs. Is this correct? Is the length of the encrypted string length always same for every keysize?

Yes, with most operating modes of AES, the length of the encrypted string is the same regardless of key size (128, 192 or 256 bits).

That's because AES-128, AES-192 and AES-256 all are 128-bit block ciphers, meaning they operate on 128-bit data blocks, regardless of key size. The key determines the mapping of 128-bit plaintext blocks to 128-bit ciphertext block, but the key size is independent of the block size.


Is there a system where multiple people can encrypt a message and then decrypt it in any order? For example, A encrypts a message.

B encrypts that.

C encrypts that.

Then B decrypts, followed by A then C.

Are there systems that allow this? Does such a property have a name?

Yes, systems that allow this have a name: commutative encryption.

In practice, there are two varieties:

If A, B, C just xor in a keystream, it all commutes.  Of course, anyone seeing the intermediate results can deduce quite a lot; this may make this unacceptable for some uses.
Pohlig-Hellman (not related to the Pohlig-Hellman algorithm); we pick a global prime $p$, and everyone selects a secret value relatively prime to $p-1$; A picks $a$, B picks $b$, and C picks $c$.  Then;

Alice encrypts $M$ by computing $M^a \bmod p$
Alice decrypts $C$ by computing $M^{a^{-1} \bmod p-1} \bmod p$

If you go through the math, you'll see that:

Encryption and decryption are inverses of each other, e.g. $\operatorname{Dec}_a(\operatorname{Enc}_a(M)) = M$
It commutes just like you asked: $\operatorname{Enc}_b(\operatorname{Enc}_a(M)) = \operatorname{Enc}_a(\operatorname{Enc}_b(M))$, etc
No one can deduce anything by observing intermediate results (assuming that the prime is large enough to make the DLog and Diffie-Hellman problems hard)


Fast irreversible transformation/compression of short messages using a secret I'm looking for a very fast function $f(m, k) $ that takes a 64-bit integer $m$ and a fixed secret key $k$ of virtually any size (generated by a CSPRNG) and turns them into a 64- or 32-bit integer $ r $, with a few additional requirements:

$ r $ must depend on both $m$ and $ k $ and be reasonably well-distributed
if a pair of $ m $ and $ r $ is known, it should not be possible to efficiently calculate $ k $ or produce $ f(m_1, k) = r_1 $
$ r $ will be used as a kind of a key or tag associated with $ m $, but it doesn't have to uniquely identify $ m $ (i.e. the existence of $ m_1 $, $ m_2 $ such that $f(m_1, k) = f(m_2, k) = r $ is completely normal), so I'm not too concerned about collisions

IOW, I need a way to quickly and irreversibly transform/compress/scramble a fixed-size integer (possibly shortening it) using a secret.
I think ideally this would be solved by a keyed cryptographic hash function like Blake* or Siphash. For example, Siphash was specifically
designed to work well on small inputs and maintain key secrecy, and it's currently used in CPython for hash table lookups.
Performance-wise Siphash-2-4 is maybe tolerable for my use case and seems to check all the boxes, but since I only need to process a 64-bit integer, it feels like an overkill and I'm still interested in anything more lightweight.
I've also looked at several non-cryptographic hash functions and their performance is very appealing, but I'm afraid many of them will fail the second requirement I listed (especially if I feed them $ k || m $, which simplifies brute-force attack in case of FNV-1A and Murmurhash3). XXH3 explicitly lets me provide a secret to customize hash values, and it seems to outperform any other decent hash function in existence, but it's also explicitly non-cryptographic, so unfortunately I'm not sure if it can provide the same level of security as Siphash, even for a use case as simple as mine.
I've also tried creating my own mixing/compression function (which most likely is not secure) and considered using a mixing/compression function from an existing algorithm (most likely not designed to be used separately from the original algorithm).
Am I missing a simpler way to do this?

In the first part of this answer, I restrict to reading requirement 2 as "if one pair $(m,r)$ is known…", and assume that $k$ is chosen at random. I entirely disregard security when an adversary knows two distinct pairs $(m,r)$, or when related keys $k$ are used.
The following construction uses the Galois Field $(\mathbb F_{2^{64}},\oplus,\otimes)$, with some irreducible polynomial¹:
$$f:\{0,1\}^{64}\times\{0,1\}^{128}\to\{0,1\}^{64}\\
(m,k)\mapsto (k_1\otimes m)\oplus k_0=r\\
\text{ where }\ k_1\mathbin\|k_0=k\ \text{ and }\ |k_0|=64=|k_1|$$
Given $(m,r)$ and $(m_1,r_1)$ with $m\ne m_1$, there exists a unique² key $k$ with $f(m,k)=r$ and $f(m_1,k)=r_1$. It follows that the construction perfectly meets it's security objective, regardless of the computational power of adversaries.
Note: For any fixed $k$ with $k_1\ne0$, there are no collisions.
Note: We wan restrict to a smaller output by removing any number of bits from the the result. We can correspondingly shorten the key $k$ by removing the bits of $k$ (in $k_0$) that do not influence the result.
Note: Computation of $f$ is simple and efficient on a CPU with built-in support for binary field arithmetic, including most modern x86 CPUs, which have carry-less multiplication. There's little point to this method otherwise.
#include <stdint.h>
#if OPTIMIZED // for Intel Westmere (2010), AMD Jaguar (2013) and later.
#include <immintrin.h>
inline uint64_t f(uint64_t m, const uint64_t k[2]) {
  __m128i u,v;
  u.m128i_u64[0] = k[1];
  u.m128i_u64[1] = 27;                  // X**64 + x**4 + x**3 + x + 1
  v.m128i_u64[0] = m;
  v = _mm_clmulepi64_si128(u, v, 0);    // u.m128i_u64[0] * v.m128i_u64[0]
  u = _mm_clmulepi64_si128(u, v, 17);   // u.m128i_u64[1] * v.m128i_u64[1]
  return k[0] ^ v.m128i_u64[0] ^ u.m128i_u64[0];
}
#else // no _mm_clmulepi64_si128
#pragma warning(disable : 4146)         // silence silly compiler's warning
uint64_t f2(uint64_t m, const uint64_t k[2]) {
  uint64_t a = k[1], x = (m & -(a & 1)) ^ k[0];
  a = (a >> 1) | (1ull << 63);          // insert sentinel
  do                                    // 63 times
    x ^= (m = (27 & -(m >> 63)) ^ (m + m)) & -(a & 1);
  while ((a >>= 1) != 1);
  return x;
}
#endif

Now I read requirement 2 as "if some number of pairs $(m,r)$ are known…". If said number is large (larger than we are willing to process 64-bit key blocks), we can no longer build a perfectly secure system.
What the question asks can be nicely solved with a 64-bit block cipher, but then there is the question of choosing it. TEA? RC5? Blowfish? Prince? Simon? Speck? One of the lightweight crypto candidates? Any will do. And then we could venture into something custom.

¹ e.g. $x^{64}+x^4+x^3+x+1$, see Joerg Arndt's Binary irreducible polynomials with lowest-most possible set bits. This polynomial happens to also be primitive, but we do not need that property.
² Proof: that $k$ can be found as $k_1\gets(r\oplus r_1)\oslash (m\oplus m_1)$, $k_0\gets(k_1\otimes m)\oplus r$, $k\gets k_1\mathbin\|k_0$.


One-way function and factoring I am confused about the hardness of the one-way function behind cryptography -- if someone could factor the large number produced back into two primes quickly then the one-way function would be broken?
     TIA

Well, there are lots of one-way functions in cryptography.  For most of them, it is not known how being able to factor is of any use  in inverting them.  For example, even if you have black box that can instantly factor any number, we still don't know how to practically find a preimage for SHA-512 (where, by preimage, I mean that, given the value of a hash, can you find a string that hashes to that value).

On the other hand, there are a few one-way functions for which being able to factor allows you to find preimages.  The most common one (and the one you're probably thinking of) is RSA.  In raw RSA, you're given the values $N$ and $e$ (and these two values are jointly known as the 'RSA public key'); the one way function is $RSA_{N,e}(M) = (M^e \bmod N)$.

Now, in RSA, $N$ is a large composite number; if you don't know the factorization of $N$, it's hard to invert; that is, given a random value $X$, it is usually hard to find an $M$ such that $RSA_{N,e}(M) = X$.  However, it turns out that if you do know the factorization of $N$, it's easy.


Would calculating the nth prime ruin encryption? I'm sure there is some proof that the nth prime can be found. But if we knew, would encryption that relies on primes be easy to decrypt?


AES and DES - reusing the same round keys Both DES and AES use key expansion to generate the round keys (for Feistel network or for the AddRoundKey operation). Each round uses a different key. Why do we need that? Why we cannot use the same key in each round?

Before discussion about the Slide attack, first, observe that the DES uses 48-bit key per round produced by it's key-schedule. If the DES uses the same key for every round than the key-space will be $2^{48}$ not $2^{56}$. Therefore it can be trivially broken by simple brute-force of two p3.16xlarge instances on AWS.

The Slide attack

Wagner and Biryokov called your type of key-schedule homogenous. This occurs when the key-schedule produce periodic subkeys and in the simplest case, the period is 1, as in your question.

While the brute-force requires $\mathcal{O}(2^{n})$, the slide attack on block cipher (if works) requires $\mathcal{O}(2^{n/2})$ and for Feistel ciphers requires $\mathcal{O}(2^{n/4})$ since the $F$ function modifies only half of the block.

The attack is independent of round numbers, all it needs the $F$, the round function, is a weak permutation; i.e. given two equations $F(x_1,k) = y_1$ and $F(x_2,k) = y_2$ it is easy to extract the key $k$, as 3 rounds of DES which is a weak permutation.

idea

Let a block cipher with $r$ rounds, then;

$X_j = F_1(X_{j-1})$ where $ 1 \leq j \leq r$ and $x_j$ represent the internal outputs, $X_0$ is plaintext and $X_r$ is the ciphertext.

In the period 1 case, $F_j = F_{j+1}$ for all $j \geq 1$.

slid pair

A pair of $(P,C)$ and $(P',C')$ is called a slid pair if $F(P)=P'$ and $F(C) = C'$.

attack

Obtain $2^{n/2}$ known-plaintext $(P_i,C_i)$ and look for slid pairs. By birthday paradox, it is expected to find to find one pair with this property.

When the round function is weak, testing a slid pair condition will be easy, and some key bit of the cipher will be recovered.

Note: This slide attack requires $2^{64}$ known plaintexts and has a time complexity of $2^{128}$ encryptions for AES and this is greater than exhaustive key search!

Efficient Slide Attacks

Bar-On et. al improved the original sliding attack with their work 1K-AES has that use the same key for every round with data and time complexity $2^{64}$. The result shows that 1K-AES is insecure.

Countermeasures

Don't use periodic key scheduling algorithms
Utilize round constant, as in AES, PRINCE, LED, Simon and Speck,...


About Primitive roots mod n in Diffie-Hellman I'm on the study of Diffie-Hellman and its related math (multiplicative group of integers $\mod n$).

In some crypto papers and documents I've read that $g$ needs to be a primitive root mod $n$ ($g$ order in $G = \phi(p)$), but we actually use $g$ as a generator of a large subgroup of order $q$, where $q$ is a large prime extracted from $(n-1)/2$ ($p$ is a safe prime). So $g$ isn't a primitive root modulo $n$, because $g$ doesn't generate the entire group of $n-1$ but generates a subgroup of length $q$.

I understand that if a prime number (say 'x') divides the group's order then a generator exists whose order in G is 'x'. This is the current schema in the implementations of Diffie-Hellman (like I said before).

Example: $q = 1349363$; $p=2q+1=2698727$. So $\phi(p) = p-1$, $q|p-1$ so a generator $g$ exists whose order in $G$ is $q$.

And here's my opinion: I think this is used because doing modular exponentiation on big generators is slow, so we can use $2$ as a generator. It will generate a lower subgroup of elements, but if $q$ is big enough, it will increase the math performance without being insecure. Correct me if I'm wrong.

But I wish to clear the following doubts:

Why is not recommended to use a primitive root mod $n$ in Diffie-Hellman?
Why do some crypto papers say that a primitive root modulo $n$ is needed?

According to For Diffie-Hellman, must g be a generator?
So a primitive root modulo $n$ (or a true generator) isn't chosen because its order in $G$ is composite. Thus it reveals information about the private exponent. Instead, a generator of a subgroup of order $q$ (factor of |G|) is used, where $q$ is prime and large enough. Is this correct?

The problem you want to make hard in Diffie-Hellman type groups is taking discrete logarithms, whereas you want exponentiation to be easy. Now when you pick a subgroup $G$ of $\mathbb Z^*_n$, the cost of exponentiation will be roughly proportional to $n$ whereas the cost of taking discrete logs will be proportional to $\sqrt{k}$ where $k$ is the order of the largest subgroup in a decomposition of $G$. (Actually, for the number field sieve the formula is more complicated and less than $\sqrt{k}$, but it is still an expression in $k$.) So you want to have $k$ big to get your security up and once you've decided on $k$ you want $n$ to be as small as possible to make the whole thing efficient. In other words, you want to minimise the computation cost to security level ratio $n/k$.

The best possible choice is to let $n = p$ a large prime: if $n$ were not a prime and had nontrivial factors, then $k$ couldn't be larger than the largest of these factors, and all other factors are just slowing things down without adding any security. Since $\mathbb Z^*_p$ has $p-1$ elements which will be an even number, there's always a subgroup of order $2$ and the best possible choice of group order is $q = (p-1)/2$ again a prime (in which case $p$ is a "strong prime"). For such a choice, $k = q$ as it doesn't have any nontrivial factors, so the computation cost/security level ratio is $n/k = p/q$ is approximately $2$, the smallest possible. And in this case any generator is automatically a primitive root.


Known plaintext, unknown 128 bit block cipher I have an encrypted configuration file from an embedded device which I'm trying to decrypt. The file seems to be encrypted in 128bit blocks, as changing a single option causes a 16 byte block to change (all bytes change). The file appears to be encrypted in ECB mode, as blocks of all-zeroes are always encoded the same way.

Is there any way of determining the cipher used, and what are the chances of a known plaintext attack?

All modern block ciphers are supposed to be pseudorandom permutations, meaning that they cannot be efficiently distinguished from a truly random permutation without knowledge of the key.  (If a practical distinguisher were to be found for a particular cipher, that cipher would be considered broken by modern standards.)

This also implies that no two secure modern block ciphers (with the same block size) can be practically distinguished from each other, unless one knows the key being used.  Thus, unless the cipher being used is broken, or unless you can somehow find out the key, the answer to your question is "no".


Diffie-Hellman Key Exchange in $GF(2^5)$ Stuck in a question where the DHKE (Diffie-Hellman key exchange ) is done in the $GF(2^5)$. The irreducible polynomial is $P(x) = x^5+x^2+1$. The $\alpha$ value is $x^2$. If the private keys of $a = 3$ and $b = 12$ what is the session key $K_{ab}$?

Now the calculation of $K_{ab}$ = $\alpha^{ab} \bmod P(x)$. This would translate to $x^{2^{36}}$. Can anyone suggest how to further break this? Should we use the concept of cyclic groups or square-multiply algo here?

To summarize, we are considering a DHKE in $GF(2^5)\cong GF(2)[x]/(P(x))$ where $P(x)=x^5+x^2+1$. The generator element is chosen to be $\alpha=x^2$. There are two parties, let's say $A$ and $B$, with private keys $a=3$ and $b=12$.

First off, I would suggest to compute the public keys of both parties. They are, by definition, $\alpha^a$ and $\alpha^b$. Then there are two equivalent ways to compute the shared secret. That is, either $\left(\alpha^a\right)^b$ or $\left(\alpha^b\right)^a$. Note that the result is not $x^{2^{36}}$.

Then you have to remember that you are working modulo $P(x)$. That is, $x^5=-x^2-1=x^2+1$ inside $GF(2^5)$. We can use this to "break" down polynomials. For example, $$x^6=x\cdot x^5=x\cdot(x^2+1)=x^3+x$$
or $$x^{10}=x^5\cdot x^5=(x^2+1)\cdot(x^2+1)=x^4+2\cdot x^2+1=x^4+1.$$
Applying this technique to $\left(\alpha^a\right)^b$ or $\left(\alpha^b\right)^a$ gives you the correct result.


How does Kerckhoffs's principle apply to Adversarial Neural Cryptography? Martın Abadi and David G. Andersen recently published a paper on arxiv titled: "LEARNING TO PROTECT COMMUNICATIONS WITH ADVERSARIAL NEURAL CRYPTOGRAPHY" (https://arxiv.org/pdf/1610.06918v1.pdf).

I was wondering why Eve neural network $E$ does not get as input the learned parameters $\theta_A$ and $\theta_B$?

If really $K$ is supposed to be the only value that comprises the symmetric key, then in order to adhere to Kerckhoff's principle, one should view the training output (namely, the final values for $\theta_A$ and $\theta_B$) as public information. So, upon "alternating" the training phase to $E$, I supposed $E$ should receive as input $\theta_A$ and $\theta_B$ as well as $C$.

An alternative view would be that the training phase is regarded as a key generation algorithm. In such a view, the only challenge remaining is to really make training very efficient. But I do not think that this view was the intention of the authors because they explicitly contrasted their work to prior work that aims at generating cryptographic keys.

So my initial question still holds. Why is Kerckhoffs's principle (https://en.wikipedia.org/wiki/Kerckhoffs%27s_principle) apparently totally overlooked in this notion of neural cryptography? What am I getting wrong?

If I'm interpreting section 2.2 correctly, the "optimal Eve" $O_E(\theta_A) = argmin_{\theta_E}(L_E(\theta_A, \theta_E))$ is actually allowed to see Alice's parameters $\theta_A$.  The training of Alice and Bob is, in plainer (and rougher!) terms, trying to solve this question: what are the best choices of $\theta_A$ and $\theta_B$ such that if:

We reveal $\theta_A$ and $C = A(\theta_A, P, K)$ to Eve but neither $P$ nor $K$;
We reveal $\theta_B$, $C$ and $K$ to Bob, but not $P$;

...then Eve's ability to infer information about $P$ is minimized but Bob's is maximized?

So I don't think there's a Kerkhoff's principle problem here.  My concern, actually, isn't that Eve knows too little about Alice and Bob, but rather whether Alice and Bob might know too much about their adversary Eve.  If we unwind the definition of the "optimal Alice and Bob" $(O_A, O_B) = argmin_{(\theta_A, \theta_B)}(L_{AB}(\theta_A, \theta_B))$ we find that it refers, indirectly through the definition of $L_{AB}$, to the definition of the "optimal Eve" $O_E(\theta_A)$.  If we chase this down in turn, we find that this definition indirectly refers to the function $E(\theta_E, C)$—the function that, given a choice of parameters $\theta_E$ for Eve, produces her guess $P_{Eve}$ of the plaintext that corresponds to the ciphertext $C$.

So Alice and Bob are allowed to know what function $E$ is.  I think cryptographers would want $E$ to be a universal Turing machine and allow $\theta_E$ to be any polynomial-time program, but it sure sounds like the paper's Eve only considers a subset of that, and that Alice and Bob know which subset that is.  So, in simpler language, I fear that Alice and Bob may know too much about "how Eve thinks" (the membership of the narrow set of functions that Eve can compute).


What are the key differences between the draft SHA-3 standard and the Keccak submission? I just noticed that on the NIST website there is a PDF with a draft of the SHA-3 standard (i.e. FIPS 202) (marked as "new", and seemingly the page was last changed on April 7, 2014).

Previously it was discussed here that NIST would be changing stuff compared to the submission, which was seen as problematic (mainly from a reputation point of view).

Did these discussed changes make it into the draft standard?
What else are the changes in the draft standard compared to the submission?
Are any of these relevant from a security point of view?

No they did not, the internals and security levels have not been changed from the draft Keccak submission, only the padding rule has changed.
The padding change is the only difference, this allows future tree hashing modes as well as the current SHAKE outputs to generate different digests given the same security parameters and message inputs. Up to 4 additional bits are added, which keeps the full padding inside a byte boundary, making implementations with octet only input able to switch to SHA-3 from Keccak with change to only a single line of code.
The padding change has no negative impact on the security of SHA-3.


Why does FS&K's SHAd-256 construction zero-prefix the inner message? Ferguson, Schneier and Kohno's Cryptography Engineering §5.4.2 describes a construction, $\operatorname{SHA}_d\text-X(m)$, which is just $\operatorname{SHA-\!}X(\operatorname{SHA-\!}X(0^b\mathbin\|m))$ (where $\operatorname{SHA-\!}X$ is any particular SHA-2 hash, and $0^b$ represents a full input block of zero bits).

I understand that the second hash is necessary to prevent length-extension attacks.

What I don't understand, and cannot find adequate explanation for, is the rationale for zero-prefixing the inner message $m$.  The book's hand-wavy explanation is that:

  Prepending the message with a block of zeros makes it so that, unless something unusual happens, the first block input to the inner hash function in $h_d$ is different than the input to the outer hash function.

But that is as far as it goes to explain the zero block.

A related but distinct question, "Understanding double hash and 0 block prepending to mitigate length extension attacks," has a partial answer from fgrieu:

  If the $0^b$ in the question's construction was absent, as in $H'(m)=H(H(m))$, we'd have the property: $\forall m,H'(H(m))=H(H'(m))$. We can construct some (largely artificial) protocols which would be secure for $H$, but are insecure for $H'$ due to that property; and correspondingly, that property makes some security proofs hairy, impossible, or weaker. With $H'(m)=H(H(0^b\mathbin\|m))$, that or similar properties do not hold, which is good for simpler/stronger security proofs.

What protocols would be insecure for $\operatorname{SHA}_d\text-X'(m)=\operatorname{SHA-\!}X(\operatorname{SHA-\!}X(m))$?  (To be clear: such a $\operatorname{SHA}_d\text-256'$ construction would not be susceptible to length-extension attacks, right?)  Does the difference matter for any "real-world" protocols that use the $\operatorname{SHA}_d$ construction today?

Is there a good name for this property ($\forall m,H'(H(m))=H(H'(m))$) that I can search the literature for?

If $H(x)$ is a random oracle, then $H(H(0^b \mathbin\| x))$ is indifferentiable from a random oracle[1] (Theorem 5, p. 444; note that [1] uses the name ‘HMAC’ for this particular construction, at odds with the standard meaning of the name), but $H(H(x)) = H^2(x)$ is not[2], and there are protocols that can be exhibited (as [2] does) which are secure if instantiated with $H$ but trivially breakable if instantiated with $H^2$.

The reason that $H(H(0^b \mathbin\| x))$ works as a random oracle is essentially the domain separation of the inner hash and the outer hash: there is no string of the form $0^b \mathbin\| x$ that coincides with a string that $H(\cdot)$ could yield as an intermediate value.

The protocol in [2] that is breakable with $H^2$ but not $H$ is a mutual proof-of-work game:  Two parties aim to prove to each other that they have each spent the work to compute $\hat H^n(x)$ and $\hat H^m(y)$ for some $(n, x)$ and $(m, y)$ chosen by the opposite party, and for some hash $\hat H$.  When instantiated with $\hat H = H$, the protocol works; when instantiated with $\hat H = H^2$, one party can ask the other to compute $u = \hat H^n(x)$ where $x = H(y)$ and $n = m - 1$, and then return $$H(u) = H(\hat H^n(x)) = H(\hat H^n(H(y))) = \hat H^{n + 1}(y) = \hat H^m(y)$$ at a total cost of two $H$ evaluations, rather than $m$ as expected, completely destroying the protocol.

This protocol is contrived.  Maybe your protocol doesn't have this affliction.  But while there is a theorem that $H(H(0^b \mathbin\| x))$ is safe for all protocols, this counterexample means that you have to separately study any protocol that you consider instantiating with $H(H(x))$ to see whether $H(H(x))$ is a problem for that protocol.

The theorem serves as a free cryptographer for everyone to sign off on the use of $H(H(0^b \mathbin\| x))$; if you want to use $H(H(x))$ you have to hire a personal cryptographer of your own to review your particular use of $H(H(x))$, and cryptographers aren't cheap.  If you already have a personal cryptographer (or auditor), the theorem lets them save work auditing your work and spend their time and energy on the rest of the work.


Homomorphic encryption or double symmetric encryption? I am new to Homomorphic Encryption.

The scenario is that the encrypted data will be sent from Alice to a trusted cloud machine for computing operations and then sent to Bob. Can HE (e.g. NTRU) be faster than using symmetric encryption and having to decrypt the data from Alice, do operations, and encrypt again to sent to Bob (e.g. AES)?

As CodesInChaos mentioned in the comments: If you have a trusted party, you don't need homomorphic encryption.

More to the point of the question-- No.

A "reasonably optimized" (especially, like NTRU, fully) homomorphic encryption scheme should always be somewhat slower / less efficient than using plain symmetric-key encryption (and 'plaintext operations' outside of a ciphertext).

To see this is not just true, but should ALWAYS be true: Note that any FHE scheme is also a symmetric-key encryption scheme (ignore the homomorphism; let the scheme's public-key be kept secret as a private encryption key). Extra features can't come for free. The best you can hope for is 'not much overhead in practice,' but (F)HE will never be faster in general.

Bonus thought: Short, and hopefully more intuitive, "proof" that FHE.Eval is /always/ going to be more expensive than the SYM-1.Dec + basic operations + SYM-2.Enc option--

Note that the decryption operation in EVERY KNOWN fully homomorphic encryption scheme is close-to-linear time: With lattice cryptosystems, you're always performing inner product of a ciphertext-vector $c$ with a key-vector $s$ (then rounding) in order to decrypt. No matter how much computation you do, the encrypt/decrypt cost remains the same.

Further, assume each 'plaintext operation' of cost "C" has cost at least "C+1" when you perform it homomorphically. ("Only +1" is quite generous.) Since FHE should allow unbounded computation, just consider computing FHE.Eval longer and longer until the "C+1"-per-operation overhead offsets the small, one-time cost of encrypting/decrypting.


Is it possible to derive a constant value from different signatures of a private key? For example perhaps deriving the same PRF from RSA signatures on different messages from a (not known) private key?
Struggling to find the proof of why not.

I understand the question to mean: is there a function $F$ whose domain is signatures under a public-key signature scheme such that, given a signature $s_1$ made with a key $k_1$ and a signature $s_2$ made with a key $k_2$, $F(s_1) = f(s_2)$ if and only if $k_1 = k_2$? Or in simple terms: can you tell who made a signature by looking at it?
You aren't going to find a generic proof of impossibility because it is possible to build signature schemes for which $F$ exists. In fact, any signature scheme can be adjusted to make $F$ possible. Given a signature scheme whose signature function is $S$, define a new scheme whose signature function is $S'(k_{\mathrm{priv}}, x) = (S'(k_{\mathsf{priv}}, x), k_{\mathsf{pub}})$ where $k_{\mathsf{pub}}$ is the public key associated with $k_{\mathsf{priv}}$. In simple terms: attach the public key to the signature. This new scheme is just as secure as the original since the new signature function doesn't reveal any more information than the original and doesn't have equality cases that the original doesn't have.
For ECDSA, given a curve with the generator $G$, its order $n$, and two key pairs on this curve $(d_1, Q_1)$ and $(d_2, Q_2)$, here's a way to construct signatures that are valid with both keys. Note that they are signatures of different messages. Given a nonce $k$ and a message $m_1$, the signature under the first key is $(r, s)$ where $r$ is the x-coordinate of $k G$ modulo $n$ and $s = k^{-1} (H(m_1) + r d_1)$. Let $e_2 = k s - r d_2$. If there exists $m_2$ such that $H(m_2) = e_2$ then $(r,s)$ is the signature of $m_2$ under the second key. Hash functions are not necessarily surjective, so $m_2$ might not exist, but if $H$ is sufficiently indistinguishable from a random oracle, the proportion of values of $k$ such that $m_2$ exists is the size of the image of $H$ among bit-strings of the appropriate length, so many values of $k$ are suitable.
Note that this is a (sketch of a) proof of existence. Finding actual examples (at least with this method) is infeasible since it requires calculating a pre-image under the hash function.
I haven't worked out the math for RSA. I think that due to the longer signatures, it is not the case in general that given two key pairs, there exists a pair of messages such that the signature of the first message with the first key is equal to the signature of the second message with the second key. I expect that this is true with high probability when the hash is sufficiently longer than half the key and false with high probability when the hash is sufficiently smaller than half the key.
Note that if you require the signatures to be of the same message, the answer is completely different. With a known message, ECDSA allows key recovery. This is not true for RSA.
A more interesting version of this question in practice is, given a signature, or more generally a set of signatures made with the same key, and a collection of public keys, is it possible to tell with a non-negligible probability which key made this or these signature? This is the problem of key privacy for signature. RSA does not have key privacy. Ed25519 looks like it might have key privacy.


Can I increase strength of ECB by decorrelating input data with compression I know that ECB block cipher mode is the weakest method of encryption because repetitions in input data with a stride of a block size lead to repetitions in output data.

However, as I may consider, elimination of repetitiveness should give a stronger result like for other modes (CBC, etc.). In addition, I know that compression algorithms are just designed specially for searching and removing certain types of correlations.

Let's consider input data are compressed using DEFLATE algorithm via zlib 1.2.11 with the highest compression level possible (9). How does such an approach increases the strength of ECB?

Update: My goal is to increase encryption speed by parallelization. I receive UTF-8 texts already deflated as specified in the previous paragraph, encrypt it with a user-supplied key, and put it to cache storage in a user folder.

One problem with this approach is that both most compression algorithms and most block ciphers in ECB mode are deterministic. In other words, if you encrypt the same text twice, even if it has been compressed before, this fact will be obvious from the ciphertext.

I'd recommend you to have a look at counter modes, in particular AES-GCM (Galois/Counter Mode). They allow you to perform encryption in parallel without suffering from the problem outlined above (provided you use different IVs for each plaintext, as you should).


AES S-Box Lookup Table Hardcoded? From what I've looked up on various AES projects, the impression I get is the lookup table is hardcoded with the values from this Wikipedia entry page:

https://en.wikipedia.org/wiki/Rijndael_S-box

Am I correct in this assumption or is the lookup table on that page just for initialization and the table gets updated once further rounds are done in AES?

When doing an implementation based on tables, yes, it is customary to hardcode the table. Some extra notes:

Usual table-based implementations of AES merge the S-box application step ("SubBytes") with the subsequent linear operation ("MixColumns"). In that case, the hardcoded table has 256 entries of 32 bits each (and some implementations use four distinct tables to merge "ShiftRows" as well, in order to avoid computing rotations).
In some languages where there is an explicit initialization step, such as Java or C#, it is customary to use it to recompute the tables instead of hardcoding them; this makes the source code clearer and the binary size smaller, at the expense of some extra CPU cost when first using the code in the application. You can find an example of that in BoarSSL, a C# SSL library (used to serve as test system for BearSSL, which is written in C); the table building is done in the static class initialization code (lines 326 to 430).

Not all AES implementations are based on tables, though. In fact, using lookup tables is problematic because of cache attacks (memory accesses at addresses that depend on secret data may leak information based on how memory caches in the CPU are impacted). "Constant-time" implementations avoid making such accesses, and instead will evaluate the S-box with non-table operations. For these, the algebraic structure of the S-box definition is very convenient, because it helps making a more efficient circuit. In 2009, Boyar and Peralta have worked out a nice circuit of boolean gates that evaluates the AES S-box in 115 boolean operations; it has been used in a bitslice context by Käsper and Schwabe to make a very efficient and constant-time implementation of AES (in CTR mode): their code is not only robust against cache attacks, but it is also about twice faster than classic AES implementations that use tables.

For more information on constant-time cryptographic implementations, see this page.


Mathematics behind end-to-end encryption I am interested in end to end encryption, recently I read some articles on its principles but I can't find anything on the maths behind the encrypting and decrypting functions that relates private and public keys. I remember to have read that they are related with prime numbers and elleptic functions but I haven't find anything else.

Can anyone tell me something else about it or suggest me an article/book on it?

End-to-end encryption refers only to the -- somewhat tautological -- fact that encryption happens on both ends and any intermediates do not have access to the keys, not to the specific math behind it.
Since the keys have to be available to both ends, public key cryptography is usually the preferred method, because the private key for each end is not transmitted to the other end, and therefore cannot be intercepted unless either end is compromised.

Also wether it is factoring-based (i.e. RSA algorithm), or elliptic-curve based refers to the method of getting the function leading to the encrypted message, which is difficult to reverse.

The basis of cryptography is quite algebra-heavy, depending on your background; that said one introductory book is  Hoffstein's: springer.com/us/book/9781493917105

Either way it's probably easier than going through the original literature on the topic. Otherwise, you may want to start with a more conceptual primer, here's one

https://blogs.msdn.microsoft.com/plankytronixx/2010/10/22/crypto-primer-understanding-encryption-publicprivate-key-signatures-and-certificates/

https://arstechnica.com/security/2013/10/a-relatively-easy-to-understand-primer-on-elliptic-curve-cryptography/

hope that helped.


Collecting entropy from a stream to a file I have a potentially infinite stream of data originating in some physical phenomena that may expose random behavior (due to quantum effects, thermal noise, the butterfly effect in chaotic dynamical systems, etc). The stream may carry some amount of entropy (true randomness), but it may be distributed unevenly throughout the stream and its density is unknown.

I have a limited storage space (say, 1GB). I need a procedure that can collect as much entropy as possible from the stream to the storage provided, and, when required, generate (in a reasonable time) a single file containing the collected entropy. It is preferable to make the resulting file as small as possible without reducing the amount of entropy it contains.

How can I implement such a procedure?

Partition the file into blocks of almost-equal size, and let $B$ denote the maximum block size (in bits). $\:$ Choose a randomness extractor whose outputs are long enough to

sample from the blocks and still have $B$ bits of the output left over.

Choose a seed for the extractor (unless you choose an extractor that doesn't actually use one).

For each [extractor's source's size] bits from the stream, apply the extractor to those bits,

use the output to sample a block as described before, let $s$ be the number of bits in that block,

set that block equal to its old value plus the left-most $s$ bits of the remaining extractor output

(both interpreted as unsigned integers) mod 2$^s$, then if any of the extractor's

output is still unused, continue as if those were the next bits from the stream.


Is it possible to create an asymmetric cryptosystem where the private keys are not easily verifiable as such? Plaintext that consists of an RSA key is easily recognizable as such, because it satisfies certain mathematical properties, in particular (See the answer for Why can an encrypted private key be brute forced?):

$$d = e^{-1} \mod  (p-1)(q-1).$$

Is it impossible to design a public key system where it was harder to verify that the decryption of the key was successful?  The usual answer to protect an encrypted key from being brute forced is to use a larger key size, but I thought hard to recognize plain-text is a good property to have in an encryption system?

A key pair (private key and corresponding public key) is always "verifiable" by simply trying to use it. E.g., if this is a key pair for a signature algorithm, then you can try to sign some data with the putative "private" part, and see if the signature can be verified with the "public" part. There is not much you can do about that.

"Hard to recognize plaintext" was thought as a line of defense in cryptosystems from, say, the 1930s. This was before the invention of the computer, hence algorithms had to be performed by hand or through relatively simple electro-mechanical apparatus. Invariably, they were quite weak and needed the extra safety of having a relatively uniform distribution of plaintext data elements. But we are now in 2011, and we have big computers and good algorithms. To state things plainly: if having a "hard to recognize plaintext" makes any difference, then your encryption algorithm sucks.

With a modern symmetric encryption systems (e.g. AES-128 with CBC mode), plaintext internal structure is not an issue.


Could public-key crypto be performed long ago if the idea had been discovered? Public-key cryptography was not invented until the 1970's. Apart from the idea not existing earlier (as talked about here), is there any reason it could not have been used earlier? For example, are there forms that are easy enough to perform by hand but complicated enough to not be solved (easily) by hand?

What an interesting question! Yes, it certainly could. The math required to carry out RSA encryption, for example, have been known for millennia. The most complex algorithms are:

Primality testing for key generation. I think that the first efficient algorithm was Fermat's, from ~1600
Euclid's, which is from 300 BC
Binary exponentiation, which I couldn't find when it was
discovered, but I'd guess it's pretty old too
Even the Chinese Remainder Theorem, which can speed up the RSA computation, is from 300 AD.

So, if someone discovered RSA and also Fermat's primality testing, then it would be possible to use RSA millenia ago.

People wouldn't need to use keys as large as in use today since any attacker would also need to do calculations by hand. The first efficient (sub-exponential) factorization algorithm, the continued fraction algorithm appeared in 1931. So an attacker would need to brute force the key with trial division, in $O(\sqrt{n})$ steps. In 1903, a 67-bit Mersenne number was factored. Leaving 2 bits of breathing room (the calculation took half a year, 3 additional bits would make it take four years), then $(67+3) = 70$-bit (21-digit) keys would be more or less safe against brute-forcing by hand. This seems to be an overestimation, though, since calculators existed at that time, see this discussion.

20-digit calculations seem a lot, but considering it may be overestimated, it seems using RSA millenia ago would be possible.

These are all approximations though, someone with deeper knowledge of math history should be able to shed more light in this question. (Maybe this question would even fit the Math.SE better)


Can I use a fixed IV with AES-GCM if I only encrypt unique plaintext values? My use case guarantees that all plaintext values are unique. In this case, is it safe to use a fixed IV with AES-GCM to carry our encryption/decryption?

No, when an IV is repeated as in $C_1 = \textsf{GCM}(K,IV,M_1)$ and $C_2 = \textsf{GCM}(K,IV,M_2)$, the resulting ciphertexts leak $M_1 \oplus M_2$ to an eavesdropper. This is because GCM is based on CTR mode which has this property.

Authenticity also completely breaks in this scenario, although it's not a one-liner explanation.  An attacker who sees $M_1, M_2, C_1, C_2$ can forge arbitrary ciphertexts.


How many hashes for high probability of finding a collision (specific case)? Suppose Bob managed to obtain 220 different digests that were generated
by a hash function employed by a target system. The hash function outputs 8-byte
digest of a message. Bob now wants to find a message that hashes into 1 (one) of the
obtained digests. How many different messages should Bob approximately hash until
there is a good probability that a generated digest will match 1 of the obtained
digests?

My answer is $\sqrt{2^{64}}$ ($= 2^{32}$) messages for a probability of 0.5. Is this correct?

Let's assume that there are no prior collisions (two different messages that generate an identical hash) for the first $2^{64}$ messages.

If you want to find a message for one hash then you would have to try all these $2^{64}$ messages to reach the probability of 1 (100%). Since you mentioned good probability we can say that we would have to try half of that for a probability of 0.5 (50%). That means that we would have to try $2^{64} / \space 2$ possibilities which would be $2^{63}$.

Now you also already have a list of 220 hashes. That means that you can reduce it because we previously only calculated it for one hash, so the solution is:

$$\frac{2^{63}}{220} \approx 4.2 \times 10^{16}$$ for a probability of $0.5$ to find a message that hashes to one hash in your list.


Can we develop a working asymmetric crypto message protocol without an asymmetric encryption algorithm? Our crypto libraries have:

DSA (4096, 512)
DH (4096)
AES (256)
SHA (512)

Let us say these are implemented directly in hardware so that trying to pull the pieces out is not possible, and the CPU isn't really fast enough to implement crypto itself.

Can we develop a protocol that permits us to exchange public keys, and at some later date send messages by courier or some means that does not assume live communication. That is, DH won't work directly because message round-trip time is intolerably long.

This question is far more interesting on a theoretical basis than any practical means by which I might have gotten here.

Use DLIES, which is essentially Diffie-Hellman with an ephemeral sender key. Assuming you know the receiver's public key, that will cost no extra round trips.

The sender does:

(eph_sender_private, eph_sender_public) = Generate_Key_Pair()
shared_key = SHA-512(Diffie-Hellman(receiver_public, eph_sender_private))
ciphertext = Encrypt(shared_key, message)
encrypted_message = (eph_sender_public, ciphertext)

The receiver does:

(eph_sender_public, ciphertext) = encrypted_message
shared_key = SHA-512(Diffie-Hellman(eph_sender_public, receiver_private))
message = Decrypt(shared_key, ciphertext)

Where Encrypt is authenticated encryption build from AES and SHA-512. For example you could follow the RFC Draft Authenticated Encryption with AES-CBC and HMAC-SHA which includes test vectors to minimize the risk of your messing it up.

If you feel fancy, replace the simply hashing in the shared key derivation by a proper KDF, such as HKDF-SHA-512.

To authenticate the sender, sign the message using a long term DSA key, which should be distinct from the long term DH key.


Effect of message length on collision attacks I know that message collisions are supposed to be hard to calculate for a good cryptographic hash.

Given 1k worth of data, it's hard to find another 1k worth of data that collides with the same hash.

But doesn't it become much easier when the message becomes variable length? I.e. it's easier to find a collision in 0-1G of data to 1k of data than it is to find one that is also exactly 1k of data.

Does knowing the intended size of the message increase the strength of USING the hashing function? I.e. a message has to be between 1k and 4k.

The short answer is that for any secure hash it is impossible to generate collisions or second preimages, regardless of message length.

If you look at theoretical attacks, however, message length can be a factor. When looking for another message that hashes to the same value as a specific message you are talking about second preimage resistance (or target collision resistance) and there the length of the target message may matter. For example, with Merkle-Damgård hash functions there are attacks that find second preimages for messages faster the longer they are.

With a collision attack, where you look for any pair of messages hashing to the same value, I do not know of a case where message length matters. Beyond allowing enough input length to exhibit collisions, of course: finding e.g. 1-byte collisions is impossible.


What is the correct name for bytes which are to be signed? I have some bytes, and I sign them with my private key using ECDSA. The resultant (71) bytes are the signature.

But what is the name of the bytes I have signed? (If this were encryption, they would be called "plaintext".)

The correct term for bytes to be signed is “message”.
Generally, it does not really matter if a message to be signed is human readable or not. Sometimes, you may also find it mentioned as “digital message”… which practically is the same and merely extends the term to explicitly hint at the fact the message is digitally stored and/or processed.
References showing the use of the term can be found at various sources. For example: scientific papers and websites talking about cryptography and/or cryptanalysis in relation to digital signatures.
For your convenience, here are a couple of quotes showing its usage (bold-italic emphasis is mine):
randomly picked, yet well-known websites

source: https://en.wikipedia.org/wiki/Digital_signature

… Digitally signed messages may be anything representable as a bitstring: examples include electronic mail, contracts, or a message sent via some other cryptographic protocol. …

source: https://support.office.com/en-us/article/Secure-messages-with-a-digital-signature-549ca2f1-a68f-4366-85fa-b3f4b5856fc6

… By digitally signing a message, you apply your unique digital mark to the message. … This information proves to the recipient that you signed the contents of the message …

randomly picked, yet well-known crypto-related papers

source: Identity-based cryptosystems and signature schemes by A Shamir - Advances in cryptology, 1985

… However, when g is known, there is a very simple way to generate any number of signatures of any message even when the factorization of n is unknown. To sign the message m, the user chooses a random number r …

source: A digital signature based on a conventional encryption function by RC Merkle – Advances in Cryptology (CRYPTO'87), 1988

… If A wishes to sign message m …

source: Group signatures by D Chaum, E Van Heyst – Advances in Cryptology (Eurocrypt'91), 1991

… If person i wants to sign message n, he chooses randomly some set r of persons (including himself); his signature will be … If person i wants to sign message m=An), he randomly chooses …

source: The exact security of digital signatures-How to sign with RSA and Rabin by M Bellare, P Rogaway – Advances in Cryptology (Eurocrypt'96), 1996

… In order to sign message M , the signer first picks a random
seed T of length …


Is the "decapsulate" function from lattice based cryptography homomorphic? Observing the code example from pqcrypto-kyber, is the decapsulate function $d$ homomorphic?

If $d(ct, sk_i) = ss_i$, is it true that $d(ct, \sum_i sk_i) = \sum_i ss_i$ ?

Kyber claims to be CCA secure. CCA schemes cannot be homomorphic (thinking through this may be a useful exercise).

It may be useful to try to work through this particular example with pen and paper by looking at algorithm 5 in the Kyber paper. Note that what is returned is some hash, which you should not expect to have homomorphic properties.


Composition of block ciphers and 3DES There is some intriguing things about DES and 3DES. Now, I know that DES is weak and 3DES was an attempt to construct a more secure block-cipher from a deprecated one.

Having this in mind, what about the composition of two independent instantiations of block-cipher (t.i.t.s with two independent keys) having a reduced number of rounds. Take the example of AES (with key of 128-bit) which has 10 rounds (and consider that the last round is complete, in the sense that it contains all the operations add-roundkey, mixcolumns, shiftrows and subbytes). If we consider a reduced version of AES with 5 complete rounds, denoted $AES^r$, and we construct a new block cipher in the following way:

$$AES'_{k_1,k_2}(.)=AES^r_{k_1}(AES^r_{k_2}(.))$$

Is this block cipher as secure as the original version of AES ?
It seems to me that it does, since the keys are independant, but I need confirmation.

Edit: Is the following composition also secure ?

$$AE''_{k_1,k_2}(.)=AES^r_{k_1}({AES^{r}}^{-1}_{k_2}(.))$$

where ${AES^r}^{-1}_{k_2}(.)$ denotes the decryption operation.

Thank you.

Well, whether $AES'$ is as secure as $AES$ depends on the length of $k_1, k_2$.

If they are both 128 bit, then what you effectively have is a standard 128-bit AES, except that prior to round 6, you replace the running key with an independent key (and you tweaked the last round, but that's cryptographically harmless).  Now, it is never a good idea to do random tweaks on ciphers, however, this appears reasonable to conjecture that this one is harmless; that the security of the cipher does appear unlikely to depend on the relationship of the subkeys in round 5 and round 6 of standard AES.  This, of course, assumes that we are interested solely in the standard attacks (chosen-plaintext, chosen-ciphertext); if we are allowed to consider related-key attacks, this construction may well be weaker.

On the other hand, if $k_1, k_2$ are each 64 bits (with the $AES^r$ subkey derivation process being somehow modified to take a 64 bit key), then what we have is definitely weaker than standard AES (even though $AES'$ takes a 128 bit key); even against a known-plaintext scenario.

This is due to a standard meet-in-the-middle attack, where to find the values $k_1, k_2$ that solve the equation:

$AES'_{k1,k2}(P) = AES^r_{k1}(AES^r_{k2}(P)) = C$

for some known plaintext/ciphertext blocks, the attacker just computes:

$F(k_1) = AES^r_{k2}(P)$

$G(k_2) = {AES^r_{k1}}^{-1}(C)$

for all $2^{64}$ values of $k_1, k_2$, and searches the lists to find a pair $F(k_1) = G(k_2)$.  This gives him solutions for $AES'_{k1,k2}(P) = C$ in $O(2^{64})$ time.


Generating unsigned, bounded random value using signed bounded random values Use case: I have a random number generator that can generate random numbers in a range that is limited by a number $x$, say $x$ ranges from $2$ to $2^{(n - 1)} - 1$ exclusive. In this case $n$ is $16$, i.e. we can generate a number from $0$ to $32767$ exclusive. Programmers will directly identify the upper bound to be a possitive, signed value of 16 bits.

Now I want to generate a bounded number from $0$ to $y$, where $y$ ranges from $2$ to $2^n - 1$, i.e. we can generate a number from $0$ to $65535$ exclusive. Yes, this is an unsigned value of 16 bits. Is there an algorithm that can do this efficiently? Loops are allowed; the random in the range $0$ to $x$ may be generated repeatedly.

If this is not possible, I have no problem allowing $0$ to $65533$ exclusive because $32766 * 2 = 65532$ and generating $65533$ and $65534$ could significantly increase the complexity.

All generated random values must have a uniform distribution.

I assume $R(x)$ is the original generator, returning $r$ uniformly distributed with $0\le r<x$ for $x<2^{n-1}$, as does Java's int nextInt(int) for $n=32$; and we want to extend that to $R'(y)$, returning $r$ uniformly distributed with $0\le r<y$ for $y<2^n$. $R$ and $R'$ should treat an argument less than $2$ in the same way (perhaps accept it and return $0$, or reject if somehow). Out of laziness I'll only handle $n$ even and $n>2$, which covers practical use cases.

If $y<2^{n-1}$, $R'(y)=R(x)$ is fine.

If $y=a\cdot b$ with $a>1$ and $b>1$, $R'(y)=b\cdot R(a)+R(b)$ is fine. That is useful when $y$ is known at compilation time and composite.

Else (when $y\ge2^{n-1}$ and prime), there is no method guaranteed to work with a finite number of invocations of $R$, and we must use some iterative method.

Out of my head (not tested), a possible line of action when $y$ is known only at runtime:

if $y<2^{n-1}$, return $R(y)$.
if $y$ is even, return $2\cdot R(y/2)+R(2)$.
if $y=2^n-1$, return $(2^{n/2}-1)\cdot R(2^{n/2}+1)+R(2^{n/2}-1)$.
repeat

let $r:=R((y+1)/2)$
if $R(2)\ne0$, return $r$.
if $r\ne0$, return $y-r$.

Notes:

With the assumption that $n$ is even, we can handle $y=2^n-1$ as $(2^{n/2}+1)\cdot(2^{n/2}-1)$.
When $R((y+1)/2)$ is computed, this is valid since $1<(y+1)/2<2^{n-2}$.
At each iteration of the loop (which occurs only for odd $y$), the value returned (if any) is correctly distributed because:

$r$ is returned with odds $1/2$, and then is uniform on $[0\dots(y-1)/2]$
$y-r$ is returned with odds $1/2-1/(y+1)$, and then is uniform on $[(y+1)/2\dots y-1]$
the "repeat" loop continues with odds $1/(y+1)$, which is at most $1/2^{n-2}$, and thus low for practical $n$.

We can lower the expected number of calls to $R$ (by $46\%$ for $n=16$ and $2^{n-1}\le y<2^n-1$) by accumulating $n-2$ uniform bits (and a sentinel) in a variable $b$ surviving across invocations, set to $0$ initially (in the C programming language, that could be static short b = 0; in the body of a function). It is however at the expense of increased complexity, and perhaps of thread-safety, and thus a bad idea in most practical situations! The algorithm (not tested) can become:

if $y<2^{n-1}$, return $R(y)$.
if $y=2^n-1$, return $(2^{n/2}-1)\cdot R(2^{n/2}+1)+R(2^{n/2}-1)$.
repeat

let $b:=\begin{cases}R(2^{n-2})+2^{n-2}& \text{if }b<4\\\lfloor b/2\rfloor&\text{otherwise}\end{cases}$
let $r:=R(\lfloor(y+1)/2\rfloor)$
if $b$ is even, return $r$.
if $y$ is even, return $y-1-r$.
if $r\ne0$, return $y-r$.


Stream Ciphers and cycling questions For all PRNGs (including CSPRNGs) lets say there is a sequence x, y, z, then when the PRNG cycles back to x, then the sequence following it will be exactly the same as before. Is this true for all PRNGs?
Are there any rules about minimum cycle length for CSPRNGs used for Stream Cipher? Because if a cycle happens, then the One Time Pad is no longer a One Time Pad and becomes insecure, right?
What are the average cycle lengths for commonly used Stream Cipher algorithms?
Is it not possible to prevent cycling by making the algorithm dependent on what it is encrypting - i.e. something like

The stream cipher is used for encrypting communication between Alice and Bob. Alice's key is K1 & Bob's is K2.
This is the conversation

Alice: Hello, Bob
Bob: Hello, Alice
Alice: How are you?

So

K1 is used to generate the stream for encrypting "Hello, Bob" and it's sent.
The next stream generated not only depends on state of the PRNG after generating the stream for "Hello, Bob" but "Hello, Bob" is also used as input for this stream. And this will be used for encryption "How are you?" and so on.

A PRNG has an internal finite state. The value of that state determines all subsequent outputs; that's the point of the PRNG being a deterministic engine. Whenever the PRNG produces a new output element, its internal state evolves into a new value. Since the internal state is finite in size, it is a mathematical certainty that the PRNG, at some points, enters a cycle and never leaves it.

The details are worth analysing:

The PRNG will enter a cycle, not necessarily start on the cycle. For instance, if the PRNG state $S$ has size $n$ bits, and, when the PRNG outputs an element, the state $S$ is replaced with $h(S)$ for some hash function $h$ with an output of $n$ bits, then, on average, the cycle will be reached after about $2^{n/2}$ steps, and the cycle length will also be about $2^{n/2}$. You won't get back to the initial state.
This is about the internal state, not the output. If you get at some point output element $x$, then later on obtain $x$ again, then you did not necessarily completed or even entered a cycle, because two distinct internal state values may yield the same output element.
In practice, for a cryptographically secure PRNG, the cycle cannot be completed or even reached, it is way too large for that. The cycle length used to be a sort of traditional measure of "security" but it does not play this role nowadays. Any cycle length beyond $2^{128}$ is as good as "infinite".

A stream cipher is an encryption system specialized in the encryption of bulk data. Many stream ciphers operate like PRNG: from they key, they produce a long sequence of pseudorandom bits, which is combined by XOR with the data to encrypt or decrypt. In such a case, the internal PRNG state is not impacted in any way with the data that is encrypted. However, some other stream ciphers modify their internal state by injecting the encrypted data as well. When the data is injected, this changes the situation with regards to cycles: if the data to encrypt is not cyclic, then you won't get a cycle.

Block ciphers can be turned into stream ciphers by using some modes of operation, in particular CFB, OFB and CTR. The CFB mode injects the encrypted data into the internal state; OFB and CTR do not. With a block size of $n$ bits (e.g. $n = 128$ for AES), then CTR offers a cycle length of exactly $2^n$ blocks, i.e. $n2^n$ bits; OFB cycle length is more random (if you are terribly unlucky you could hit a short cycle).

A condition for a stream cipher to be deemed "secure" is that its output is computationally indistinguishable from randomness even when encrypted a long sequence of zeros. A consequence is that in a secure stream cipher, the cycle cannot be fully walked or even simply reached in practical terms. Beyond that point, cycle length has no meaning for security.


Security in case of Malicious and Augmented Semi-Honest Adversaries On page 29 of Book Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay, there's this proposition:

  Let π be a protocol that securely computes a functionality f in the presence of malicious adversaries. Then π securely computes f in the presence of augmented semi-honest adversaries.

There's a proof following this proposition. In the proof, they say that the distribution over messages will be identical since the real adversary will follow the protocol exactly. But since an augmented semi honest adversary might change the input, won't the distribution over messages change as well?
Also, why can't a similar proof be drawn for security in case of semi-honest adversaries?

Moreover, is the definition of security in case of augmented semi-honest adversaries analogous to that in case of malicious adversaries? In the book, I was unable to find a formal definition of security for augmented semi honest adversaries.

P.S: This is the proof:

  Let π be a protocol that securely computes f in the presence of malicious adversaries. Let A be an augmented semi-honest real adversary and let S be the simulator for A that is guaranteed to exist by the security of π (for every malicious A there exists such an S, and in particular for an augmented semi-honest A). We construct a simulator S′ for the augmented semi-honest setting, by simply having S′ run S. However, in order for this to work, we have to show that S′ can do everything that S can do. In the ma- licious ideal model, S can choose whatever input it wishes for the corrupted party; since S′ is augmented semi-honest, it too can modify the input. In addition, S can cause the honest party to output abort. However, S′ cannot do this. Nevertheless, this is not a problem because when S is the simulator for an augmented semi-honest A it can cause the honest party to output abort with at most negligible probability. In order to see this, note that when two honest parties run the protocol, neither outputs abort with non-negligible probability. Thus, when an honest party runs together with an augmented semi-honest adversary, it too outputs abort with at most negligible probabil- ity. This is due to the fact that the distribution over the messages it receives in both cases is identical (because a semi-honest real adversary follows the protocol instructions just like an honest party). This implies that the simu- lator for the malicious case, when applied to an augmented semi-honest real adversary, causes an abort with at most negligible probability. Thus, the aug- mented semi-honest simulator can run the simulator for the malicious case, as required.

As pointed out in the comments, an augmented semi-honest adversary is one who can change its input before the protocol execution begins, but from then on the adversary runs the protocol specification exactly.

Note that if a protocol is secure for malicious adversaries, then the simulator must be able to work also for an adversary who changes its input and then behaves honestly. Thus, the protocol is secure also for augmented semi-honest adversaries.

The reason that this does not work for semi-honest adversaries is because the ideal-world simulator for a semi-honest adversary cannot change the input. That is, in the case of malicious adversaries, both the real adversary and the ideal simulator are stronger than for semi-honest adversaries. This fact means that security for malicious adversaries does not necessarily imply security for semi-honest adversaries (because the ideal simulator cannot run in the semi-honest case if it needs to change the input of the corrupted party). In the book, we give an explicit counter-example of a protocol that is secure for malicious adversaries but not for semi-honest. I know that this is extremely counter-intuitive, but that's the reality.