Elliptic Curve Cryptography Encryption and text representation implementation I'm writing a coursework and right now I've implemented the ECDSA algorithm, but I also need to encrypt and decrypt small text files (.txt) using elliptic curve cryptography.

The problem is that I do not know how to represent the message in the file.

I don't know your exact scenario. However you have two options to encrypt data using elliptic curve cryptography (ECC). I'd recommend going with the first option I present.

Use elliptic curve integrated encryption scheme (ECIES). ECIES basically performs ElGamal-like encryption on a key. The key is generated at random and encrypted like in ElGamal (replace the multiply operations with add operations). One then can use this symmetric key to symmetricly encrypt and authenticate the data. ECIES defines how to exactly do that. You then go ahead and simply process the data as you normally would using a symmetric encryption scheme.
Use generalized ElGamal on elliptic curves (no abbreviation, likely never deployed or proposed outside of ECIES). You can as well simply use the generalized ElGamal construction and somehow represent the data you want to encrypt as a point on your curve (which is harder than it sounds).I do not recommend this method. The reason is that you're limited to a message space of 256 to 512 bit (32-64 bytes) and that representing your message may actually be quite difficult, as the reconstruction of the message data from the "decrypted" point won't be easy.

If you're question was only aiming at "How can I represent my bytes in the textfile for the encryption?", then by using approach no. 1 the solution is rather straightforward and with approach no. 2 you have to invent some scheme yourself to aid re-construction. This could go as follows:

Represent your message as octet string $B$.
Convert the octet string to an integer $b$.
Initialize $c=0$
Check if $b$ is a valid x-coordinate on your curve, if yes go to step 6
Set $b=b+1$ and $c=c+1$ and go to step 4
Encrypt the data and append $c$ (maybe with some sort of separator)

Reconstruction should be more easy. You retrieve $b$ by decrypting the message and setting $b$ to be the x-coordinate of the resulting point. Now you simply subract $c$ from $b$ yielding the original $b$ value and making you able to reconvert the integer to a byte array (the text in your file).

Note: If an attacker tampers with $c$, he can let you decrypt the ciphertext to arbitrary messages. Because of this property you should always prefer ECIES.

Represent the text message as byte array. Note that, EC generally used for Diffie–Hellman Key Exchange and Digital Signature. The following link is about En-/decryption with elliptic curve integrated encryption system (ECIES) which may be helpful to you:
Code Examples – En-/Decryption with ECIES


Does one time pad randomness help brute force attacks? I understand that attempting to brute force the decryption of a message coded with a one time pad results in generating every possible message.  The Wikipedia example is that decoding "EQNVZ" with key "XMCKL" produces "HELLO", but the key "TQURI" produces equally plausible "LATER".

However, a "more random" one time pad is supposedly better than a "less random" one time pad.  So there's a way to compare the randomness of two pads, right?

If key TQURI is "measured" as less random than XMCKL, doesn't the likelihood the pad is as random as possible mean HELLO is the more likely message?

Say a coded message consists of only plain English.  A 50-character message could decode to a huge number of possible messages using the same huge number of possible keys.  As we decode character-by-character we can discard anything that isn't obvious English.  That would still leave a large number of possible messages (I have no idea how to estimate how many), but we would simultaneously be increasing the length of the supposedly random key.

If one possible decoding begins ATTACK AT DAWN using the key GJXWHELZYHWLXE while another decoding begins SEND MONEY NOW using the key AABBCCDDEEFFGG, we can probably discard the latter since a pad would never use such a repetitive key.

Therefore, the rule would be to only retain the English decodings for the "most random" keys.  (I have no idea how to pick such a cutoff.)  Could that possibly reduce the potential messages to a reasonable number of candidates?  (I imagine longer keys let you determine their degree of randomness with greater confidence, but I don't know how to calculate that kind of stuff.)

Another possibility would be to retain only messages that parse reasonably well.  BATTALION ALPHA ATTACKS AT DAWN makes sense, but SUNSET DOGGY COOKIE FLOOR can probably be discarded.

Even if individual messages generate a large number of decoded candidates with sufficiently random keys, it would seem a sequence of messages would establish a context that hints at which decodings are valid.  For example, if Message 1 "equally" (because of key randomness) decodes to the candidates

A. WHEN DO WE ATTACK
B. SHOES GREENER ARE
C. MASHED ROOF CARRY

and Message 2 in reply "equally" decodes to

A. ATTACK AT DAWN
B. LEAVE PARLANCE
C. DOG ALPHA MODE

then it seems the "conversation" is probably WHEN DO WE ATTACK/ATTACK AT DAWN.  (Granted, the reply would also decode to ATTACK AT 0100, ATTACK AT 0200, ATTACK AT DUSK, etc., but we're picking the solutions with the "most random" keys.  And even if the keys for ATTACK AT 0100 and ATTACK AT DUSK tied at an equal level of randomness, it's still useful to know an attack is imminent.)  It would seem the more messages you have, the easier it is to guess (or apply some AI regarding) the general thread being discussed.

Therefore, a modified brute force approach would prune away possible but unlikely decodings by (1) discarding invalid and nonsensical content within messages, (2) abandoning decodings with keys not meeting a required threshold of randomness, and (3) abandoning decodings that don't fit intermessage context.  Pruning would have to be done as each new message character is input, to avoid wasting time and space on futile branches.

Would that kind of approach still leave an astronomical number of possible decodings?  Or could it reduce the candidates to a resonably small enough number that NSA computers might possibly be willing to take a stab at predicting (at some level of confidence) what a set of coded messages is probably talking about?

Wikipedia's entry on brute force says a one time pad attack

  ...would eventually reveal every... character string possible, including
  the correct answer – but of all the answers given, there would be no
  way of knowing which was the correct one.

But it seems like some answers could be computed as more likely than others.  Can the set of possible answers be reduced to a reasonable number, especially when the randomness of the required key is taken into account?

There is no such thing as a random key.  There are only randomly generated keys.

What I mean by that is that randomness is not a property of the key (or message, or number, or whatever), but of the process that generates it.  For example, it is not meaningful to ask whether the number 5 is random, or whether it is somehow more or less random than the number 4.  However, if I pick up a die and roll it, and it lands with the "5" face up, then I can meaningfully say that I have just randomly selected the number 5 (and we can also meaningfully discuss just how random or not the way I rolled the die may have been).

In English we often do use "random" as an adjective to describe a thing (as opposed to an action), when we really should be saying "randomly chosen" or something similar.  But this needs to be understood as just a linguistic shorthand.  "A random number" really means "a randomly chosen number", and that's all there is, or can be, to it.

Why am I stressing this point so much?  It's because when you ask something like:

  If key TQURI is "measured" as less random than XMCKL, ...

you're revealing a fundamental confusion about what "a random key" really means.  As I wrote above, randomness is not a property of the key string itself, so there's no way to assert that, say, the string "TQURI" is somehow more or less random than "XMCKL" or, for that matter, "ABCDE".  Even trying to make the comparison is meaningless.

All that we can meaningfully ask is how likely it is that each of those key strings would appear if we, say, randomly picked five letters from a bag containing each letter of the alphabet and wrote them down (returning each picked letter to the bag before picking the next one).  And the answer to that question is that each of those strings (yes, even "ABCDE") is equally likely to be the result of that process.

Thus, if our one-time pad was generated using the method I described (or by any other equally random means), then none of those proposed keys is any more likely to be the correct one than any other, and so examining them yields no information about the message.

Ps. Yes, this also means that randomness testing is, strictly speaking, a fool's endeavor: a truly random process is equally likely to output any string of a given length, so no such string can be said to be any more or less random than any other in that sense.

The best we can do is to look for distinctive features that may appear disproportionately more often in the results of certain kinds of non-random (or incompletely random) processes, and declare the observation of such features as evidence that the process that generated the output may not be perfectly random.  In that sense, it would be more appropriate to call any such tests "non-randomness testing".

Even then, in doing so, we must necessarily accept the possibility of "false positives", i.e. the possibility that even a perfectly random process can, and will, occasionally generate outputs that look like the output of some non-random process.  A perfectly random 5-letter string generator must, necessarily, generate the string "AAAAA" with probability $1/26^5 \approx 0.00000008$ — and if it did not, it would not be perfectly random.

The confusion is probably coming from using the term "randomness" instead of "the probability a key uses N different characters".  The more characters the set of possible keys uses, the more characters a randomly selected key will tend to have.  In other words, after randomly choosing a key of 14 characters from A to Z, the key will probably use about 11 different characters.  It's going to be rare that you end up with only 1 or 2 different characters in the key.

Here's a run of 10 million random 14-character keys using A to Z:

Over 3 million keys used 11 characters, while only 56 keys used only 5 characters.  There were no keys using 4 or fewer characters.  Over 130,000 keys had no repeating characters and used all 14.  Trying only keys with 10 to 12 different characters still gives you over 78% of the keys.

Therefore, yes, skipping the most unlikely keys will reduce your search time and probably not skip the correct answer.  You'll still need to do a lot of computing for the remaining cases.


How to argue to a paranoid that RSA is safe? From today's standpoint, most people would claim RSA to be secure. However, to my knowledge, this is purely based on the speculation that no one knows a computational feasible way to find a $d$ for given $n$ and $e$, s.t. $ed \equiv 1 \mod \varphi(n)$ - which can be reduced to the factorization problem.

However, it is still an assumption that the factorization problem is hard to solve but nothing that has been proven mathematically. Worse, as far as I understand it, it is not even clear to which complexity class integer factorization belongs. And if the past year has thought us anything then it is that often the "paranoia argument" is not that paranoid at all.

So I always wondered how probable it is that indeed no one has found an efficient solution to the factorization problem yet. How would one know? Or, in short:  How do you convince a paranoid that RSA indeed is secure?

The security of every single cryptographic algorithm(*) of any kind is ultimately based on: "many people looked at it for a long time and did not find a way to break it". Security proofs boasted by some algorithms are quite useful but they don't actually prove security, they move it (a security proof is a reduction to another problem which has to be assumed to be strong).

So one could "measure" the strength of an algorithm by the accumulated scrutiny it has sustained successfully. In that sense, RSA is about the best in class: it relies on mathematical principles which can be argued to have been studied for more than 2500 years by the smartest mathematicians in the World. Elliptic curves cannot compete with that.

This argument is, of course, debatable. At best. Yet one has to take into consideration that paranoia, by definition, is a distortion of the perception of reality and the balance of risks. So the paranoid can be convinced by arguments which depend on that distortion.

(*) Except the very few algorithms with unconditional security, like Shamir's Secret Sharing, but they are limited in scope. That which is done with RSA (asymmetric encryption, digital signatures) can be easily proven to be infeasible with unconditional security; e.g. signatures can always be theoretically forged through exhaustive search on signature values, since the verification algorithm is, by definition, public.

Convincing people is actually a more psychological than cryptographic endeavour. Context matters. If the context is economical, then it suffices to say: "Maybe RSA can be broken, but your competitors use RSA. Not doing the same incurs the risk of letting them run ahead of you." Indeed, the paranoid is averse to risk, and not doing the exact same mistakes as the competition is the biggest risk that can be taken by a business.

RSA isn't secure from paranoid point of view!

RSA is vulnerable to quantum calculus
RSA could be broken very using large cluster, and for that only public key need
RSA could be broken with use of soldering iron on author of message

Plus, you could use weak prime numbers at source, so your LargeNbits private key could be broken quick, with just know that you have it weak.


What encryption should I use: Blowfish, Twofish, or Threefish? The title of this thread pretty much sums up what I'm asking: what is the best encryption to use out of the three — Blowfish, Twofish, or Threefish?

TL;DR: Twofish and Threefish are fine.
It is not the best idea to have the cipher you want to use hardcoded because you can't upgrade easily when one of them is broken. to quote mikeazo in the comments:

What you should do is develop your application to not be bound to a specific cipher.

Twofish

In 1999, Niels Ferguson published an impossible differential attack that breaks six rounds out of 16 of the 256-bit key version using $2^{256}$ steps.

As of 2000, the best published cryptanalysis on the Twofish block cipher is a truncated differential cryptanalysis of the full 16-round version. The paper claims that the probability of truncated differentials is $2^{−57.3}$ per block and that it will take roughly $2^{51}$ chosen plaintexts (32 petabytes worth of data) to find a good pair of truncated differentials.

Bruce Schneier responds in a 2005 blog entry that this paper does not present a full cryptanalytic attack, but only some hypothesized differential characteristics: "But even from a theoretical perspective, Twofish isn't even remotely broken. There have been no extensions to these results since they were published in 2000."

https://www.schneier.com/academic/twofish/
https://www.schneier.com/blog/archives/2005/11/twofish_cryptan.html
Threefish

In October 2010, an attack that combines rotational cryptanalysis with the rebound attack was published. The attack mounts a known-key distinguisher against 53 of 72 rounds in Threefish-256, and 57 of 72 rounds in Threefish-512. It also affects the Skein hash function. This is a follow-up to the earlier attack published in February, which breaks 39 and 42 rounds respectively. In response to this attack, the Skein team tweaked the rotation constants used in Threefish and thereby the key schedule constants for round 3 of the NIST hash function competition.

In 2009, a related key boomerang attack against a reduced round Threefish version was published. For the 32-round version, the time complexity is $2^{226}$ and the memory complexity is $2^{12}$ for the 33-round version, the time complexity is $2^{352.17}$ with a negligible memory usage. The attacks also work against the tweaked version of Threefish: for the 32-round version, the time complexity is $2^{222}$ and the memory complexity is $2^{12}$ for the 33-round version, the time complexity is $2^{355.5}$ with a negligible memory usage.

http://www.skein-hash.info/ (the design of Threefish is based on it).
Blowfish

At this point, though, I'm amazed it's still being used. If people ask, I recommend Twofish instead.
— Bruce Schneier, Blowfish's creator, 2007

Swordfish
                         GABRIEL
              Here's the deal. I need a worm,
              Stanley. A hydra, actually. A
              multi-headed worm to break an
              encryption and then sniff out
              latent digital footprints
              throughout an encrypted network.

                            STANLEY
              What kind of cypher?

                            GABRIEL
              Vernam encryption.

                            STANLEY
              A Vernam's impossible. Its key
              code is destroyed upon
              implementation. Not to mention
              being a true 128 bit encryption.

                            GABRIEL
              Actually, we're talking 512 bit.

source

I prefer blowfish because the key length is 448 bits. But due to it`s small block size (64 bits), I recommend using CBC mode.

I prefer blowfish to AES because AES is the government standard and I don`t trust the government. For instance, the old government standard, DES, was 56 bits. At the time DES was created, it was strong enough to not be broken by a PC, but weak enough to be broken by the NSA. The government has a history of making powerful encryption illegal.


Suitable Symmetric Algorithm for Encryption Please, I would like to encrypt word not more than 5 letters such as (GO, HI, APPLE, EYES) and my key length just (40 bits only), please I am looking for a suitable symmetric algorithm that it can be lightweight, fast as well as less processing required so it can suit my mechanism?

Please any suggestion and sorry for my weak English ):

Is there any particular reason to use a key length of just 40 bits? Because it is vulnerable to brute-force attacks. To have a reasonable strength, the minimum reasonable key length nowadays is 128 bit (source).

If you don't care about this stuff, you may use one of the following: DES-40, RC2, RC5, Blowfish. These ciphers support a key length of 40 bits, as you require. Anyway, any of these ciphers always has block size different from 5 bytes, which you are probably interested into. I'm not aware of any cipher with a block size of 5-byte/40-bit.
The alternative would be to use a stream cipher that supports a key length of 40 bits, such as RC4 (you can find many more here).

You have the following requirements:

A $40$ bit key
considerably fast / lightweight / low processing time

With these requiements it is impossible to find anything, which is also secure. Basically, your own requirements make sure, that it's really easy to brute force - probably on a single computer already.


Creating an encryption key from several other keys and using hash functions I want to combine two or more keys to create a single encryption key that relies on all of them.  What is the proper method for doing that? Simple XOR? Using hash functions?  Something else?

I personally used this: k = md5( key1 || key2 ).  Note: || means concatenation.  I used md5 because I use 128-bit encryption and thus need a 128 bit output key.

Some other questions arise here for me:

Is using MD5 secure for this specific purpose?
I don't know of any other standard 128-bit output hash functions. It seems newer cryptographic hash functions all have 256-bit and more output lengths.
So is using another hash function that has a 256/512-bit output and then truncating the result down to 128 bits secure to an equal or more degree than using MD5?

Note that key1 and key2 are random keys, not passwords, and thus key stretching is not relevant or applicable.

If it is relevant, I generated both keys, and I know that both keys are cryptographically random.  Neither key was supplied by an untrusted party.  At present both keys happen to be the same length, but I'd prefer a more general solution that does not rely upon this assumption, if possible.

If the keys have constant, known length, I'd concatenate them, and then apply SHA256. If they have variable length, applying some separation mechanism might be useful.

Truncating hash functions works well. If the original hash function is good, a truncated hash function has the same properties, albeit at a correspondingly lower security level. Truncating SHA-256 is certainly better than using MD5.

I recommend something like:

Truncate(SHA-256(output-size || number-of-keys || sizeof(key1) || key1 || sizeof(key2) || key2 ...), output-size) where output-size <= 256

the problem with hash-functions such as md5 and sha* are that they were not designed to solve the problem you have: create a cryptographic hard key for further use. they were design to calculate hashes very very fast without having a too high chance of hash-collisions.

what you really want to use is a so called key derivation function. examples for such functions are:

scrypt, paper
bcrypt
pbkdf2

what kind of secrets you pipe into that function to get the actual key is pretty much up to you. the main point of such functions is that it takes relatively long time to calculate the  key and thus slowing down brute force attacks quite a bit.


Does AES(x || x) provide secure message authentication when message fits in a single block? Suppose I have x = <64 bits of data>. I build a 128 bit block $P = x || x$, and transmit a message $M = AES(K, P)$. The receiver has the same $K$.

The receiver can then decrypt the message, split the decrypted block in two 64 bits parts, and comparing them for equality. What kind of guarantee would the equality check provide? Would they be able to securely authenticate the message?

Edit: as stated in a couple answers, the $x||x$ concatenation is a red herring. The scheme looks equivalent to padding x to 128 bits with all zeroes, then checking the decrypted block for the same sequence.

Concatenating two copies of your message is unnecessary and is equivalent to padding out your 64 bit message to the full 128 bits with zeros from a security standpoint (which happens automatically in the encryption process).

  Would they be able to securely authenticate the message?

I assume you mean Authenticated Encryption.  The simple answer is no.  AES on its own only provides provides confidentiality, not Authenticated Encryption (which is defined as confidentiality, integrity, and authenticity).  To get true Authenticated Encryption you would need to use some sort of hash function to create and append a mac, which is validated during the decryption process.

More information on Authenticated Encryption can be found here.

EDIT:  Sorry I was making a few assumptions about other concepts outside the scope of this question.  The reason why simply encrypting one block of AES doesn't give you integrity or authenticity is because it is susceptible to modification by an active attacker.  One way this would work is actually pretty simple, but it assumes you would also use an Initialization Vector (IV).  While not specifically stated in your question, this would be required to make the message resistant to Replay Attacks and is the only way a block cipher is CPA secure.

Assuming CBC mode, the IV is XOR'd over the plain text before encryption.  If you were to XOR what you think is in the plain text (a guess), then XOR what you want to be in the plain text, it will be XOR'd into the plain text before it is encrypted, thus modifying it to whatever the attacker wants.  Other modes could be venerable to attacks like this also.

You could also use this method and the fact that the first 64 bits of the message should match the second 64 bits as a oracle where by you could test one character at a time and watch what response a server gives back to actually decode the message.

Sorry for not being specific (as I don't know that much about AES itself) but you should go with RSA for messages, generally asymmetric encryption is great, but slow. The best solution is to encrypt AES password with RSA (pgp for example) and then use this password to encrypt messages. This way you can share passwords in safe way.

And pgp allows source verification, that makes best solution for you.


Needham–Schroeder fix by adding opponent's identity to the first message Recap: Needham–Schroeder is as follows:

$A \rightarrow B :   \{A, N_a\}_{pk_B}$
$B \rightarrow A :   \{N_a, N_b\}_{pk_A}$
$A \rightarrow B :   \{N_b\}_{pk_B}$

Then, there is a MITM attack by Lowe as follows:

$A \rightarrow C(A) :   \{A, N_a\}_{pk_C}$
$C(A)\rightarrow B     :   \{A, N_a\}_{pk_B}$
$B \rightarrow C(A) :   \{N_a,N_b\}_{pk_A}$
$C(A)\rightarrow  A       :   \{N_a,N_b\}_{pk_A}$
$A   \rightarrow  C(A)    :   \{N_b\}_{pk_C}$
$C(A)\rightarrow  B       :   \{N_b\}_{pk_B}$

Now $C(A)$ knows both $N_a$ and $N_b$, and he can compute the session key.
The solution that Lowe suggests is to put $B$'s identity to the second message:

$A \rightarrow B :   \{A, N_a\}_{pk_B}$
$B \rightarrow A :   \{N_a, N_b, B\}_{pk_A}$
$A \rightarrow B :   \{N_b\}_{pk_B}$

But what happens if we put B's identity into the first message?

$A \rightarrow B :   \{A, B, N_a\}_{pk_B}$
$B \rightarrow A :   \{N_a, N_b\}_{pk_A}$
$A \rightarrow B :   \{N_b\}_{pk_B}$

Is it still vulnerable to MITM attack or is it secure too?

It's easy to see that the man-in-the-middle attack you describe still applies to the modified protocol.

$A \rightarrow C(A) :   \{A, C, N_a\}_{pk_C}$
$C(A)\rightarrow B     :   \{A, B, N_a\}_{pk_B}$
$B \rightarrow C(A) :   \{N_a,N_b\}_{pk_A}$
$C(A)\rightarrow  A       :   \{N_a,N_b\}_{pk_A}$
$A   \rightarrow  C(A)    :   \{N_b\}_{pk_C}$
$C(A)\rightarrow  B       :   \{N_b\}_{pk_B}$

The idea why adding $B$'s identity to the second message might be helpful is that $B$ is telling the receiver who they are. So if $A$ sees that message they will realize that something is afoot, since they wanted to talk to $C$ but received a reply from $B$.¹

Whereas in your solution Alice tells the receiver who $A$ thinks they are. But since the man in the middle does not forward this message blindly, but in fact decrypts it and uses it to construct an entirely new message, this doesn't help in any way.

¹This only really helps if the public key encryption scheme used does not have malleable ciphertexts. Using encryption for authentication is just not a good idea and does not lead to robust solutions.


What is the "Random Oracle Model" and why is it controversial? What is the "Random Oracle Model"?  Is it an "assumption" akin to the hardness of factoring and discrete log?  Or something else?

And why do some researchers have a strong distrust of this model?

A random oracle is described by the following model:

There is a black box. In the box lives a gnome, with a big book and some dice.
We can input some data into the box (an arbitrary sequence of bits).
Given some input that he did not see beforehand, the gnome uses his dice to generate a new output, uniformly and randomly, in some conventional space (the space of oracle outputs). The gnome also writes down the input and the newly generated output in his book.
If given an already seen input, the gnome uses his book to recover the output he returned the last time, and returns it again.

So a random oracle is like a kind of hash function, such that we know nothing about the output we could get for a given input message $m$, until we actually try $m$. This is a useful tool for security proofs because they allow to express the attack effort in terms of number of invocations to the oracle.

The problem with random oracles is that it turns out to be very difficult to build a really "random" oracle. First, there is no proof that a random oracle can really exist without using a gnome. Then, we can look at what we have as candidates: hash functions. A secure hash function is meant to be resilient to collisions, preimages and second preimages. These properties do not imply that the function is a random oracle.

Indeed, see SHA-256 (or SHA-512 if you wish). It suffers from something called the "length extension attack". This is an artefact from the Merkle–Damgård construction: to hash a message $m$, the message is first split into fixed-size blocks (64 bytes for SHA-256), the last block being padded with some bits which include the length of $m$, and some ones and zeros such that we end up with a full block. Each block is then processed over a running state, the hash output being the last block value.

So suppose that there is a message $m$, that I do not know, but I know the length of $m$ and its hash $h(m)$. With that information, I can rebuild the padding bits which were added (let's call them $\pi$). Then, I can envision the message $m'$:
$$ m' = m || \pi || x $$
for some value $x$ that I choose arbitrarily. I then know that the computation of $h(m')$ will begin by splitting $m || \pi$ into blocks and processing them, and after having processed the last bit of $\pi$, the current "running state" will be exactly $h(m)$. So, if I know $h(m)$, I can finish the computation of $h(m')$ by taking it from there, and I can do that without knowing $m$. In particular, I end up with $h(m')$ while not having presented $m'$ to the gnome.

This property proves that SHA-256 is not a random oracle. Yet, it does not endanger in any way the resistance of SHA-256 to collisions or preimages. Therefore, being a random oracle seems to be strictly harder than being a secure hash function.

It has actually been shown (by Canetti, Goldreich and Halevi) that random oracles cannot exist "in all generality" in the following sense: it is possible to build pathological signature and asymmetric encryption schemes, which are secure when they internally use a random oracle, but which are insecure whenever an actual computable function is used instead of the mythical gnome-in-the-box.

Summary: proofs in the random oracle model are fine, but are never complete enough to cover a practical implementation: we know that any function we will use in lieu of the random oracle will not be a random oracle; so security relies on the fervent hope that the parts where the actual function is not a random oracle do not impact security. This justifies a bit of mistrust. Still, a proof in the random oracle model is much better than no proof at all.

The bear describes a process for choosing and computing a uniform random function involving gnomes in boxes, but this doesn't really explain what the random oracle model is in the context of proving security reductions.  There are three parts: uniform random functions, cryptosystems built out of hash functions, and random oracle proofs.

Uniform random functions.
A die roll has a probability distribution on the possible outcomes {1, 2, 3, 4, 5, 6}.  The outcomes all have equal probability 1/6 when it is a fair die roll, in which case we call the distribution uniform.  We can also have a uniform distribution on coin tosses {heads, tails}, and a uniform distribution on sock colors {red, blue, green, teal-with-mauve-trim, …}, and so on, for any finite set of possible outcomes.

We can also have a uniform distribution on $t$-bit-to-$h$-bit functions $H\colon \{0,1\}^t \to \{0,1\}^h$.  This space of functions is a finite set: you can write down a finite truth table for every bit of the $h$-bit output in terms of the $t$ bits of input, so there are exactly $(2^h)^{2^t}$ such functions; in the uniform distribution, each one has equal probability $1/(2^h)^{2^t}$.

One way to choose such a function uniformly at random is to wander through the Library of Babel and pick a book with $2^t$ pages, each of which has an $h$-bit string on it, so that the content of page $x$ is $H(x)$.  Another way is to trap a gnome in a box with a coin and an empty book of $2^t$ pages; enslaved thus, when you ask the gnome for an input $x$, the gnome consults page $x$ in the book, and if it's empty, flips the coin $h$ times and writes down the result.  Another way is to just flip a coin yourself $h 2^t$ times and write down a gigantic truth table.

However you choose a function $H$ uniformly at random—whether by randomly browsing a library like a civilized being, or by enslaving a gnome like a savage bear—for any particular function $f\colon \{0,1\}^t \to \{0,1\}^h$, the probability $\Pr[H = f]$ of getting that function is $1/(2^h)^{2^t}$.  Another way to put this is that for any particular input $x$ and output $y$, $\Pr[H(x) = y] = 1/2^h$—and the value at each distinct input is independent, so $\Pr[H(x_1) = y_1, \dots, H(x_\ell) = y_\ell] = 1/2^{h\ell}$ if $(x_1, \dots, x_\ell)$ are all distinct.  This property makes the model of uniform random functions easy to reason about.

Cryptosystems built out of hash functions.
Some cryptosystems are defined in terms of a hash function.  For example, RSA-FDH—Full Domain Hash—uses a hash function $H$ for public-key signatures:

A public key is a large integer $n$.
A signature on a message $m$ is an integer $s$ such that $$s^3 \equiv H(m) \pmod n.$$
To make a signature, the signer, who knows the secret solution $d$ to the equation $$3 d \equiv 1 \pmod{\lambda(n)},$$ computes $$s := H(m)^d \bmod n.$$

The use of a hash in signatures is crucial for security, as Rabin first observed in 1979[1]: if we instead used the signature equation $s^3 \equiv m \pmod n$, then anyone could immediately forge the signature 0 on the message 0, or take two message/signature pairs $(m_0, s_0)$ and $(m_1, s_1)$ to forge a third $(m_0 m_1 \bmod n, s_0 s_1 \bmod n)$, or forge a signature $\sqrt[3]{m}$ on any integer cube $m$, etc.

The formulas are written in terms of $H$, so you can write a procedure that computes the various parts of the cryptosystem with $H$ as a parameter alongside all the others:

def sign(H, n, d, m):
    s = modexp(H(m), d, n)
    return s
def verify(H, n, m, s):
    return modexp(s, 3, n) == H(m)

What properties do we require of $H$?  Typically some combination of preimage resistance, collision resistance, etc.  For a uniform random function, the expected cost of finding a preimage or finding a collision is high.  We could imagine enslaving a gnome in a box, and using sign(gnomebox, n, d, m) and verify(gnomebox, n, m, s):

book = {}
def gnomebox(m):
    if m not in book:
        book[m] = random(2**h)
    return book[m]

However, for this cryptosystem to be useful, we need everyone to agree on the same function, so we need everyone to share the same gnome.  Sharing gnomes is not a scalable way to do commerce over the internet, which is the only reason capitalism doesn't choose to rely on this particular type of slavery to concentrate wealth.

Instead, when we actually use this cryptosystem, we agree to pass, say, SHAKE128-2047 as $H$, when we choose $n$ to be 2048 bits long: s = sign(shake128_2047, n, d, m), verify(shake128_2047, n, m, s).

When we use a particular hash function like SHAKE128 together with particular fancy math like $s^e \equiv H(m) \pmod n$, the hash function could in principle interact with the fancy math in a way that destroys security, but the hash function we choose has been studied for many years to get confidence that it has no useful properties other than being cheap to evaluate, and even if it did turn out to have bad interaction or bad properties—say because we used SHAKE128 but the fancy math internally uses the inverse of the Keccak permutation for some reason, or because we used MD5 as $H$—we could swap in a different hash function.

If we make a bad choice of hash function, there might be easy attacks that depend on the choice of hash function, like a way to compute $H(m \mathbin\| m')$ given $H(m)$ but not $m$ and thereby forging hashes of messages with unknown prefixes, or like finding MD5 collisions and thereby disrupting Iran's nuclear program.  But there might also be attacks that don't depend on the choice of hash function.  Can we say anything in general about the rest of the cryptosystem?

Random oracle proofs.
To get confidence that forging signatures is hard, we show that a forger can be used as a subroutine to solve the RSA problem and invert $x \mapsto x^3 \bmod n$ for uniform random $x$.  We suppose that solving the RSA problem is hard; consequently, if a forger can be used to solve the RSA problem, forgery can't be much easier than solving the RSA problem.

Specifically, we give the forger access to $H$, the public key, and a signing oracle which returns the signature on any message of the forger's choice:

def forge(H, n, S):
   ... S(m0) ... S(m1) ...
   return (m, s)

Here we would obviously pass lambda m: sign(H, n, d, m) as $S$; the point is that the forger is only allowed to call the signing oracle $S$, but is not allowed to inspect it or to see what the secret key $d$ is.

The forger is successful if, given (m, s) = forge(H, n, S), the resulting message and signature pair pass verify(H, n, m, s), subject to the restriction that $m$ was not passed to the signing oracle $S$.  (Otherwise, the forger could win by asking $S$ for a signature on a message and returning that, which would not impress anyone as a method of forgery.)  Obviously, a forger might win by guessing a signature at random, which has a very small but nonzero probability of success.

Given such a forger, we will show how to compute cube roots modulo $n$ with comparable success probability: specifically, a cube root function cbrt that uses forge as a subroutine and wins if modexp(cbrt(n, y), 3, n) == y.  Let's assume that the forger makes at most $q$ queries to the hashing oracle $H$ or the signing oracle $S$.

We will make our own specially crafted hashing and signing oracles for the forger to use: they will be specially crafted to let us extract an RSA problem solution, but the hashing oracle we construct still has uniform distribution, and the signing oracle we construct still produces valid signatures for the cryptosystem instantiated with the specially crafted hashing oracle.

def cbrt(n, y):
    j = random(q)    # Guess at which one the forger will invert.
    i = [0]          # Mutable counter.
    ms = {}          # Maps message we have seen to index i.
    ys = {}          # Maps image we have given out to index i.
    xs = {}          # Maps index to preimage of H0.
    def H0(m):
        ms[m] = i[0]
        if i[0] == j:
            xi = m
            yi = y
        else:
            xi = random(n)
            yi = modexp(xi, 3, n)
        xs[i] = xi
        ys[yi] = i[0]
        i[0] += 1
        return yi
    def S0(H, m):
        if m not in ms:
            if modexp(H0(m), 3, n) == y):
                # We accidentally won without the forger.
                raise Exception
        return xs[ms[m]]
    try:
        (m, s) = forge(H0, n, S0)
        return s
    except Exception:
        return xs[ys[y]]

(This procedure is the standard proof of RSA-FDH security by Mihir Bellare and Phil Rogaway[2], Theorem 3.1.)

When the forger returns an attempted forgery $(m, s)$, there's a high probability that it passed $m$ to the hash; there's a $1/q$ probability that it was the $j^{\mathit{th}}$ query to the hash, in which case we returned $y$ from our carefully crafted hash; then if the forger was successful, $s^3 \equiv y \pmod n$, as we hoped.

Of course, there's also a tiny chance that the forger stumbled upon a successful forgery by chance for another message it fed to the hashing oracle, but that happens with probability $1/n$ which is very very very very very small.  There's also a chance that our cube root procedure stumbles upon a successful cube root without the forger's help, but again, with probability $1/n$ for each query from the forger, which is very very very very very small.

Thus, if the forger has success probability $\varepsilon$, our cube root procedure has success probability approximately $\varepsilon/q$, with a little extra computation for some more calls to modexp.  This suggests that if there's a cheap algorithm to compute forgeries using $q$ oracle queries, then there's an algorithm to solve the RSA problem costing only $q$ times as much—provided the forgery algorithm is generic in terms of $H$.

This was a particularly simple ROM proof; others use more elaborate techniques like the forking lemma, where we rerun the adversary's algorithm with the same random choices inside the algorithm, but a different oracle[3].

Why is this model controversial?
In practical terms, it's not controversial: only academic cryptographers in an ivory tower worry about it, while practitioners have used ROM-based cryptosystems for decades largely without trouble.  Hash functions like MD5 have gone bad, admitting collisions, and the Merkle–Damgåard structure admits length extension, but these cause problems just as well in non-RO proofs.  So what is their objection?

It is tempting to draw the following inference:

  If a scheme is secure in the random oracle model, then it is secure if we instantiate it with a particular hash function like SHAKE128 as long as the hash function isn't too badly broken.

Obviously, as above, we could devise a cryptosystem that is broken if you instantiate it with SHAKE128, but works fine if you instantiate it with pretty much any other hash function.  Ran Canetti, Oded Goldreich, and Shai Halevi proved an academically very cute result: there exists a signature scheme which is secure in the random oracle model—meaning there's a random oracle proof like above showing how to turn a forger into an algorithm to solve some hard problem—but which is insecure with any practical instantiation[4].

It can be built out of any secure signature scheme $(S, V)$ you like, and it works roughly as follows:

To sign a message $m$ with secret key $\mathit{sk}$,

If $m$ is of the form $(i, \pi)$ where $\pi$ is a proof that $(i, H(i))$ is in the graph of the $i^{\mathit{th}}$ polynomial-time function in some enumeration of them,* then the signature is $(\mathit{sk}, S_\mathit{sk}(m))$.  (Such a proof can be verified in polynomial time.)
Otherwise, the signature is $(\bot, S_{\mathit{sk}}(m))$.

To verify a signature $(z, s)$ on a message $m$ under public key $\mathit{pk}$, compute $V_{\mathit{pk}}(s, m)$.  (We ignore $z$, which serves only as a back door.)

This signature scheme can be proven secure in the random oracle model, because the probability that $(i, H(i))$ is actually in the graph of the $i^{\mathit{th}}$ polynomial-time function in any particular enumeration of them is negligible for uniform random $H$, but if you choose any particular family of functions for $H$ then it is easy to construct a back door message that dumps out the private key by simply using its index in the enumeration.

This is a complexity-theoretic trick to devise a pathological signature scheme that throws a temper tantrum if you try to instantiate it in the real world.  What the Canetti–Goldreich–Halevi scheme shows, by counterexample, is that the inference we would like to draw is not formally valid.

One might infer that there is some technical criterion distinguishing pathological counterexamples like this from the multitude of ROM-based protocols actually devised for practical use like RSA-FDH, RSA-KEM, RSA-OAEP, RSA-PSS, DH key agreement, etc.

Some academics choose instead to leave the random oracle model in the dustbin on the basis of this counterexample, and focus on finding ways to convert attacks on (e.g.) a signature scheme into preimage or collision attacks on the hash function, or find systems that through extreme contortions avoid hash functions altogether—a setting which is dubbed the ‘standard model’ in passive-aggressive phraseology to cast shade on the random oracle model and its practitioners.  This comes at considerable cost to the complexity of proof techniques and the efficiency of the resulting cryptosystems, which seldom if ever appear outside academic journals and conference proceedings, no matter how strongly they express feelings there[5][6][7][8].

On the other hand, this doesn't mean that random oracle proofs are useless in practice.  Protocols with random oracles have been wildly successful in the real world, to the point that nearly every public-key cryptosystem used in practice takes advantage of them—as a design principle they are highly effective at thwarting attacks from the first secure signature scheme in history[1] to modern Diffie–Hellman security[9].

Indeed, not only have we had no reason to doubt the security of (e.g.) RSA-FDH in practice in the quarter century of its existence, but it is hard to imagine that a $q$-query forger could actually be a factor of $q$ cheaper than an algorithm to solve the RSA problem, since the distribution on message hashes and signatures from the signing oracle, $(h_i, {h_i}^d \bmod n)$, is exactly the same as the distribution on quantities anyone could have computed without a signing oracle, $({s_i}^e \bmod n, s_i)$; and since the hash oracle is independent of the secret key.  This suggests that there may be something awry in our attempts at formalization.

It would not be the first thing awry with formalization of cryptographic attacks in the literature.  For example:

There is no formalization of collision resistance of a fixed hash function like SHA3-256[10][11].  On 257-bit outputs, there is guaranteed to be some collision $x_0 \ne x_1$, so there is a very cheap algorithm that prints collisions: it simply prints $(x_0, x_1)$ with no effort.  But we have no idea how to find it without spending energy to compute an expected $2^{128}$ evaluations of SHA3-256.
There is almost certainly a 128-bit string $s$ such that the first bit of $E \mapsto \operatorname{MD5}(s \mathbin\| E(0) \mathbin\| E(1))$ is a high-advantage distinguisher for $E = \operatorname{AES}_k$ under uniform random key $k$ from a uniform random permutation $E$[12], which violates the premises of most inferences drawn about bounds on the PRP advantage of AES, e.g. those justifying the use of AES-GCM in practice.  But we have no idea how to find $s$ without spending an obscene amount of energy.

None of these technical issues of formalization prevent the widespread and highly successful use of collision-resistant hashes or of AES.  Nor should they prevent the use of random oracles as a design principle or justify the summary rejection of essentially all public-key cryptography in practice.

* There are more technical details: actually we work in the asymptotic setting where everything is parametrized by an input size, and we consider families of functions keyed by a seed and indexed by the input size, and enumerating functions bounded by some superpolynomial cost, etc.  See the paper for details if you're interested.


How does hash function in Elgamal signature scheme prevent existential forgery attack? I have heard that hashing the message M prevents an existential forgery attack. I was wondering how.

Existential forgery attacks allow the attacker to choose (or calculate) a signature, and then the message is derived from this signature (and the public key) using the existential forgery attack algorithm.

The signature is valid for the derived message, but the problem is that the attacker cannot control the message. It could be anything.

Hashing the message before verification requires the attacker, Oscar, to additionally find some data that hashes to his derived message, which is practically impossible.

Hashing allows the recipient to know that the message comes from an intended person. By using the SHA-1 algorithm, if the hashed message does not match up, then the recipient knows that the message has been forged/is fraudulent. Check out digital signatures for more information.


Strong RNG for encryption/authentation algo I saw in the market several hardware options for creating strong RNG to produce strong KEYS:

HSM
TPM internal TRNG
Intel RDSEED (TRNG)/RDRAND

My questions are;

What is the strength/entropy difference between them? (using intel RDSEED is much lower cost than buying an HSM)
Why feeding TRNG seed (like RDSEED) into the PRNG mechanism (RDRAND)? doesn't that lower its strength?
Cant I use RDSEED for creating a key (using KDF) without RDRAND?

RDRAND/RDSEED is the focus of all three of your questions here.  If you're looking for truly random numbers (as indicated by the trng tag),   it's probably worth realising that there is substantial anecdotal and circumstantial evidence that RDRAND/RDSEED isn't a TRNG.  Have a look at my analysis from another question, specifically item 10. That indicates that it's not just me spouting weirdo conspiracy theories.

Since my analysis discourages the cheap Intel approach, you're left with TPMs and HSMs. Clearly a HSM costs waay more than a TPM.  You could argue that a HSM might be more secure/reliable as they tend to be build to international standards like FIPS and commonly accepted in security scenarios.

The entropies should be identical at 8 bits/byte, but I also offer this warning.  How do you know? Computational indistinguishability means that you can't differentiate even a simple construct like $E_k(pepper||time)$ from a truly random sequence. And both hardware are designed tamper resistant, which means that you can't personally audit them. So similarly, look at this TPM criticism.

It's a tough choice as a lot of what applies to my RDRAND/RDSEED thesis also applies to TPMs and HSMs.

As for the remaining two parts:-

Yes, feeding a PRNG from a TRNG seed does lower the mathematical strength of the output. A caveat though is that as long as you create your 128/256 bits of initial Kolmogorov randomness, it should be sufficient for most cryptographic purposes. It just means that the output entropy is no longer truly random. Those 128/256 bits remain a constant no matter the output length. Till you re-seed. This is what occurs inside *nix's \dev\urandom, just using other entropy sources.
RDSEED's raison d'être is key creation and seeding.  If you believe that the output entropy is real, then all you have to do is acquire it.  You get it in batches of 16 - 64 bits via registers. It's a bit dry, but instructions are here.  No KDF is required as it should be truly random at 8 bits/byte and therefore perfectly secure. A KDF is indicated when going from a password to a key.


Can anyone explain to me the difference between the OTP (one-time pad) and Vernam Cipher? I heard they are very similar, although there are subtle differences between the two.

Confusion arises because many people use the terms Vernam cipher and one-time pad interchangeably--but they are not the same thing.
When young Gilbert Vernam, an AT&T research engineer, got his patent in 1919 (for a "Secret Signaling System"), Vernam cipher meant a fast encryption method using an additive stream cipher that was machine-based and used Baudet with modulo 2 addition.
XOR was born.
According to this unclassified NSA historical account (p.2):

Gilbert S.Vernam, working on new developments in telegraphy, came up
with a novel (and relatively simple) scheme for encrypting TTY. He
mixed  two  Baudot-coded  punched  paper  tapes (hole  being  a  “+,”
no  hole  a  “-”): one  tape  contained  the plaintext message and the
other the “key.” These tapes were added  “modulo  2”  (“exclusive
or”)  in  a  mechanical  tape reader producing an output cipher signal.

This was a huge improvement over the tedious codebooks and the German ADFGVX cipher, which was susceptible to cryptanalysis. Interestingly, in 1918, the U.S. Army was uninterested in Vernam's work.
But there were several problems no one understood at the time:
1.  The key had not been generated in a truly random manner
2.  The key was on a looped tape
3.  The key was reused

Not a one-time pad.
Enter Joseph Oswald Mauborgne--artist, cryptographer, and U.S. Army General-- the first person to send a radio signal from an aircraft to the ground.  He had the realization that if the key had been generated in a random manner, then the ciphertext from Vernam's machine would be unbreakable.
Frank Miller, an American cryptographer, had already invented the one-time pad in 1882, but the glory seems to have landed on Gilbert Vernam instead of the two people who had actually figured it out.  This reminds one of how Blaise de Vigenère had a cipher named after him that Giovan Battista Bellaso had invented much earlier.
Vernam cipher and the OTP are not the same thing.  Moreover, when we say OTP that can refer to a physical object, usually one that is easy to hide and destroy.
These days, we mostly think of the OTP as a model for encryption systems.

I think he is looking for difference of one time pad in vernam cipher and One Time Password (the 4/6/8) digit number which is used for transaction authentication)

One Time Password:
In OTP, the user gives his password w (more precisely a secret pass-phrase of at least 10 characters) to the OTP generator.
The generator generates a random seed s which consists of 1–16 lowercase alphanumerical characters.
It then hashes w concatenated with s and reduces it to 64 bits using a standard function.

This produces a string S = H(w,s). (The purpose of the seed is to diversify the pass-phrase, since it may very well be the case that the same pass-phrase is used in different applications by
a particular individual.)
The generator then computes ${p_i=H^{N-i}(S)}$ for i=0,...,N, and gives them to user with s.
The OTP generator also sends ${p_0=H^N(S)}$ and s to the server and discards everything from its memory.
The server keeps last 64 bit one-time-password p , a sequence integer i, which is first set to 1, and also keeps s in memory with integritiy protection.

To simplify,See below image, here server generates till N+1 hash values.

Server generates ${H(x), H^2(x),…,H^n(x),H^{n+1}(x)}$, and stores only ${H^{n+1}(x)}$

The User is given ${H^n(x),…,H^2(x),H(x)}$, one at every requeest to server.
Now when user sends ${H^n(x)}$ , server checks creating ${H^{n+1}(x)}$ and matches with stored ${H^{n+1}(x)}$, and server updates stored value to ${H^n(x)}$ , next time user sends ${H^{n-1}(x)}$ and same procedure repeats.
Attacker can compromise Hash but user goes from right to left, so attacker can generate new Hash but can’t create old Hash.
Problem Here is after n one time password, sever-client has to try setup new password.
Vernam Cipher
It is a one time pad cipher, Here key and message of n bit length are XORed, and, number of messages are number of keys, say i, and probability of using any key with a message is ${1/2^i}$. Hence, only one unique key is associated from key space to unique message,  That is why it is called One Time Pad cipher.


Why does the modulus of Diffie–Hellman need to be a prime? I read a lot about Diffie-Hellman, but there is one thing I dont understand: why does the modulus p need to be a prime? What if it would not be a prime?

Answer to Martin's and Vadim's comments:

Let $n:=p$ and you want to find $x$ with $g^{x} \equiv y \bmod pq$

Calculate the two easier DL problems:
 ${x_p}$ with $g^{x_p} \equiv y \bmod p$
 ${x_q}$ with $g^{x_q} \equiv y \bmod q$

Note that
$x_p \equiv x \bmod p-1$
$x_q \equiv x \bmod q-1$

With the chinese remainder theorem you can calculate $x'$ from $x_p$ and $x_q$ with
$x' \equiv x \bmod lcm(p-1, q-1)$

It does not need to be a prime. All that's required for the ciphering scheme to work for a (g, p) pair is that g is a generating element for the cyclic multiplicative group defined by p.

The opposition to using non-prime p usually based on the fact that knowing factorization of p makes the cipher easier to break by solving "easier" problems for each of its factors. However, this is nothing more than a logical fallacy. If the problem is hard to solve for a prime p, it will be as hard (or harder) to solve for any composite number that has p as a factor.


Public key encryption I am not getting whole idea behind Public Key Encryption technique.

As according to fact, public key encryption method uses two keys a public key known to everyone private key known only to recipient of the message

For an instance let assume, John wants to send a secure message to Jane, He uses Jane's public key to encrypt the message. Jane then uses her private key to decrypt it.

The thing i am not getting is, as far as i know if we want to encrypt any message using a key, from that same key only we can decrypt that particular message.

But in public key encryption case both keys are different than how it is possible to decrypt the message.

Please clarify my issue and guide me through if i am going anywhere wrong in understanding the whole concept

Here is a great video which shows principles for public key cryptography using colors, which makes it easy to understand for everyone:
https://www.youtube.com/watch?v=YEBfamv-_do

Now what you missed is that it is possible to generate a secret key, and give away something which enables encryption but not decryption. This is the principle of public key encryption.


How secure is it to use password as AES key? I am developing a steganography app where user encrypt any file into an audio file. The user can enter a password to protect the hidden data. The same password is converted as a 256 bit key and the hidden data is encrypted using AES. I was wondering, how secure is using password as the AES key?

Passwords are commonly used for both authentication and encryption. Sometimes this is done securely. "Commonly" is an interesting word here, because passwords are commonly turned into encryption keys in ways that do not follow good security practices, and also passwords commonly do not have enough entropy to be suitable for generating encryption keys.

Generally the term "x is only as good as y" would apply to encryption keys and passwords, such as "key is only as good as password", but the method used to convert the password into the key is more important for the majority of password choices. If you were using a long string of random characters, even MD5 could be acceptable... but you probably are using a shorter password built from real words and phrases. Let me be clear that MD5 is not acceptable to convert passwords into keys.

A 'Password Based Key Derivation Function' (PBKDF) is what is needed to convert your password into a suitable encryption key. There is debate over the specific features and properties a PBKDF should have, but its purpose is to compensate for the poor entropy of commonly chosen passwords, among other things, such as properties of the cryptographic primitives that PBKDFs are built from.

Cryptographic hash functions and block ciphers are commonly used to build PBKDFs, and they do an excellent job, but they are extremely fast and use minimal resources such as memory and cpu cores, which can be a profound advantage to an attacker. Thus a PBKDF is mainly used to slow it down, usually by iterating the primitive thousands or even millions of times. More modern PBKDFs also consume larger amounts of memory, and some may only operate quickly (for verification) by using multiple cores. A 'salt' is used as an input to the PBKDF to prevent the same password from generating the same key unintentionally when used in different situations or by different users. The salt is stored where the password would be processed in order to get the correct key.

Best practice is to use a PBKDF to generate a 'key encryption key' (KEK), then a full entropy random key is used to encrypt the data, and the KEK is used to encrypt that key. That way a password change does not require reencryption of all the data, just the key. The KEK is never stored, only used to encrypt and decrypt the data key. The encrypted data key and PBKDF salt are stored with the encrypted data.

You may not have control over the password a user enters, but you do have control over how it is processed into a key, and you may be able to make recommendations to your users as to good password choices. Attacks only get better, passwords should be as long as possible while still being memorable. Estimating password entropy is difficult, so the PBKDF is extremely important to preventing it from being cracked. If you can accurately estimate entropy you may be able to warn a user that their password may be insufficient.

You should be very open with your users about how you convert their password into a key, it is "common" for secrecy of the method to be associated with extremely bad security practices, and more and more people are starting to realize it (due to an ongoing string of hacks and stolen password databases with lots of press coverage). Additionally, if an individual that understands cryptography can be confident in the security it provides, they may be inclined to recommend the product. I certainly would be.

Note that security is only as strong as the weakest link. If you are using an excellent PBKDF but have poor programming leaking key material into virtual memory, the product is not secure. Do not rely on good cryptographic components to do the work of security for you, it is more complex and difficult than that. It is an entire system. Sorry for the long answer.

I hope you hash your password with something secure like sha-256 the way recommended by sp800-132 section 5.3 http://csrc.nist.gov/publications/nistpubs/800-132/nist-sp800-132.pdf. in that case, brute-force attacks on hash collisions are unlikely to succeed.

Your design has the security of the password ..... "", "abc123". "azerty". "123456789" are the most common passwords and the first guess of the tools based on dictionary attacks. Rainbow dictionary attacks are well explained in http://en.wikipedia.org/wiki/Dictionary_attack#Pre-computed_dictionary_attack.2FRainbow_table_attack are based on precomputed databases of password hashes as the key.

"Pre-computed dictionary attacks, or "rainbow table attacks", can be thwarted by the use of salt, a technique that forces the hash dictionary to be recomputed for each password sought, making precomputation infeasible provided the number of possible salt values is large enough"

Then you can increase the security of your app by enforcing stronger longer passwords, like the mandatory use of all of lowercase, uppercase and digits, avoid repeated letters and allow non alphanumeric characters, and forbid passwords less than xx bytes. See section 3.2 of http://csrc.nist.gov/publications/drafts/800-118/draft-sp800-118.pdf about strength.


Encrypting or HMACing password digests Assuming I'm using bcrypt to digest passwords, is any additional security gained by either encrypting or HMACing the resulting digests? By requiring a key to compare password hashes, I would expect that this would prevent any attempt at brute forcing sans the key.

The keys for this operation are actually stored somewhere other than our application servers, and all cryptographic operations are performed there via API calls. The service is designed to never divulge keys themselves, and only operate on keys by an opaque ID. So it should be considered somewhat less likely that our keys would be compromised in an attack than in typical webapp scenarios. Keys are also unique per customer of our application.

I would normally only consider HMAC for this operation, but this would require extracting (and storing separately) the salt from the bcrypt digest. So simply encrypting the crypt digests seems to be the simplest approach, and intuitively should produce the same desired security properties.

Is this approach reasonable and sane? We already have the cryptography infrastructure in place, so it's not considerably more difficult to encrypt/HMAC our hashes than it is to compute them in the first place. Is there a reason to prefer an HMAC over AES-128-GCM?

Either is safe, but I would prefer encryption for two reasons:

As noted in the comments, you can change the key without needing to know the original password.
Encryption doesn't add to collisions, while HMAC can. The probability is tiny, but it adds to the probability that the password hash caused a collision. Not worth worrying about, but since it's avoidable...

On the other hand, HMAC does have one advantage: no IV, so no extra space. (GCM even adds an authentication tag.) If you can use something like a user ID as a counter, even that advantage could be lost. If not, that could be important in some cases.

HMAC and AES-128-GCM are similar in the sens that both are symetric primitives (i.e. there are more or less the same key management issues) and both require to store extra data (salt vs. authentication tag).

An issue with encryption is that in case a poor padding scheme is used (i.e. no random) we may face to several collisions in the encrypted password table and an attacker (having the table of encrypted passwords) might perform a statical analysis to spot common passwords (e.g. 123456) and guess some of them.


Is a PRF applied to a secure MAC also a secure MAC? Suppose I apply a PRF to a secure MAC.  Do I still have a secure MAC?

Yes.

A secure PRF is a secure MAC. A secure MAC of a secure MAC is a secure MAC. Therefore, applying a PRF to a MAC still gives you a MAC.

Depending on the length of the inner MAC and the PRF you may lose security bits, but if they are long enough it works.

Assuming you're asking if PRF(MAC) can be used as MAC (message authentication code)? Depends on the PRF. MAC is de-factor PRF too with several properties in mind (collision resistance, pre-image resistance, avalanche effect, non-linearity...).

Until your PRF keeps these properties, you should be ok. The basic idea is you should not weak the strength (length) of the MAC.


What are "encrypted instruction sets"? In 1999, a news article (Careless mistake reveals subversion of Windows by NSA) discussed "encrypted instruction sets". What exactly are these? Please provide a link so I can find more information.

Does it have anything to do with the following:

A First Practical Fully Homomorphic Crypto-Processor Design

Next-Generation Secure Computing Base

A similar question was asked here some time back (What are 'Encrypted Instruction Sets' ?), but it did not garner any useful responses.

I am already aware of hardware-based encryption & Intel's native support for AES. This one seems very different from the others.

i guess that encrypted instruction set is an encrypted instruction commands for cpu that will only work for encrypted programs.you can steal the program but can't execute it on your normal computer,or you can't hack to that computer because that computer can't run normal standard program unless it switch to normal instruction or translate the program.


Brute forcing the secret key in Elgamal encryption Crypto noob here, I am attempting to do this programming challenge. I do not have the secret key that is used to decrypt the message. However, the key is small enough for a brute force approach. I am attempting to write a function that will solve for the secret key with other variables used in the process.

  She tells Bob values of $p$ and $pe \equiv p^e \pmod{n}$ (p raised to power of e mod n)
  as her public key. Meanwhile the value e remains her secret key (there
  is no easy way to calculate it from $p$ and $p^e$).

I have $pe$, $p$, and $n$. Here is some code written in java.

static int findE(int n, int p, int pe) {
    for(int e = 0; e < n; e++) {
        if(modular_pow(p, e, n) == pe)
            return e;
    }
    return -1;
}

static int modular_pow(int base, int exponent, int modulus) {
    int c = 1;

    for(int i = 0; i < exponent; i++) {
        c = (c * base) % modulus;
    }
    return c;
}

I calculate $p^e \pmod{n}$ for all possible values, but my "findE" function always returns -1. I have tested my modular_pow function and am certain that is not the problem. Maybe I am misunderstanding the instructions. Thanks for any help!

Given $p$ and $p_e \equiv p^e \pmod{n}$. You need to calculate $p_e$. Propose $e$ is small enough to brute-force. The simplest way would be to calcute $p^e \pmod{n}$ for values $e \in \{1,2, ..., n-1\}$ until you find $p_e$.

So all you need would be something like this:

static int findE(int n, int p, int pe) {
    int base = p;
    for(int e = 2; e < n; e++) { // also it suffices to start at e=2
        p = p * base % n;
        if (p == pe) return e;
    }
    return -1;
}

Even though you are doing to much calculation (for every value of $e$ you recalculate all values of $p^{e-1}$), right now i do not see why your code would'nt work.
Update: forget all i said about modular exponentation, that was bullsh*t.


Let $N=p\,q$ be an RSA modulus such that $p>N^\beta$ and $\displaystyle p=\sum_{i=0}^k a_i\,x^i$ such that $\max(a_i)<N^\delta$ and

  $$\delta <\frac{1}{k+1}\bigl(1-(1-\beta)^\frac{k+1}{k}-(k+1)(1-(1-\beta)^\frac{1}{k})(1-\beta)\bigr).$$

Then one can factor $N$ in polynomial time (see here).

In your question $a\ne b$. Let $b=a+c$. So

  $$p=2a^2+2ca+c^2,\ q=2a^2+2c+1.$$

In this case ($q>N^{0.499}$, $k=2$)  we have $a_0=2c+1, a_1=0$ and $a_2=2$ which means that if $2c+1<N^\delta$ then we can factor $N$ in polynomial time.

though this is a brute force
https://crypto.stackexchange.com/a/60190/59847

or we can start from $p =\sqrt{n}$ up.


What are the requirements from a Round function in Feistel network? Let's assume a balanced network with many (dozens?) rounds. And a simple (selecting key bits) key schedule.
What does it take from the round F function to make a secure block cipher? obviously we need non linearity and some avalanche. But is this sufficient, how can this still fail?
Does a high round count compensate for any mild weaknesses in the F function?

What does it take from the round F function to make a secure block cipher?

The ability of providing resistance to most common attacks like differential, linear, algebraic, slide and others mainly depend on the features of S-box (if used). * Simon does not use an S-box.
To design F-function, it depends on the structure of your Feistel
cipher Type I, II, III and others (which differ in term of number of
branches, number of F-function, internal structure of F-function).
The size of plaintext (64,128) could also influence the size of box
(4-bit or 8-bit), like piccolo vs Clefia. Therefore, the differential probability, linear probability and algebraic immunity differ, 8-bit S-box provide higher immunity features, therefore lower number of active S-boxes needed to provide minimum immunity, hence lower number of rounds.
The internal structure of F-functions such as SP vs SPS influences
diffusion (in term of number active-box). In addition, the use of
different MDS matrices in r-rounds (multiple round diffusion or
diffusion switching mechanism (DSM)) provide higher diffusion compared
to using 1 MDS matrix. CLEFIA employs DSM.
On the other hand, 8-bit s-boxes such as those in AES are expensive in term of
masking against side channel attacks. One way is to use smaller
s-boxes (easy to mask) to build larger s-boxes or using 4 bit S-box.

Does a high round count compensate for any mild weaknesses in the F function?

I don't think if you have self-similarity F-function, it will be
vulnerable to slide attack, increasing the number of rounds will not
providing compensate for weakness. To solve the self-similarity of F-rounds it is recommended to add constants. For how to chose round constants for simple key scheduling, I recommend to read

  Proving Resistance against Invariant Attacks: How to Choose the Round Constants

There are others structures of internal F-function (not only SP, SPS) such as ARX (e.g. the Simon cipher) that have been design in a triangle of security, performance and size, and resistance to both mathematical and implementation attacks (such as timing, DPA).

Does a high round count compensate for any mild weaknesses in the F function?

This may be the case, and this is (perhaps) tangential evidence.  A Feistel network forms a block cipher with a number of rounds, often using a simple compressive (F) function. Whilst not a Feistel network, the Threefish block cipher is part of the Skein family of hash functions, and is associated with this quote from it's design paper:-

"The core design principle of Threefish is that a larger number of simple rounds is more secure than fewer complex rounds. "

I include this quote as it specifically relates to increased round count.
 Threefish's compressive MIX function has geometric similarities with an F function.  It would not be a huge leap to assume that the principle of additional rounds providing additional security holds. It is certainly not evidence to the contrary, and I can't recall any professional construct that is safer when shorter.

Plus, the Wikipedia article on Fiestel networks seems to suggest that you're correct. Whilst additional rounds make not immunise a network from all possible attacks, it seems like common sense that more rounds generally increase the overall security when all other things are equal. It must at least increase diffusion if nothing else.


An unbreakable book cipher? In a recent press interview, a former terrorist of the 1970s described the cipher his group used to communicate. He claimed that method was unbreakable and I wonder if cryptographers today would agree. Here is how it functionned:

Take two identical books (same edition): one for the sender, one for the recipient.
Each sign - one could include spaces between words as signs - is encoded as follows:

  (page number) (line number) (number of character on the line) (random
  number)

additions, subtractions, multiplications or divisions of certain agreed value in a certain order are then applied. For example, 357 could mean:

  (page number*3) (line number -5) (character number +7)

This means that negative values can be created, especially if the
substraction value is in the double digits

A software script for such a cipher would be I think relatively easy to design. Also, the agreed values of the operations in step 2 can be changed anytime so the same base text can be reused.

Bottom line, it means for example a single 7-letter word would produce a string of 28 numbers, of various lenghts and some negative values or decimals or fractions perhaps - depending on what values are used for the operations.

what is your opinion on this method?

Book ciphers are well understood and this seems like a fairly minor variation. Following Kerchoff's Principle we separate the key being the book and the arithmetic operator and numbers and the rest. Picking a random number for fourth position makes no difference in this regard. But even if we let that be a secret to it makes little difference. Humans are lousy at picking random numbers and this will be apparent.

Multuplying by a constant is also a really bad idea. It will be very quickly apparent all numbers in a certain position are a multiple of constant and will be devided by it.

Subtracting or adding a number from row or character number will also be apparent after collecting sufficient data by observing the skewed range. such an addition will be slightly harder regarding page number due to higher cardinality of page numbers but won't necessarily be an issue see next.

Humans doing a poor job picking random numbers. Many people who use book ciphers flip forward a bit from where they are or start reading from the start of the page. This means rare letters will require on average more skipping forward leading to some leakage.

Also the book itself may be selected from a limited set of books can make the book itself guessable.  Given a large library of online books brute forcing such a cipher isn't all that difficult.

If you do not want to mark the book making it physically obvious it is a cipher key it is difficult to prevent repetitions when randomly selecting characters.

If the book is considered a secret not chosen from a limited selection available at your local book store for instance and the person using it picks a random starting point in the book for each letter and seeks the next matching one and marks off each used letter to prevent duplicates then it is a fairly secure cipher even without the additions described.

In reality most book ciphers have been and will be broken.

Whenever I read the critique of book ciphers I usually wince at the claim that all of the available texts of the world are available to the NSA or other serious people and hence the obscurity of the text is no longer a defence. On the other hand there is nothing to stop 2 communicators from saving 10,000 pages from 10000 random websites in a single snapshot.
And then randomly ordering those 10,000 pages into nothing resembling their sources.
The original web sources will deviate from the saved text over time as well and good luck with finding them on the internet wayback machine which doesn't save deeper pages.
Provided each character was eliminated at each use, I see no reason why this can't be as practically secure as a OTP.
Even better, if the sites chosen change content quickly then there is no reason that the same selection of sites could not be vacuumed again, randomised again (with the same agreed method) and used again. This way there would be an endless source of random characters.


Inversive Congruential Generator The inversive congruential generator over the prime field $k=Z/pZ$ is given by the iterations of the map $x\mapsto a/x+b$ if $x\neq 0$ or $b$ if $x=0$.
One can choose $a,b$ in $k$ such that the orbit length of the iteration is exactly $p$. My question is very simple:

Is the Inversive Congruential Generator actually used in Cryptography? Is there any known attack against it?

The inversive congruential generator is not commonly used in cryptography. Its basic description, in fact, makes it entirely unsuitable for it—once you know a single value of $x$, you can predict the remainder of the sequence, which is something a secure pseudorandom generator should not allow.

To avoid the above trivial attack, you could truncate the output to, say, half of the bits of $x$. But the truncated inversive generator is also predictable by more elaborate means, as long as you truncate fewer than half the bits.

To top it off, inversion modulo $p$ is a very slow operation, which makes this generator very inefficient. So even for non-cryptographic purposes this is not a good generator to use.

There are some inconsistencies with the arguments in the above answer.

You want to compare ICG with a cryptographically secure pseudorandom number generator.

Consider the cryptographically secure Blum Blum Shub (it should be one of the best, according to the abstract of this paper for example: https://pdfs.semanticscholar.org/8074/d7df08e2bcbe8f433ec368a5d84c8061f9be.pdf )

The pseudorandom number generator is simply given by $x_n= x_{n-1}^2$ modulo $M=pq$ that is the product of two large primes: see https://en.wikipedia.org/wiki/Blum_Blum_Shub for a quick introduction.

Observing even one iteration $x_n$ results in knowing exactly all the other terms of the sequence. The whole point is that only the "least significant bits" (notice: not "the most significant bits", in contrast with the setting of the attack mentioned in Samuel's answer) are sent or even only the bit parity of the element in the sequence (see again https://en.wikipedia.org/wiki/Blum_Blum_Shub for a reference)

Notice that this strategy of sending only the bit parity of $x_n$ is directly applicable to the Inversive Congruential Generator (ICG) and then the problem of predicting the sequence looks immediately untreatable (of course, if $a,b$ are hidden).

Concerning the computational cost: the ICG costs essentially one inversion mod p (notice that if in the definition of the ICG one chooses $a,b$ "very small", the multiplication of $a$ and $1/x$ can be counted as an addition).
On the other hand, Blum Blum Shub costs one multiplication. The ratio of the cost of  an inversion and a multiplication is only $O(log log log(p))$, which make the two generators very similar from a computational point of view.

On the other hand, ICG has the advantage of covering the entire space $\mathbb F_p$ is $a,b$ are suitably chosen.

That is never possible for the Blum Blum Shub generator: modulo $M=pq$, you will never get an element multiple of $p$ and also even the multiplicative group $(\mathbb Z/pqZ)^*$ (meaning the invertible elements modulo $pq$) is never cyclic for odd $p,q$.


Store hashed password using Digest authentication Digest Authentication is something like this:

Server sends client a nonce.
Client hashes username and password with nonce.
Client sends hashed value back to server.
Server validates hash.

However, it seems like this requires the server to have access to the password plaintext, otherwise it wouldn't be possible to verify each hash with unique nonce values.

Is there some way to follow this authentication protocol without requiring the server to have access to password plaintexts?

The server doesn't need the plaintext.  When the password was "saved" the server generated a nonce and concatenated that with the password and then hashed the combination.  The server saves the nonce and the hash, not the password.  Now, when client sends the hashed value to the server all the server does is compare that it against the saved value.


Share two secrets between two parties Alice has a secret A, Bob has a secret B. They have a secure channel and a MAC. They each want to know the other's secret, but don't particularly want to give up their own. However, neither will not lie about the secret, but if possible, will stop communications once [s]he learns the other's secret.

How can such a protocol work, that if Alice or Bob doesn't correctly follow all steps in the protocol, neither person can gain any information about the other's secret.

You may not use a third party.

M.O.Rabin answered the question in 1981, named it oblivious transfer.


Can we construct fully homomorphic encryption scheme based on non-circuit approach? At present, all FHE scheme are be constructed based on circuit approach. Can we construct fully homomorphic encryption scheme based on non-circuit approach?  Is Polly cracker non-circuit approach ?

Is Polly cracker non-circuit approach?

Polly Cracker is non-circuit.

  Can we construct fully homomorphic encryption scheme based on non-circuit approach?

The best info for this I could find comes from a recent paper proposing a non-circuit approach due to Xiao, et al..

They identify a number of non-circuit systems, but go on to say that "they all either have been broken or lack conclusive security evidence."

They then propose a symmetric system which reduces to the problem of factoring.

So it seems that the answer is yes, one can be constructed. It is still an active area of research, however, and I personally wouldn't use the proposed systems yet.

Now, what I am exactly not quite sure of is what non-circuit means? In the paper I reference, they state:

  The main works on homomorphic encryption algorithms are circuit based. They develop the encryption schemes and computation algorithms considering a single bit plaintext. All operations on various operand types can then be achieved by constructing the corresponding circuits.

So is a circuit approach simply that the cryto algorithms assume a single bit plaintext? If that is the case, then there are many, many more FHE systems which are "non-circuit". In fact, the BGV system does not require single bit plaintexts. So perhaps I am missing something in the circuit vs non-circuit discussion.

Yes There was recently a breakthrough FHE and it used p-adic ring homomorphism. the paper was published on nov 10 2012. and the algorithm is LITERALLY quasi-linear time without any "lambda" factor in the keys and NO noise in the ciphertext. it seems to be a very big breakthorugh and i don't know why no one has paid attention yet but me :P . here is a link to that paper, its VERY mind boggling and amazing. If you dont know p-adic numebrs, then take a look at the abstract and conclusion; and if the algorithm really works as claimed then it will throw IBM and Microsoft decades behind. here is the link http://www.ijtpc.org/volume1/JTPC1386.pdf
I hope you enjoy reading about this breakthrough. btw, the homomorphic part of the encryption "LITERALLY" goes like for addition E(m1)*E(m2) = E(m1+m2) and multiplication is like
E(m1)^m2 = E(m1*m2) ; Algorithm says it used p-adic ring exp to obtain this effect. Its way different and much advanced than Gentry's scheme.


Is cryptography an interesting field for research? I am now styding for first year bachelor's degree in Mathematics for IT. In the future I would like to major in the same field and possibly continue trying to get a Ph.D. But I still have options to take a different path.

Even though I have a long journey ahead, I am thinking about trying to write a "scientific bachelor's thesis" (that's how we call bachelor's thesis with scientific results on my university in my language) when the time comes.

Is cryptography a field with interesting and imporant problems to solve? I know about some interesting problems like P=NP and some stuff about (post-)quantum cryptography, but surely that's not what majority of problems are like.

So, is cryptography a field where it is easy to find meaningful and interesting problems to solve?

(I am not sure if this is the right place to ask this, so please inform me if I should ask somewhere else.)

Cryptography is a nice field in which not only problems to solve are a-plenty, but it is also one of these fields where individuals can make significant discoveries in a relatively short time. A PhD student in cryptography will typically write three or four articles during his thesis; by comparison, a "pure mathematics" PhD student will generally produce a single article in the same time. Informally, to make new advances, you have to first learn the existing science; in cryptography, this means getting up to date with about 40 years of research. In mathematics, that's closer to 200 years, hence the comparatively higher effort to reach the "publishable" state.

Moreover, cryptography is an applied field, by which I mean that it has immediate practical applications. This means money: you can make a very nice living out of cryptographic expertise. A PhD is a very good key to unlock such things (I have a PhD and I am a consultant in cryptography, and my experience is that both facts are related). Intellectual fulfilment is of primordial importance to a balanced life, and money does not make happiness; but money is still some super useful stuff, and being able to live out of doing intellectually rewarding things is a nice combination to achieve.

In any case, mathematics are always useful for anything related to computers. A lot of computer users and developers can get along with a very low understanding of the underlying principles, but the maths are what explains why computers work that way. Mathematics allow to look beyond the magic.

Drop the maths.  There is no maths in IT and no useful maths at all in general unless you do investment banking.  Despite what teachers tell you (they're lying) qualifications are not required in IT, only experience and ability. Absolutely do not do a PhD (makes you unemployable) unless you intend to work in Germany.   You can easily prove the truth of what I say by spending some time on the main site (stackoverflow /jobs).  Learn Java + Javascript and get experience.  If you can't get experience but know what you're doing, just lie on your CV.  That's how winners get ahead.

As to cryptography, it's likely that it will stagnate /die out as quantum key distribution matures.  As soon as it's exchange rate is improved to the point of transmitting raw data rather than only keys, only one time pads will be required.  Even children can use a one time pad.  And it's resistant to quantum computation.  At that point, encryption will become the domain of physicists and engineers.  It's understandable to want to protect your rice bowl, but remember that the Luddites and coal miners were swept away.  I generalise (somewhat) but I hope that you get the idea.

I guess that it might remain for disc encryption /ATM cards, or other scenarios where fibre optics aren't natively used.  But there'll be nothing remaining to get a decent high salary over.  Overly pessimistic?  Daft?  Ask a black or yellow cab driver.  Just sayin'.


Efficient AES - Use of T-tables I'm really in trouble! I'm trying to understand how the T-tables in AES encryption work. But I don't know if I get the point.
What I understood is that they are used to reduce the whole computation of the iteration of AES just looking at the T-boxes and the XOR operation.
Now, what I got is that:

    State                 M Matrix
┏             ┓       ┏             ┓
┃ d4 e0 b8 1e ┃       ┃ 02 03 01 01 ┃
┃ bf b4 41 27 ┃       ┃ 01 02 03 01 ┃
┃ 5d 52 11 98 ┃       ┃ 01 01 02 03 ┃
┃ 30 ae f1 e5 ┃       ┃ 03 01 01 02 ┃
┗             ┛       ┗             ┛

I have my State matrix and M matrix composed by 4X4 bytes. Each t-table should receive in input one byte and give in output 4 bytes.
Now, in order to create the t-tables i will have in the first table:

T0=(d4*02)+(d4*01)+(d4*01)+(d4*03)
   (e0*02)+(e0*01)+(e0*01)+(e0*03)
   (b8*02)+(b8*01)+(b8*01)+(b8*03)
   (1e*02)+(1e*01)+(1e*01)+(1e*03)

Then the second table should be:

T0=(bf*03)+(bf*02)+(bf*01)+(bf*01)
   (b4*03)+(b4*02)+(b4*01)+(b4*01)
   (41*03)+(41*02)+(41*01)+(41*01)
   (27*03)+(27*02)+(27*01)+(27*01)

And so on...until I'll have 4 tables. Am I right? Now...How can I use these tables?

(You should take a look at page 18 of FIPS 197 where it describes the MixColumns transform).

You're close. Swap the order of your matrices so that you have:

|02 03 01 01| |d4 e0 b8 1e|
|01 02 03 01| |bf b4 41 27|
|01 01 02 03| |5d 52 11 98|
|03 01 01 02| |30 ae f1 e5|

And then you compute the new columns. i.e. the new first column is:

|02 03 01 01| |d4|
|01 02 03 01| |bf|
|01 01 02 03| |5d|
|03 01 01 02| |30|

Which equals:

|02*d4 + 03*bf + 01*5d + 01*30|
|01*d4 + 02*bf + 03*5d + 01*30|
|01*d4 + 01*bf + 02*5d + 03*30|
|03*d4 + 01*bf + 01*5d + 02*30|

And so on.

Do you See the pattern in the sum? Each column in the matrix is multiplied by an element in the column and then they are summed. We can precompute these columns, and compute the above sum using 4 table lookups and 32-bit XOR operations.

The tables will be arrays of 32-bit values which look like this ("|" denotes byte concatenation):

T0[00] = 02*00 | 01*00 | 01*00 | 03*00
T0[01] = 02*01 | 01*01 | 01*01 | 03*00
...
T0[FF] = 02*FF | 01*FF | 01*FF | 03*FF

T1[00] = 03*00 | 02*00 | 01*00 | 01*00
T1[01] = 03*01 | 02*01 | 01*01 | 01*01
...
T1[FF] = 03*FF | 02*FF | 01*FF | 01*FF

T2[00] = 01*00 | 03*00 | 02*00 | 01*00
T2[01] = 01*01 | 03*00 | 02*00 | 01*00
...
T2[FF] = 01*FF | 03*FF | 02*FF | 01*FF

T3[00] = 01*00 | 01*00 | 03*00 | 02*00
T3[01] = 01*01 | 01*01 | 03*01 | 02*01
...
T3[FF] = 01*FF | 01*FF | 03*FF | 02*FF

Using four tables, you can compute the new state matrix with 16 table look-ups and 12 32-bit XOR operations.

You can use one table instead of four tables, as the 2nd table is the first rotated by one byte and so on.


Montgomery Reduction I'm taking a hardware cryptography class and working on a problem that focuses on Montgomery Reduction.

So by definition:
Computing $a * b \text{ mod } N$

Pick $R$, s.t. $R > N$, $gcd(R,N) = 1$
Compute $N^{-1} \text{ mod }R$
$a’ = a * R \text{ mod } N$
$b’ = b * R \text{ mod } N$
$c’ = (a’ * b’) * R^{-1} \text{ mod } N$
$c = c’* R^{-1} \text{ mod } N$

Claim: $c ≡ a * b \text{ mod } N$

Proof: $c’R^{-1} ≡ (a’b’)R^{-1} R^{-1} ≡ (a’ * R^{-1}) * (b’ * R^{-1}) ≡ a * b \text{ mod } N$

If $R=2^k, x * R, ÷ R, \text{ mod } R$ are trivial an option to implement modular exponentiation.

Now I am ask to solve for this given the following 25 modulo 109 w.r.t. 128. The question I have is since I only have $a= 25$, does this mean there is no $b$ value?  And if that is the case, I can ignore calculating the $b’ = b * R \text{ mod } N$ expression and also remove it from calculating the $c$ equation?

Consult the transcript from the class, there is an example he works through which is very similar to this problem. Fundamentally you're trying to solve the problem c = (T + T(-N^-1) (mod R)N)/R (mod N). I suggest creating an equation in Excel (or other tool of your choice). Test your equation using the inputs from the example problem (EXAMPLE INPUTS: T=69, N=109, R=128, -N^-1 = 27). When you're confident your equation is working for that (EXAMPLE PROBLEM SOLUTION = 61), then plug in the values for this problem. Hint: T = 25 for this problem.

Answer is 30:
$$T=25, N=109, -(N)^{-1} = 27, R=128$$
$$\Rightarrow T(R^{-1}) \bmod N$$
$$\Rightarrow m=T*(-N)^{-1} \bmod R \Rightarrow m= 25*27 \bmod 128 \Rightarrow m=35$$
$$\Rightarrow t= (T+m \cdot N)/R \Rightarrow (25+(35*109))/128 \Rightarrow t=30$$


Where can I find a description of the SHA-0 hash algorithm? Where can I find the description and or pseudocode for the SHA-0 hash algorithm? I am looking for something on these lines: HMAC RIPEMD.

I have been implementing a few of those (HMAC, HOTP, TOTP and MD4, MD5, RIPEMD-128,160)

The reference on SHA(-0) is FIPS 180 (archived scan) of 1993 May 11. The standard itself is referenced on the NIST website, but that links to another scan lacking page 1 and the one before, thus foreword, abstract, explanation... There's also this text draft of 1992 January 22 (also here with less indication on origin).

The Proposal for Change of that into SHA-1 was published on 1994 July 11 and is online at the Federal Register with partially garbled text, including for the security-critical change:

  In Section 7 of [1] (page 9), the line which reads
      (b) For t=16 to 79 let Wt = Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16.
  is to be replaced by
      (b) For t=16 to 79 let Wt = S1(Wt-3 XOR Wt-8 XOR Wt-14 XOR Wt-16).
  where S1 is a left circular shift by one bit as defined in Section
  3 of [1] (page 6), namely S1(X) = (X << 1) v (X >> 31).

Note: What's kept of the original PfC has messed-up sub/superscripts (a modern web artifact), and misses the closing parenthesis on the modified expression for Wt (possibly an omission in the original).
This is was a technical change in the design, critical for improved security, rather than a correction of a typographical error as could be understood by casual reading of the PfC. This change was introduced without rationale, and initially without ensuing changes in the test vectors. It is thus reasonable to suspect that it was intentionally sneaked quietly, with knowledge that the original was not as secure as intended against educated collision attacks.

The revised document is FIPS 180-1 of 1995 April 17, referenced on the NIST website (with a link to an external scan of the actual document).

Changing source code for SHA-1 into one for SHA(-0) is easy: just remove the one-bit rotations of a 32-bit word of the 512-bit message block. For example, in the reference implementation of RFC 6234, change

W[t] = SHA1_ROTL(1, W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);

to

W[t] =          (   W[t-3] ^ W[t-8] ^ W[t-14] ^ W[t-16]);

You can try this - https://github.com/tyage/sha0/blob/master/lib/sha0.rb I don't know how good or accurate it is.