How is the AEScrypt password related to the underlying AES key AES uses a key that is at most 256 bit.

I assume AESCrypt uses AES.

When a file is encrypted with AEScrypt, there is no limit to the length of the password.

What is the relation between the AESCrypt password and the key size of the underlying AES encryption?

I assume AESCrypt uses AES.

AEScrypt uses AES-256 in CBC mode. However, the program also uses SHA-256.

  When a file is encrypted with AEScrypt, there is no limit to the length of the password.

The Linux implementation of AEScrypt limits password to 1024 characters.  This means: it is practically unlimited, and you can use even very long passphrases. (The other versions of the program may vary in password length.)

  What is the relation between the AESCrypt password and the key size of the underlying AES encryption?

Nothing. The AES key will be always 256 bits. However, if the password has insufficient entropy, the AES key although 256-bits long will not be secure against password brute-forcing attempts.

Password security

The program uses salted (128 bit IV) SHA-256 to derive key to use from password. The hash is invoked 8192 times, which is quite small. This means that possible attackers are able to try brute-forcing quite a w few hundred thousand or a million passwords per second. Thus, passwords containing e.g. little entropy or just few dictionary words are likely broken with ease.

It is very likely that password is the weakest link. To have as much entropy as full AES-256 key, passphrase needs to contain around 25 words. Password would need to be somewhere around 50-100 characters. Generally, nobody often uses that long passwords (AEScrypt would allow it, see above).

Key use

The result of key derivation is a key that is used for AES (encryption/decryption) and HMAC-SHA256 (protect file integrity/prevent modifications). The same key is used for both purposes.

Issues (detected when analyzing code)

Ad-hoc salted hashing would be better replaced with scrypt. I'd like PBKDF2 more than hash, because it is well studied construct although it gives little other benefits.
It is not recommended to use one key for different purposes. (It does not seem to vulnerable, though.)
The AES implementation used is not side-channel free.
The /dev/urandom is used much more than is minimum needed. (Works badly together with any software that uses /dev/random.)

None of these appears very bad (i.e. easy to exploit in usual usage).


Is there an algorithm to hide text in another text, while preserving the meaning of the latter? Is there a way to hide a text message $A$ inside another text $B$ using a cryptographic cipher/algorithm, while preserving the sense/meaning of $B$ and without anybody being able to notice there is a message $A$ hidden in text $B$?

I am looking for something that can be processed either manually or by a computer.

For clarification: I don't mean to hide a message like “Attack X” saying “I went to X on holiday this summer” but an actual cipher/algorithm.

I know for sure there must be something, but being new to cryptographic and not knowing much about it, I don’t know where to look or what to look for. Is there a way to achieve this? If there is, could you (besides a reference) also provide a short example?

I think you can embed message $A$ into message $B$ with simple $LSB$, but you will have message $B'$ and maybe  alter the meaning. If you want the message $B'$ to retain the original meaning, you should design $B$ to do that.


Point at infinity for Jacobian coordinates Why is the point at infinity ∞ in affine space corresponding to (1 : 1 : 0) for Jacobian coordinates? How can this be shown? Is ist just to add the negative and see that the outcome is 1:1:0 or is there some "higher magic" to verify that a priori?

Jacobian coordinates are obtained by letting $x = X/Z^2$ and $y = Y/Z^3$.  The usual Weierstrass equation $y^2 = x^3 + a x+ b$ then, by multiplying both sides by $Z^6$, becomes
$$
Y^2 = X^3 + aXZ^4 + bZ^6
$$

An affine point $P = (x,y)$ corresponds to the Jacobian point $P = (t^2x:t^3y:t)$ for any $t \neq 0$.  Observe that letting $P = (X:Y:Z)$, one gets $X/Z^2 = (t^2x)/t^2 = x$ and $Y/Z^3 = (t^3y)/t^3=y$; that is, the affine coordinates of $P$, as expected.

The point at infinity $\mathcal{O}$ corresponds to $Z = 0$.  Plugging $Z=0$ in the above equation yields $Y^2 = X^3$.  The point at infinity has therefore for representation $(t^2:t^3:0)$ for any $t \neq 0$ ---you can check that $(t^3)^2 = (t^2)^3$.  For example, taking $t=1$ yields $\mathcal{O} = (1:1:0)$, which is the usual representation chosen to represent the point at infinity in Jacobian coordinates.  But any $t \neq 0$ is valid; $(1:-1:0)$ is also a valid representation for the point at infinity in Jacobian coordinates (this corresponds to $t=-1$).

Note. The case $t=0$ is not valid because $(0:0:0)$ is not.  This supposes that the elliptic curve is defined over a field.  Over a ring $R$, $t$ should be chosen in $R^*$.  Remark that if $R$ is a field then $R^* = R \setminus \{0\}$.


Cracking a hash which descends to a single value after repeated hashes Assume I have a hash function (such as the one below) and a cipher, and I know that if I repeatedly hash any string over and over again, it will eventually descend to one unique value.

Is there any known way to crack a hash function following this pattern? Does this property lend itself to any exploitable vulnerabilities?

Hash function (in python):

def compute_hash(uinput):
    if len(uinput) > 32: return
    blen = 32
    n = blen - len(uinput) % blen
    if n == 0:
        n = blen
    pad = chr(n)
    ninput = uinput + pad * n
    r = ""
    for i in range(0, blen, 4):
        s = ninput[i:i+4]
        h = 0
        for j in range(len(s)):
            h = (h << 4) + ord(s[j])
            g = h & 4026531840
            if not(g == 0):
                h ^= g >> 24
            h &= ~g
        r += chr(h % 256)
    h = ""
    for c in r:
        h += c.encode("hex")
    return h

This specific hash function is weak; it appears that what this hash function does is pad out the string to be hashed into a 32 byte string, and then take the 8 4-byte substrings, and maps each substring individually into an individual byte.

This immediately makes it trivial to find a preimage; start with a random 31 byte preimage (there appears to be a bug in the code if it is presented with a 32 byte input), hash it, and for every byte of output that is wrong, modify the corresponding 4-byte substring in the preimage, and repeat until the hash is the expected value.

However, to answer the general question of whether a hash function with the specific property that is necessarily weak, well, I believe that we can produce an example of such a hash function that is not.  One such example would be:

Given the empty string, outputs the empty string
Given a string $S$ of length $L$, generates the first $L-1$ bits of $SHAKE256(S)$

This function would appear to be strong given a long input (because we believe that SHAKE256 is a strong hash function), but repeated application of this hash function eventually will cycle at the empty string.


Memory-expensive hash from an array of hashes? Why can't people make a hash function that requires dozens of mega bytes of memory instead of cpu to avoid all the cracking and hacking?
What I have in mind myself is this:

We have an input $X$, we choose hash function SHA2-256,  make a multi-megabyte array.
Hash $X$ and put it in the beginning of the array.
Hash the previous hash and put it next to it.
$(hash(x), hash(hash(x)))$
Step 3 until the array is full
Reverse the array
Hash the array in N passes, In each pass reading 1 byte and skipping $N-1$

I'm planning to use this for authentication, I'm not sure if it's a good idea or not, just need to know if it stop the damn GPUs from cracking my passwords.

EDIT:

This is why people shouldn't make their own encryption – see the comment by John Meacham proving this algorithm insecure. An easy fix IMO is to require the algorithm to go multiple passes over the reversed array. Like: get the first byte, skip 15 bytes, get another byte and so on… and when we reach end of the array, start from beginning, only this time we get the second byte, skip 15 bytes and so on… and we do this 16 times until we have read every byte in the array. Of course number $16$ is probably not a good number but still I think the whole idea is good.

The premise that people cannot make a memory intensive password hashing function is incorrect. scrypt does approximately what is described in the question. Of course you still want to limit the amount of memory, especially if many of these hashes are to be calculated in parallel.

Furthermore, you could have a look at the password hashing competition where m_cost is specifically mentioned as a possible parameter to the hash function. You'll have to look at the candidates to see if that parameter is present and how it is used though.

Note that the main idea of using larger amounts of memory is to protect against brute force attempts that make use of hardware acceleration. Just scaling up the amount of memory to rely on the speed of memory access does not make sense; an attacker may have a system that does faster memory access than your system. It's less likely that an attacker has both hardware acceleration and a hugely fast & large memory system.


How do you perform the invert operation of Pm = kP on elliptic curve? I'm stuck on this, may be due to the fact I'm missing something.
If I'm right, in order to reduce a Message to a point on an elliptic curve the operation is:
$\text{MsgPoint} = \text{msg}\cdot P$  with
  - $P$ being the Base point of the curve,
  - $\text{msg}$ being the message converted to an integer
  - and the operation $\cdot$ being the scalar multiplication

My question is: How do you perform the inverse operation?
formulated differently:
I know $\text{MsgPoint}$ and the Base Point $P$ and I want to find the $\text{msg}$?

In fact, I'm searching a way to retreive the Message from its elliptic point value:
$$P_m + kP_B - n_B(kG) = P_m + k(n_B)G - n_B(kG) = P_m  $$
I'm able to get back $P_m$ (decode), but $P_m$ is a Point on the elliptic curve, which is obtained by computing in the encode:
$P_m$ = scalar_mult(message_converted_to_integer, curve.G)
How to get the message_converted_to_integer value?

How to you perform the invert operation ?

Actually, we hope that is a hard problem.  After all, if someone has an efficient way, given $G$ and $xG$, to recover $x$, almost all crypto based on elliptic curves is broken (exception: isogeny-based crypto).

So, what do we do?  Well, we arrange things so that we don't need to solve this hard problem to decrypt.

One way is the change how we do things.  Instead of trying to encode the message as a point, we can use ECIES:

We have a private key $k$ and a public key $kG$
To encrypt with the public key, we pick a random value $r$, and compute both $rG$ and $r(kG)$.  Then, we transform $r(kG)$ into a symmetric key, and use that to symmetrically encrypt the message.  Then, the ciphertext consists of both $rG$ and the encrypted message.
To decrypt with the private key, we compute $k(rG) = r(kG)$, and use the exact same transforming to turn that into the same symmetric key, and then use that to decrypt the message, revealing the original plaintext.

This works quite well, and avoids any awkwardness about converting a message into a elliptic curve point in a reversible fashion...


Can ECC correctness issues allow “remote attackers to spoof ECDSA signatures”? CVE-2015-2730: Mozilla Network Security Services (NSS) before 3.19.1, as used in Mozilla Firefox before 39.0, Firefox ESR 31.x before 31.8 and 38.x before 38.1, and other products, does not properly perform Elliptical Curve Cryptography (ECC) multiplications, which makes it easier for remote attackers to spoof ECDSA signatures via unspecified vectors.

  The formulas appearing in ecp_jac.c do not handle the case when the addition produces infinity or adds a point to itself. An attacker can use this to generate specially-crafted signatures that cause the validation algorithm to compute the incorrect point.

For the equations and other details, please check the following link: https://bugzilla.mozilla.org/show_bug.cgi?id=1125025

Could this Elliptic Curve Cryptography issue really lead to spoofed ECDSA signatures or is this purely a theoretical attack?

Glancing through the Mozilla notes, it would appear that it would actually be infeasible to generate a forged signature (that is, not involving the private key) that would tickle this bug.  In fact, if someone could generate a signature that would tickle this bug, they could deduce the private key (and so wouldn't need exploit this implementation flaw).

During ECDSA signature generation, the verifier creates two EC points $u_1 G$ and $u_2 Q$, where $Q$ is the public key, and $u_1, u_2$ are two integers computed as a part of the verification problem.  The verification routine then adds these two points, apparently, the bug happens if either $u_1G = u_2Q$ (the addition is actually a point doubling), or if $u_1G = -u_2Q$ (the result of the addition is the neutral element).

However, if either is true, then $\pm u_2^{-1} u_1 G = Q$, and hence $\pm u_2^{-1} u_1$ is the private key.  Hence, if the attacker can generate a signature that satisfies either of these two conditions, he can compute $u_1, u_2$, and then directly recover the private key.  And, with the private key, the attacker can sign anything he wants.

Now, Mozilla was quite correct in fixing this bug; however it doesn't look like it's exploitable.


GCM mode GHASH sensitivity to timing attacks In GCM mode of authenticated encryption, is it a security concern if the GHASH implementation timing can vary?

If the timing varies according to the AAD/ciphertext data, it looks as though that doesn't matter because that data is public anyway. But if the timing varies according to the GHASH key, does that reduce security?

If the timing varies with public information, then it's not a problem.  If the timing varies with secret information like the key in GCM, it is a problem.  (While GCM feeds only AAD and ciphertext to GHASH, other AEAD schemes like GCM-SIV feed the plaintext to GHASH/POLYVAL; timing dependent on any secret information is a problem.)

It's hard to make a fast software implementation of GCM that does not vary with the key, since you're evaluating a polynomial in $\operatorname{GF}(2^{128})$ at the GHASH key.  (t is tempting to make a much faster software implementation that does vary with the key by using variable-time table lookups.)  Worse, each block of the message (AAD or ciphertext) figures into the GHASH formula exactly once, but the key, and its square, and its cube, etc., figures in many times.

And CPU instruction sets and programming languages are historically designed to support integer arithmetic, not Galois field arithmetic, so even on a CPU that does support Galois field arithmetic natively, reliably taking advantage of it requires nontrivial engineering effort.


Why do we implement a protocol? In general, after we design a secure cryptographic protocol and make sure that it is efficient (e.g. through complexity analysis) we implement it.

Questions:

Do we implement it for proof of concept?
Do we implement it to support our claim that the protocol is efficient?

I assume the question is related to academic work: why do we implement a protocol if we already know how efficient it is by a complexity analysis? The answer depends very much on the type of protocol. However, the answer typically is that a theoretical complexity analysis usually does not suffice to understand the concrete efficiency. If the "previously best known protocols" required a certain number of operations and your improvement is exactly the same but with less operations, then this could suffice. However, this is rarely the case. Rather, your protocol may have less exponentiations but more communication; it may have less symmetric operations but be less memory efficient. It is almost impossible to really know that it's more efficient without implementing it.

Another issue, which is certainly the case in secure multiparty computation (where I work), is that implementation helps us understand what the bottlenecks are. In fact, we are very often surprised at what the "expensive" part is. In just one example, in this paper (sorry for the self citation, but it's just a good illustrative example), we were very surprised to find out that a large percentage of the time went on a matrix inversion which had nothing to do with the cost of the cryptographic operations. Without implementing, we never would have found out about this.

One thing that as a field we have to improve upon is the quality of our work in this sense. We don't have good benchmarks and implementations and comparisons are all very ad hoc.

I will finish with one final comment. Despite the above, not all new protocols need to be implemented in order to be published. When the protocol contains an important new idea, or when it clearly beats the previous work, then it can be published without an implementation. However, follow up work with implementation is always important. (Of course, protocols whose claim is that of asymptotic and theoretical efficiency never need to be implemented.)


What is Regular Digest/Hash Function I was reading a paper, Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing where there was a reference to message digests being 'regular'

Here, MD is a message digest. I've not been able to find anything online about the regular property of message digests/hash functions. Does anyone here know about it?

The first Cryptography textbook implicitly containing word regular for hash functions may be in Stinson's book Cryptography Theory and Practice, First Edition, 1995, around pages 234-237. T

  Since we are interested in a lower bound on the collision probability, we will make the assumption that $\mathbf{h^{-1}(z) \approx m/n}$ for all $\mathbf{z \in Z}$. (This is a reasonable
  assumption: if the inverse images are not approximately equal, then the probability of finding a collision will increase.)

Stinson's book is pointed out by Bellare and Kohno's article,

  Stinson, in the first edition of his book, shows that Equation (1) is true under the assumption that $h$ is regular. There is no information regarding the case where $h$ is not regular.

This term is not defined in Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing, 1996

  Of course, the latter attack can be prevented if $\text{MD}$ has additional properties besides being collision-free (e.g., if MD is “regular”).

Only mentioned as an additional requirement for the hash function.
This  definition from Hash Function Balance and its Impact on Birthday Attacks, 2004, by Bellare and Kohno

  Textbooks tell us that a birthday attack on a hash function $h$ with range size $r$ requires $r^{1/2}$ trials (hash computations) to find a collision. But this is quite misleading, being true only if $h$ is regular, meaning all points in the range have the same number of pre-images under $h$; if $h$ is not regular, fewer trials may be required.

A brief result from the Bellare and Kohno's article;

Let $C_h(q)$ be the probability that the birthday attack on a hash function $h: D \to R$ succeeds in finding a collision in $q$ trials.

With balance measurement $\mu$ and up to constant factors

$$C_h(q) = \binom{q}{2} \frac{1}{r^{\mu(h)}}.$$

A collision expected with $r^{\mu(h)/2}$ trials.

$\mu(h) = 1$ meaning that $h$ is regular and this is standard birthday collision.
$\mu(h) = 0$ meaning that $h$ is a constant function so attack has $\mathcal{O}(1)$

This, actually indicates that the values are between regular and constant function. If the balance $\mu(h) =1/2$ than a collision can be found in $r^{1/4}$ trials, less than $r^{1/2}$

Result: If a hash function is not regular, finding a collision is easier than regular hash functions.

Bold in quoted text are mine


Cracking transposition cipher I have a task to decrypt custom made transposition cipher, as I'm not the cryptography expert, I would appreciate any help.

I've been given the table of characters ...

M A N B C
D E F G H
I K L O P
Q R S T U
V W X Y Z

... with images representing:

swap
up twice
left twice

(There's no word about the order of these steps)

The hints are:

MAN
NP = CL

Texts to decode is: ET KO KF

I've tried to fit the steps for getting CL out of NP, but with no luck. Also, there's no sign if the characters are "pushed" while making steps, or the character we're moving is being swapped with the next letter (I'm not even sure if we're moving characters or columns or something else). I know it might seem not explained enough, but as I'm not an expert, I wanted to ask you as it might be some known pattern.

This looks like a Playfair cipher with MAN as the key.

For characters not in the same row / column, you make a rectangle with the encoded characters at the corners, and the characters in the same row on the opposing sides of the rectangle form the decoded letters. For NP we have -

[N]--B-->C
 F   G   H
 L<--O--[P]

Which yields CL.

So for ET we have -

[E]--F-->G
 K   L   O
 R<--S--[T]

Decoding to GR.

For KO we need a new rule, since K and O are on the same row. For items on the same row we simply shift each letter left one position, wrapping back to the start of the row if needed. This means KO yields

I<--[K] L<--[O]

In other words, KO -> IL.

Finally for KF we have -

 E<--[F]
[K]-->L

Which yields LE

So ET KO KF gives us GRILLE.


What are the required properties of a PRNG to make it suitable for a stream cipher? As an example, if a PRNG passes the BigCrush test suite, and has a period of 2^1024, can it be used on its own to make a secure stream cipher?

What are the required properties, and similarly, what are the bad properties that the PRNG must not have?

The best known algorithm to guess the next bit with probability near 1, without knowing the $n$-bit seed, has to cost approximately $2^\lambda$ bit operations, where $\lambda \leq n$ is the security parameter.

You can't determine this by feeding the output of the PRNG to a generic statistical hypothesis test, because by its very nature that statistical hypothesis test has only very limited hypotheses about how the PRNG might differ from a uniform random string of bits.  These generic statistical hypothesis tests are designed without particular knowledge of the PRNG.

You can really determine this only by feeding it to a swarm of cryptographers, but that works only if it appears as tasty to cryptographers as a bleeding hand to a piranha.

Cryptographers are a picky bunch that aren't much interested in spending their time on designs that aren't really interesting for some reason, like protecting trillions of euros of financial transactions, or performing better than modern standard stream ciphers today (like ChaCha, or AES-CTR with hardware acceleration) at the same conjectured security level.

And they don't usually want to spend time on designs whose designers haven't already studied and demonstrated to resist a litany of standard attack strategies.


Two different approaches for Key Expansion using the AES-256 algorithm? I am implementing AES 256-bit Algorithm from the Theory given in the book, "Cryptography and Network Security" by Behrouz A. Forouzan.

The Algorithm described in the Book in relation to Key Expansion, defines AddRoundKey like this:

From the given 32-Bytes Cipher Key, I am supposed to generate 4 * (Nr + 1) words. Nr being the number of rounds which is equal to 14 in 256bit AES and each word is equal to 4-Bytes.

So, according to the equation, 4 * (Nr + 1), We have total 4*(15) = 60 Words to be generated. Those 60 words are w[0],w[1],w[2],w[3],…,w[59]. The first 8 words would be generated directly from the given 32bytes cipher key:

w[0] = First 4Bytes of Cipher key
w[1] = Next 4bytes of Cipher Key
w[2] = Next 4 bytes of Cipher.
…
w[7] = last 4-bytes of Cipher key.

The remaining words (w[8] to w[59]) would be generated according to the following Formula:

If, i mod 8 is not equals to 0 and i is the word number from 8 to 59

    W[i] = W[i-1] ^ W[i-8]
    ; ^ = XOR Operation

else

  W[i] = t + w[i-8]

where t equals to, SubWord(RotateWord(W[i-1])) ^ RCon(i/4). If i mod 4 = 0, but imod8 is not equals to 0 then, W[i] would be W[i] = SubWord(W[i-1]) + W[i-8] After the above algorithm is implemented, It is quite easy to calculate AddRoundKey.

But Wikipedia's "Rijndael key schedule" article has a totally different method of calculation which I am unable to understand. They use different techniques, and there are few Constants like n and b, which weren't mentioned in the book, nor are they mentioned anywhere else. Yet, Wikipedia's Algorithm is using them.

I would like to know the difference between the AES256 algorithm presented in the book and the AES256 article on Wikipedia. Can you explain and/or help me understand why there are two different approaches for Key Expansion in relation to the AES-256 algorithm?

The descriptions are the same thing.

The n and b constants on Wikipedia are simply the original key length in bytes and the number of bytes in the generated key schedule. Here, you have a 256-bit key generating a 60-word keyschedule, so n = 32 and b = 240.

I'm going to re-structure the provided algorithm to be more clear. The special case i mod 4 should be broken out as a separate block, I'll tweak the conditionals, and I'll reorder the cases to occur more sequentially.

if i mod 8 = 0:
    t = SubWord(RotateWord(W[i-1])) ^ RCon(i/4)
    W[i] = t + w[i-8]
else if i mod 4 = 0:
    W[i] = SubWord(W[i-1]) + W[i-8]
else
    W[i] = W[i-1] ^ W[i-8]

It's the same code, just written a little differently. It already looks more like the Wikipedia description.

The version here is word-based and uses the constant 8, whereas the Wikipedia version uses byte offsets and the variable n, which means it takes a bit of effort to compare computed offsets between them. Just in case it isn't obvious, note that W[i-8] here is equivalent to the frequently used phrase "four-byte block n bytes before the new expanded key" on Wikipedia.

Now compare the structure:

The first 8 words are a straight copy of the key.

Compare Wikipedia step 1 with the initial w[0] ... w[7] assignment here.
Both descriptions have a loop that generates the keys in sets of 8 words.

This is step 3 on Wikipedia. (The substeps there aren't numbered, but I'll refer to them as 3.x.)
The first word of each set of 16 has special processing.

Compare Wikipedia step 3.1 with the case i mod 8 = 0 here.

The t value in this step is the same as the "key schedule core" from Wikipedia. Note that the index value to RCon in the Key Schedule Core only increments once per loop. Here it increments 4 times per loop because it is a word-based counter, but we divide by 4 to re-normalize it.
The next 3 words have the simple definition: XOR the previous word with the word 8 words back.

Compare Wikipedia step 3.2 with the else case here.
The next word (the fifth of the round) has special processing. Compare Wikipedia step 3.3 with the case i mod 4 = 0 here. (Note that the i index here is zero-based, so i mod 4 = 0 means we're at an index of 5.)
The next 3 words have the same definition as two points above. Compare Wikipedia step 3.4 with the else case here.

That's all. They're the exact same thing, down to the step.


CKM_RSA_PKCS vs CKM_RSA_X_509 mechanisms in PKCS#11 What is the exact difference between the CKM_RSA_PKCS and CKM_RSA_X_509 mechanisms in the PKCS#11 v2.20 specification (Please explain with an example)?

As very clearly indicated by the specification, CKM_RSA_X_509 performs "raw" RSA. Raw RSA is simply modular exponentiation. So it performs just the RSASP1 function in the PKCS#1 standards. This means that a user should - at the minimum - also provide a secure padding mechanism. Otherwise the conditions to perform a secure RSA signing operation are not met.
CKM_RSA_PKCS on the other hand also performs the padding as defined in the PKCS#1 standards. This padding is defined within EMSA-PKCS1-v1_5, steps 3, 4 and 5. This means that this mechanism should only accept messages that are 11 bytes shorter than the size of the modulus. To create a valid RSASSA-PKCS1-v1_5 signature, you need to perform steps 1 and 2 of EMSA-PKCS1-v1_5 yourself.
Both of these mechanisms are only building blocks for creating a signing algorithm. You won't get a valid PKCS#1 signature by supplying random data to either mechanism. These methods have been defined to give more control to the user of the mechanism.
Sometimes protocols such as older SSL specifications do use their own signature schemes (concatenating an MD5 and SHA-1 hash, leaving out the hash indicator). Those protocols cannot be supported without a direct implementation or lower level primitive being available.
Another reason that CKM_RSA_PKCS exist is that it may not be very efficient to perform the full PKCS#1 v1.5 signature generation on the security token. It is very inefficient to send an entire text document to a smart card. Just sending a hash structure calculated on the host computer is much faster.

A final note: you should never let an attacker be able to use CKM_RSA_X_509 for the keys in your token, nor should you give him alter the padding you supply to that mechanism. In general it is better to use up to date mechanisms that represent complete signature schemes.
EDIT: apparently access to the private key operation in itself is not enough to break the RSA key. Of course letting an attacker have access to the private key operations is insecure in itself, but it won't allow copying / breaking the private key if the operation is well implemented. I presume it does open some attack vectors for the simple reason that an attacker has more control over the input to the modular exponentiation.


What does the $\|$ operation mean in cryptographic notation? I am studying elliptic curves problems, which also includes study of related protocols such as ECIES. The problem is that I don't understand the notation $\|$. What does this operation mean?

Some stuff is mentioned on Wikipedia's Integration Encryption Scheme article, but this algorithm is better explained in the book Guide to Elliptic Curves. This operation is mentioned in Alice's 3rd step:

$$ k_E \| k_M = \operatorname{KDF}(S \| S_1) $$

In terms of algorithms, it usually means concatenate - as in, join two binary (or otherwise defined) strings together (in this order). For wikipedia's cryptography articles that's nearly always the case.

When it is on the left side of an assignment, this means split the string from the right side into these component strings. This makes only sense if the length of most components is already fixed, of course – like here for the encryption and MAC keys.

In terms of programming languages such as C, however, it means logical or. Whilst it is unlikely the authors have confused them, it is something to be aware of.

Different notations may be used for string concatenation, including the single pipe sign $s_1 | s_2$ and the plus sign $s_1 + s_2$, although the double pipe sign as in the question seems prevalent.


The parameters included in TLS 1.2 server signature in the ServerKeyExchange In TLS 1.2, section 7.4.3 in the standard documentation on Server Key Exchange Message, it says that the parameters covered by the digital signature are as follows:

  dh_p
           The prime modulus used for the Diffie-Hellman operation.

  dh_g
       The generator used for the Diffie-Hellman operation.

  dh_Ys
       The server's Diffie-Hellman public value (g^X mod p).

These parameters are hashed first. My question is: when the hash of these parameters is computed, is it computed over a concatenation of these parameters? or are they combined in any other way?

Section 7.4.3 specifies this:

  struct {
      select (KeyExchangeAlgorithm) {
          case dh_anon:
              ServerDHParams params;
          case dhe_dss:
          case dhe_rsa:
              ServerDHParams params;
              digitally-signed struct {
                  opaque client_random[32];
                  opaque server_random[32];
                  ServerDHParams params;
              } signed_params;
          case rsa:
          case dh_dss:
          case dh_rsa:
              struct {} ;
             /* message is omitted for rsa, dh_dss, and dh_rsa */
          /* may be extended, e.g., for ECDH -- see [TLSECC] */
      };
  } ServerKeyExchange;

The meaning of digitally-signed is explained in section 4.7. In this case, the above means that the input to the signature algorithm (i.e., that which is hashed) is the concatenation, in that order, of:

the client random (32 bytes), as sent by the client in the ClientHello;
the server random (32 bytes), as sent by the server in the ServerHello;
the encoding of the ServerDHParams structure. This is the complete encoding, including length bytes.

The ServerDHParams structure is itself defined as:

  struct {
      opaque dh_p<1..2^16-1>;
      opaque dh_g<1..2^16-1>;
      opaque dh_Ys<1..2^16-1>;
  } ServerDHParams;     /* Ephemeral DH parameters */

Thus, what goes in the hash function, immediately after the 64 bytes for the client and server randoms, are the two bytes that encode the length of dh_p, followed by dh_p; then the two bytes for the length of dh_g, then dh_g; finally, the two bytes for the length of dh_Ys, then dh_Ys.

Since the ServerDHParams structure is itself sent over the wire as part of the ServerKeyExchange, it is simpler to think of it as follows: what is signed is exactly the concatenation of the client random, server random, and the bytes encoding the ServerDHParams, as sent and received.


SHA-256 Hash over multiple SHA-256 Hashes I am trying to implement a checksum over multiple files.
We can assume, that i have a package containing N files. I want to identify such a package uniquely by following calculation:

SHA256-Hash over every file.

I save the result bytes of the hash-function for every file.

And then i calculate the sha256 hash over the concatenated file-hashes.
The reason, why i hash the file-hashes again is, that i want to provide a shorter footprint of the whole package.

From my point of view this should be enough to identify a package. But my knowledge concerning cryptography is really limited at all - so i wanted to ask the experts.

Thanks in advance

Yes, this is fine for verifying that the file contents match the original. You are basically using a hash list. As long as SHA-256 is collision resistant, there is no way to find a hash that would be ambiguous and refer to two or more known file sets.

In addition to the potential issues mentioned in the comments, storing just the aggregate hash value leaves you with no way to figure out which file failed to match. That is why it is common to store the intermediate hashes as well to see which file would have to be e.g. downloaded again.


Unit testing a library RNG and its seeding for practical security Suppose I have a cryptography library that provides me with a black-box random number generator that is supposed to be suitable for long-lived key generation.  (Under the hood it may be assumed to use some combination of /dev/random or equivalent, and stretching with a CSPRNG.)

I would like to write a unit test that can detect implementation errors that would result in practical failures of security.  For instance, it should reliably detect the infamous CVE-2008-0166 (Debian OpenSSL weak key generation) if applied to a version of OpenSSL with that bug.  Note that statistical tests as discussed e.g. in this earlier question will not do the job by themselves, because of the CSPRNG in between me and the guts of the black box (the CSPRNG itself has already been checked by use of test vectors).

How might this be accomplished?

You're not going to like this answer, but strictly speaking, you can't.

In a number of specific cases you can do what you want. For example, in the specific case of the Debian PRNG debacle, you could detect that (and as a matter of fact, bad keys generated by this PRNG failure were tracked down). But that's because the RNG was not seeded much at all and ended up with some small number of possible states. (I'm saying RNG not CSPRNG because I'm not considering any cryptographically insecure pseudo-random number generators.)

But if the output stage of your PRNG comes from a suitable pseudo-random function, it will pass all your tests. AES in counter mode, an iterated hash function, and so on will all be just fine -- these outputs are themselves pseudo-random functions and therefore pass all your pseudo-random tests. It will be cryptographically secure from a mathematical reference point. If it is insecure, it will be insecure because of an operational failure, like the Debian problem, which was operational, not mathematical.

You are only going to find practical failures of a PRNG by white-box testing. You will have to have a reasonably smart crypto person to code-review it. You will have to look inside it to see if it is constructed correctly.

Consider this as a badly-built PRNG: imagine a chip with a PRNG that is seeded with a completely random 64-bit number to which is added the chip's serial number, and then a high-quality output stage (Yarrow, SP 800-90 DRBG, etc.) generates random bits from that seed from then on.

In other words, for the entire family of chips, there's a single 64-bit chunk of entropy E, and each chip has put into it E+1, E+2, ... E+N for the N chips we manufacture. Call this number E_n.

We'll presume that all re-seeding is broken and has no effect. You very likely won't be able to tell this from testing the output only.

You might in some cases -- for example, let's suppose that the output is a naïve iterated hash. You might be able to detect that the substring R[i..i+31] is equal to SHA256(R[i-32..i-1]). But be lucky to detect that, because you'd have to explicitly check for it.

Similarly, testing its output can tell you if the output function isn't a PRF, but not a lot more than that, and these days the errors aren't going to be because of the output function. Even dummies are going to get that right; look at the Debian debacle again. The problem was seeding, not pseudo-randomness.

You wouldn't find it if the bogus chip hashed in E_n along with each iterated hash, or if there was an HMAC. You wouldn't find it if there was a simple counter hashed in, either. You almost certainly wouldn't detect anything amiss if the PRNG used a cipher in counter mode with E_n as the key, either. (There are plenty of edge cases where you would -- for example, if you used DES in counter mode and happened to pick a weak key, you might detect that. Bear with me for the general case here.)

This completely bogus random number chip has only 64 bits of good randomness in the entire chip production, and yet no black box testing is going to detect that. You're only going to find the problem by auditing its design and implementation, not by testing its output.

I told you you weren't going to like my answer, but there it is. Black box testing will only detect a small class of stupid errors, and none of the evil ones.

Jon


Is this a valid "fix" for deterministic encryption in encrypted databases? It appears (after doing some light research) that for encrypted databases to be practical enough to be usable, deterministic encryption is required, specifically with regard to the type of encryption that always produces the same ciphertext for a given plaintext and key pair. I understand that deterministic encryption allows equal plaintext values to be detected, is possibly vulnerable to frequency analysis and lacks semantic security i.e. is vulnerable to chosen plaintext attack.

However, is it possible to minimize or remove these drawbacks by:

ensuring only authorised use of the database (to prevent chosen plaintext attacks), and
by injecting known encrypted tuples of carefully selected (bogus) values to balance out the cyphertexts to deflect frequency attacks? These bogus values would be dropped from a user's query results at the user's end prior to being presented to the user.

Of course, this would mean possibly doubling the database size, but I would like to ignore that for now...

I work in the area of data-at-rest encryption, so I feel fairly qualified to answer your questions.

Re. 1: Access control is well and good but it typically isn't modeled in cryptographic proofs of security because it's an extra assumption, and proofs try to use as few assumptions as possible. It's obviously important for the real-world security of a database, but to be safe you have to assume everybody is an attacker, even someone with valid credentials.

re. 2: Your strategy for deflecting frequency analysis is usually called 'homophonic encryption' in the literature. It is indeed useful for making certain statistical attacks much more difficult, but its efficacy is highly dependent on the particulars of the type and number of bogus values injected, and crucially also on the distribution of the plaintext data.

If your database will primarily be doing information retrieval and/or search-type stuff, a much more secure (in theory and practice) primitive is searchable symmetric encryption. It gets you the functionality without needing deterministic encryption.


key size of public key in McEliece The length of public-key matrix in McEliece cryptosystem is $n \times k$. Then the key size is $\frac{n \times k}{8}$ bytes. But I find that the key size is $\frac{(n-k) \times k}{8}$ bytes. why ?

Let $G$ be the public key matrix. With Gaussian elimination, you can find a Matrix $G'$ with $G = (E_k | G')$, where $E_k$ is the identity matrix with dimension $k$. Then, you only have to store $G'$. And $G'$ has the dimension $(n-k) \times k$.

Source: German Wikipedia (https://de.wikipedia.org/wiki/McEliece-Kryptosystem)


Elliptic curve one time signatures This is kind of an academic question, but I wonder if it's possible to build an intentionally one-time signature scheme with elliptic curves?

I assume you could do it by supplying ECDSA with deterministic input instead of randomness during signing, resulting in "sudden death" if two messages are signed by the same key. This however includes all the complexity of ECDSA. I feel like there's probably a way to get one time signatures out of elliptic curves via some simpler construct.

(One-time-ness is normally an undesirable property, but imagine it's a desired property. You explicitly don't want multiple signatures per secret key, so you want to strongly discourage that by making it result in loss of security.)

Supplying ECDSA with deterministic input doesn't make for a one-time signature—RFC 6979 chooses the per-signature secret as a deterministic but secret function of the message.  However, there is a variant of ECDSA—or EdDSA—that could probably work.

In ECDSA, a public key is a point $A$ on a curve with standard base point $G$, and a signature on a message $m$ is a pair of integers $(r, s)$ such that $$r = f\bigl(x([H(m) s^{-1}] G + [r s^{-1}] A)\bigr),$$ where $f$ maps a coordinate to a scalar.  For any particular $r$, there are only approximately two $s$ values that work—$s \equiv \pm [H(m) k^{-1} + r k^{-1} a] \pmod n$, where $k$ is the per-signature secret, $a$ is the secret scalar such that $A = [a]G$, and $n$ is the order of the group.  (There may be a few other $s$ values because of the weird $f$, but there aren't many.)

Instead of choosing $r$ at signing time, you could choose $r$ at key generation time: then a public key is a pair $(A, r)$ and a signature is an integer $s$ satisfying the same equation.  Then publishing two different signatures, that is two different $s$ values for a single $r$ value and therefore for a single per-signature secret $k$, would leak the private key to anyone who can solve a trivial linear equation.
Similarly, in EdDSA, a signature is a pair $(R, s)$ of a point $R$ on the curve and an integer $s$ such that $$[8 s]G = [8]R + [8 H(R, A, m)] A.$$  Again, you could make $R$ part of the public key $(A, R)$, leaving only $s$ in the signature.

This doesn't really enable any simplifications—where previously you could have (say) 32-byte public keys and 64-byte signatures, now you have 64-byte public-keys and 32-byte signatures, and the cost of signing and verifying is exactly the same.  But it does guarantee one-time signatures on threat of leaking the private key.


DES algorithm exhaustive key search 2^55 instead of 2^56 How is it possible to do an exhaustive key search (DES algorithm) and only search for 2^55 instead of 2^56 keys ?

This is a slide from my course if this helps you. I don't understand it.

What you want  follows from the DES complementation property so only the remaining 55 key bits need to be brute-forced.


Undefined $E_y(1,r_{i,j,1})$ notation in cryptography paper, suspect ElGamal-like I'm trying to understand a paper that uses the notation $E_y(1,r_{i,j,1})$ (full text available in link, used just once on Page #35, 6th page of pdf, Section 3.3, Step 1c) in the context of an encryption similar to ElGamal.  I don't understand why/how $E_y()$ takes two inputs.

The $r_{i,j,n}$ part is well defined (series of random numbers).  I've figured out $E_y(x)$, which isn't defined in the paper, but used as an ElGamal-like encryption with previously defined public key $y$ (not to be confused with the $E_{k,i}$ or $E_k$ terms which aren't functions and are just lists of cards for the $k$th deck of cards), though I had originally thought $E_y(x)=xy^r$, based off the proof of theorem 2 on the very last page I think it is the ordered tuple $E_y(x)=(g^r,xy^r)$.

What could two arguments represent? I'm guessing one is the message to be encrypted, and the other is specifying the $g$ or $r$ term.

An ElGamal ciphertext encrypting a message $m$ (as you say) is a tuple $(g^k,m\cdot y^k)$ when working in a group $G$ generated by $g$ with public key $y$.

Some people make the "randomizer" $k$ explicit by writing $E_y(m,k)=(g^k,my^k)$ to denote that they can control and know this input and that this input is not freely chosen by the encryption algorithm (typically if one uses ElGamal encryption as a commitment and requires proofs of knowledge about the plaintext - I guess this is what the guys do). So, people often write $E_y(m)$ if they do not care what the value of $k$ is and write $E_y(m,k)$ if they want to know what the value of $k$ is. Then, $E_y(1,k)$ is just an encryption of the identity in $G$ giving ciphertext $(g^k,y^k)$.


Encrypt a small amount of data with a password derived from PBKDF2 I have a small amount of data (about 128 bits) to secured with a strong password.

I plan to run PBKDF2-SHA2-256 on the password and a 128 bit random salt to generate a 256 bit derived key. Then with the first 128 bits of the derived key (Key1), XOR it with the data to encrypt it. Then create a MAC by using the last 128 bits of the derived key (Key2) i.e. HMAC-SHA-256(Key2, encrypted data). The data would be stored as salt | encrypted data | MAC tag.

Is it fine to do that? Or is there a more standard construct?

Is it fine to do that?

Yes, it should be fine, as long as you do not reuse the key/salt-pair for encrypting another piece of data.

  Or is there a more standard construct?

Any authenticated encryption algorithm would work. E.g. AES-GCM with the PBKDF2-derived key.

If you are going to use the same password for encrypting many such pieces of data there are more efficient ways to do it, so that you do not need to compute PBKDF2 anew for each of them. For example, have a constant salt for it and also a message-dependent nonce you use for the encryption algorithm.

There are also alternatives for PBKDF2 that you might prefer, like bcrypt, scrypt, argon2, if you happen to have them available. They make it more difficult to test password guesses, which you might want if you are unsure about the strength of the password.


Diffie-Hellman key generation We all see X509 certificates with 2048/4096-bit RSA key pairs; however, it is difficult to understand how they work in the DH part of the TLS handshake.
At most, they authenticate and sign. DH 4096-bit generates "parameters," which I know is time-consuming.
When the server generates those parameters, what do they look like? What has the 4096-bit key become? I generated certificates with Let's Encrypt, but I cannot recall seeing the process. I only saw an RSA key pair, I think. Yet DH will be used for the session key exchange, not the RSA keys.
So far, I have only found one document that talks about public and private keys for Diffie-Hellman, even though most people on the web say there are public and private keys with DH.

Generally, named curves are used for DH and servers don't generate parameters themselves. These are configured using a specific number in the TLS protocol. The keys on the other hand are always re-generated preferably for each connection for TLS. This is assuming that an ephemeral key exchange is used, which can be identified using the postfixed letter E in the cipher suite for TLS 1.2 (DHE or ECDHE). Because of this the shared secret should always be specific to a TLS session.
RSA is a completely separate algorithm from DH. The RSA private key is used to authenticate the TLS handshake including the freshly generated DH public keys. RSA doesn't require any parameters (other than the key size). The color explanation of DH doesn't have anything to do with RSA. In principle you can use an entirely different key size for RSA and DH, although it makes sense to use a set that has approximately the same strength.
Let's Encrypt will never know about the DH parameters, they are specific to the TLS connection and are not included in a certificate.


CBC variant: why encrypt the nonce with a different key? I am a newbie at cryptography. I understand the CBC encryption, somewhat. You don't want to use the same "IV" for every message because then the ciphers are not very random. My question is regarding the nonce-based CBC. My main question is why does the nonce needs to be encrypted with a different key than the rest of the message?

And a side question is does the nonce needs to be different? Or can it be predictable and reusable?

Below is a picture of what I am referring to. This image shows excellently the point I am referring to but does not explain it. Why can't k1 = k?

(From A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup, problem 5.14)

I believe that it has to do with the model of nonce selection, in particular, that the attacker is allowed to choose the nonce (as long as it is unique).

If we assume that such an attacker is plausible, then if the nonce is encrypted with the same key as everythine else, then attacker can perform a chosen nonce/plaintext attack which serves as a distinguisher, as well as allows an attacker to decrypt low-entropy plaintext.

Here's how it works: suppose the attacker has a ciphertext where he has a guess $t$ to the value $m[i]$, and (of course, the ciphertext values $c[i-1]$ and $c[i]$).  Then, the attacker constructs a message with the first block being $c[i] \oplus t \oplus c[i-1]$, and asks it to be encrypted with the nonce value $t \oplus c[i-1]$.  He then examines the first block of the resulting ciphertext; if it happens to be the value $c[i]$, then (with high probability) his guess is correct.

If his guess of $t$ was correct, that is if $t = m[i]$, then we have
$c[i] = E_k( t \oplus c[i-1])$ (as that's the formula the encryptor used to create $c[i]$)

So, here is what the encryption process would do: the mode would first encrypt the nonce; the nonce is $t \oplus c[i-1]$, and so the result of the encryption would be $c[i]$.  That is then exclusive or'ed with the first block of the plaintext message, which is $c[i] \oplus t \oplus c[i-1]$; the result of that xor is $t \oplus c[i-1]$.  That is then encrypted; again, the result of that encryption is $c[i]$; and that is the first block of the encryption.

If $t \ne m[i]$, it is quite unlikely that the result of the two encryptions will happen to be the value $c[i]$.

Having the process that initially encrypts the nonce use a distinct key foils this attack.

Now, if we assume that the attacker cannot arbitrarily choose the nonce (e.g. the nonces are sequential), then this attack does not apply; reusing the same key is safe.


Difference between strongly universal and $\delta$ univeral hash functions Define a family of strongly universal hash functions as:

$$\forall x_1, x_2 \in \{0,1\}^n, \forall y_1, y_2 \in \{0,1\}^m, ~ x_1\ne x_2: ~~ \Pr_{h\in H} [h(x_1) = y_1 ~\text{and}~ h(x_2) = y_2] \le \frac{1}{2^{2m}}$$

if $h: \{0,1\}^n \rightarrow \{0,1\}^m$
and a family of $\delta$ universal hash functions:
$\forall x_1, x_2 \in \{0,1\}^n$ where $x_1 \neq x_2$:
$$Pr_{h \in H} [h(x_1) = h(x_2)] \leq \delta$$

(Definitions according to Moni Naor slides.

Then I see why strongly universal implies $2^{-k}$ universal (simply pick $y_2 = y_1 = h(x_1)$), but according to Moni Naor slides, $\delta$ universal does not imply strongly-universal.

Since I don't fully understand the counterexample on the slides ($h(x) = x$) I am searching for a counterexample and an intuitive description of the differences between the two definitions?

There are two orthogonal question axes here:

Universal vs. strongly universal.
A universal hash family has bounded collision probability: for any inputs $x \ne y$, the probability that they collide under a random hash function $H$ is bounded by $1/t$, where $t$ is the number of possible hash values: $$\Pr[H(x) = H(y)] \leq 1/t.$$  (If hash values are $m$-bit strings, then $t = 2^m$.)  However, although the probability of collision may be bounded by $1/t$, knowledge of $H(x)$ may inform you about $H(y)$ for certain pairs of $x$ and $y$.

In a strongly universal hash family, sometimes called pairwise independent, this does not happen because the hash values of any two inputs $x \ne y$ are independent uniform random variables: $$\Pr[H(x) = u, H(y) = v] = \Pr[H(x) = u] \cdot \Pr[H(y) = v] = 1/t^2,$$ for any hash values $u$ and $v$.  This is called pairwise independent because it may be limited to any two variables—for any positive integer $k$, there's a corresponding notion of $k$-wise independence.

Obviously any pairwise-independent hash family is universal (proof: exercise), but the converse does not hold.  For example, fix a prime $p$, and define $H_1(x) = a x$ on $\mathbb Z/p\mathbb Z$ for uniform random $a \in \mathbb Z/p\mathbb Z$.  Then $H_1(x) = H_1(y)$ means $ax = ay$, an event which, for $x \ne y$, happens if and only if $a = 0$, so $$\Pr[H_1(x) = H_1(y)] = \Pr[a = 0] = 1/p.$$  But if $H_1(x) = a x = u$, there is only one possible value of $H_1(y) = a y = v$, namely $v = y u/x$, so

\begin{equation*}
     \Pr[H_1(x) = u, H_1(y) = v]
     = \begin{cases}
         1, & \text{if $x v = y u$;} \\
         0, & \text{otherwise.}
       \end{cases}
   \end{equation*}

Hence $H_1$ is not pairwise independent, because for certain values of $x$, $y$, $u$, and $v$, $\Pr[H_1(x) = u, H_1(y) = v] = 1$ is far above the bound of $1/p^2$.  That is, if you know $x$ and $y$, and you learn $u = H_1(x)$, you can perfectly predict what $v$ will be even if you didn't know a priori what the secret hash key $a$ was.
Universal vs. $\delta$-universal.
This is just a generalization of the concept: you replace the bound $1/t$, for a hash family taking on $t$ possible hash values, by the bound $\delta$, which is usually a small multiple of $1/t$.  There is a corresponding notion of a $\delta^2$-strongly-universal hash family.  A $1/t$-universal hash family is just universal.  A $1/t^2$-strongly-universal hash family is just strongly universal.

For example, fix a prime $p$, say $2^{130} - 5$, and let $r \in \mathbb Z/p\mathbb Z$ be uniform random.  For a polynomial $f$ over $\mathbb Z/p\mathbb Z$ of degree at most $\ell$, define $H_2(f) = f(r)$.  We can encode a message as the coefficients of the polynomial $f$.  If $H_2(f) = H_2(g)$ for polynomials $f \ne g$, then clearly $f(r) = g(r)$, so $r$ is a root of the polynomial $f - g$.  But there are only at most $\ell$ such roots.  Since every $r$ has probability $1/p$, we have

\begin{equation*}
     \Pr[H_2(f) = H_2(g)]
     = \Pr[r \mathrel{\text{is a root of}} f - g]
     \leq \ell/p.
   \end{equation*}

Thus, $H_2$ is $\ell/p$-universal.  Here $\delta = \ell/p$ is a small multiple of the number $1/p$ of distinct outputs from $H_2$.  This hash family $H_2$ is noteworthy in cryptography because it is the basis of the Poly1305 message authentication code, which is a contender (along with GHASH) for the most popular MAC in the world.  (Some background on the history and role of universal hashing in message authentication codes in cryptography.)


Is McEliece secure with non-binary Goppa codes? A binary Goppa code with codewords of length $n$ bits that can fix $t$ errors with a polynomial over $GF(2^m)$ can encode $k = n - mt$ bits long data.
That is one needs to add $mt$ check bits to fix $t$ bits.
This means at most 1/m-th of the codeword can be filled with errors.
On the other hand if you work in a field of $GF(p)$ where $p$ is some prime, to fix $t$ wrong symbols you need to add only $2t$ more symbols (as the polynomial for the generic case needs to have twice degree). So $k = n - 2t$. And in the most extreme case half of the codeword can be error.
If I understood correctly "information set decoding" relies on finding a $k$ symbol long subset of the the transmitted data that doesn't contain errors. So this means it's an advantage to be able to introduce more errors in the message. And it seems the general Goppa codes are better at doing that.
Is there any particular reason we use binary Goppa codes instead of general Goppa codes? Does binary codes defend better from other kinds of attacks?
EDIT: I'm also interested in the case where the code's polynomial is over $GF(2^m)$, but the codeword's elements are not over $GF(2)$ but also over $GF(2^m)$. It's tempting to use a field like $GF(2^{16})$ so the matrix and polynomial elements are represented by "short words" and the transition to bits part is are omitted so we can do all the stuff within a single field, the generator matrix's elements are also short words. And the input is also processed as 2 byte batches: easier and faster vectorized implementation is possible.
EDIT2:
In information set decoding we are looking for a subset in the ciphertext that are not in error. In an $[n, k, t]$ code. We can pick k elements ${n \choose k}$ way and the number of possible correct guesses is ${n-t \choose k}$. So the chance of stumbling upon an error free sequence is ${n-t \choose k}/{n \choose k}$.
Now let's use a generic Goppa code over $GF(1021)$. Let $n = 725$, $t = 145$ and $k = 725 - 2*145 = 435$
So calculate ${725-145 \choose 435}/{725 \choose 435} \approx 6.953 \cdot 10^{-71}$. Which is about $2^{-233}$. So 233 bits of security.
Elements in $GF(1021)$ can be represented in 10 bits giving us a key size of 3153750 bits or about 400kB.
With binary Goppa-codes more check symbols needed. Consider code over the extension field $GF(2^{13})$ with parameters $n = 5600$, $t = 172$, so $k = 3364$
${5600-172 \choose 3364}/{5600 \choose 3364} \approx 4.373 \cdot 10^{-71}$.
For similar security levels. But the matrix is now larger than 2 MB.
Hence my question.

The problem is that you're only referring to plain information set decoding.  Indeed, for plain ISD, the complexity of attacking a Goppa code over $\mathbb F_q$ would scale as one would expect with $q$.

However, Stern's algorithm for ISD does not scale purely with the code size.

Following a geometric distribution, we can express the expected cost of an ISD algorithm as

$$
\mathbb E [\text{cost}] = \frac{\text{cost of one iteration}}{\mathbb P [\text{successful iteration}]}\text.
$$

For Stern's algorithm, given parameters $p$ with $0 \le p \le w$ (where $w$ is the weight of the error vector) and $l$ with $0 \le l \le n - k$,

The probability of a successful iteration does not depend directly on $q$ and can be expressed as a function of $n$, $k$, $w$, $l$ and $p$.
The cost for one iteration is
$$
(n - k)^2 (n + k) + ((\kappa - p + 1) + 2 N {(q - 1)}^p)l + \frac{q}{q - 1} (w - 2p + 1) 2p (1 + \frac{q - 2}{q - 1}) \frac{N^2 {(q - 1)}^{2p}}{q^l}\text,
$$
where $\kappa = k / {2}$ and $N = \binom{k / {2}}{p}$.

As you can see, the way the algorithm scales with $q$ depends a lot on the parameters $p$ and $l$.  Therefore, $p$ is usually chosen to be quite small in order to minimize the effect of going through too many subsets (the ${(q - 1)}^p$ and ${(q - 1)}^{2p}$ terms).

Please see Christiane Peters' thesis, which has an entire chapter devoted to this.  It also discusses additional improvements and proposes exact values for $p$ and $l$.

Of course, there are also Goppa codes over $\mathbb F_q$ for which such a cryptosystem would be secure.  You can find some proposals and analyses in the thesis, too.


Blake2 vs md5 for checksum / file integrity I'm working on something that requires computing a checksum / file integrity. I've heard MD5 was no longer recommended. Should I use Blake2 instead? Is there a specific variant of Blake2 I should use for checksums? Blake2s? Blake2sp?

Yes, you should choose BLAKE2 instead of MD5.  Any of the BLAKE2 variants—BLAKE2s, BLAKE2b, BLAKE2sp, BLAKE2bp—is an improvement over MD5, even if you just use them for 128-bit digest sizes like MD5, although it is generally better to use at least 256-bit digests.  BLAKE2b is a good default; BLAKE2s is slower on 64-bit systems but friendlier to 32-bit systems; BLAKE2sp and BLAKE2bp are optimized for systems with large vector units or multiple cores to parallelize hashing long messages.

So go and rip out MD5, and put in BLAKE2 instead, and you'll almost certainly be be better off.

You've ripped out MD5?  Good!  But we should also talk about what you're trying to do with it in the first place, because while BLAKE2 is not worse than MD5, there are things neither MD5 nor BLAKE2 nor anything with the same shape—a fixed hash function—can do no matter how good they are at what they do do.

So, when you say ‘checksum’ and ‘file integrity’, what are you trying to do?  Here are some possibilities:

You're trying to detect random errors with a very simple distribution, like independent errors, or burst errors.

In this case, while BLAKE2 is not worse than MD5, you might be better off with something designed to be a checksum like a CRC rather than something designed to be a random function like BLAKE2 and MD5:

A CRC polynomial with a factor of $x + 1$ is guaranteed to detect all errors of odd parity.
An $n$-bit CRC with a nonzero $x$ term is guaranteed to detect $n$-bit burst errors.
Various other errors can be guaranteed detected by a judicious choice of generating polynomial; see the standard Koopman–Chakravarty reference (preprint, paywall-free) for more details.

This is relevant when there is no adversary involved.
You're having a conversation with someone with whom you share a secret $k$, and you want to prevent anyone else from forging messages.

In this case, you actually need a message authentication code, or MAC, which has the property that nobody who knows the key can find the MAC for any message except ones they've already seen by asking you politely to give it to them.

BLAKE2 has a built-in MAC: you can specify a key, and it magically turns into a MAC.  There are other alternatives, like HMAC-SHA256, or even HMAC-MD5 (which is to the best of our knowledge still secure up to well below $2^{64}$ messages, but you should consider switching away just so that you don't have MD5 in your code at all).
You're publishing statements that you want anyone in the world to be able to verify, but nobody to be able to forge.

In this case, you actually need signatures, which are like MACs except there are separate keys for signing (private key) and verifying (public key).  In principle BLAKE2 could be used in a signature scheme, but in practice I haven't seen any, and any good signature scheme for practical use will come with predetermined choices for any hash functions, like Ed25519 uses SHA-512 and Ed448 uses SHAKE256.

Of course, anyone who wants to verify a message needs to know the public verification key a priori: if they got it on the same channel as the signed message, the adversary could have replaced the whole thing—but at least the recipient will have the public key for next time, so the adversary would have to replace the whole thing on every day the recipient tries to fetch the public key and/or signed message.
You're publishing a manifest of files in a distribution, like a software package repository, and the manifest is published on a different channel—known to be unforgeable, e.g. because you got it over SSH or HTTPS from a good server—from the software packages themselves—e.g., because you download them over HTTP from a sketchy CDN.

In this case, BLAKE2 is a good choice!  If you used MD5, you might be in trouble.  But you should also be sure that there actually is a qualitative difference in security between the channel on which you transmit the manifests and the channel on which you transmit the files; if an adversary can modify both at the same time, the hashes accomplish nothing.
You're using a hash as a key in a content-addressed storage scheme, like Tahoe-LAFS.

In this case, BLAKE2 is a good choice!  If you used MD5, you would definitely be in trouble.


Is it possible for this tweakable block cipher scheme to be secure for more than $2^\frac{n}{2}$ blocks? $2^{n}$ blocks? In the title, $n$ is the block size in bits and will not be used to denote it in the body of this question unless otherwise stated. Imagine that we have $\mathbb{K} \in \{0, 1\}^{\ell_{K}}$, $\mathbb{T} \in \{0, 1\}^{\ell_{T}}$, and $\mathbb{X} \in \{0, 1\}^{\ell_{X}}$, $E(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$, and $D(K, T, X): \mathbb{K} \times \mathbb{T} \times \mathbb{X} \rightarrow \mathbb{X}$. We have a tweakable block cipher where the encryption of a block of data is returned by $E(K, T, X)$, the decryption of a block of data is returned by $D(K, T, X)$, $K$ is the secret key, $T$ is the tweak, and $X$ is the block of data. Suppose that this tweakable block cipher is meant to be used in such a way that $T$ is equal to the block number. If $\ell_{T}$ is sufficiently large, then will the maximum number of blocks that can be encrypted under this scheme be equal to or possibly even greater than $2^{\frac{\ell_{X}}{2}}$ or even $2^{\ell_{X}}$?

Abstractly, there is no $2^{l_X/2}$ limit on the security of a block cipher. The security claim is that the block cipher is indistinguishable from a random permutation which it may remain even after the adversary has seen all its inputs and outputs (for a particular key). Similarly, there is no reason a tweakable block cipher needs to become insecure after a certain number of blocks are encrypted.

In practice the security of a block cipher depends on the mode of operation you use and most of those break down one way or another after $2^{l_X/2}$ blocks.

Practical ciphers also do not claim perfect security. AES-128 security claim is only "128-bit security". If you construct a tweakable block cipher from AES-128 the security bound is even lower. E.g. XEX/XTS security proof adds a term that is proportional to the square of the number of encryptions. So you should not use it more than AES itself, but in fact a small factor fewer times.

If you have a tweakable block cipher that is not constructed from another block cipher, its security claim may or may not depend on its block size. So using it like you describe may or may not be secure for more than $2^{l_X/2}$ blocks.


Why are the indicator drums of a Bombe machine labelled from A to Z clockwise? I am researching the Bombe Machine, having just completed a project on the Enigma Machine. I visited The Rutherford Journal - The Turing Bombe, and it claimed that

  The scales on the three indicator drums are designed to show the ‘rotor core starting positions’ at a ‘stop’ when measured in terms of the corresponding Enigma ring-settings for the Enigma rotor settings: ZZZ. This is the reason why the letters on the scales on the indicator drums are in the reverse order to those on all the other drums.

I don't understand this explanation, though. Aren't the indicator drums used to determine the rotor core offset? And I thought that the rotor core offset was calculated by the rotor position minus the ring setting. As the Bombe tests the rotor positions from A to Z, shouldn't the indicator drums also run from A to Z, since the Ringstellung is assumed to be a constant ZZZ?

I emailed someone, and it turns out that the rotor positions found by the Bombe are used as the ring setting in the checking machine. Because the ring setting is the "negative" of the rotor position, the indicator drums spin backwards, so that it shows the correct ring setting that corresponds to the rotor positions for the checking machine.


What's the difference between PBKDF and SHA and why use them together? I've been reading a little bit about hashing lately and according to AgileBits, they use "SHA512 within PBKDF2" in their new vault file.

I've looked in Wikipedia for both names and I know PBKDF2 is a key derivation function and SHA is a cryptographic hash function but I can't really understand the difference and why they are both used together with one inside the other.

Can anyone explain this for a person without experience in cryptography?

(You can assume I only know about math, if necessary).

SHA-512 is a cryptographically secure hash, PBKDF2 is what we call a Password Based Key Derivation Function. If the resulting secret isn't used as key but as hash value it's also called a password hash. Password hashes differ from secure hashes in the sense that they contain a salt and a work factor / iteration count.

Both cryptographic hashes and password hashes are one way functions designed to create a short, fixed sized output from a given input. In the case of the password hash the input would be the password and salt. The size of the salt and the iteration count are commonly considered configuration parameters; both do of course influence the output of the password hash.

Password hashes are generally build on top of Pseudo Random Functions or PRFs. A usual form of PRF is a HMAC or Hash based Message Authentication Code, which in turn uses a hash internally. When hash-based PRFs such as HMAC are used then the type / size of hash used is often configurable. Password hashes however do not need to be build using hashes. Any other PRF, such as ones based on symmetric ciphers, may do. bcrypt for instance is build on top of Blowfish, a block cipher.

Password hashes need a salt so that identical passwords won't map to the same hash. They therefore also prevent rainbow tables (containing precalculated password / hash pairs) from being useful. Furthermore they contain a work factor / iteration count so that an attacker needs to perform more work to calculate the hash of each possible password. This is needed because most passwords are not random enough. Without the work factor the attacker would be able to test vast amounts of possible passwords using brute force or a dictionary attack.


How to use Homomorphic encryption for secure computing Arctan() function? In the multi-party communication(MPC), if partyA has the coordinate(x1 y1) and partyB has the coordiante(x2,y2), how two parties can securely compute Arctan((y1-y2)/(x1-x2)) without revealing their coordinates to each other?

While this may be of interest as an academic exercise, they can't securely compute it without revealing their coordinates (or at the very least leaking a lot of information about their coordinates).

Consider that partyB gives a secure service to partyA whereby partyA can calculate the arctan without exposing its coordinate. Let's say this result is $v$. Then clearly $y_2 = y_1 + (x_2 - x_1)\tan v$, which is already leaking a very large amount of information about $(x_2,y_2)$. Indeed, if partyA can make an additional query to that service, passing in some other coordinate, then partyA has sufficient data to calculate the coordinate precisely.


Does the Initialization Vector in DES have to be 8 bytes long? I was experimenting around with DES and decided to implement an IV (Initialization Vector) for it. I noticed that in DES, which is 56 bits and 8 parity bits, the IV would be 8 bytes in length. Does that mean that if I were to program DES but using a 128-bit key, the IV would be 16 bytes in length instead of 8 bytes in length? (Cryptography Rookie here)

The IV is part of the block cipher mode of operation, not of the block cipher itself. The block cipher simply doesn't have any input for an IV, it just takes an input block and produces an output block using a key. So you cannot implement an IV for DES itself.

The block size is however usually of influence to the mode of operation. Even then, the IV may still be different from the block size for some modes. To make it a bit more complex, some modes of operation such as CTR mode and GCM mode (for 128 bit block ciphers such as AES) may have different options to implement an IV or nonce.

The DES block size is always 64 bits, regardless of the key size, just like 128 bits is always the block size of AES. The key size is not (necessarily) of any influence to the block size, although it may be advantageous for the key size to be a multiple of the block size in case keys need to be encrypted by other keys (wrapping a key by another "wrapping" key).

For CBC mode, which is often explained as one of the first modes to starting cryptographers, the IV needs to be the full block size. Furthermore, for CBC the IV needs to be indistinguishable from random to any adversary. That means that the IV is always set to 8 bytes or 64 bits.

Note that DES itself only supports 64 bit keys, of which 8 bits are parity bits, so an effective key size of 56 bits. Triple DES or DES-EDE may use two keys. It then uses key A for the first encryption, key B for DES in decryption mode and keyA again for encryption, so an ABA-key.

However, as these block encrypts / decrypts are simply stacked on top of each other, the block size stays the same: 64 bits. Therefore, for CBC, the IV does need to be 64 bits / 8 bytes as well.


If we can find prime numbers larger than 17 milion digits, why can't we find all 1024bit primes? "Largest Known Prime Number Discovered; Has 17,425,170 Digits"
http://www.sciencedaily.com/releases/2013/02/130213225424.htm

If we can find prime numbers larger than 17 milion digits,
why can't we find all 1024bit (just 309 decimal digits) primes?

Due to the prime number theorem the number of primes with length $2^{1024}$ is approximately

$$\pi(2^{1024}) - \pi(2^{1023})\approx  \frac{2^{1024}}{\ln(2^{1024})}- \frac{2^{1023}}{\ln(2^{1023})} \approx \frac{2^{{1024}}}{709.8} - \frac{2^{1023}}{709.1}\approx 2^{1013.5}$$

The number of atoms in the universe is approximately $10^{80} \approx 2^{265.75}$, which means...

Edit, fixing math:

... you would have to fit just around $2^{748} (\approx 2^{1013.5 - 265.75})$ prime numbers in every single atom in the universe in order to store this list.

To further break this down:
Assume you could program atoms to output 1 prime at a time for 1 attosecond (shortest measured time, $2^{-18}s$), you would still need $2^{663.1}$ years, and it's been "only" $2^{33.7}$ years since the Big Bang.

Short: It's far, far beyond the anything ever achievable. And this is not due to our technical limitations, it's just not possible in existence.


Extracting the hidden text off an image embedded with steganography Is it possible for me to extract the hidden text off a stego-image without using the same application that the hidden text was hidden with.

I used 5 applications that do steganography such as, SteganographyX, QuickStego, Xiao Steganography, SSuitePiscel & OpenStego. I only inserted hidden text in a .BMP image and did not embed any type of encryption to make it more secure, just kept it basic.

The thing is that if i hid text using for example QuickStego, i cannot extract what i hid with another application mentioned above.

Is it possible to create such code and create my own application that does let me extract an image's hidden text created by any steganography tool? Like with python or something?

Yes, you can write a single application to reveal the hidden information as long as you know the method and they are not encrypting the messages they hide. The Wikipedia article in Steganography tools lists some information about availability as an opensource, their methods, and usege of encryption. And some information can be found on their website.

For example, QuickStego says that;

  The QuickCrypto steganography function allows carrier files to be photographs, drawings, images (.jpg, .gif, .bmp file types) and sounds (.wav and .mp3 file types). Any type of file can be hidden within these types of carrier files. Files and text to be hidden can easily be encrypted prior to hiding if required.

and SSuite Picsel

  SSuite Picsel secures all your text messages using Steganography encryption...

If encrypted you must know the encryption algorithm and the key to decrypt the message after you retrieve the hidden messages.

There may be also a patent problem since the SSuite Piscel is a company. They may have some patents on the steganographic methods. You may write your software by reverse engineering their products, but distributing it; may cause legal problems.


What is the difference between probabilistic and deterministic prime-factor recovery function in NIST 800-56B? In the previous standard, the deterministic was not included. It is already in the current standard.
What is the reason for this?
Can I use both function?

The probabilistic algorithm has (at least part) of it's runtime that follows an approximately geometric distribution. So it can sometime take a long time. In some applications, that's an issue: for excellent reasons, there's almost always some finite timeout to any process, often determined experimentally. Geometric distribution of execution time is a tried and tested method for field failures. I've seen this in more than one Smart Card production line at the RSA key generation step.
I have not analyzed the deterministic algorithm in detail, but it's maximum run time for a given parameter size can be strictly bounded, and is I guess lower than for the probabilistic algorithm in some sizable fraction of cases (perhaps, often; or even to the point of being faster on average). Also, if an implementation is made strictly constant-time, that's one less area of worries against side-channel leakage.


What is the time complexity of the RC4 encryption & decryption algorithms? I'm trying to figure out what the time complexity of RC4 encryption & decryption algorithms is, in big-O-notation.

Stream ciphers are essentially just random number generators, so for each input bit they generate a random bit (based on a seed, i.e. the key) and combine it with the input bit, giving you the output bit.

So:

 c = m ⊕ G(k)
 m = c ⊕ G(k)

Where c is ciphertext, m is plaintext, G is the RNG and k is the key.

As such, all stream ciphers should be O(n) against the length of input data.


Where can I find the standard definition for GPG ECDSA signature? I am playing around with GPG which I'd like to use to sign an integer and use the resulting signature binary in another piece of code.
So far I have created a simple PGP packet parser with which I think I can successfully extract the elliptic curve point representing the public key.

Comes then signature parsing from the PGP message and which I haven't been able to interpret so far, finding no hints in RFC4880 or 5480 which define all bytes up to the last 68, the signature representation.
But how should this 68 bytes be parsed exactly? Which RFC would be the one to look at?

An ECDSA signature in PGP is indeed encoded as MPI(r) MPI(s)
This is confirmed by RFC6637 which refers back to RFC4880. This is made more clear in draft RFC4880bis which incorporates the former.

Multiprecision integers (MPI) format is itself described in RFC4880, section 3.2


How do I store encrypted files on a web server and decrypt them locally? I want to store files (images) on a public webserver and let users see them if they know a password.  The server shouldn't have the unecrypted files and the server can only serve files, not perform any server-size computation.

One thing that I know about crypto is that I know very little so I'd like a review of the following plan:

Description of the idea:

I plan to encrypt the images with AES-256, random IV, and save them as a concatenation of IV and encryption output.  Some images will have the same passwords, some won't.

To view these files, the user will type his password into an input box on a webpage and javascript will download the encrypted file and use the password that he typed in to decrypt the image and display it.

The download and decryption of images is slow and I expect it to fail if the password is wrong so I'd like to store a "password check" that will execute locally, in javascript.  My idea is to store, in a plain-text "index file", some sort of hash of the correct password.  (The index file is far faster to download than the image.)  The javascript will locally check if the hash of the password matches what's listed in the index file before downloading and displaying images.

I plan to create the index file and encrypted images in .Net and do all the javascript with crypto-js, so any algorithm that I use should be available with those.  I want to minimize download times and javascript run time if it doesn't compromise security.

Questions:

How do I expand the user's password into a valid AES key?  So far, I plan to use PBKDF2 because it's available in .Net and crypto-js.

Should I have a separate salt for each image?

If so, should I store that salt in the encrypted image with the IV/encrypted-file or in the index file?  What advantages/disadvantages are there to the options?  For instance, I could do PBKDF2 while waiting for the image to download.

How do I store the password check?  So far, I plan to use PBKDF2 for this, too, and put a random salt and PBKDF2 output in the index file.  The per-password salts would be different from the per-image salts, of course, because otherwise the AES key for each image would be in plain text in the index file!

Is there any reason that PBKDF2 would be a bad choice for both password-check and image-decrypt?

Any security mistakes that I didn't think of?  I know that downloaded javascript can't be trusted but I'll let my users decide if they want to take that risk or use https to get the javascript.

Edit, resolution: My resolution is Ilmari Karonen excellent answer.  Per valid password, I generate 128-bits with PBKDF2, each time with a new, random salt.  I store the salt per password in the index file.  Per photo, I generate a random IV and random key and encrypt.  In the photo index file, per photo, I store the photo's key, encrypted by the per-password PBKDF2.  I also store a second encryption of the photo's key, this time with the first byte of the photo's key incremented by 1 modulo 256.  That is used to check that the password, already verified as valid for some photos, is valid per-photo.  Doubling the PBKDF2 bits for authentication purposes is far slower than just attempting all the image-key decryptions and testing the results.

This is crypto, not stackoverflow, so I won't include the code here but all the encrypting is done with .Net and all the decrypting in javascript and it works.  I can provide it freely if someone wants it.

You were doing fine up to the point where you wrote "JavaScript".

Of course, JavaScript as a language is not fundamentally unusable for crypto (although, as a high-level scripting language, any crypto primitives implemented in JavaScript are likely to be rather slow and hard to secure against side channel attacks).  However, when you write "JavaScript", I assume you mean code sent by the server and executed on the client by a browser.

This security model is fundamentally flawed for two reasons:

first, if you're not using HTTPS, then anyone who can intercept the communication between the client and the server (by, say, ARP or DNS poisoning, or a rogue WiFi access point) can modify the code sent to the client and insert their own back doors; and
second, even if you do use HTTPS to secure the connection between the client and the server, the client is still blindly executing any code given to it by the server.

If your goal, as you write, is to prevent the server from learning or tampering with the data by encrypting it on the client side, then you haven't really accomplished anything of the kind: the encryption may be done on the client, but it's done using code sent by the server, and there's nothing preventing that code from storing the user's keys and passwords and hiding them among data sent to the server.

(Of course, a careful inspection of the code and the network traffic it generates might uncover such back doors, but most users will be neither able nor willing to carry out such an inspection.  And it's not enough for just one or two users to do it, since the other users have no reason to trust that the code they've been sent is the same as the code that's been sent to others.)

For more information on why this is a bad security architecture, see e.g. this post from Bruce Schneier's blog and the articles linked from it.

OK, so what should you do then?  Well, if you want to run some JavaScript (or other) code on the browser without the server having full control over it, you could make it a browser plug-in that the user can install.  This still won't be entirely secure, since the plug-in itself could be compromised, but at least it limits the attack surface a little.  (Of course, you should probably make sure the plugin isn't able to silently upgrade itself, since that would just reopen the hole completely.)

You can also try publishing cryptographic hashes (e.g. SHA-256; not MD5, that's broken) of your code to allow users to verify that it hasn't been tampered.  Of course, if I download both the code and the hashes from your site, you (or an attacker in between, if you didn't use SSL) might have tampered with both, but at least, if I was careful and paranoid enough, I could in principle look for copies of the hashes elsewhere (e.g. Google's cache) to be sure that I've got the same software that others have.

The bottom line, though, is simply that it's really hard to provide a crypto service which is secure against the potential compromise of the service provider itself.  You can either do your very best, and inform your users about the remaining holes — or you can give up, do the crypto on the server and just use SSL for transmitting the data (and maybe hint at users that they may want to encrypt their data locally first, just in case).  But please don't try to fool your users with insecure half measures like in-browser JavaScript crypto.

Ps. Rereading your question, I notice that you did address, or at least wave your hands at, this issue at the end.  Still, my point stands.  Compared with the big glaring hole of running potentially untrusted crypto code, I see no obvious flaws in any of the rest of it.

Anyway, given that PBKDF2 is (deliberately) slow, especially in JavaScript, you'll probably want to minimize the number of times a legitimate client needs to execute it.  So I'd suggest something like this:

Let $P$ be the user's password.  When the user enters it, the client hashes it into a 128-bit key $K_P = \text{PBKDF2}(P)$ (preferably salting it with some user-specific value).
When each file is encrypted, a random 128-bit key $K_F$ is generated.  The file is encrypted using AES in a suitable mode (not ECB) with the key $K_F$ and sent to the server.
The client encrypts $K_F$ with $K_P$ using AES in ECB mode (which is OK, since we're just encrypting a single 128-bit block), yielding $C_K = \text{AES}_{K_P}(K_F)$.  It also encrypts $K_F' = K_F + 1$, where $+$ denotes addition modulo $2^{128}$ (or even just modulo $2^{32}$ or $2^8$, with the remaining bits untouched), yielding $C_K' = \text{AES}_{K_P}(K_F') = \text{AES}_{K_P}(K_F + 1)$.
The client sends $C_K$ and $C_K'$ to the server, which stores them in the index.
When the client wants to decrypt a file, it first downloads the index, decrypts $C_K$ and $C_K'$ to get $K_F$ and $K_F'$, and checks that $K_F' = K_F + 1$; if not, it asks the user the confirm that the password is correct.
If the check passes, the client now knows $K_F$, and can download and decrypt the file.
If the user wants to change their password, the client just needs to recompute $C_K$ and $C_K'$ for each file and send the new values to the server; the file keys $K_F$ need not be changed, and thus the files themselves need not be re-encrypted (although it's nice if the client does provide that option too, in case the users suspects the file keys may have been compromised).


Using hash for one time pad key Recently I've been delving into security algorithms, I already knew some of the (easy) math behind AES and RSA and how to and not to implement it. But well, i got a bit bored so i thought I'd just do something fun and i wrote a small bit of code for the OTP (not so difficult)

then i thought, and this concerns my question: If you give someone a OTP key and you tell him that the (say SHA 256) hash of the previous plaintext will be the new key, how secure is this? Obviously you start with a perfectly random key an will never make your plain text longer than your key. (so a proper one time pad function)

So you have a key, you decrypt the cyphertext you get, then you hash the retrieved plaintext and this has will be the key for your next message. In my mind this would be as secure as the OTP when starting with a proper key. But then again my mind isn't really suited for simulating real applications, haha.

So does anyone have an idea on how secure this would be?

EDIT i might want to clarify your next plain text will of course be as long as the generated  hash, if you need to write a longer message you will use the hash of your newly typed plain text, and so on.

Not as secure as a one time pad. A key concept with one time pads is that no part of them is ever reused. It is a common pitfall of people attempting to implement cryptography to assume that an obscure relationship is necessarily a secure one: it is not. You are create a chain of SHA hashes that can be observed, and potentially decoded.

Therefore what you have described is not an effective one time pad. The one time pad depends on the idea of a pre-compiled book of codes that have no relationship to one another, and that are used exactly once. If any sort of iteration is observed between the ciphertexts, this ruins the pad.

From the outside this seems like a hard code to cryptoanalyze, but I don't think it is massively difficult. Differences between your ciphertext will be analyzed, and when is found that you are not using a standard encryption scheme, the various pitfalls of self implemented crypto will be explored.

The security of your entire system can be no better than the original secret in that case, and the additional secrets generated from original secret actually worsen the security of the system, because they give some clue as to the original secret, however obscure that clue might be. To be as secure as a one time pide, the keys should bear absolutely no observable relationship to one another.

If I were to cryptoanalyze your system, I would first figure out the nature of the cipher text, and the nature of the keys. If I had access to a single key (say by brute forcing, or a flaw in the encryption) then I would be able to detect fairly quickly via automated methods that the key was a SHA hash.

At that point, I would try to guess the plaintext of the hash. If I had access to multiple keys I would notice that key size might correlate to message size in some way. From there it would be obvious that key was related to the message somehow. I will admit that brute forcing an entire message against a SHA hash is unreasonable, but all it takes is one leaked message to start pulling things apart.

If I ever decoded the plaintext from any one of the hashes it would be game over. System cracked. This was a quick analysis, others might be able to go deeper into the math side of this.


Proper method of writing pseudo random sequences into binary files? I am working in Python and created a B.B.S. implementation that outputs a sequence of pseudo random positive integers into a Python list.  I would like to write this data to a binary file and pass it through ENT and Diehard to see how well it does, but I have no idea how to properly do this.

So far I have been writing these pseudo random sequences in python lists into binary files with the struct package, but even PRNG's like B.B.S. are horribly failing these tests, so I know I must be writing the data to the file incorrectly.

Would anyone be able to tell me the correct way to write a pseudo random sequence of integers of form [85285422, 1065539406, 1143357354, 812899410, 796171749, 531684531, 771767949, 527982099, ...] in a python list into a file for testing with ENT and Dieharder?

Blum Blum Shub requires larger parameters for security than parameters that are typically suggested for factoring (or QR). See this answer for references.

The short of it is that there are likely no issues with using struct, but that you likely need to use a modulus of $\approx 6800$ bits and extract no more than $5$ bits per iteration to a concretely secure PRNG from BBS.


What is the difference between MACTripleDES and TripleDES? I was asked to encrypt/decrypt a string using MACTripleDES. Is there any difference between MACTripleDES and TripleDES? If, where exactly is the difference between both?

Triple DES is a block cipher.  (Specifically, it's a variant of the old DES block cipher with better security, but several times lower performance.)  You can use it to encrypt small blocks of data (64 bits = 8 bytes, for Triple DES), but what it's really useful for is as a building block for other cryptographic schemes, such as stream encryption or message authentication codes (MACs).

MACTripleDES is, apparently, a class in the Microsoft .NET framework that provides some kind of a MAC using Triple DES.  The documentation doesn't actually seem to say which MAC construction it uses, but this answer on SO implies that it's classic CBC-MAC.

Note that raw CBC-MAC is not, by itself, secure for variable-length messages.  To make it secure, you need to use one of the techniques described in the linked Wikipedia article (prepending the length to the message, encrypting the output with a different key, or using a separate MAC key for each message length), or use a more modern MAC algorithm like CMAC instead.  (You may also wish to consider using a more modern cipher with a larger key and block size and better performance than Triple DES, such AES.)


Why are theoretical hash constructions based on the hardness of the discrete logarithm problem not really used in practice? In an old 2010 Q&A at StackOverflow, Pornin states:

  … a good hash function "should not" allow a property such as surjectivity to be actually proven.

This makes sense to me when looking at, for example, the SHA-2 function family.

Yet, in an answer to Has any crypto hash function been proven to be surjective?, Lindell provides an answer with a nice example of a hash function that allows such proof.

Since the widely known, theoretical construction based on the discrete log problem combined with a Merkle-Damgård transform seems pretty solid at first glimpse, it begs for the question why alike hash constructions don't tend to be practically used more often. The surjectivity (and according collision resistance) proof seems to be a plus when comparing it to the somewhat non-provability (more of an assumption) of the surjectivity of SHA et al.

Is this merely based on the fact that discrete log functionalities tend to be computationally expensive and harder to implement on specific hardware (compared to constructions like SHA-2)?

Or are there other implications (maybe related to cryptographic security or specific attack vectors) which could explain why such theoretical hash constructions based on the hardness of the discrete logarithm problem don't tend to be practically used and preferred (due to the more clear proof)?

I would say it is largely due to

  the fact that discrete log functionalities tend to be computationally expensive and harder to implement on specific hardware (compared to constructions like SHA-2)

In many (perhaps most) use cases, hash functions are not primarily used for their cryptographic security properties, but for efficient and comfortable data management, e.g. in databases. So complexity of running the algorithm should be minimal.

In addition, good hash functions do provide strong security and have several advantages over applications of finite group schemes (where the discrete logarithm applies). In particular, they provide extremely little algebraic structure, meaning there is not much to attack in the first place. This is also the reason why many consider hash functions to be quantum computer resistant, while it is already known that Shor's algorithm can solve the DLP efficiently.

In short, I do not know of any advantage that a DLP-based hash function would bring about, while there certainly would be some shortcomings by comparison.


How to prove truncated MD (or chop MD) hash function is collision resistant? We have a collision resistant hash function (based MD construction) H with 2n bits hash value size.
Call chop(H) is a chopping n-bits from H's hash output.
How can I prove a chop(H) is collision resistant with n-bit?

How to prove a chop(H) is collision resistant with n-bit?

Is this statement true?  Is it true that all collision resistant hash functions remain collision resistant after chopping?

As a hint, you might want to consider this question.