Multi User limited Time Encryption of big Datasets Updated Question: New Thread

Original Question: (Thanks cypherfox for answering that one)

I am in need to store data > 100 TB on a local network share (NAS/SAN) and grant individuals access to the encrypted data. For all users, besides me, the data can be read only, and sequential access to the data (only one user can access the data at one time) is fine.

The biggest problem is that I need to revoke individual users access from time to time (in addition to the recall of the network share access). I could encrypt the master key with user individual keys but this would not prevent technical experienced users from stealing the master key right? So I would need to re-encrypt the data every-time a user is recalled. Is there a way to do this more efficient than copying all data to a new encrypted image/disk? For 100 TB this would need more than 9 days.

Maybe someone can give me an advise which system/tools/techniques I should use and where the decryption should take place (client/server). Here the summarized key facts:

~ 100 TB Data
max 5 user at the same time or 20 over the whole time span
data stored an a local NAS/SAN connected to an 'offline' network
the files have easily multiple GB, so some kind of transparent decryption to avoid copying the data would be necessary
even a user could copy the data while he is a regular user, and even if he has no network share access anymore, we need to depreciate his decryption access

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

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

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

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


Tools for modelling and analysis of cryptographic protocols I am designing some cryptographic protocols and I am new to it.
Are there any well-known tools that can be used to model and design these protocols?
And also verify or analyze their validity?

If not a tool, is there any popular approach or formal method to design and analyze crypto protocols that are  widely accepted?

I am searching for some tools like NRL Protocol Analyzer. Are there any other popular such tools that are considered more sophisticated?

There are a couple of options for protocol analysis tools.
(I don't know any established tool for their design - as said by someone else, designing your own protocols is not really recommended.)

If you are looking for formal methods based, symbolic tools, some well-known tools that have been applied to many protocols are ProVerif and Scyther. Given that you were looking for the NRL protocol analyzer, I guess this is the class you are interested in. The NRL protocol analyzer has been superseded by the Maude-NPA tool. If you are looking for something recent with interesting new features, the Tamarin prover may be worth considering. All these tools work in the "symbolic" model often referred to as the Dolev-Yao model: they assume that the underlying cryptographic primitives (encryption schemes, signature schemes) are perfect and analyze all possible interactions between an active network attacker and the protocol. The mentioned tools can verify correctness of a protocol (with respect to an unbounded number of sessions) as well as find attacks.

The other tool mentioned here, CryptoVerif, works very differently. It aims to establish "computational" security: it (partially) automates the game-based reductions typically used for proving the security of cryptographic primitives or Key Exchange protocols. Here one tries to construct a proof that if the attacker can break the protocol, he can break the underlying hardness assumption. (An example of such a hardness assumption is computing the discrete logarithm in a Diffie-Hellman style setting.) The tool cannot find attacks. In this category I would also recommend looking at EasyCrypt and CertiCrypt.

These two types of tools work at different abstraction levels, and usually a higher abstraction level makes it feasible to analyze more complex protocols.
For example, Scyther and ProVerif have been successfully used for relatively complex/large protocols. The tools in the second category give more precise security guarantees, but have so far only been used for primitives or very small protocols.

Caveat 1: if a tool finds an attack for you, you can effectively verify that it is a real attack on your protocol, which is useful. If the tool says "no attack" or "proof", it can still be the case that there is a flaw in your protocol model or security property, or that there is an attack outside of the scope of the used tool. All these tools differ in very subtle (technical) ways, which can make it very hard to compare their results.

Caveat 2: there are many more tools in the first category and I'm sure other people can explain cases in which you might want to consider on of the alternatives I didn't mention. However, without seeing your protocols and their intended security properties it is hard to give generic advice.


Database row level encryption scheme I am wanting to secure some highly sensitive data in a database. This would mean that the data needs to be encrypted and remain secure for 100 years if it were to fall into adversary hands. I also want to limit the amount of data that is vulnerable in plaintext at a time in RAM. This is so there is less chance of plaintext data being paged to disk. Also the database may be quite large so it needs to be more efficient than decrypting the whole database at a time just to access it. Therefore I am thinking about encrypting the sensitive data on a database row level. This would mean a unique index which references the record is unencrypted, so each record can still be found/retrieved, however the sensitive data itself is encrypted.

My solution would be to have the data per database row:

index | IV | sensitive encrypted data | MAC

A 256 bit database key will be used to encrypt the sensitive data which will be generated using /dev/random.
The IV for each row will be 256 bits from /dev/urandom (faster than /dev/random).
The encryption algorithm will be Twofish.
The MAC of each record will be HMAC-SHA3 of the index, IV & sensitive data using the key.

The system is single user. The user will create a strong alphanumeric passphrase (minimum 14 characters).

A password based key derivation function will be run on the passphrase to create a derived encryption key which will then be used to separately encrypt the database key with Twofish. This is so the user can change their password without having to re-encrypt the entire database - they can just create a new password and re-encrypt the database key instead.

To derive the key from the passphrase, PBKDF2 will be used with 10,000 iterations using HMAC-SHA3 with a 256 bit output and a salt of 256 bits obtained from /dev/urandom.
What I am trying to do is balance the number of password characters required to make the data secure versus making it reasonably fast for users on a mobile device which have slow processors and limited memory. I don't expect the user to wait more than 5 seconds for the PBKDF to complete.
A MAC is created using HMAC-SHA3-256(derived encryption key, salt | encrypted database key) and stored next to the salt and encrypted database key on disk. This can be verified when logging in to make sure they entered the correct password.

When the program loads, the user enters the passphrase. The KDF runs, which generates the key to decrypt the database encryption key. The real encryption key is then the only thing kept in RAM while the program is running and used to verify and decrypt individual database records when required.

What's the optimal length for the row level IV? Is 256 bits fine?
Is the minimum password strength of 14 characters and 10,000 iterations of PBKDF2 strong enough to protect the 256 bit database
key? If not, what parameters would work?
Is PBKDF2 still a good algorithm still to use here? If not, what Scrypt parameters?
Any further changes or recommendations to make the system secure?

The way the iterations work is that it roughly increases your security (in bits) by $\log_2(iterations)$.  So you would still need $\frac{\log{2}}{\log{97}}\cdot (256 - \log_2(10000)) \approx 37$ characters in your password to have 256-bits of security.  Think of it this way, if you have $2^{256}$ possible keys, that is an astronomically large number.  Much more than the number of elementary particles in the universe.  In comparison, 10,000 is basically nothing.  Increasing the keyspace gives you exponential security, while adding iterations to your key derivation function gives you only linear security.  It's nice, but at the end of the day it doesn't help as much as you think it does.

Having said that,  you probably don't need 256-bits of security anyway.  As I said before, that is a ridiculous amount of security.  No increase in computational power will ever let anyone brute force a 256-bit key.  There are physical limits to computation, and it would take something like the entire energy of a dozen stars to be able to do that.  The reason we have things like AES-256 is that we anticipate in the future people will find more efficient attacks against AES which do not require brute forcing.  But, with a longer key we hopefully delay these attacks.  So, if someone discovers an attack which works in time $2^{n/2}$, AES-128 will be effectively broken.  But, with AES-256 we still have 128-bits of security, which should suffice for a while longer.

For 100 years, the number of bits of security you really need is closer to 120-150.  The outside limit of what anyone can brute force today is probably 70-80 bits, and remember adding bits gives you exponentially more security.  So, you would really only need a password that was 17-20 characters long.


Why this isn't second preimage resistance? I've been reading on preimage resistance and trying out few examples for the same and I'm trying to figure out why the following hash function does not have the second preimage resistance and any suggestions would be appreciated.
$$h(M) = \operatorname{AES-Enc}\big(M[0\ldots n], M[(n+1)\ldots 2n]\big) \oplus M[0\ldots n]$$
For the given hash function, since we XOR the output of AES with the first half of the input message, if I consider a message all bits zero then my hash-function would simply resolve to $\operatorname{AES-Enc}(0^n, 0^n)$. Now to show it doesn't have second preimage resistance I understand, that I need to find another message $M' != M $. But, if I consider another message $M'$ which is an all bit 0 except last bit flipped then the hash function will be $AES(0^n, 0^{n{-1}}1)$ but the output, in this case, won't be the same as $h(M)$ and so on.. so I'm a bit confused at this point and any hint would be greatly appreciated!

Using the hash function;
$$h(M) = \operatorname{AES-Enc}\big(M[0\ldots n], M[(n+1)\ldots 2n]\big) \oplus M[0\ldots n]$$
One can find many pre-images with the given hash value $h$

take arbitrary $M[0\ldots n]$
calculate $x = M[0\ldots n] \oplus h$
Decrypt AES with the key $M[0\ldots n]$ and the ciphertext is $x$
$$m =\operatorname{AES-Dec}\big(M[0\ldots n],x\big)$$

let $M[(n+1)\ldots 2n] = m$ then we are done, found a pre-image. Now if the founded pre-image is different than the provided $M$ with the $h = h(M)$, then this is a second pre-image for the hash function. If not, one can look for others to find a secondary image for this hash function. Therefore, this is neither a pre-image resistant nor second pre-image resistant hash function.
We just used the property of AES that is a permutation under a key and the key is free to the attacker.


Meaning of pseudocode "$(C, S):=$" I've seen pseudocode of this form in the Montgomery multiplication related theses: $(C, S) := a[j]*b[0]+C$.

What's the meaning of "$(C, S):=$", or what is the real code that was converted from this pseudocode like?

I believe that the meaning is "compute the $2n$-bit value $a[j]*b[0] + C$, and then assign the top $n$ bits to $C$ and the bottom $n$ bits into $S$


What is a differential trail? From what I could find it relates input differences to output differences usually across multiple rounds.

But is it the entire probability distribution over all output differences for one input difference? Or is it the list of differences that produce the output difference with the highest probability?

What is the exact definition of differential trail?

Imagine you have a function like this: $$f(x) = p_3(p_2(p_1(x))).$$
Now imagine that you find a pair $\Delta_0, \Delta_1$ such that $p_1(x \oplus \Delta_0) = p_1(x) \oplus \Delta_1$ with probability $2^{-n_1}$, $\Delta_2$ such that $p_2(x \oplus \Delta_1) = p_2(x) \oplus \Delta_2$ with probability $2^{-n_2}$, and $\Delta_3$ such that $p_3(x \oplus \Delta_2) = p_3(x) \oplus \Delta_3$ with probability $2^{-n_3}$. Then:

$\Delta_0 \xrightarrow{f} \Delta_3$ is a differential for $f$ (with probability at least $2^{-n_1 n_2 n_3}$ if we can assume independence);
$\Delta_0 \xrightarrow{p_1} \Delta_1 \xrightarrow{p_2} \Delta_2 \xrightarrow{p_3} \Delta_3$ is a differential trail, also known as differential characteristic, for $f$ (with probability $2^{-n_1 n_2 n_3}$ if we can assume independence).

So, a differential trail contains not only the input and output differences going into your function, but also all of the intermediate values (and respective probabilities). You can also say that a differential is the combination of all the differential trails with the same input and output values.


Industry standard recommendations for memory usage defaults for a password hashing function? I've been looking around for any studies done on this topic with respect to memory-hard password hashing. I'm inclined to simply impose no extra overhead by default, to be honest, but I'd really like to know what the industry standard recommendations might be.

If it's for a single user workload (e.g. passphrase to key derivation for encryption / cold storage of private key, local login): explore the largest that's unlikely to cause disk paging or equivalent (including memory compression) on any of the targeted platforms, divide by 2 just in case, and round down to the nearest size parameterizable.
For servers workloads, one wants to comfortably fit the largest fast cache (e.g. L3 if present, or L2) to conserve energy and CPU power; thus: take that cache size, divide by the physical number of threads sharing it (often twice the number of physical CPUs, and rarely more), divide by 2 so that some cache is left, and round down to the nearest size parameterizable. For multi-thread password hashing, that's assuming some parametrization or lock insures there's never more threads password-hashing than there are physical number of threads.
If I had to throw a reasonable number without knowing context, I'd make it 128kiB to err on the functional side (at the expense of not making use of the DRAM on many platforms, thus making security less than it could). I do NOT claim this is an industry standard in any way.
Reasons to choose less: avoid becoming intolerably slow and energy hungry on more platforms.
Reasons to choose more: increase the investment and to a degree operating cost for attackers.


Term for the ratio of ciphertext to plaintext size? Is there a term that determines the ratio of size of ciphertext $|c|$ and plaintext $|n|$? I vaguely recollect reading it as scale out factor. Is there a better term? Or a popular term for this?

Ciphertext expansion, or expansion ratio are terms used to indicate this.


The difference between MAC algorithms and what to use I've been looking into message authentication codes and found several ways to create integrity for a message. I know of the following algorithms:

HMAC, this can use any cryptograhpic hash function and a key, for a HMAC to be secure the underlying hash function does not have to be (though I assume it would be a good thing to not use broken hash functions just for the sake of good practice) I also understand it is better not to use the same key for encryption and HMAC but to use a different key for both.

GCM, GCM is a mode operation for symmetric encryption ciphers. The benefit of this is that the key you encrypt with, also does the authentication.

CBC-MAC is a MAC based on the mode operation CBC, conterary to what i first thought you first encrypt the text with (for example) AES-CBC and then apply the CBC-MAC (If using encrypt then mac) and it is not the CBC mode for encryption with authentication.

I believe the best thing to do is encrypt then MAC as explained here

What i would like to know (given I'm working with data over internet): what is the best algorithm to provide integrity and did I miss any well-know-good-to-use algorithm.

Also, I've seen these terms used interchangeably but authentication is something different than integrity right? authentication is verifying the sender (PKI) and integrity is verifying the received data (MAC). but then why is it message authentication, i know an other word for it is MIC (which seems better to me) but is used in WPA (when MAC has an other meaning). Could someone be so kind as to explain the terminology as well?

First the theoretical explanations:

Integrity and authenticity are different goals to achieve, but both are achieved (for symmetric encryption) with a MAC.
You should probably be using encrypt-than-MAC or an authenticated cipher unless you have very good reasons not to. No blanket statements can be made though.

HMAC: HMAC is a often used construct. It is recommended to use a separate key for the HMAC but you may get away with using the same key as used for encryption as I haven't heard of any attacks that could attack a scheme with one key for HMAC (but if anybody switches it to CBC-MAC you're in trouble). HMAC, as noted, relies on a hash. A hash function could either be faster or slower than a cipher.

GCM: GCM is an AEAD cipher that has very good performance on (Intel) 32 / 64 bit processors, especially if hardware support can be utilized. As it uses the GMAC construct it may be faster than performing a separate MAC function. It's also pretty easy to use, but it may be hard to get right on embedded systems. Because of the speed it's also known as a 1.5 pass authenticated cipher (as in: the data is processed 1.5 times, 1 time for encryption and 0.5 times for authentication/integrity).

CBC-MAC: is an insecure construct that uses a block cipher (usually the one also used for encryption, of course). There are attacks on CBC-MAC, it should only be used on data of known length and you should use a separate key.

There are other MAC constructs, notably:

CMAC which is basically a fix for the length-related deficiency of CBC-MAC
Poly1305-AES - which is often combined with one of the stream ciphers from Daniel J. Bernstein

And there are many AEAD ciphers as well:

OCB mode (multiple versions) a patented single pass mode, very efficient
CCM mode, a packet based AEAD cipher that uses a 128 bit block cipher with fun peculiarities
EAX an AEAD cipher that uses a 128 bit block cipher, brought up as a candidate to replace CCM at NIST because of the fun peculiarities

MAC algorithms alone are not authenticated ciphers, so if you need encrypt as well, you'll have to specify your own protocol on how to do this. There are efforts to create an authenticated cipher (AEAD cipher) out of CBC and HMAC. Basically EAX mode has done the same with CTR and CMAC. Don't include the IV in the calculation. AEAD ciphers will automatically include it.

Finally note that AEAD ciphers are very much a topic of research.

There's a lot more to be said about MAC algorithms and AEAD, but this is as broad as I would like to go.


Can anyone briefly explain the 'theta step' of compression box in SHA3? Can you explain the 'theta' step of the compression box:

D[X] = C[X-1] ^ ROT(C[X+1, 1])

In this step all the indices should be taken modulo 5.

Do we have have to rotate it after taking mod 5? And is C[X-1] left rotate or just putting the values of x as 0,1,2,3,4 and then taking mod 5?

And ROTC[X+1,1] is right circular rotation by 1 bit after taking mod 5, right?

Please help me regarding this.

Can you tell me the 'theta' step of compression box

Keccak/SHA3 has no compression function, the inner function is a permutation.

  In this step all the indices should be taken modulo 5.

Yes that is correct.

  Do we have have to rotate it after taking mod 5 ??
  And C[X-1] is left rotate or just putting the values of x as 0,1,2,3,4 and then taking mod 5.

C is a 64-bit temporary value, as is D. The index is done mod 5, not the value. X-1 mod 5 is the same as X+4 mod 5 for the index, addition is less likely to cause problems in code, and is generally easier to read, but is listed as subtraction in the specification for reasons which I hope are obvious.

  And ROTC[X+1,1] is right circular rotation by 1 bit after taking mod 5, right??

Actually it is a left rotation on the 64-bit value by 1 bit. This is because the first bit is considered the least significant, so moving it by 1 bit to the next significant location is a left rotation when the least significant bit is on the right end of the value in memory.

If we look at theta without any loops, it looks like this:

C[0] = A[0,0] xor A[0,1] xor A[0,2] xor A[0,3] xor A[0,4];
C[1] = A[1,0] xor A[1,1] xor A[1,2] xor A[1,3] xor A[1,4];
C[2] = A[2,0] xor A[2,1] xor A[2,2] xor A[2,3] xor A[2,4];
C[3] = A[3,0] xor A[3,1] xor A[3,2] xor A[3,3] xor A[3,4];
C[4] = A[4,0] xor A[4,1] xor A[4,2] xor A[4,3] xor A[4,4];

D[0] = C[4] xor (C[1] <<< 1);
D[1] = C[0] xor (C[2] <<< 1);
D[2] = C[1] xor (C[3] <<< 1);
D[3] = C[2] xor (C[4] <<< 1);
D[4] = C[3] xor (C[0] <<< 1);

A[0,0] = A[0,0] xor D[0]; A[0,1] = A[0,1] xor D[0]; A[0,2] = A[0,2] xor D[0];
A[0,3] = A[0,3] xor D[0]; A[0,4] = A[0,4] xor D[0];
A[1,0] = A[1,0] xor D[1]; A[1,1] = A[1,1] xor D[1]; A[1,2] = A[1,2] xor D[1];
A[1,3] = A[1,3] xor D[1]; A[1,4] = A[1,4] xor D[1];
A[2,0] = A[2,0] xor D[2]; A[2,1] = A[2,1] xor D[2]; A[2,2] = A[2,2] xor D[2];
A[2,3] = A[2,3] xor D[2]; A[2,4] = A[2,4] xor D[2];
A[3,0] = A[3,0] xor D[3]; A[3,1] = A[3,1] xor D[3]; A[3,2] = A[3,2] xor D[3];
A[3,3] = A[3,3] xor D[3]; A[3,4] = A[3,4] xor D[3];
A[4,0] = A[4,0] xor D[4]; A[4,1] = A[4,1] xor D[4]; A[4,2] = A[4,2] xor D[4];
A[4,3] = A[4,3] xor D[4]; A[4,4] = A[4,4] xor D[4];

Where A[x,y] is one of the lanes of the state with row index 'x' and column index 'y', and '<<<' is a left rotation of the value to the left by the bits to the right.


What is the most efficient lattice problem solving algorithm? I've recently become very interested in post-quantum cryptography, specifically lattice-based cryptography. As of this posting there exists no quantum algorithm that can perform better at solving lattice problems than a conventional computer.

There are, however, algorithms that exist that theoretically can solve lattice problems, albeit slowly.

I'd like to study one or more of these algorithms myself to help me better understand lattice cryptography and lattices in general.

So, what is the most efficient lattice problem solving algorithm and why is it so efficient?

What you want is probably a lattice reduction algorithm.

Lattice cryptography usually relies on the Closest Vector Problem (CVP) or the Shortest Vector Problem (SVP). Solving these involves the Lenstra–Lenstra–Lovász lattice basis reduction algorithm, or LLL. This algorithm is the quintessential lattice reduction algorithm, and is probably what you are looking for. This algorithm is used internally by other algorithms, such as Babai's nearest plane algorithm for CVP.

Note that the LLL algorithm is not able to reduce lattices in higher dimensions, which is the case with practical lattice cryptography. Instead, different algorithms are required, such as BKZ 2.0 for NTRU. However for the purpose of learning about lattice reductions, understanding LLL should be sufficient.


How to produce a ternary value (3-face "dice roll") digest from a message? Apologies in advance if the terminology I am using in the title of this question, is flawed.
I want an algorithm that will produce a ternary value (meaning from a set of three, as opposed to from a set of two as is the case with a 1 bit / binary value) given some message (of arbitrary length, much the same way message digest procedures accept such messages).
The required properties of the algorithm mirror requirements on cryptographically secure message digest algorithms:

The algorithm has to be deterministic with respect to input, producing same output for same input

The product of the algorithm must be irreversible to the original message. Arguably, reversing one single ternary bit into some message of any substantial length sounds akin to solving some intractable data compression problem, but just mentioning this for the requirements own sake.

The set of values the algorithm would produce must feature a sufficiently "random" distribution.

Every value would be present in quantities amounting to exactly 1/3 of the set, meaning the algorithm must also feature "fair" distribution of values.

To express this more plainly, perhaps, I am ultimately looking for a message digest algorithm which, instead of yielding some 128-, 256- or any other amount of bits worth of digest, yields one single ternary (as opposed to binary) value/number.
An algorithm that, by extension, turns a product of some existing traditional message digest (e.g. SHA-256) into a ternary value, would suffice, but I am not sure I can, for instance, just divide some 256-bit value by 3 to get me some sufficiently random value distribution. However, piggybacking on an existing, cryptographically secure message digest algorithm, could be a solution in general, I suppose.

Take the output $H$ of $\operatorname{SHA-256(M)}$ or any other hash of $b$ bits. Count the number $u$ of bits set in $H$ and output $u\bmod3$. This is optimally close to unbiased in $\{0,1,2\}$, for an ideal hash and the requirement to deterministically output a value for any $M$.
Counting the number of bits set can be fast. Sometimes there's even an instruction or compiler intrinsic for that. This popcount instruction was nicknamed NSA instruction on the (unverified) rumor it was added to mainframe computers subsided by the US government to help in some form of cryptanalysis based on Hamming distance.
There are equally good alternatives. E.g.: take all 32-bit words of the hash, add them (the total can require 35 bits), then reduce modulo $3$. Or: take all words of the hash reduced modulo $3$, add the results, reduce modulo $3$.

Argument: if we take a uniformly random integer $v$ in $[0,2^b)$ and reduce it modulo $n$, we obtain as $b$ grows a nearly uniformly random number in $[0,n)$, slightly biased towards $0$. With $n=3$, and $b$ even, $0$ has probability $\frac13+\frac1{3\,2^{b-1}}$, and both $1$ and $2$ have probability $\frac13-\frac1{3\,2^b}$. This bias is undetectable for $b\ge128$, and can't be lowered.
Noticing that $2^j\bmod3$ is $1$ for even $j$, and $2$ for odd $j$, we can compute $v\bmod3$ quickly from the binary expression of $v$, by counting the even-weight bits that are set in $v$, subtracting the number of odd-weight bits that are set in $v$, and reducing modulo $3$.
We'd get the same result by complementing the $\left\lfloor\frac b2\right\rfloor$ odd-weight bits, counting all the bits set, subtracting $\left\lfloor\frac b2\right\rfloor$, and reducing modulo $3$.
In our case, the polarity of the bits in $H$ is immaterial, thus we do not need to complement the odd-weight bits, and an offset is immaterial (it only changes the slightly favored outcome), thus we can remove the final subtract. And we reached the first paragraph's method.


Key transport vs key encapsulation? What exactly is the difference between key transport and key encapsulation? Either they seem to be used interchangeably, either I'm mixing stuff up.

Key encapsulation or key wrapping is the encryption of a key with another key. There may be a symmetric key or asymmetric key pair that encapsulates the key destined for transportation; this key can then be called a key transport key.

Key transportation is simply the secure transportation of a key. For public keys you'd expect integrity and authenticity - so that the receiver can trust the public key to have been sent by the right entity. Secret keys require confidentiality as well - which is why they are commonly encapsulated. Private keys would also require confidentiality of course, but generally you should not transport private keys at all - they're private: not to be shared.

Commonly I'd expect encapsulation / wrapping to be used for secret keys for secure transport. It is however perfectly possible to secure them otherwise (diplomatic post with a USB-thumbstick for instance).

Key encapsulation & transport is just one way of establishing keys between two or multiple parties. Another way would be (authenticated) key agreement, key sharing schemes and so on.


Is it secure to use order preserving encryption in practice? When I read papers, I often see the comments, "order-preserving encryption is deterministic and it is not IND-CPA secure", or in general "it is not secure enough to be implemented in practice". So I am wondering if these comments are correct especially from the practical implementation's point of view. I know a lot of works based on OPE. If it is not that secure in real world, can I think of these works as be more theoretical than practical?

Timely question, since attacks on the order preserving encryption in CryptDB were recently in the news. Quoting the research paper (pdf), there are two attacks they use on OPE:

sorting attack: is an attack that decrypts OPE-encrypted
columns. This folklore attack is very simple but, as we
show, very powerful in practice. It is applicable to columns
that are “dense”in the sense that every element of the message
space appears in the encrypted column. While this
may seem like a relatively strong assumption, we show
that it holds for many real-world datasets.
cumulative attack: is a new attack we introduce that decrypts
OPE-encrypted columns. This attack is applicable
even to low-density columns and also makes use of combinatorial
optimization techniques.

In practice they were able to decrypt fields with a relatively small range possible values with very high confidence.
The response from the developers was that:

OPE encryption should be used for “high-entropy values” where the order does not reveal much

I would not think there are many circumstances where that would be the case and yet both privacy and ordering (rather than e.g. deterministic encryption only) is needed, but there are probably some. E.g. some very exact timestamp might fit the bill in some circumstances, if finding the approximate value would not be a problem but the exact value would.
So practical applications where it is secure may be limited but they probably exist.


Is there an upper limit to plaintext size in XSalsa20Poly1305? While fiddling with the NaCl implementation in Go, specifically SecretBox, a general crypto question came up after reading the documentation.

Quote:

  Package secretbox encrypts and authenticates small messages.

I haven't seen this before. Is there a maximum size? What constitutes as a small message?

I've looked for some paper or documentation explaining that line, and I even went through the source, but I can't find any related information anywhere which explains the noted limit when it comes to the size of the message.

Practically, I just successfully encrypted hundreds of megabytes of data. So, I am really puzzled as to why the docs say it was specified for small messages only. Currently, I am guessing that there is a cryptographic reason for this which I simply may not be able to find.

So – to recap – what I'm asking is: in Salsa20, is there a limit to the message size that is possible? If there is, can you additionally provide a hint where I can find a related reference/paper for me to look at?

Update:

The issue that I opened has been resolved, and the documentation updated to clarify the limits.

As a comment points out, it’s most probably a mistake/error in the docs.

If you look at “What is the PRG period of stream ciphers such as RC4 or Salsa20?”, you’ll find an answer which explicitly points out the limits of Salsa20 (quote)

  …Salsa20 used as a stream cipher, it uses a 64-bit block counter and 64-bytes blocks, limiting its capacity to $2^{73}$ bits. After that, the counter would rollover, and thus the output.

That’s a 1180591620717411303424 bytes (around and about 1180591620 Terabyte) maximum size until rollover, which I wouldn’t really call “small”. But that might just be me…

For reference purposes, see the Salsa20 paper (PDF).

EDIT

  Comment by Eclipse:
  SecretBox uses Poly1305 so could it be something about how they work together?

I also don’t see any reason the use of Poly1305 would limit things. If you – for example – look at RFC 7539: ChaCha20 and Poly1305 for IETF Protocols, you’ll read a usefull hint (on page 20) which – from my point of view – practically excludes Poly1305 as the source of any “small message” limits.

Quote:

  …, the ciphertext length field in the construction of the buffer on which Poly1305 runs limits the ciphertext (and hence, the plaintext) size to 2^64 bytes, or sixteen thousand petabytes (18,446,744,073,709,551,616 bytes to be exact).

When you look at page 6 of that RFC, you’ll read that that RFC assumes it’s safe to handle 247,877,906,880 bytes (nearly 256 GB) with Poly1305. So Poly1305 doesn’t really seem to be a limiting factor either which might explain a “small message” comment like that.

All that’s left is a potential limitiation in the implementation itself. If you can’t find “small message” limits in the sourcecode either – which you already checked and confirmed to not exists – an error in the docs is most likely. In the end, the statement …small messages seems to be nothing but a “small” glitch in the docs which causes superfluous confusion where it shouldn’t.


Desirability of chaining an LCG in an authentication scheme Suppose that:

$E(k, x)$ is the encryption of data block $x$ with key $k$ using a block cipher.
$L_{Key}$ is the key size of the block cipher in bits.
$L_{Block}$ is the block size of the block cipher in bits.
$F(x) = (a \cdot x + c) \mbox{ mod } m$, so it's a linear congruential generator.
$m = 2^{L_{Block}}$ is the modulus to be used in $F$.
$a$ and $c$ are such that $F$ has a full period.
$K \leftarrow \{0, 1\}^{L_{Key}}$ is a secret key to be used with the block cipher.
$J \leftarrow \{0, 1\}^{L_{Block}}$ is a value that is derived in some way from $K$, perhaps through using $E$ and a constant.
$T \leftarrow \{0, 1\}^{L_{Block}}$ is an authentication tag.
$i$ is a one-based index.
$x_{i} \leftarrow \{0, 1\}^{L_{Block}}$ is the $i$th block in a stream of data to be verified.
$s$ is the number of data blocks.
$y_{i} = x_{i} \oplus J$.
$t$ is an intermediate value that is calculated prior to $T$. It is first calculated as $t = F(y_{1})$, after which it is recalculated as $t = F(y_{i} \oplus t)$.
$T = E(K, t)$.

Seems secure enough to me (I know that isn't a good assurance, but I know jack about cryptanalysis), assuming the block cipher is secure. Block ciphers typically invoke one or more modular addition operations, so I don't think computing $b \boxplus c$ (where $b = m \cdot x$) is going to be a slow operation. I have no clue as to how much slower the multiplication would be. Would it be too slow to make for a good authentication mode?

Update #1: If $a = 65537$, then computing $a \cdot x$ would only require shifting $x$ to the left by four places and then adding $x$ to the result, which would be much faster than if $a$ had a larger Hamming weight. How much of an improvement in speed would this provide over GCM?

Would it be too slow to make for a good authentication mode?

No, it would be too insecure for a good authentication mode.

In particular, given any message $M$ that's at least two blocks long, it's trivial to find a second message $M' \ne M$ that has the same tag (no matter what the key is); and hence one could be substituted for the other without detection.


Automatic generation of secure passwords with the least inconvenience for a user I'm working on a web site for a private company that should allow them to upload files, which will be later retrieved by their affiliates. The site will be available from a public Internet using private URLs for each uploaded file. All files uploaded will be encrypted-and-MAC'ed using AES-256 encryption. Files could be retrieved by a recipient only if they know the password for each file.

Since humans are pretty bad at picking secure passwords I decided to generate passwords for such encryption automatically and display them for a user after the file is uploaded & encrypted.

Another detail that I need to mention is that after each file is uploaded an employee of the company may transmit its password to a recipient (via a phone call or a fax.) Thus a requirement for this password to be something that can be both "secure" and "manageable" by a non-cryptographer.

So my strategy was to come up with a set of unambiguous characters and numbers that will be easy for a human being to relay over the phone.

I came up with the following 20 characters:

  efghkpqrsuwxy2345679

But my question is, how many of those characters shall I include in the password to make it secure, and at the same time make it not too hard for a sender/receiver to work with?

The entropy of a random password is given by the formula:

$H = log_2 N^L = L\log_2 N$

where $N$ is the number of possible symbols, and $L$ is the length of the password. Since you want to know the minimum length to achieve a determined level of security, then the answer to your question is $L = \lceil \frac{H}{log_2 N} \rceil$.

In your case, $N=20$, and your desired entropy $H$ depends on the requirements of your system. RFC 4086 gives some guidelines about it. Let us assume you want to have only a one in a million chance of a password being guessed, then you need at least 39 bits of randomnes, so $H = 39$. Then $L = \lceil \frac{H}{log_2 N} \rceil = \lceil 9.02 \rceil = 10 $, so you need at least 10 characters.
Of course, if you want to achieve more bits of randomness, then the length will increase. For instance, for 128 bits, you need at least 30 characters.

Note: All this info comes from Wikipedia


Necessary to authenticate nonce if authentication-key is derived from nonce? Lets suppose my messages are composed like this: unique_message_nonce + encrypted_message + mac

Because I don't have an AEAD-scheme, I can encrypt and authenticate my message in two ways:

Use authenticated-encryption for message:

let key = KDF(key: master_key, info: "Key:" + unique_message_nonce)
let nonce = KDF(key: master_key, info: "Nonce:" + unique_message_nonce)
let (encrypted_message, mac) = AuthEnc(key: key, nonce: nonce, message: message)

Encrypt the message and compute MAC over unique_file_nonce + encrypted_message:

let encryption_key = KDF(key: master_key, info: "EncKey:" + unique_message_nonce)
let encryption_nonce = KDF(key: master_key, info: "EncNonce:" + unique_message_nonce)
let encrypted_message = Enc(key: encryption_key, nonce: encryption_nonce, message: message)

let mac_key = KDF(key: master_key, info: "MACKey:" + unique_message_nonce)
let mac = Auth(key: mac_key, message: unique_file_nonce + encrypted_message)

Is the first one secure?

Usually, you would use the 2nd one and authenticate everything because if s.o. tempers with the nonce, he might be able to alter the plaintext without changing the MAC.

However, as far as I can see, in the 1st one the unique_message_nonce is implicitly included in the MAC:

If s.o. changes unique_message_nonce, key will change too and the authentication will fail
Without knowing master_key, an attacker cannot manipulate unique_message_nonce to create a malicious key

Yes. Assuming KDF and AuthEnc are secure and you are using them with correct prameter lengths, the first one is secure.

Usually, you would use 2nd and authenticate everything because if s.o. tempers with the nonce, he might be able to alter the plaintext without changing the MAC.rrect parameter lengths, yes your first scheme is secure.

In any proper AE(AD) scheme, the nonce is used in both the ciphertext and the MAC generation so tampering with it will inevitably lead to a MAC verification failure.

The only thing I would change is dropping the nonce calculation. There is not really a point in deriving the nonce from your master key, if you already know unique_message_nonce is actually unique (and that is all that most popular AEAD schemes like GCM and CCM need).

I would even prefer version one over the second one. It is a lot simpler for the developer and AE(AD) schemes were built for just what you want. The fewer steps you have to do yourself, the fewer errors you can make.


Solving Diffie-Hellman vs DLP I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP).
Obvisously solving the DLP (discrete log) is at least as hard as solving the DH problem.
What about the converse :

In a general setting (cyclic group, no other assumption) ?
With specific groups (multiplicative groups of finite fields, various EC, ...) ?

I found ftp://ftp.inf.ethz.ch/pub/crypto/publications/MauWol00c.pdf discussing the matter but this paper is more than 20 years old so I guess it might be outdated...

According to Wikipedia (with two articles sourced):

Computing the discrete logarithm is the only known method for solving the CDH problem. But there is no proof that it is, in fact, the only method. It is an open problem to determine whether the discrete log assumption is equivalent to the CDH assumption, though in certain special cases this can be shown to be the case.


Is the Vigenère Cryptosystem malleable? Is the Vigenère Cryptosystem malleable, and how can we prove that it is (or it is not) malleable?

Vigenere Cryptosystem is as follow:

You chose a key $(K_0,...,K_{m-1})$ consisting of elements in $Z_{26}$.
Then a ciphertext for the message $(M_0,...,M_{n-1})$ is $$(M_i+K_{i\mod m}\mod 26)_{i \in [0..n-1]}$$

It is easy to see that you can generate a ciphertext for the message $(M_0+1,...,M_{n-1}+1)$ by adding 1 to each letter. It is therefore by definition malleable.


Proof of number of logins in last N days without saving login times Let's say we have an user Bob. User Bob logs in into our web application every so often. We are a website that tries to save as little information about our users, however we'd like to know which users are inactive so we can suspend their account.
Is there any way we could save information about Bobs logins in a way that doesn't tell us anything about when he logged in, but tells us how many times Bob logged in in last n days?
Assume everything is being done on server side, and only thing we're trying to prevent is data leak in case of a database breach or similar.

I'm not sure cryptography is the way to go. A day level counter could suffice, possibly aggregated later to coarser resolution and deleting any old information you no longer need.
If you want accurate counting for last N days with a certain resolution of last N days the information on what you did N days ago must be kept. It can be inferred by querying count and querying it again after a short while. But you could perhaps do things more fuzzy, maybe store some users data together and inactivate a user group if together they didn't meet the threshold and replace which users are grouped together periodically.


How to Understand Authenticated Key Exchange? I am reading some articles about key exchange. I know classic key exchange, such as Diffie-Hellman key exchange. This type of algorithm is vulnerable to man-in-the-middle attack. However, when using a digital signature algorithm, this attack is invalid.

So, does authenticated key exchange consist of classic key exchange and a digital signature algorithm? Who can tell me?

One way to understand this is through a rather abstract and constructive viewpoint, abstracting away specifics.

As you mentioned, a DH key exchange needs to be done in an authenticated manner otherwise man-in-the-middle attacks become possible. In other words, we needs the communication to happen on a authenticated channel.

How do we get an authenticated channel? One way is to use digital signatures. They would allow to verify that the message comes from the legitimate sender. However we still have a problem, the verification keys needs to be transmitted somehow and so far we only have an insecure channel.

In order to resolve this problem, we send digital signatures parameters over an authenticated channel that is obtained by using certificates. If we trust certification authorities, we have indeed an authenticated channel.

Everything put together in a constructive way:

1) Using certificates we construct an authenticated channel that allows exchange of digital signature parameters

2) Using digital signatures, we construct an authenticated channel that allows key-exchange(D.H).

3) Using key exchange results we could also construct a secure channel.


Recover secret SHA-1 constants given Oracle There's a black box that's basically SHA-1, except that the constants (h0, h1,...,h4) are secret. We can pass it arbitrary inputs and get the corresponding outputs.

Given this, is it possible to recover the constants used?

No.  If it were, that would demonstrate a PRF distinguisher against the SHA-1 compression function, which would be an astonishing result showing that SHA-1 is far more broken than anyone has ever seriously anticipated.


GetModulus negligible probability I have this textbook definition, I shall include below.

GenModulus denotes a ppt algorithm that, on input $1^n$, outputs $(N, p, q)$ where $N = p\,q$ and (except with negligible probability) $p$ and $q$ are $n$-bit primes.

A few pages back in the book, it did say $1^n$ was the security parameter, which I assume applies above.
My first question is, what exactly is an $n$-bit number? I assume, to use an example with decimals, that $3$-bit would be a number no greater than $111$ in binary which is $7$ in decimal.
My next question is, what do they mean by negligible probability within the context of this question? I assume it means the two prime numbers $p$ and $q$ are guessable by an adversary with negligible probability.

What exactly is an $n$‑bit number?

In the context, number designates an element $m$ of the set $\mathbb N$, the non-negative integers. Such $m$ is $n$‑bit if and only if $n\in\mathbb N$ and $\lfloor2^{n-1}\rfloor\le m<2^n$, or equivalently $n=\left\lceil\log_2(m+1)\right\rceil$. When $n\ne0$, that simplifies to $2^{n-1}\le m<2^n$, or equivalently $n=\left\lfloor\log_2(m)\right\rfloor+1$.
Any $n$‑bit $m$ in $\mathbb N$ has a unique $n$‑bit bitstring representation $x$ in binary per big-endian convention, and when $n>0$ the leading bit of $x$ is $1$. It holds $\|m\|=|x|=n$ per the notation in Katz&Lindell's Introduction to Modern Cryptography.
Any $n$‑bit bistring $x$ represents an at-most‑$n$‑bit $m$ in $\mathbb N$ per such convention. It holds $\|m\|\le|x|=n$ and $0\le m<2^n$. In some contexts¹, it's (slightly incorrectly) stated that such integer $m$ is $n$‑bit, when really $x$ is $n$‑bit and $m$ is at most $n$‑bit. The question is making just this when it states

$3$‑bit would be a number no greater than $111$ in binary which is $7$ in decimal.

What do they mean by negligible probability within the context of this question?

It means that for any polynomial $r$ (with positive leading coefficient²), for $n$ sufficiently large, the probability is less than $1/r(n)$ that it does not hold that $p$ and $q$ output by the algorithm are $n$‑bit primes.
Equivalently: for all $k>0$ exists $n_k$ such that $n>n_k$ implies that said probability is less than $1/n^k$.
Still equivalently: it is allowed only with probability bound to vanish when $n$ grows (and faster than any polynomial in $n$) that $p$ or/and $q$ are not prime, or/and are more or less than $n$‑bit.
Said probability is computed over all the inputs of the deterministic version of the Probabilistic Polynomial Time algorithm considered, where the randomness is explicitly introduced as an extra parameter, rather than implicit.

I assume it means the two prime numbers $p$ and $q$ are guessable by an adversary with negligible probability.

No. Nothing is stated in the definition quoted in the question about the probability that $p$ or $q$ can be guessed. That comes later in the text.
The probability in the definition is there to formally accommodate a probabilistic primality test, which can let a composite $p$ or $q$ creep out on rare occasions³. In practice, that probability is made so low that it's neglected.

¹ Including textbook RSA when dealing with the message rather than key generation.
² That's left implicit in Katz&Lindell's Introduction to Modern Cryptography, ed. 3, definition 3.4
³ It additionally allows $p$ or $q$ to occasionally not be $n$‑bit, as could be the case for $n<2$ (there's no prime less than $2$‑bit); or for primes generated as the smallest prime at least $m$ drawn uniformly at random in $[2^{n-1},2^n)$, which outputs a prime larger than $2^n$ with probability $O(n/2^n)$.


Encrypting (CBC) identical files with same key and different IV, is it less secure? I would like to learn more about cryptography.

Let's say you encrypt multiple files with CBC encryption using the same key, but each file has a unique (and pseudorandom) IV. Does this weaken the security of the data? Is it easier to obtain the key if you have many instances of the same data encoded with a different IV? Let's assume that the attacker knows all the files are the same or at least partially (first half) the same.

Thank you for your time.

You don't need to worry. There is no known weakness in CBC mode or AES which would mean that encrypting identical files (with different initialization vectors) makes it easier to retrieve the key, or decrypt the data.

The different initialization vector for CBC makes it sure that even the same file results in different input to the block cipher, and thus different output, so an attacker doesn't even know that these two ciphertexts are the same file (other than for the file size).

To crack AES, now the best known method is to try different keys and encrypt or decrypt one block with each, and compare the output with either captured ciphertext or known (or "guessed") plaintext (where we take the IV or previous block into account), until one matches. (For keys bigger than 128 bit, we might need to check with a second block.) If we don't know anything about the plaintext (which is quite rare, but might occur when encrypting a key), this doesn't work - and here our "twice the same file" can help:

decrypt the same block of both files
XOR each with the previous block each (or the IV in case of the first block)
compare.

This needs about twice the work as an ordinary known-plaintext attack, though, which is already out of any realistic ability to crack, if the key space isn't somehow reduced, i.e. if the key is generated from a password.

Note that there is a "weakness" in CBC which says that the total number of blocks to be encrypted with each key should be limited to about $2^{n/2}$, where $n$ is the block size in bits, to make the probability of repeated outputs (and thus repeated XOR-masks for the next block) neglectible. This doesn't really depend on encrypting the same or different files, though, and for 128-bit blocks, this number is quite high ($2^{68}$ bytes, around 200 exabytes, which is half of the world's total digital content (of 2009)).


HMAC-SHA-512 output randomness? This is regarding an online roulette game that claims to be fair. Here is the explanation:

Two strings are created:
STRING1 = "[NONCE]:[SERVER SEED]:[NONCE]"
STRING2 = "[NONCE]:[CLIENT SEED]:[NONCE]"

HMAC-SHA512 is used to hash STRING1 with STRING2 as the secret key, giving us a 128-character hex string.

The first 8 characters of the hex string are taken and converted to a decimal.

This decimal is then divided by 429496.7295 and rounded off to the nearest whole number.

This whole number is used as your roll, with the maximum possible value being 10,000.

My question is, is the output of HMAC-SHA-512 100% random in order to use it as a random number generator like that, or in other words, is there equal chance to hit any number?
Can HMAC-SHA-512 output even start with "FFFFFFFF" or with "00000000"?
The way I see it, it is 50% less likely to hit the first number (1 or 0) or the last number (10000).

Out of the $10001$ possible outputs

$7295$ occur with a probability exactly equal to $429497$ in $2^{32}$.
$2705$ occur with a probability exactly equal to $429496$ in $2^{32}$.
One value, specifically the value ten thousand, occurs with probability exactly equal to $1$ in $2^{32}$.

The mean value of the distribution is approximately $4999.5$. It is approximately a uniform distribution over the range $[0, 9999]$. It is much more uniform than a real-world fair die roll's distribution, but it's also a huge bias in the world of cryptography.

It's not a bias large enough to discourage gamblers. Cryptographers aren't going to be inclined to gamble even for more fair odds based only on the odds and payouts (A lot like the story/rumor about physicists' conferences being unwelcome in Vegas. However that's not to say mathematically minded people might still be irrational or find other reasons for playing.)

Ignoring the value $10000$, each of the $7295$ over-represented values deviates from its expected probability by a factor of $1.0000006298$ and each of the other $2705$ values deviates by a factor of $0.9999983015$.

The multiplication method (using exact math, floating-point arithmetic is not necessarily exact) of transforming one uniform distribution to another uniform distribution over a smaller range has the same amount of bias as the naive division-remainder (without rejection sampling) method that people warn programmers not to use. The bias for the multiplication method, however, is more subtle because it doesn't lead to the over-represented elements all being low elements.

For this specific distribution $0$, $1$, and $2$ are all slightly over-represented. $3$ is slightly under-represented. $4$, $5$, $6$ over-represented, $7$ under-represented, $8$, $9$, $10$ over-represented, $11$ and $12$ over-represented, $13$ under-represented. I think most (or all) of the over-represented elements occur in runs of two or three. And the under-represented in runs of one.

As for the protocol you described, I can't say much about the specifics because you aren't precise in your description.

I can say that the output of algorithms like SHA-512, and by extension HMAC-SHA-512, can safely by treated as a uniform distribution of all 512-bit long bit-strings. Hash functions are often modeled as a random oracle. Wikipedia describes it as:

  In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted.

The hash output can begin with 00000000 or FFFFFFFF or any other 32-bit value. In fact, every possible prefix of a given length $n$ is expected to occur each with the probability $2^{-n}$.

It is possible to create a fair shared random value between multiple parties using hash functions. Two parties choose a random secret number, exchange those numbers between each other simultaneously (so no one can cheat by changing their number), and create a new agreed-upon shared random value by hashing the two secrets. (They obviously need to agree on the order they hash each number.)

A commitment scheme is used to prevent parties from changing their secret number after observing the other player's number. They send each other hashes of their own secrets. They don't reveal to each other the actual value of their secret by exchanging hashes. It's not possible to determine the input from just the hash function's output assuming the input is sufficiently unpredictable. (Having high entropy.) A player cannot swap out the secret value they commit to without finding a collision in the hash function. (Using a prepended random nonce makes finding collisions even harder because you cannot use precomputed collisions.)

The final hash of both secrets, the nonce, and whatever other data is involved results in a random value from a uniform distribution (under the assumption that the hash function behaves like a random oracle). Any change in input to a hash function results in unpredictable changes to the output. This means that one party doesn't have to trust that the other party's secret is random as long as their own number was chosen randomly.

However, even with commitment schemes, it is still possible to cheat if aborting the protocol allows the second person to walk away with a smaller loss by not cooperating by revealing their secret than the loss they would incur by cooperating. (Sort of like people who hit the reset button on their game consoles when they're losing to another player. Or flipping a chess board off the table.) The second person has enough information to calculate the result of the game on their own, and so they might pretend to have their computer crash to avoid paying out larger winnings.

And again, your description of the protocol is vague, so we can't say whether the actual protocol is secure or not. (And even if the protocol were secure it's another matter whether or not the implementation is correct.)


Why is Curve25519 mostly used for key exchange? When i studied the Applications where Curve25519 is used, i found out, that it is mostly used for the key exchange. Examples are the Signal Protocol and Threema.
I know, that Curve25519 has a pretty fast arithmetic, so my first idea was, that it is used to decrease the server load. Am i right with my idea? Can someone give me a better answer?

Edit:
I understand that my question may be not clear enough: Why is it not used for encryption/decryption of messages, when used in messenger like Threema?

A number of reasons contribute to this.

Curve25519 has a non-governmental origin.

It's a curve that's very safe by design, and impregnable to many side-channel and other weaknesses that other curves suffer from.

Also, it's a curve with 'nothing up my sleeve' coefficients.

Unlike the NSA curves, which NIST endorse.

Although not directly related, after the backdoor in Dual_EC_DRBG had been exposed, suspicious aspects of the NIST's P curve constants led to concerns that the NSA had chosen values that gave them an advantage in finding private keys. Since then, many protocols and programs started to use Curve25519 as an alternative to NIST P-256 curve.

As Kelalaka states, the constant time scalar multiplication provided by the Montgomery ladder is also pretty cool.

You cannot directly encrypt arbitrary amounts of data direct with elliptic curves.

The public key is a point on the curve and the private key is a number.

There isn't an elegant mechanism to directly encrypt (generalised ElGamal notwithstanding).

That's why key agreement revolves around finding a shared point on the curve and using a digest of the x co-ordinate of that shared point to use with a fast, secure symmetric cipher.


Non adjacent form of an integer is unique I have tried to look up the proof for NAF (Non-adjacent form) being unique for every integer, but as far as I have seen, textbooks only mention it as a property of NAF, but no proof is given. Also I understand that the number of zeroes in NAF representation is more than in its binary representation but how do I prove that NAF representation of an integer has 2k/3 zeroes for a k-bit integer in general. Even a textbook reference that contains these proofs would be appreciated.

Non-Adjacent Form (NAF), also called Balanced Binary Representation (BBR), is a representation of integers reminiscent of binary, but with an extra $-1$ value for digits, and such that at least one of two adjacent digits is $0$. Because the resulting representation has at least half of its digits at zero (typically about $2/3$), it can be used to speed-up modular exponentiation, or point multiplication on an arbitrary group (e.g. Elliptic Curve).

We define a NAF of $a\in\mathbb N$ as any tuple of $j\in\mathbb N$ integers $a_i\in\{-1,0,+1\}$ with $0\le i<j$, such that:

$a=\sum_{i=0}^{i=j-1}a_j\;2^j\;\;$ (same formula as for binary)
$j>0\implies a_{j-1}\ne0\;\;$ (the highest-rank digit, if any, is non-zero)
$0<i<j\implies a_i\;a_{i-1}=0\;\;$ (at least one of two adjacent digits is $0$)

Each $a$ has a unique NAF (we'll prove this in detail). These defining properties of NAF need no change for an extension to $a\in\mathbb Z$. There is either $0$ or $1$ more digit in the NAF for $a$ than in the binary representation of $|a|$; more precisely, for $a\ne0$, $j=\lceil\log_2(3|a|)\rceil-1$.

Counting from $0$ in NAF goes (showing the big-endian form, then the little-endian tuple):
 $\;a=0:\;$             $\;\;\;j=0\;\;()$
 $\;a=1:\;$          +1 $\;\;\;j=1\;\;(a_0=+1)$
 $\;a=2:\;$       +1  0 $\;\;\;j=2\;\;(a_0=\;\;\;0,\;a_1=+1)$
 $\;a=3:\;$    +1  0 -1 $\;\;\;j=3\;\;(a_0=-1,\;a_1=\;\;\;0,\;a_2=+1)$
 $\;a=4:\;$    +1  0  0 $\;\;\;j=3\;\;(a_0=\;\;\;0,\;a_1=\;\;\;0,\;a_2=+1)$
 $\;a=5:\;$    +1  0 +1 $\;\;\;j=3\;\;(a_0=+1,\;a_1=\;\;\;0,\;a_2=+1)$
 $\;a=6:\;$ +1  0 -1  0 $\;\;\;j=4\;\;(a_0=\;\;\;0,\;a_1=-1,\;a_2=\;\;\;0,\;a_3=+1)$
 $\;a=7:\;$ +1  0  0 -1 $\;\;\;j=4\;\;(a_0=-1,\;a_1=\;\;\;0,\;a_2=\;\;\;0,\;a_3=+1)$
 $\;a=8:\;$ +1  0  0  0 $\;\;\;j=4\;\;(a_0=\;\;\;0,\;a_1=\;\;\;0,\;a_2=\;\;\;0,\;a_3=+1)$
 $\;a=9:\;$ +1  0  0 +1 $\;\;\;j=4\;\;(a_0=+1,\;a_1=\;\;\;0,\;a_2=\;\;\;0,\;a_3=+1)$

To establish that an integer $a$ can't have two different NAFs, we use an argument of infinite descent, a special case of proof by contradiction. We hypothesize there exists integer(s) with at least two distinct NAFs, and define $a$ as the smallest such integer. We'll construct an integer $b$ less than $a$ with two distinct NAFs (leading to contradiction).

We note one of the two distinct NAFs for $a$ using $j$ and $a_i$, and another using $\tilde j$ and $\tilde a_i$, swapping theses if necessary so that $\tilde j\le j$. The only case with $j=0$ gives both NAF empty, thus identical, hence $j\ge1$.

If we had $a=0$, we would have $a=0=\sum_{i=0}^{i=j-1}a_j\;2^j$ with $a_{j-1}\ne0$, and by explicitly computing the minimum and maximum of the other terms as a sum-of-powers, we show this can't hold. Hence $a>0$, and hence $\tilde j\ge1$.

We consider three cases each leading to contradiction:

If $a\equiv0\pmod2$, then by reducing modulo $2$ the equation $a=\sum a_i\;2^i$, it comes that $a_0=0$.
$b=a/2$ is an integer less than $a$ (since $2b=a$ with $a>0$), and it's easily verified that the $j-1$ integers $b_i=a_{i+1}$ for $0\le i<j-1$ obey each condition for a NAF for that $b$. Similarly, a NAF for that $b$ is the $\tilde j-1$ integers $\tilde b_i=\tilde a_{i+1}$ for $0\le i<\tilde j-1$, and that's another NAF (since $a_0=0=\tilde a_0$ and the two NAFs for $a$ are distinct).
If $a\equiv1\pmod4$, then by reducing modulo $4$ the equation $a=\sum a_i\;2^i$, it comes that $2a_1+a_0\equiv1\pmod4$, thus $a_1=0$ and $a_0=+1$ (notice that $a_1=+1$ and $a_0=-1$ is ruled out by $a_1\;a_0=0$).
$b=a-1$ is an integer less than $a$, and a NAF for that $b$ is the $j$ integers $b_0=0$, and $b_i=a_i$ for $1\le i<j$. Similarly, another NAF for that $b$ is the $\tilde j$ integers $\tilde b_0=0$, and $\tilde b_i=\tilde a_i$ for $1\le i<\tilde j$.
If $a\equiv3\pmod4$, then by reducing modulo $4$ the equation $a=\sum a_i\;2^i$, it comes that $2a_1+a_0\equiv3\pmod4$, thus $a_1=0$ and $a_0=-1$ (notice that $a_1=-1$ and $a_0=+1$ is ruled out by $a_1\;a_0=0$).
$b=(a+1)/2$ is an integer less than $a$, and a NAF for that $b$ is the $j-1$ integers $b_i=a_{i+1}$ for $0\le i<j-1$. Similarly, another NAF for that $b$ is the $\tilde j-1$ integers $\tilde b_i=\tilde a_{i+1}$ for $0\le i<\tilde j-1$.

There are several ways to explicitly construct the NAF of an arbitrary integer $a>0$ from that of a smaller integer $b$, recursively, until reaching $b=0$ that has a trivial NAF. For example:

If $a\equiv0\pmod2$, we build the NAF for $a$ as a tuple with one more element than the NAF of $b=a/2$, with $a_0=0$, $a_{i+1}=b_i$.
If $a\equiv1\pmod4$, we build the NAF for $a$ as a tuple with two more elements than the NAF of $b=(a-1)/4$, with $a_0=+1$, $a_1=0$, $a_{i+2}=b_i$.
If $a\equiv3\pmod4$, we build the NAF for $a$ as a tuple with two more elements than the NAF of $b=(a+1)/4$, with $a_0=-1$, $a_1=0$, $a_{i+2}=b_i$.

In all three case, it is easy to derive the properties required from the NAF of $a$ from these for the NAF of $b$.

Various sources credit the idea, proof of uniqueness of NAF representation, and proof of optimality of the non-adjacency criteria from the standpoint of maximizing the number of zeros, toGeorge W. Reitwiesner, Binary arithmetic (paywalled), Advances in Computers, vol. 1, pp. 231-308, 1960.

I recommend Jeffrey Shallit: A Primer on Balanced Binary Representations (1992-1993, Department of Computer Science, University of Waterloo). I'm not the only one to find it late!

Marc Joye and Christophe Tymen: Compact Encoding of Non-Adjacent Forms with Applications to Elliptic Curve Cryptography (in proceedings of Public Key Cryptography 2001) notice that we can re-encode NAF as bits using a simple Hamming code, storing integers as NAF essentially as compactly as in binary, while keeping them directly usable for fast point multiplication.


AES-128 CBC encryption : ciphertext size seems too large I am trying to encrypt messages with the AES symmetric algorithm using C language.
I am using a key, an Initialization Vector (IV) and a plaintext, all with a length of 16 bytes.
I expected as output a ciphertext of 128 bit, instead it is of 256 bit. Can you explain me why?

ECB and CBC require padding or a scheme called ciphertext stealing if the size of the messages is not a multiple of the block size. Commonly a scheme such as PKCS#7 padding is applied, quite often by default (i.e. without you explicitly specifying it, e.g. OpenSSL defaults to PKCS#7 compatible padding).
Such padding schemes are created to apply for messages with any binary value. That means that if the size of the plaintext is identical to a multiple then the padding is applied nevertheless. The reason for this is that it is otherwise impossible to distinguish between the plaintext and possible padding. In your case that means that the input to CBC mode is a block of plaintext and another block of just padding.
If your message is always a multiple of 16 then you can use CBC without padding, usually by specifying this explicitly. If you use a scheme that only e.g. contains text strings that cannot end with a zero byte then you could use "zero padding". This is also useful for languages that use NUL-byte termination for the strings such as C. Beware, some implementations will always pad when using "zero padding" as well.
Ciphertext stealing is not used much, it could be used for messages longer than one block.
Finally, you could do without CBC altogether and use counter mode (CTR mode or SIC mode) or one of the authenticated ciphers based on it (GCM for instance).


AES key reuse and guessing the key Bit of a noob question and a fair bit of Googling didn't help. I understand that the current encryption standard is AES256. A few questions

Is the point of this (and other encryption techniques) to reuse the same private key for multiple messages? If we're using one-time keys, then a simple addition is enough and the complicated AES256 protocol is unnecessary yes?
If we are using the key multiple times, how many times is it okay to use it before the message is no longer secure?
How do we measure the strength or weakness of such a protocol? I assume the objective of an attacker is to guess the key but how is it quantified, how easily someone can guess the key?
Is it that given the encrypted and the plaintext for a given key, how easy it is to guess the key that is used as the "standard" to judge?

Apologies if this is too basic but all the explanations about AES focused on the details of the protocol, not these more basic concepts.

You're missing a piece in your understanding of modern encryption.

AES is a symmetrical block encryption cipher. It describes how to use a key (which can be 128, 192 or 256 bits) long to encrypt and decrypt a single block of fixed size (128 bits) of data. That's it.

In order to have a complete encryption/decryption system, you need to couple it with several other pieces.

First, you need to decide how you're going to apply that algorythm to data that aren't exactly 128 bits long. At the same time, you might want that "system" to provide additional properties: make sure that encrypting two identical pieces of data with the same key will not result in the same encrypted data, providing a (standard) way to verify that a given block of data has been properly decrypted, etc.

That's the job of the mode of operation of your block cipher (and the padding algorythm you pick). There are several you can pick from which have different properties (and some are "protected" by patents which can makes their use expensive). Which one you choose depends mostly on what you're going to apply it to.
Almost all of these mode of operation will use something call an initialization vector (IV) which is a block of data that is use to initialize the processing and which should be unique but not private (so you can send it with the cipher text without any risk).

Once you couple these two elements, you can start thinking about key management.

AES is symmetrical so it uses the same key for encryption and decryption. There is no public key involved.

So, after this, the answers to your questions are:

The reuse of the key is not a problem as long as you have chosen a mode of operation that is appropriate for your application (and of course, if you have used it properly). This is because the mode of operation will "pre-mix" your clear text data in a way that, even before encryption, two identical block of data you feed to the actual AES algorythm will never be identical (or at least, not more often than by random chance).
To simplify, you can reuse a private key as often as you want as long as you can generate new initialization vector for each message.
The "strength" of algorythm mostly is defined on how long it takes for an attacker to test a set keys. A perfect cipher would have you attempt a full decryption using half the possible keys (key space) before you had a 50% chance of finding the right one. Many attacks on modern cryptographic ciphers consist of finding ways to test a key faster than going through the whole system or being able to obtain information about the key based the on input or output (sometimes both). The whole science behind this art if called "Cryptanalysis".

As you can see, finding out if an cipher is "safe enough" is a very complex tasks. That is why no serious system uses its own private crypto: it is just too hard (and expensive, and long) to come up with a good proof of safety. Hence the "rule zero" of secure software development: "don't write your own crypto". It's hard enough to use known algorithms properly...


Deletion in RSA Accumulator I am studying RSA Dynamic Accumulators and I have a question: why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known? Is possible to calculate the deletion only with the RSA modulus $N$?

I'm assuming you are talking about the typical dynamic RSA accumulator from "Dynamic Accumulators and Application to Efficient Revocation of
Anonymous Credentials", by Camenicsh and Lysyanskaya (see PDF here).

First, recall that the accumulator over prime elements $x_1, x_2, \dots, x_n$ is computed in $O(n)$ time as:
\begin{align*}
A &= g^{x_1 x_2 \cdots x_n}
\end{align*}

Second, recall that after removing some $x_i$ from the accumulator $A$, we end up with a new accumulator $A'$:
\begin{align*}
A' &= g^{x_1 x_2 \cdots x_{i-1} x_i \cdots x_n}
\end{align*}

To answer your first question,

  Why is it simpler to calculate the new accumulator value after a deletion if the secret $\phi(N)$ is known?

Because knowing $\phi(N)$ allows us to easily compute $A'$ from $A$ as follows:
\begin{align*}
A' &= A^{{x_i}^{-1} \bmod \phi(N)}
\end{align*}

To understand this, recall that additions and multiplications are reduced modulo $\phi(N)$ "in the exponent."
Also recall that numbers that are coprime with $\phi(N)$ (e.g., $x_i$) have multiplicative inverses $\bmod \phi(N)$ [1].

Note that you can compute $A'$ from $A$ directly, without needing to know the other accumulated elements $x_j, j\ne i$.

To answer your second question,

  Is possible to calculate the deletion only with the RSA modulus $N$?

I'm assuming you mean "calculate the new accumulator." The answer is "yes," and you can probably see why.
Remember that, just like we can compute $A$ in $O(n)$ time, we can also compute $A'$ in $O(n)$ time (i.e., by repeated exponentiations):
\begin{align*}
A' &= ((((((g^{x_1})^{x_2}) \cdots)^{x_{i-1}})^{x_i})\cdots)^{x_n}\\
   &= g^{x_1 x_2 \cdots x_{i-1} x_i \cdots x_n}
\end{align*}

Later edit: As @Maeher nicely pointed out, without the trapdoor you need to know the other elements $x_j, j\ne i$ in order to remove $x_i$, since removing is just recomputing the accumulator without $x_i$.

If you are interested in an accumulator where you can both add and remove without knowing the other elements, you can read the elegant work by Papamanthou et al on "Streaming Authenticated Data Structures" from EUROCRYPT'13 (PDF here). Computing new witnesses requires knowing at least part of the accumulated elements, since the construction is merely a different kind of Merkle tree. However, unlike a Merkle tree, existing witnesses can be updated given just the added/deleted elements (no need for additional sibling paths). Currently, this accumulator is based on lattices and will be less efficient.

Still, Qian et al implemented it in "Streaming Authenticated Data Structures: Abstraction and Implementation" at CCSW'14 (PDF behind paywall).

Hope this helps 2 years later :)


Explanation of correlated randomness for garbled circuits While studying Yao's garbled circuits I was mentioned that correlated randomness played some part in MPC. I looked for online documentation but everything I've found is far too complicated for me to understand.

Could anyone briefly explain the role (and functioning) of correlated randomness?

Correlated randomness and garbled circuits are two different approaches to achieve secure multiparty computation. They have nothing to do directly with each other.

Highly multi-party protocols like SPDZ, TinyOT, etc., which are secure against a dishonest majority, are based on correlated randomness. Protocols in this paradigm have two phases.

In the first phase, the parties do a specialized MPC for the following task: it takes no inputs, but samples $(r_1, \ldots, r_n)$ from some agreed-upon distribution, and outputs $r_i$ to party $P_i$. The outputs of this phase are called the correlated randomness. Since this phase doesn't use any specific inputs of the parties, it can be done well beforehand.
In the second phase, the parties consume their correlated randomness to perform MPC of a desired function $f$, on their chosen inputs for $f$. This phase is often information-theoretically secure (assuming the security of the first phase).

The absolute simplest correlated randomness is a multiplication triple (proposed by Beaver in 1991). Let $[s]$ denote a situation where the parties have a secret-sharing of $s$. The details of the secret sharing are not too important -- you can imagine simple additive secret sharing or Shamir secret sharing. The only important property is additive homomorphism: from $[s],[t]$ it is possible to compute $[s+t]$ (cheaply, usually without interaction).

The correlated randomness consists of $[a],[b],[c]$ where $a,b$ are random field elements and $c=ab$. These values are called a multiplication triple. I won't elaborate on the parties generate a multiplication triple, I just want to focus on how random values like this can be used for MPC.
Later suppose the parties have secret shares $[x]$ and $[y]$ and they want to multiply them to learn $xy$. This is a multiplication of chosen inputs. How can they use the multiplication triple, which uses random values that are unrelated to the multiplication they really care about?

Parties compute $[x+a]$ and $[y+b]$ (using additive homomorphic properties of the secret sharing) and publicly open them as $d=x+a$ and $e=y+b$. Since $a$, $b$ are random and unknown to any party, opening $d$ and $e$ reveals nothing about $x,y$ (but this "one-time pad" means that this particular multiplication triple can be used only once in this way).
Note that $xy = (d-a)(e-b) = de - ae - da + ab$. But parties know $e,d$ in the clear and they have secret shares of $a, b,$ and $ab$. So they can use the homomorphic properties of the sharing scheme to compute $de - e[a] - d[b]
+ [c]$ and open it. The result is the $xy$ they care about.

This (and other tricks) are roughly how correlated randomness is used for MPC. For a very good overview of this protocol paradigm, I highly recommend Claudio Orlandi's excellent tutorial video about the topic.


Software implementation of symmetric and asymmetric bilinear pairings I have recently read a paper about pairings, which only implemented asymmetric bilinear pairings and it mentiond that $\eta_{T}$ pairing is the most efficient algorithm for symmetric pairings. I wonder is there any software implementation on elliptic curves could achieve both asymmetric and symmetrci pairings e.g. $e(g,g), e(g,h), g\in G_{1}, h\in G_{2}$

Take a look to MAGMA. To evaluate MAGMA scripts, in their website go to the tab Calculator. Craige Costello has a free tutorial titled Pairings for Beginners with examples of the Weil and Tate pairings in MAGMA.


What security checks do I need for SRP-6a? I'm implementing an SRP-6a login system.  What security checks do I need to do?  Note that the modulus is sent to the client at algorithm startup.

Here is the list I have so far.  I'm using the Wikipedia names for the variables.

Verify that $N$ is an appropriate size.
Verify that $N$ is prime.
Verify that $q = \frac{N-1}{2}$ is prime.
Verify that $g$ is a generator of $(\mathbb{Z}/N\mathbb{Z})^\times$ by verifying:

$1 < g < N-1$
$g^q = -1 \pmod N$

Verify that $0 < A < N$.
Verify that $0 < B < N$.
Verify that $u \neq 0$.
The server should not send its proof before the client provides its valid proof.

Regarding the primality checks, what algorithm should I use?  Should I randomize the parameters during the primality check in order to prevent a false server from finding a composite that passes what the client checks?

This is a good question, but I would consider hardcoding a known good group. There does not seem to be an advantage to letting the server decide if you can afford to use high enough parameter values.

The SRP paper lists the following checks:

"n is a large safe prime" (this is your first three points)
"g is a primitive root of GF(n)" (your next point)
"A > 0" (modulo n, which you make sure of by checking the upper bound)
"B > 0" (ditto)
"a, b > log[g] n" (missing)

(The ordering constraint in your last point is mentioned elsewhere.)

You are missing the last one from the paper, but it is not essential:

  The probability of this happening is infinitesimal (less than 2^-1014 for 1024-bit n), but the check is trivial.

One of your checks is unnecessary:

  Verify that $u \neq 0$.

This will never happen with a secure hash, and if the hash allows finding inputs that force this, you will have worse problems. (But it is a fast check, so no problem.)

  Regarding the primality checks, what algorithm should I use?

Miller–Rabin is common. AKS is too slow in an interactive protocol. I would follow the recommendations from standards like FIPS 186 (pdf), if you must do this.

  Should I randomize the parameters during the primality check in order to prevent a false server from finding a composite that passes what the client checks?

Miller–Rabin uses random numbers anyway. Also, by choosing the correct number of rounds (see above) you should be able to make the probability of a false positive low enough to make finding one impossible.


Does the secret key used in AES have to prime? I’ve looked around this site and the web quite a bit, but can’t find a definitive answer on whether or not the secret key $k$ used in the AES crypto-system has to be a prime number? Or can you just use any random values for the $128,192$ or $256$ bit long keys?

As a personal educational exercise, I’m working on my own implementation of AES, but my only other crypto experience is with the RSA crypto-system, though rather an elementary understanding, where the keys need to be prime, so I guess I just assumed the key for AES did as well. From what I gather the answer is “no”, but I don’t know enough about AES yet, to know whether or not that makes any difference?

No, it does not have to be a prime.

All you need is an appropriately long and random key:

AES-128 = expects key-length of 16 raw/binary bytes (= 128 / 8 bits per byte)
AES-192 = expects key-length of 24 raw/binary bytes (= 192 / 8 bits per byte)
AES-256 = expects key-length of 32 raw/binary bytes (= 256 / 8 bits per byte)

As a practical example, you could use a hashing function like sha-2 to generate a key from a random password, or from a Diffie-Hellman session key, or from an RSA session key, etc. Of course, if it does not conflict your individual purposes, you would be advised to use a deliberately slow key derivation function such as pbkdf-2, bcrypt, or scrypt together with a random salt instead of SHA-2… but let’s stick with SHA-2 to keep it easy.

Depending on the implementation, SHA-2 will return either raw binary bytes, or – more likely – a hex string representing those raw binary bytes. AES-256 for example takes a 32 byte key, which corresponds to 64 characters in hex encoding. All you need to do is to use those bytes SHA-256 returned as a key for AES-256 and you’re set.

In pseudo-code, it would go something like this:

plaintext = "This is top secret!"
key = sha256("This is the password.")
iv = cryptographically_secure_rng();
ciphertext = aes256(plaintext, key, iv);


Storing AES encrypted RSA private keys on a server I'm thinking about creating an encrypted messaging web application where users create RSA key pairs, they store the public key on the server for others to see and also store an AES encrypted private key on the server. Thus, to verify their identity, they can decrypt the private key and send a signature.

That said, I'm curious is this is a reasonable idea. I know some similar services that require you always use the same device (like an iPhone) and won't let you use the same account on a different machine. This leads me to believe that they are storing a private key locally on the device. It seems reasonable to me to store an AES encrypted RSA private key on the server, but I am no expert on the subject and since I don't see anyone else doing it, I'm a little skeptical.

Any thoughts or concerns about this?

Given that you used a strong password to derive the AES encryption key: Yes you could securely store your RSA private key in encrypted form on a server. BUT, since there is no technical need to have your private key on the server, why would you risk it?

Look at it that way: Suppose you have very sensible data (like private photos or so). Now you could encrypt it with a strong algorithm and password and send it to all your friends, knowing that no one would be able to to decrypt it. Anyways, I personally would still not do that. Even if I trust the encryption, I would not unnecessarily give encrypted data to someone else for no good reason.


Can someone help me understand this? In the book Serious Cryptography
It says for a cipher's permutation to be secure
"Different keys should result in different permutations. Otherwise it becomes easier to decrypt without the key: if different keys result in identical permutations, that means there are fewer distinct keys than distinct permutations, and therefore fewer possibilities to try when decrypting without the key. In the Vigenere cipher, each letter from the key determines a substitution; there are 26 distinct letters, and as many distinct permutations."
Cam someone explain this please?

Since we're talking about classical cipher, I'll assume an alphabet will be the dataset we're working with; thusly, a letter from the alphabet will be a datum from the dataset.
A permutation defines the process that maps letters to possibly different letters. Two friends can agree on a single such permutation to exchange secret information.
If we want the encryption algorithm to be useful, different groups of people should be able to easily obtain different permutation by choosing a key.
However, if a different key can select the same permutation, then that key breaks the secrecy of the first key. Even worse, if a group of keys yields same (or even similar) permutation, then decrypting other messages encrypted using other keys in the group of keys becomes very easy. And this is very bad for an encryption algorithm.
Update for OP's comment
The above text discusses a "hypothetical" cipher (not Vigenere or any specific cipher) with weak keys, and explain some reason why it can be bad (it is bad regardless of what cipher we're talking about).


Zero Knowledge Password Proof I'm working on implementing a cryptographic system and I'm trying to understand the Zero Knowledge Password Proof concept. So here's some background:

To generate a secret key I am:

Doing an ECDH key exchange and generating 2 secret keys. One key is to encrypt messages and the other key is to HMAC sign the data. To derive the secret keys I am sending the username from the client along with the public keys and using the password on the client and server to derive the encryption keys by running the ECDH keys through a KDF function so that if the keys were retrieved the passwords could not be known.
Once I have these secret keys I want to use them to encrypt a message that does not include the password to send over to the server to authenticate that the client does indeed have the correct password.

I want to make sure that I implement this properly and I know that if I encrypt something that is preknown to the server that could be insecure because of some attacks that involve knowing the plaintext as well as the cipher. Do I need to just create a random string to encrypt? Any thoughts? Thanks!

I don't believe your protocol meets the standard definition of Zero Knowledge Proof, as a cheating verifier can learn more information about the secret than allowed.  In particular, suppose we have a cheating verifier (server) that has a list of one million potential passwords.  Then, he can run your protocol with a client that knows the password, run the KDF with all one million passwords, and see which one allows him to decrypt the message.  This allows the cheating verifier to check his entire dictionary of passwords at once.

If you are looking for a password verification protocol that avoids such weaknesses, I suggest you look at either the SRP protocol or the EKE protocol; both were designed specifically to avoid such weaknesses.

Now, as for your question about encrypting known plaintext, well, that's not actually a concern.  Strong encryption method (say, AES with a good mode) are designed to be strong against known (or even chosen) plaintexts.  Now, in your case, since you're just verifying knowledge of the shared key, you don't even need to encrypt anything; generating an HMAC of some standard data would be sufficient (or, at least, it would be if your protocol didn't have the above problem).


Encryption method with master key and user keys I am working on a concept for a game that in the end will allow data sharing via plain text, but I would like to give the user the option of encrypting the data so that other players cannot modify it, but the program/game will still be able to read the data for use otherwise.  My question then would be, is there a method of encryption where the game/program has a master key that can decrypt the data, but also the user can input their own password as a key to modify the data?  Thank you for your time.

I'll show a scheme with the following presumption:

the game has its own server key, this key is hidden in the game data somewhere (this usually cannot be secured completely, the game has to store the key somewhere);

So what you can do is to encrypt your game data with a randomly generated data key. If you use GCM mode of operation then you can verify if the data was tampered as well during decryption. This data key itself you encrypt (wrap) with the game key and the user key.

Now the game can always access and change the data. But the user needs to supply the user key. However, the user only has a password, so we need to convert that password to a user key. The way to do that is to use a Password Based Key Derivation Function such as PBKDF2, and use the output as the user key (note that you need to supply the PBKDF2 with a random salt that you generated & stored when the user account is created).

In the end you can make it as easy or hard as you want. One very interesting feature would be to let the user sign the game data as well; in that case the game can reject tampered game data.

It may also be a good idea to encrypt game data values separately, you can use a hash of the identifier of the specific data as Initialization Vector for the encryption/decryption.


How safe is my method I'm building a website. I have an API which takes 2 parameters: delete_user(user_id, hash).

And there is method to evaluate hash using SHA512:

String hash(String user_id)
{
   String key = "23jfk3jf...343fk";
   return SHA512(user_id + SHA512(key));
}

And the second method to validate:

bool validate(String user_id, String hash)
{
   if(hash(user_id) == hash)
   {
        return true;
   }
   else return false;
}

Every user knows his user_id and the hash value of his user_id.
user_id has length K symbols
the key in hash method has M symbols
hash method is not public to users, but validate method is.

Is it hard for a user to find any pair (String user_id, String hash), for which validate will return true (of course, user_id is not his own account's user_id). Let's say K = 10 and M = 50?

This is the pre-image attack on hash functions, i.e.

pre-image attack : given a hash value $y$ find a pre-image $x$ such that $y=h(x)$.

Good designed cryptographic hash functions have $\mathcal{O}(2^{n})$ classical pre-image resistance for $n$-bit output. The classical attack tries all possible input space to find a $x$ that hashes the target hash value. Due to the birthday paradox, we don't expect that all values exist in $2^n$ bit space. Some will occur more than one. This will not change the complexity.

Assuming that you are using base64 encoding to store the values, then each position in the string hash 64 possible character (= is used for padding).

Concentrate on a target user_id, an attacker will search 50 character keyspace to match. $$ \text{hash} \stackrel{?}{=}\operatorname{SHA512}(\text{user_id}, \operatorname{SHA512}(key_i)$$ This will make $64^{50} = 2^{6\cdot 50} = 2^{300}$ This is a huge number to deal with any available computing power. If you are using another encoding, you can adjust the values.

Hash functions are designed to run fast. This will also make an attack time fast if there is any. You can make it slow by making iterations or you can use already existing solutions like HKDF, PBKDF2, etc. They have iterations to increase the attack time.

Your scheme seems fine up besides there are some considerations;

There is already HMAC (Hash Based Message Authentication Code or keyed-hash message authentication code). It's security proven by Bellare, Mihir (June 2006). New Proofs for NMAC and HMAC: Security without Collision-Resistance under the assumption that the compression function is PRF.

You can use HMAC with SHA512, too. If the size does not really an issue, you the full output of the HMAC-SHA512, (or your scheme)


What is the right notion of security to use for file encryption? It seems that several file encryption systems do NOT use authenticated encryption. (E.g. gpg --symmetric and boxcryptor as far as I can determine). I understand that this is generally considered insecure, but is not demanded of full disk encryption. But for individual file encryption, for example where one is storing tax files for their own use later, it does seem that ciphertext indistinguishably under chosen ciphertext attack (IND-CCA) is too strong (I am not providing an oracle).  Is there any notion between IND-CPA and IND-CCA that one should consider?

Yes. $\:$ NME-CPA is such a notion, and is equivalent to modifying the IND-CCA notion so that

$\;$ the adversary can submit more than one ciphertext simultaneously
$\;\;\;\;$ and
$\;$ the adversary can only submit ciphertext(s) one time
$\;\;\;\;$ and
$\;$ that time must be after receiving the challenge ciphertext
$\;\;\;\;$ and
$\;$ after submitting ciphertext(s), the adversary also can't submit any plaintexts

.


Indeterminate Message Validity as a Noise Source in High Volume Channels Question Rephrased:

Does randomisation of valid and invalid messages in a high volume channel add security?

Scheme: valid messages are identified by a pre-shared random number sequence and noise- large volumes of random messages which can be encrypted by a large range of dummy keys- are ignored by the receiver but can be used to consume the resources of an attacker regardless of the attack mechanism/approach.

Any such arrangement using high volumes of noise must allow the receiver to ID valid messages. A truly random pre-shared number list would appear to be superior to any other sequencing.

Please take this with all respect and decency you deserve, but you're absolutely wasting your time with this elaborate scheme :-) What you propose is a protection system for true OTP transmissions. The OTP doesn't need protection.  We know this and I'm not going to further champion its virtues.  But I will put some numbers to my reasoning:-

Assume what I call computer Morse code (characters A-Z, 0-9, space, period).  That's a 38 character alphabet.
Also assume for comparison a 256 bit key for something like AES.
There is an answer here as to how much energy it would take to simply cycle through a 256 bit counter from a thermodynamics perspective. The answer quotes Bruce Schneier's back of the envelope assessment at needing  all the energy from a super nova (and more), which is quite a lot of batteries.
Using our computer Morse alphabet, 256 bits of entropy is equivalent to 49 characters.  That's a short message.
A more likely Twitter length message (160 characters) is 840 bits of entropy, or 2^840 permutations.
That would take many more super novae + even more batteries and it proves that it's impossible to brute force a Twitter length OTP message.
This is all based on having a good OTP generated with a good true random number generator made from physical components like cogs, diodes and wires.  Absolutely no cheating and using /dev/random and certainly not CryptGenRandom.

So don't bother making the NSA's life more difficult that it already is.

Where your system has merit though is channel masking.  The high and perhaps constant level of comms traffic obscures the time and number of real messages. This is standard counter intelligence against traffic analysis and chatter measurement as part of military communications intelligence.  Heavy stuff.

For no practical reason, this is a very recent super nova, lovingly named G1.9+0.3:-

and is more likely to reoccur than breaking a good OTP. Instead focus your effort on generating the OTP correctly.