Why does RSA need p and q to be prime numbers? Despite having read What makes RSA secure by using prime numbers?, I seek clarification because I am still struggling to really grasp the underlying concepts of RSA.
Specifically,  why can't we choose a non-prime $p$ and $q$?
I do understand the key concept: multiplying two integers, even two very large integers is relatively simple. However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.
If this is correct, then the original question posed by the OP in this thread continues to befuddle me.
This section from Henrick's answer in this post contains the relevant information:

It also means that if you were to select $p$, $q$ just as odd integers, you
would make it harder for yourself to find $\phi(n)$, while at the same time
decreasing the relative size of the second-largest prime factor, and
thereby making it easier for everyone else to factor n. In fact, it
would be as hard for you to factor n as it would be for everyone else,
so you would completely lose the trapdoor component of your scheme
(if not making it completely infeasible to find a pair $e$, $d$).

But I do not understand why we make it harder for ourselves to find $\phi(n)$. I BELIEVE that it has to do with the fact that for any prime, $n$, all integers up to $n-1$ are relatively prime. If the integer is not prime, then we actually need to find which integers up to n are actually relatively prime.
I understand how we are decreasing the relative size of the 2nd largest prime. For example: $10403$ has prime factors of $[101,103]$ while $11000$ has prime factors of $[2, 2, 2, 5, 5, 5, 11]$.
So, if I understand things correctly, choosing a non-prime $p$ and a non-prime $q$ would theoretically work, but the issue is that we would be creating a more insecure encryption scheme since:

the product of non-prime $p$ and non-prime $q$ are more easily factored (2nd largest prime is smaller than if $p$ and $q$ were prime);
finding $\phi(n)$ becomes more difficult for the key generator step, which decreases efficiency with the aforementioned decrease in security

Sorry if this is completely obvious, but I am a newbie in higher math and programming. I really want to understand this as deeply as I can.

However, factoring a large integer is extremely difficult, even for a computer using known factoring algorithms.

Not categorically. Factoring a large integer is trivial if it is only composed of small factors.

A fairly naive algorithm for factoring N is the following:

while N > 1:
  for p in increasing_primes:
    while p divides N:
      N = N / p
      factors.add(p)

With this algorithm, $340$ $282$ $366$ $920$ $938$ $463$ $463$ $374$ $607$ $431$ $768$ $211$ $456$ can be factored in exactly $128$ iterations of the innermost while. (The number, of course, is $2^{128}$)

The more prime factors a composite number has, the smaller those factors have to be. For example, $919 \cdot 677 = 622$ $163$. With the naive algorithm, this takes $157 + 1 = 158$ iterations to factor. A number of roughly the same size comprised of three factors, $73 \cdot 89 \cdot 97 = 630$ $209$, only takes $25 + 2 = 27$ iterations to factor.

Similarly, a 1000-digit number composed of two roughly equally-sized factors will take about $10^{497}$ iterations to factor. A 1000-digit number composed of 100 roughly equally-sized factors will take about $434$ $294$ $481 + 99 \approx 10^{9}$ iterations. And a 1000-digit number composed of 1000 roughly equally-sized factors will take about $4 + 999 \approx 10^{3}$ iterations.

So, to make factoring as difficult as possible, you want the prime factors to be as large as possible, which means you want N to have the fewest factors possible. With $p$ and $q$ prime, $N$ has two factors. With $p$ and $q$ composite, $N$ has at least four factors, possibly more.

Note that this is far from a complete answer on why (we think) RSA is secure, but I hope it gives a more intuitive / example-based idea of why $p$ and $q$ should be primes.

Note also that $p$ and $q$ should be similar in magnitude. If one is much larger than the other, factorization becomes easier. For example, if $p = 43$, the naive algorithm would only take $14$ iterations.

(After reading the comments (thanks Taemyr and Daz C), I corrected some mistakes in the answer. The main point is unaffected.)

There are multiple reasons, RSA uses a Modulo multiplication group with modulus $PQ$.  Due to the nature of groups, this group does not contain all natural numbers between 1 and $PQ$, rather it only contains the numbers that are coprime with $PQ$.  Coincidentally, the number of elements happens to be $(P-1)(Q-1)$.
But that is when $P$ and $Q$ are prime.  If you assume, P is not prime, but rather is semiprime so that $P=AB$ and $A$ and $B$ are prime, the number of elements in a group $PQ$ is no longer $(P-1)(Q-1)$ but rather $(A-1)(B-1)(Q-1)$.  So if you were to use $(P-1)(Q-1)$ during the extended euclidean algorithm you would not find the correct decryption key (the key can be found using $(A-1)(B-1)(Q-1)$).
That's the first reason, the second reason is that by using 3 prime numbers rather than 2, there are 3 additional keys that partly work for decryption.
by applying the EEA to the same encryption key and $(A-1)(B-1)$, $(A-1)(Q-1)$, and $(B-1)(Q-1)$ you get keys that can decrypt messages encrypted using E with modulo $ABQ$.  Decryption is not guaranteed, but it is possible.  Additionally, these 3 keys can also decrypt some messages that cannot be decrypted using modulo $ABQ$ by using modulo $AB$, $BQ$, or $AQ$ depending on which of the 3 extra keys are used.
Lastly all 3 prime numbers need to be as long as a traditional RSA prime (if not, $A$ and $B$ would be easier to find than $Q$, and finding $Q$ is trivial if you know $A$ and $B$), as both keys contains $PQ$, the key length is $len(P)len(Q)+len(E)$ (roughly $len(Q)^2)$.  If 3 primes are used, they key length is now $len(A)len(B)len(Q)+len(E)$ (roughly $len(Q)^3$).
These 3 reasons make it rather impractical to use 3 prime numbers, you have to especially implement non-prime handling, to result in an overall weaker algorithm, with a longer key.
All of these issues only compound if more primes are used.


Is it possible to encrypt a message's destination as well as its content? I have imagined a way to break through any kind of censorship but since I don't have enough professional knowledge of cryptography I don't know whether it is feasible or not.

If there is a method that can only enables the recipient to know this message is for him, and when others catch this message they don't even know who will receive that, then no one can block a certain site unless he can decrypt it.

I hope some professionals can respond to this question and tell me if this is possible.

Any peer to peer mesh network would be sufficient.  If peers pass messages on to other peers then no peer can no for certain which peer a message is intended for.  It would be possible to determine (with some degree of confidence) the source of the message.

The real difficulty is handling all the other problems.  How do you deal with malicious nodes, denial of service attacks, and who pays for the network as peers are anonymous.  That is just the tip of the iceberg.

As a real world example the Bitcoin network uses similar system for connecting peers and passing messages.  Transactions are simply messages shared peer to peer in an adhoc fashion (your node tells all your peers who tells all their peers who tells are their peer .... and the recipient is one of them).  Bitcoin solves a lot of those "bad node" problems because the messages (transactions) have a cost in term of fees taken out of the transaction.  They are low but they do prevent things like some attacker just creating a bunch of nodes and telling them to make a trillion messages to cripple the network.

Pretty much TLS can do this - by encrypting the link to the recipient's mailserver, any intercept would be unable to see the header info (and hence, which user of the mailserver is receiving the mail)

Onionskin routing is better at hiding who is sending an email, but usually does not conceal the recipient (as the last hop is normal SMTP)


Is there a floating point CSPRNG? Is there a floating-point CSPRNG that operates, natively, using floating point operations?

Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU to beat.

EDIT: Floating point doesn't matter too much.   Specifically, I'm looking for something for which GPUs or FPUs are, by far, the optimal hardware to use: as opposed to custom hardware, because the operations used are already heavily optimized on GPU.

My understanding is that floating-point-operations (FLOPS) are probably the best candidate here.    (It seems to me that most chaotic attractors can be trivially run using FLOPS.)

Are you sure?

Float operations are very hard to reproduce in diverse environments.

Do you round towards positive, negative or zero? Do you handle denormals or just treat them as zero? What about dividing by zero?

I'm sure we would love to have that problem with every cipher we implement.

  Looking for a CSPRNG that's very fast on GPUs, and would be hard for a CPU or FPGA to beat.

To beat FPGA... don't do anything. There are problems that are slow on CPUs & GPUs, but otherwise you won't have as big FPGA that can reach nearly same frequency. If that wasn't case we wouldn't have processors, just builtin FPGAs that switch between GPUs and CPUs...

To beat CPU... just use something that uses a lot of simple math... +,-,xor,ror,rol etc. This doesn't have to be on floats, ints will suffice. Chacha20 might work well on GPUs. Note that this won't be slow on CPUs, it will just be faster on GPUs because it parallelizes well (and this is always case, because CPUs are complex beasts that can do more than GPU, except there just isn't enough of it for raw number crunching at that speed).

Honestly, most cryptographic primitives will be faster on GPUs because they frequently rely on number crunching, and rarely do any significant memory access and/or branching.

Just remember that there are still ASICs that will always win against you, because they are exceptionally good at number crunching (and if you are looking to outrun them, argon2 and CPU are your friends).

Here is an example of what I'm looking for.   Yes, it hasn't been tested.   The underlying attractor has been proven a good source of randomness, and approximations of this technique have been used for other CSPRNG systems.

Convert a seed to 4 FP numbers between 0 and 1.
Calculate the hyperlorenz attractor using FP arithmetic for N iterations, and these numbers as the initial conditions.
For reference on why I would choose something like this:
https://www.researchgate.net/publication/308109900_Image_Encryption_using_Four-Dimensional_Hyper_Chaotic_Lorenz_System
Take the last X FP outputs, hash them with SHA3, then take the result and call it your first random number.   Continue iterating N times and outputting the results.

While the hashes are fast, the FP operations will be slow.   So this will, slowly, generate pseudorandom numbers, and will be both FP heavy, with highly sequential FLOPs.

To prevent cryptanalysis, the settings for N and X must be high enough that you're not capturing too many bits per iteration.   Keeping X low increases the ratio of FLOPS.  Keeping N low makes the algorithm more efficient, but less secure.

EDIT: Although the lorenz family of attractors are provably unpredictable and well-studied, the number of bits to capture per iteration is a matter that would require some experimentation and analysis to be provably secure.   Possibly it could be a number much less than one.   In which case this could be terribly inefficient.   There are other attractors used in secure cryptographic pseudo random number generators that may yield a better entropy level per iteration.

(I suspect that a fun paper to write would be one that can turn any chaotic attractor into a CSPRNG by determining optimal values of X and N for a given level of security required, level of leakage, etc.   Autotune for CSPRNG.)

The concern responders have for the approximations used in FP operations aren't really an issue and are basically useless non-information, please stop posting them.   Far more data is discarded and approximations made in other attractor-based integer CSPRNGs.   In fact you could simply change any FP system into an integer system with sufficient motivation.   But the point would be to make a system that's optimized for FPU's... which are can be analogized as the cheapest, most powerful and plentiful ASICs on earth.


Size of p in ElGamal cryptosystem? In the ElGamal cryptosystem, I was wondering whether the $m$ (message) should be less than $p$ (large prime). Because on decryption, we are getting $m \bmod p$. For $m \bmod p$ to be equal to $m$, shouldn't $m$ be less than $p$? So what should be the size of $p$? Should it be a very very large prime number if I need to encrypt a file of 5 GB or something?

As your message treated as one element in the finite field defined by $p$, it must be smaller than this $p$.

There are other reasons, but you mention one about why to use hybrid systems. When you encrypt using public key, the process starts by generate a random symmetric key used to encrypt your data. What is encrypted using the public key is this symmetric key.

Another reason is to encrypt to more than one recipient. The data itself is encrypted once for all, and is this symmetric key the one encrypted for each target.

Note that the size of a symmetric key is much smaller than the size of its equivalent in security in public key.

no.. just have only a very large prime $p$, then break your file into chunks less than $p$..

use Cipher Block Chaining (CBC) or Cipher Feedback (CFB) to get the work done.

For more concrete references on them, see Modes of Operation. this Wiki is pretty cool to begin with. Maybe you can look at here after that :)


Why MACs are so important despite digital signatures doing everything a MAC can do and more When an entity A wants to send a message to entity B, he can attach a MAC to the message. Entity B on receiving the message can use the pre-shared key to compute the same MAC and confirm if the message is untampered with.

This approach protects A and B from an external attacker who might want to mess with the message. However, it does not protect A from B or B from A. For example, A can craft a message and claim that it came from B since B is the only entity that shares this particular key with A.

Digital signatures eliminate this problem, since the MAC is replaced with a hash which is encrypted with the senders private key. Usage of the private key means that A and B cannot deny or forge messages between each other.

Which brings me to my question. Why do MACs continue to be so relevant when they are susceptible to the kind of attack described above? Under what circumstances would one prefer a MAC to a digital signature?

Note that I have been made aware that there is a question on here which seeks for a comparison between MACs and digital signatures. That question is different from mine since I am looking for concrete cases where MAC would be used instead of digital signatures. Can someone quote a protocol, application, etc, where the disadvantages of the MAC relative to digital signatures can be ignored?

There are many advantages of MAC's over signatures.

For signatures you need to use asymmetric key pairs. Public keys need to be trusted for this to work. Unfortunately establishing trust is not that easy. Furthermore you don't want to use a private key stored on, for instance, a smart card (which would require a PIN and would likely be too slow).

Instead you can simply agree an authentication key (or a key for an authenticated cipher). This allows much more efficient operations both regarding

the speed of calculation of creation and verification of the authentication tag / signature and
with regards to the size of the authentication tag / signature.

For many protocols the problem that the receiver can also spoof authentication tags is not a (huge) issue. It could be a bigger issue for protocols where the two participants use the same authentication key for both sending / signing messages and receiving / verification of messages. TLS, to name just one protocol, uses separate keys.

Public keys may not have been exchanged yet between A and B (maybe all they have at that point is a pre-shared secret).


Authentication over the phone? Are there any known good methods of performing authentication over the phone in a way that's not susceptible to replay attacks?

The specific scenario that comes to mind is having an automated call centre which verifies the identity through one or more questions. Since the phone line is not guaranteed to be secure (or the user may simply be in public), the calls can be eavesdropped.

One idea that came to mind would be something akin to CHAP - the user hears a challenge, mentally hashes it (per this CryptoSE Q&A, perhaps Blum's hash is a good candidate) and then speaks the solution out loud. Has something like this been attempted before and are there any known vulnerabilities?

Take a look at the military's Dryad for authentication.


Allow everyone to decrypt a message, but don't allow anyone to encrypt it I would like to create a software that will be installed on multiple clients. I would like to broadcast an encrypted message to all of those clients. Each client should be able to decrypt the message and react to it. However, noone should be able to create such a message that could be decrypted by those clients.

So, I would like to be the only entity that is able to create the encrypted message. At the same time I would like everyone to be able to decrypt the message I have created. I would also like the message to be sent in encrypted form, so digital signature alone won't suffice.

Is it possible with assymetric cryptography, i.e. RSA or ECC?

I know some people encrypt with private keys and decrypt with public keys, but lots of sources specify this approach as insecure/invalid. So, I would like to know what's the proper, secure and valid approach?

Update: edited to provide more context information, because maybe my generalization was confusing. It's not about the network, but rather I'm trying to think of some software registration key scheme. I would have multiple clients. When someone buys a key, I would send this person an encrypted registration info. His copy of the software would read this encrypted key info, decrypt it, and store on the disk in decrypted form. I would like to prevent converting this decrypted form into encrypted form again to prevent registration key from being stolen by some malicious software. The key would be useless in decrypted form because the software wouldn't accept decrypted key; it would accept only encrypted keys.

This is a scenario where your description would be much improved if you explicitly considered the following questions, which you should always ask in cryptography:

Who are the "honest" parties? (See at the bottom for an explanation of the scare quotes.)
Who are the adversaries?

In particular, you've not taken enough care to describe who the adversaries are.  The first obvious thing we can imagine is that there are third parties—neither your software nor its clients, both of whom would count as "honest parties"—that would eavesdrop on the broadcast and would like to know its plaintext.  If that's the model, then a simple solution would be:

All the messages are encrypted with a symmetric algorithm whose key is shared by the broadcaster and all the clients;
The broadcaster signs every broadcast with its own asymmetric keypair, and all clients verify the signature on every broadcast.

But there's a problem with this way of looking at it: should the clients really be modeled as "honest" parties, or are they actually a type of adversary?  Encryption only protects message confidentiality if the recipient is an honest party, who keeps the keys and plaintexts secret.

The problem with your scenario then is that you're disclosing information to another party and expecting them not to disclose it to anybody else.  That works if and only if the other party is "honest," and it could easily fail if the other party is an adversary.

Note that in cryptography, "honest party" is not a moral term.  It's a party to some protocol who can be counted on to execute it faithfully.  While an adversary is a party that cannot be counted on to follow the rules.

Unless you are dealing with a bunch of clients on a single small network, you are probably not doing a true broadcast, but rather just sending the same message to each client.  So I would just think in terms of sending a bunch of individual messages, each of which just happens to contain the same content.

As far as the encryption, I would recommend a normal SSL connection, perhaps with a "Wake up" message so each client knows to fetch the message.


ECDSA Public key randomness If I have a 256bit ECDSA public key how likely is it that the same public key will be generated by another person. Will it take on average 2^256 tries to generate same public key? If I xor the first 32bytes of the public key over the second 32bytes and only have 32bytes is it now 2^128 tries to generate the same 32byte data? Or less? Thanks

ECC public keys are not random numbers.

They are generated through a scalar multiplication of a random scalar with a known/public point on the curve, called Generator.

The entropy lies entirely in the random scalar. Two public keys will collide if the random scalars collide.

When you say "256bit ECDSA  public key" you probably mean that your elliptic curve curve is defined over a finite field whose size is approximatively $2^{256}$. This would explain why you are mentioning a public key of 64 bytes in your question.

Now, in cryptographic secure elliptic curves, that size is closely related to the size of order of the generator, which is actually the size of your random scalar.

Therefore, without knowing the exact curve you are using I can't exactly answer the question. But approximatively the expected probability is: $\frac1{2^{256}}$

This has nothing to do with the encoding, so xoring the key over itself doesn't really make sense to me, or I didn't understand it.

Well to start of, great question it really got me thinking. unfortunately I cannot give you an exact answer but i can tell you the chances of getting the same public key as someone else is negligible. If the chance would have been anything but negligible the whole system would collapse since and attacker would have just as much chance of getting your key then.

so i don't think you should worry about this, but that is my opinion. also an interesting read is this paper about Key-collisions in (EC)DSA, it is about how there is no algorithm (currently) which can search and create key collisions. Well that's the jest of it anyway. unless the discrete logarithm problem (DLP) gets solved we're safe ;)

I hope this helped.

also check this question and answer on security.stackexhange.com It's for an ssh key but the math is similar and the chances about the same.


Is there a practical way to crack an AES encryption password? I heard that the fastest method to crack an AES-128 encryption, or and AES-256 encryption is by brute force, which can take billions of years. But I can't help thinking there's got to be a faster way.
Because the AES encryption scrambles the data contained in a zip file, the password could be found by unscrambling that data correctly. Say if a portion of the data in the file is known, for example a string at the end of a file, or a header containing an expected sequence of bytes in a known file type.
 Then by comparing the scrambled bytes with the 'expected' unscrambled bytes, the password can easily be determined by computing an algorithm that converts those bytes because both the scrambled bytes and the unscrambled bytes are known. Only the formula is unknown.
However, the condition for this type of cracking is that the zip file contains known file types which have a determined data format and places certain data in certain locations in the file. For instance, a 3ds file always starts with a header containing the bytes "4D4D".
Hence a list of possible passwords to rearrange the sequence begin to be narrowed down as the cracking progresses.
So is this method plausible? or is there something wrong with it,  like maybe the actual address of the bytes in the zip is different from the address in the unzipped file.

Yes, in the question's situation, a password-recovery attacks is entirely reasonable.

The question considers a (partially) known plaintext attack, where e.g. some header of the encrypted file(s) is known, for a file encrypted with AES, where the key has been determined from a user-supplied password. In this scenario, it is not important to consider the expected number of AES operations for brute-force search of the AES key ($2^{127}$ for AES-128, $2^{255}$ for AES-256) because that's not the best (nor a credible) attack strategy.

The reasonable attack strategy is password cracking: try passwords, approximately from most to least likely to have been chosen, and for each attempt decryption up to the point where known plaintext is reached, and move on to the next password if this test fail. Attack cost will depend on:

How the password was chosen. Users vary widely on that, and 123456 will be easier to find than MdSm2aZ!t&5u*Z5. That varies widely with the context, and motivation of users. See the obligatory XKCD.
How the password is transformed into an AES key. A password-based key derivation function should be used here, parametrized so that it adds a sizable cost.

The cost for an attack grows roughly as $2^E$ times the cost of the PBKDF (assuming that dominates the cost of testing a password), where $E$ is the password entropy in bits. For example, if the password is 6 random decimal digits ($E=\log_2(10^6)\approx19.9\,\text{bit}$), and the PBKDF + plaintext testing uses 0.1 second of CPU time (300000 CPU cycles @3GHz), a competent attacker will use an average of $10^6\times10^{-1}/2=50000\,\text{s}<14\,\text{h}$ of CPU time to find a password, that is less than 2 hours of wall clock time with a single 8-core PC, minutes for a powerful adversary.

The AES standard is theoretically unbreakable in non-trivial time, hence why everyone is using it.

Brute force would be a bad idea, since a 12 digit password with no symbol have 3.9087701e+20 combinations.

Your best bet is a dictionary attack with a good set of rules and a massive massive dictionary. I recommend the RockYou database.


Why is Bcrypt called a Key Derivation Function? I am trying to understand why is bcrypt called a Key Derivation Function?

I looked up the details of Ekfblowfish on Usenix article.

After reading it, I understood that:

The password is the encryption key. The length of the password can vary and so the length of the encryption key can vary (max is 56 bytes or 448 bits).
128 bit salt, it does not provide the details about how this salt is generated? It only says, that the 128 bit salt along with the variable length encryption key is used to modify the S Boxes and the P Array.
When it says, Key Schedule, it refers to both, S Boxes and P Arrays. The Key Schedule keeps changing using the bits of 128 bit salt and the encryption key.

Now, what key are we deriving here? It is not clear, why is bcrypt called a Key Derivation Function?

So, does it mean that at the end of Expensive Key Schedule, we have a unique value for S boxes and P array contents which are further used to encrypt "OrpheanBeholderScryDoubt" using ECB mode.

So, aren't we deriving the Key Schedule (S boxes + P Arrays) instead of the Encryption Key (which is the same as the password that was supplied as an argument in the starting)?

Which key has been derived using Eksblowfish?

It's called a key derivation function because that's what you'd typically use its output for — as a key for some other cryptographic algorithm.  (Of course, you can also use the output of Bcrypt for other purposes, e.g. storing it in a database as a password hash, but that's really a secondary use case.)

In general, key derivation functions (KDFs) serve a number of purposes:

Key separation: This is the most basic use case for KDFs. Basically, you have one key, but need several.  This might be e.g. because you're a server that needs to communicate with multiple clients using distinct keys for each, or simply because the algorithms you're using together (e.g. a cipher and a MAC) have only been proven secure under the assumption that they each have separate and independent keys.  You can solve this problem by using a KDF (with different salts) to derive multiple (quasi-)independent subkeys from your original key.
Key expansion: Related to the above, some algorithms may require rather long keys for practical reasons, even though the desired security level against brute force guessing could be met with a shorter key.  In such cases, you can use a KDF to effectively extend the length of your key.
Key whitening: Many encryption algorithms, such as block ciphers, require a key that consist of a fixed number of (effectively) random bytes.  If you have a key that is not in the required format (such as an arbitrary-length passphrase, or a Diffie-Hellman shared secret), you can use a KDF that accepts arbitrary input key material to hash it into a byte string of suitable size.
Key stretching: This is the specific use case for which Bcrypt (and other "password-based" KDFs like PBKDF2 or scrypt) are designed for.  Basically, say you have a user-entered passphrase that may have a relatively small amount of entropy (say, from 20 to 40 bits), in addition to all the other issues mentioned above (too short / too long, wrong format), and you want to use it to encrypt/decrypt some data (or to authenticate the user) while making it hard to break the encryption by guessing the passphrase by brute force.

The solution is to use a deliberately slow (and possibly memory-hungry) KDF, like Bcrypt, to derive an encryption key from the passphrase.  By making the derivation process deliberately take a very long time (say, a whole second, which might be a million times more than a simple non-stretching key derivation would take), you can slow down any brute force attacks by the same factor.  The reason it's called "key stretching" is, presumably, because you're taking a "short" (low-entropy) key and effectively making it as resistant to brute force attacks as a "longer" (higher-entropy) one.

Now, that's a whole bunch of jobs, and indeed one might argue against lumping all functions designed for some or all of these tasks under the single label "KDF", but that's how the established terminology works.  There is some justification for it, since systems that require the latter properties often also require the former.

Still, different KDFs do have different strengths; for example, Bcrypt is pretty good for key stretching, but somewhat awkwardly limited in other respects.  If I wanted a Bcrypt-based system that handled all of the points above, I might consider e.g. combining Bcrypt with HKDF (from RFC 5869), like this:

Use HKDF-Extract to whiten the input key material / passphrase, avoiding the input length limits of Bcrypt.
Feed the pseudorandom key generated by HKDF-Extract through Bcrypt to stretch it against brute force attacks.
Use the output of Bcrypt as the PRK for HKDF-Expand, to provide efficient key separation and expansion.

In addition to Ilmari's excellent answer I would like to address your questions and clarify some points for you:

  I am trying to understand why is bcrypt called a Key Derivation Function?

Because it derives a key from given input. This key is then used as unique value for a password in the case it is used for password hashing. bcrypt is a Password Based KDF. This means that the key is derived from a password (together with the salt and iteration count of course, the password is the principal input though).

  ...

  After reading it, I understood that:

    the password is the encryption key. The length of the password can vary and so the length of the encryption key can vary (max is 56 bytes or 448 bits).
        128 bit salt, it does not provide the details about how this salt is generated? It only says, that the 128 bit salt along with the variable length encryption key is used to modify the S Boxes and the P Array.
        When it says, Key Schedule, it refers to both, S Boxes and P Arrays. The Key Schedule keeps changing using the bits of 128 bit salt and the encryption key.

  Now, what key are we deriving here? It is not clear, why is bcrypt called a Key Derivation Function?

The password is used as input for the key for the Eksblowfish algorithm. This should be considered an implementation detail.

  So, does it mean that at the end of Expensive Key Schedule, we have a unique value for S boxes and P array contents which are further used to encrypt "OrpheanBeholderScryDoubt" using ECB mode?

  So, aren't we deriving the Key Schedule (S boxes + P Arrays) instead of the Encryption Key (which is the same as the password that was supplied as an argument in the starting)?

First the key schedule for which the password is used as part of the input parameters, then the encryption which results in the derived key. The derived key is just a bunch of bytes (the ctext` from your article).

Of course you should not directly store the ctext directly if you want to use it as (base for a) key. Storing Concatenate(cost, salt, ctext) is mainly useful for using it as a password hash. If it is a string starting with $2y$ then the concatenation is stored as a crypt compatible string.

  Which key has been derived using Eksblowfish?

The output ctext. You can use this output for any cipher or as password hash. Your confusion arises from mixing the output with the implementation.


Intuition for SHA3 sponge construction I would like to get some intuition on the security of the sponge construction. I'm referring to this diagram and notation.

Let's consider the case where we have don't apply $f$ in the squeezing phase i.e. we simply take the bits in the r-space ($Z_0$ in the figure) at the end of absorption and call that the hash of our message.

The Wikipedia article says that one could replace the XOR function and simply choose to overwrite the $r$ bits with the message instead of using XOR. The security level is not compromised if this is done and makes it easier for me to understand.

Reading a few other answers, it seems to be the case that the core thing that keeps SHA3 safe is the lack of knowledge about the state of $c$ in the final step. But this seems problematic.

For instance, let's say I have the hash of a known message (and therefore the internal states $c$ corresponding to this message at all stages) and would like to modify the last part i.e the $P_{n-1}$ bits. It seems like I have a very localized problem i.e. I know $(r_1, c_1) \xrightarrow{f} (r_2, c_2)$ and must find $(r_1', c_1) \xrightarrow{f} (r_2, c_2')$ for arbitrary $c_2'$. If I want to do it for any intermediate block, $P_k$, then $(r_1', c_1) \xrightarrow{f} (r_2', c_2)$ is the constraint, where $r_2'$ is arbitrary. This is because the bitrate is overwritten in intermediate blocks so that part of the output can be arbitrary while for the last block the state of the capacity is not used so it can be arbitrary. Moreover $f$ is just a permutation and so this task seems... not too hard?

I want to add, I know that hundreds of very clever people have tried various attacks and failed so this has a good resolution. This isn't some crackpot "I broke SHA3" post - it's more of a "what aspect of SHA3 am I missing" post!

So if it's just a permutation of 0s and 1s as we've concluded, what is hard about finding an alternate message string that satisfies the constrains I've mentioned on the permutation outcome?

To be more precise, it is a pseudo-random permutation from $\mathbb{Z}_{2^{1600}}$ to $\mathbb{Z}_{2^{1600}}$. It is not just 0s and 1s changing positions.

Because of the size of $\mathbb{Z}_{2^{1600}}$ (which contains $2^{1600}$ elements!), the input and output are related in a somewhat random (but  deterministic way), and it cannot be predicted without actually evaluating the permutation (or its inverse) on a given input and checking the result.

There are tools such as linear and differential cryptanalysis that can be used to try and predict the output, but keccak-f was explicitly designed so that using these techniques would be computationally intractable.

  It seems like I have a very localized problem

You cannot isolate parts of the state and work on them independently. Changing one bit of the state and then applying the permutation diffuses those changes across the entire state in an unpredictable manner.

You have correctly identified the crux of SHA-3’s security. It has a fairly complex domain extender to handle all of the different digest lengths. The first mechanism pads up to the rate size for message sizes below the respective rate size of the digest length. The second mechanism (called the capacity) pads a constant number of lanes containing only zeros to the respective rate size until the full state size is reached.

For the XOR function to be called the message size must exceed the rate size for the specified digest length. Now keep in mind that one of the state chunks will always be appended with zeros (i.e. the capacity). There are also some issues with message sizes that equal the rate size, in which case an empty string is automatically appended to the end of the message. I’ve never been able to find any security reasons for adding this string, or even get someone else to acknowledge that this string exists. But it’s there and I can prove it. You should be able to overwrite the state without calling XOR and not compromise security. This has to do with the theta function being initialized with a full state of zeros. YES, regardless of your definition of theta, it’s initialized with a full state of zeros.

Now the current goal of cryptographers is to find a capacity that contains all zeros, and thus prove the existence of a collision in SHA-3. We’ve already found those values (we know the collisions are out there just sitting smugly…those bastards), but it was the result of carefully crafting an inverse function that violated the two mechanisms outline in the first paragraph. But out of this effort certain statistical advantages were gained by processing the inverse function. Bit prediction through chi is statistically relevant, verifiable, and represents the only real talking point with regards to the otherwise extremely robust security of SHA-3. The attacker must bind the state’s output capacity region at zero, and run the inverse function (a whole bunch of times) hoping the resulting input state also has a capacity region filled with zeros. Google might be able to take a swing at it with some deep meet-in-the-middle vector magic, but right now free start collisions is the only thing I can find.


Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known? Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any two hybrids $H_i$ and $H_{i + 1}$ can only be efficiently distinguished with probability $2^{-\lambda}$. So, by iterating through all the hybrids, it seems to me that the probability that $H_1$ and $H_n$ can be efficiently distinguished is bounded by $(p(\lambda) - 1) \cdot 2^{-\lambda}$ using union bound. Asymptotically, this probability is negligible in $\lambda$.
My question is that, when $n = p(\lambda)$ is polynomially bounded with respect to $\lambda$ but not known, it seems impossible to choose a reasonable $\lambda$ such that $(p(\lambda) - 1) \cdot 2^{-\lambda}$ is sufficiently small (e.g., $< 2^{-40}$). I think that the same issue may exist as well when it comes to some computational security parameter $\kappa$. It would be appreciated if someone could give me any hint on this question. Many thanks.

a function "polynomially bounded" means there exists $d\in \mathbb{N}$ such taht
$f(\lambda)\leq \lambda^d$ asymptotically.
You don't have to know $f$, but if you want to bound the advantage of your adversary asymptotically, you have to know a such $d$ which verifies this inequality.
If you don't, then you can't deduce anything. But in general, if you look the proof in details what is $n$, and why it has been claimed polynomially bounded, it's easy to find a such $d$, such that $n\leq \lambda^d$ asymptotically.


Does keyless encryption exist? Does there exist an encoding/hashing/encryption scheme whereby the original string can always be derived in its entirety given the entire encoded/hashed/encrypted string, and nothing else (no key/password). But also, no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string.

Basically this would be an algorithm that deterministically and reversibly jumbles up a string in such a way that the reversal algorithm requires the entire jumbled string.

Does such a thing exist? If so, what search terms should I use to learn more about it? I don't know enough about the subject to know the right words to find more information.

Clarification

  I'm wondering whether there exists an encoding/hashing/encryption scheme whereby the original string can always be derived in its entirety given the entire encoded/hashed/encrypted string, and nothing else (no key/password). But also, no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string.

I am assuming that "no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string" means "no portion of the original string can be derived given anything less than the entire encoded/hashed/encrypted string", otherwise the question would be self-contradictory.

Answer

It sounds like you are looking for a permutation. A permutation is an invertible transformation on a fixed-size set of blocks. If your input is larger, the/an All-Or-Nothing Transform may be useful. The OAEP mentioned by @DannyNiu is an example of an AONT.

For example, many block ciphers are built by interleaving applications of a permutation with the addition of secret key material. The permutation provides diffusion, which ensures that if you modify any part of the output then attempt to invert it, you end up back at a completely different input.

If you simply strip the key addition portion from a block cipher, it should also do what you're asking. For example, AES consists of subBytes, mixColumns, shiftRows, and addRoundKey. If you were to omit the addRoundkey operation, you would be left with a fixed permutation that provides the required avalanche effect and some degree of unpredictability. Another example of a permutation is keccak-f, which does the mixing for the SHA3 algorithm.

A key-less permutation does not provide encryption

Note that such a construction with no key is no longer providing encryption, as it is not possible to provide confidentiality of the message without some kind of secrecy, which is what the key provides. If anyone who has an input message can compute an output "ciphertext", or anyone who has an output "ciphertext" can invert it to the input message, then clearly confidentiality of the input cannot be achieved.

You tagged this question with "encoding", so perhaps confidentiality is not required in your use case. You would need to establish what you need this construction for and whether or not this is an issue.

Let's take the simplest cipher I can think of which the key is not obvious: ROT13. You replace a letter with the 13th letter after it, in the alphabet. Because there are 26 letters in the alphabet, you don't need to inverse the algorithm for decryption. Is ROT13 an example of keyless encryption, a very weak one of course? No, because 13 is your key. I don't think any algorithm that can be expressed with a computer can be keyless.

Another bizarre example of which the key is not obvious is a language. Obscure languages have been used as a form of encryption. The most famous example are the code talkers of World War II. Navajo was an unwritten language at that time and the only way to encrypt a message was using your language skills and your mouth. You decrypted a message using your ears, your language skills, and pen and paper. So is this form of encryption keyless? To answer that question, we have to know if this algorithm can be expressed by a computer. There is no way for a computer to translate English to Navajo right now, but there are services that can translate English to Chinese and vice versa. If we trained a language model that could automatically translate English to Navajo using a computer, that model would be your key.

So this answer doesn't ultimatively exclude any form of keyless encryption might exist. I just had a look at some encryption topics not covered by RFC or NIST and I don't think it's possible for keyless encryption to exist.


Is there a signature scheme for the Cramer-Shoup cryptosystem? I have a project that I have to use cryptosystem and signature scheme for it.

I've read about Cramer-Shoup cryptosystem and I want to use it since it is more secure the ElGamal cryptosystem, but, I need a signature scheme based on it which I did not find.  Is there such a signature scheme?

If it does not exist I thought of two solutions:

I can use DSA for it but since there is one generator $g$ in DSA and two generators $g_1$,$g_2$ in Cramer-Shoup cryptosystem. So I think I may not be able to use it.
I can generate a separate DH key and use it as a signature public key for the user. Then I could use this key for DSA. But I am not sure if this is considered secure.

Are these options valid?

It is very bad practice to use the same private key for two different schemes. In some cases this is secure but you need to explicitly prove it. One example of this can be seen here: http://www.pinkas.net/PAPERS/combined.ps.

My suggestion is to take the Cramer-Shoup group and to define a separate key pair for DSA or Schnorr signatures. You can use the generator g_1 and this will be fine (the group can be the same; it's just the key that has to be different).

This link seems to give sufficient insight:


What is difference between PRG, PRF, and PRP Until what I have gotten is: A PRG is generator is a part of PRF that produces pseudo-random values for the function. PRF is semantically secure and has no worries of being invertible. Fine, then where is PRP used? What is PRP, where it comes to, how it benefits.

A Pseudo Random Function is a function that is indistinguishable from a function selected at random from the set of all functions with the same domain and value set. A Pseudo Random Permutation is, similarly, a bijective function that is indistinguishable from a bijective function selected at random from the set of all bijective functions over the same domain. For instance, a cryptographically secure block cipher parametrized by a secret key is a PRP.

The term PRG is otoh most commonly used for stateful functions that are used for generating successive pseudo random strings, e.g. to be used as a key, iv, salt, nonce etc.

To me a PRP is a type of a PRF. Meaning that a PRP is where X=Y and is efficiently invertible. (NOt entirely accurate but it formed the basis of my understanding.


AES vs other types of encryption such as Twofish I am kinda of confused about what are some major differences between AES, Twofish, and other types of common encryption algorithms.

Rijndael (aka AES) and Twofish were both candidates and finalists for the Advanced Encryption Standard contest, a three year selection process which yielded the selection of Rijndael as the standard.

Contest submissions were required to be block ciphers of block size 128 bits and support key sizes of 128,192 and 256 bits. Submissions were put through rounds of cryptanalysis and assessment by prominent members of the cryptographic community. NIST, the competition organiser, made the final decision that Rijndael would become the AES.

At a high level both AES and Twofish are 128 bit block ciphers supporting 128,192 and 256 bit key sizes. Both ciphers are (despite a small number of theoretical attacks) secure in the computational/pragmatic sense that nobody has yet found a way to break them. Both ciphers are based on heuristic constructions, meaning that we don't have a proof of security showing a reduction to some known hard problem, instead their security is based on the fact that nobody has broken them yet. Both ciphers satisfy the pseudorandom permutation (PRP) function model in that their output cannot be distinguished from a random permutation in the block size.

High-level differences between the ciphers are that AES and Twofish are based on a substitution-permutation network (SPN) and a Feistel-network respectiveley. These networks are applied in rounds where AES has 10,12 or 14 rounds depending on the key-size, Twofish always applies 16 rounds.

Aes is based on elliptical curve and abstract mathematics such as groups and fields. Twofish isn't. Aes is commonly used by most https servers and is recognized by ssl or tls, twofish isn't.


How secure is the Bitcoin protocol? Are there any evidence (other than not being cracked so far) that the Bitcoin protocol is secure? "How secure" is it?

(I realize that this might not qualify as a meaningful question - feel free to edit if you can improve it. Also, if you liked this question, you might like the Bitcoin Proposal.)

There are several uses of cryptographic algorithms in the protocol.

Accounts/Transactions

To move money from one account to another, you need to collect some data (the previous transaction(s) which got you the money, the target account, the amount you want to transfer) and sign them, using the private key which belongs to your account.

For this signature Bitcoin uses the ECDSA algorithm.

If I can fake your signature, I can also steal your money.

The (public) addresses of the accounts are given as address = version || hash || checksum, where version = 0 (one byte), hash = RIPEMD-160(SHA-256(public-key)) and checksum = first 4 bytes of SHA-256(SHA-256(version || hash)). (The checksum mainly protects against transmission errors.)

If I can somehow generate a private key whose corresponding public key has the same SHA-256 hash as your one, it will have the same address, and I can steal your money. If I can create a fitting private key for your public key, this is also possible.

For now, there is no known attack at the ECDSA algorithm (and I think even with second-preimage attacks at SHA-2 to find a second public key with same hash, you would need an attack at ECDSA to get a useful private key).

It is much easier for now to use a trojan or such to steal the actual private key of the owner. (But this would be off-topic here.)

The Block chain

For a transaction to be deemed valid, it has to be included in the block chain, e.g. in one of the blocks consisting this chain.

To create this block, a miner uses a Merkle tree of hashes, which refer the individual transactions included in this block, the previous block, and some other data. This tree uses SHA-256, too.

A block is considered valid (e.g. other peers will accept it, and build their own blocks on it) if the hash of the header is lower than some number (the "target"). This can be reached by manipulating one part of the block, the nonce value, calculating the hash, and repeating until one is lucky hitting the right nonce to make this block valid.

If there are several valid blocks running around (which are not descendants of each other), "good" miners will usually build on the one with the longest chain.

So, how could we cheat here?

If we can break SHA-2, e.g. by finding a faster way to get the right nonce than trying many of them, we can generate the blocks faster than everyone else. This would mean that we will get all of the mined coins, at first. Having a monopole, we can also effectively decide which transactions to include and which ones not (this could be a denial-of-service for competitors who want to transmit money).

I'm not sure if we could in fact include bogus transactions this way (or by other SHA-2 breaks means) in our Merkle tree - I think the receivers of a blocks should still check if its transactions have actually a valid signature.

For now, no such break of SHA-2 is known.

Bitcoin blockchain allows immutability ( along with transparency). This means if once you write data it is nearly impractical to change the data. Since, the new blocks keep getting added to store upcoming data and to change any bit of data you need to change all upcoming blocks, breaking so much of encryptions while coping up with more of blocks that are formed in impractical.


Known-plaintext attack on 1-round Feistel networks Consider a simple, 1-round Feistel network.

Because the ciphertext is essentially $(L_1,R_1)$, if one knows the plaintext $(L_0,R_0)$, the only unknown left is $K$.

However round functions in Feistel networks are not necessarily invertible. For example, one could in principle use a cryptographic hash as a round function.

The Feistel network equation would become:

$R_1=L_0 \oplus \operatorname{sha2}(R_0,k_1)\\L_1=R_0$

One could XOR $R_1$ (known ciphertext) and $L_0$ (known plaintext), thus obtaining $\operatorname{sha2}(R_0,k_1)$, but this would not yield the key unless one uses brute force.

Clearly brute force is always possible - and there are other issues with a 1-round Feistel network, for example it leaks half of the plaintext - but I was wondering.

When one talks about KPA against 1-round Feistel networks, is it implicit that brute force can be used in the end to obtain $k$, for non-invertible round functions?

Regardless of the specific $f$ function, you already observe that you can obtain
$$
R_1\oplus L_0=f(R_0,k_1)
$$
where $k_1$ the first round subkey is your target.

But $R_0$ is also a part of the known plaintext. So you have a system of equations for the bits of $k_1$ which you can systematically attempt to solve. For a normal Feistel function $f$ (which is one to one or the cipher wouldn't be invertible) this is straightforward.

Exactly how $sha_2(R_0,k_1)$ is defined plays a part here:

Possibilities include $sha_2(R_0||k_1),$  or $sha_2(R_0 \oplus k_1)$ (possibly with padding or repeating of $k_1$ to make it the same length as $R_0.$).

In any case you can try to use the $sha_2$ equations, noting that the effective input length is essentially at most the length of $R_0$ plus the length of $k_1$ and hence a strong hash function is most likely one to one for such inputs. Using the random oracle model, a randomly chosen function from an input of length, say, 128 bits, to the full digest size for sha_2 of 512 bits is one to one with overwhelming probability (see birthday paradox, addressed in many answers to questions on crypto stackexchange).

I think it will recover some different K if the length of K is longer than R_1.


ECC public key encryption without symmetric cipher Imagine the following scenario. A process is running in background and permanently encrypting some data. An adversary has full control of the process, e.g. it can dump the process memory any time and read the symmetric key. It is essential that the adversary cannot decrypt the data, therefore only public-key encryption without any symmetric cipher component is feasible.

What would be the best method for data encryption in this scenario using ECC?

ECC cant really be used to encrypt and decrypt data - it doesn't have the required properties. An asymmetric cipher such as RSA would have to be used, as this can encrypt and decrypt data.

ECC can be used for bilateral key exchanges, and to sign/verify data. RSA can sign/verify data, do KEMs, and encrypt/decrypt data.


How secure will this be against brute-force attacks? I'm looking into encrypting files like this: First, I SHA-1 hash the password. Let's say the password is something normal like "hello123", and then hashed. Then I encrypt a file using this:

openssl aes-256-cbc -a -salt -in file -out file.enc

(using the hash for the password).

So it's basically just an AES-256-CBC encryption with a salt.

How easy would it be to crack this by brute force? (Assuming the attacker knows that we have aes-256-cbc with salt and that the original password is hashed.) For instance, how long time would it take these days, on "normal" hardware?

I don't know how you're adapting the digest of SHA-1 to meet the key requirement of AES-256 (stretching the 160 bit digest into a 256 bit key), but if you somehow have a way of doing that without seriously compromising key entropy, then you have a theoretical key space of $2^{256}$. That window is limited by the limitations on your encryption passphrase however. In an ideal case for decryption where the person cracking your cipher has your program and knows the limits on your passphrases, they don't have to test all $2^{256}$, only your possibilities.

Say you limit passphrases to $10$ keys, alpha-numeric. That's $62$ characters to work with. The practical key space for you is $62^{10}$.

Arguably, it is currently impossible to decrypt even in the above worst-case scenario. This is largely due to another factor: verification of success. Say you only had $200$ possibilities. Someone trying to decrypt the file needs a way to check if each of the $200$ attempted keys yielded accurate results. Given that they may not know the nature of the file, that seriously complicates the process.

You're good for a while.

This is easily cracked if you encrypt Bitmap Picture with CBC mode cipher since the 128 bits data block will be the same on bitmap pixels.


What is the "compression function" in Merkle-Damgård? Is the "compression function" in Merkle-Damgård just a collision-resistant, one-way hash function but one that operates only on fixed size inputs?

If so, is MD just a way to extend it to work on arbitrary length strings?

A compression function takes two fixed size inputs: a chaining value and a message and returns a fixed size value. So it's essentially a hash function with fixed input size.

Merkle-Damgård is a domain extender, which turns that compression function into a hash which supports arbitrarily long messages.

MD uses the output of the compression of one block as the chaining value when hashing the next block. It also describes how to pad the message so it consists of complete blocks.

The merkel-damgard scheme highlights the point that for  a hash function to be collision resistant, the compression function needs to be collision resistant. This guarantee helped in creation of hash functions like SHA, WHIRLPOOL, MD etc.
According to this scheme, the input message can be of variable length, but the its length should be a multiple of a given number (say n), for ensuring this padding is used, then message is broken into m parts each  of length n.
The number of times the iteration runs depend on this number m. At first step an arbitary digest of fixed length (say p) is used, and after first iteration, compression function uses the first of m parts of input message M and this arbitary digest to create a new digest of the fixed length p, which is used by next iteration as input with 2nd of m parts of input message M,  till m iterations.
After m iterations, the final digest is of fixed length p.
Hence input can be of arbitary size, but the digest is always of a fixed size.

In short, Yes, MD is a way to work on arbitary length input, while ensuring collision resistance.


What are the advantages of TOTP over HOTP? HMAC-based One Time Password (HOTP) was published as an informational IETF RFC 4226 in December 2005. In May, 2011, Time-based One-time Password Algorithm (TOTP) officially became RFC 6238. What advantages does it introduce?

One of the advantages is purely on the human side of security. From RFC 6238's abstract:

  The
     HOTP algorithm specifies an event-based OTP algorithm, where the
     moving factor is an event counter.  The present work bases the moving
     factor on a time value.  A time-based variant of the OTP algorithm
     provides short-lived OTP values, which are desirable for enhanced
     security.

(Emphasis mine.)

The TOTP passwords are short-lived, they only apply for a given amount of human time. HOTP passwords are potentially longer lived, they apply for an unknown amount of human time.

The reference to "enhanced security" is referencing (at least) two areas: The value of a compromised key, and ability to attack one.

First, should a current HOTP password be compromised it will potentially be valid for a "long time". Ensuring frequent use of the HOTP in human time is not a part of the HOTP design, so it is unknown how long the current HOTP password will be valid for and we have to assume the worst case, namely, that it will be a "long" time. This allows the attacker to use a compromised password at their leisure. But should the current TOTP be compromised, it will not be useful for very long because in one TOTP time increment it will be invalidated. Of course, in theory the attacker could grab and use the password in negligible time, but it does prevent a practical human aspect. For example, someone who gets a look at your current Paypal key (which rotates every 30 seconds, IIRC) can't go home and try to use it later, they would have to lunge for a computer in the moment. Someone who compromises they key may not realize it until after the key has expired. Etc.

Second, if you are attacking a key, your work is potentially invalidated or set back every time increment of the TOTP because the target has moved. Perhaps an attacker has discovered an attack against an OTP scheme that allows them to predict the next password only if they have some number of the last 10 passwords, but it takes about 2 hours of computing time to do so. If the OTP changes every minute, their attack is pretty much useless. Brute-force attacks are inhibited as well, because the next password is chosen the same distribution each time; it is possible to brute-force exhaust the password space and not find the password. TOTP doesn't eliminate those sorts of attacks, but hopefully it limits which ones have the ability to be effective.

Neither is worthwile.  Changing number codes were invented by RSA in 1984 to block keyloggers. More than 90% of todays internet breakins take place as a result of phishing, and we're seeing incidence of entire countries having more malware infected machines than clean ones (the boleto bandits, have pocketed $1bn cash so far, & are still going strong).

TOTP and HOTP are almost completely ineffective against todays' risks.

You need solutions that include mutual authentication, and transaction verification, not 30-years-old gizmos.


How would I convert committed coordinates $x$ and $y$ to a commitment of the EC point without revealing the point (in Zero Knowledge) or vice versa? I am working in the secp256k1 elliptical curve, though I suspect this would apply to any elliptical curve.  I have a Pedersen Commitment of the $x$ and $y$ coordinates in some discrete log scheme with generators $g$ and $h$. The point described by $x$ and $y$ is equal to $G^n$, where $G$ a public generator and $n$ is a secret (using exponentiation to represent point scalar multiplication on elliptic curves). Is there a method to get from the $g^x h^{r_1}$ and $g^y  h^{r_2}$ to $G^n H^{r_3}$, where $H$ is a second generator in the curve and all $r$ values are secret random numbers, using Zero Knowledge Proofs where needed?  A method in the other direction, going from the commitment of $n$ to a commitment of the two coordinates $x$ and $y$ would also be applicable.  I haven't been able to find such a proof in my research and I have not been able to think about how to create one.

My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash. This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key. If someone has done this, then I guess the question is moot and I will reference an applicable paper instead of designing it myself, thus a link to any such paper would also be an acceptable answer to this question. Unfortunately, I have not seen such a paper myself in my research.

EDIT:

I should also note that before the commitments of the coordinates were in the form $g^x h^{r_1}$ and $g^y h^{r_2}$, they were two lists of bitwise commitments that were homomorphically combined to become $g^x h^{r_1}$ and $g^y h^{r_2}$.  I did not lose those commitments, so they are available.  It was probably a mistake to suggest combining them, as it could introduce problems in performing operations on them due to differing orders between groups.

It's quite useful that you included yuor actual goal in the question, to avoid the XY problem.

  My goal is to design a Zero Knowledge Proof of Knowledge of the private key associated with a public key which has been hashed (using the Bitcoin address hash) in such a way that the only public information is the environments (generators, settings, etc) and the result of the hash function, as well as all associated functions like the Bitcoin Hash.

If we assume that pulic parameters are known by everyone, you only give the verifier a single piece of information: The hash-value of the public key. And here it is quite irrelevant what kind of public key is used - you need a ZK proof for a preimage under the according hash function.

I am not sure what you mean with "all associated functions like the Bitcoin Hash". But the goal here seems to be keeping the identity of the Bitcoin account secret, so I guess that additional information does not reveal the public key either.

  This proof can be used to prove ownership of a non-spending Bitcoin account without revealing the public key.

Actually, this is probably wrong. The reason for this is, that knowledge of a preimage under a hash function does not guarantee that the preimage is actually a valid Bitcoin account. For that you would need a different ZK proof, in which the verifier actually needs the according public key.

In the setting of Bitcoins, I think your agoal is not achievable. What you actually would need is a proof for membership of a group, e.g. the group of owners of valid accounts, and I can imagine that being possible - if the system is designed that way. This would be similar to group signatures, etc. But without an according setup, I don't see any way to achieve your goal.

Regarding your idea with the commitments and the EC public key:

You have two Pedersen commitments $a = g^xh^{r_1}, b = g^yh^{r_2}$ and then $c = G^nH^{r_3}$, which is like a Pedersen commitment but not in a prime order group but an elliptic curve.

Now, regardless of what $x$ and $y$ actually are, $a$ and $b$ could potentially be any element of the group, because the Pedersen commitments are perfectly hiding. So maybe you can generate $G^nH^{r_3}$ somehow from $a$ and $b$, but that will definately reveal $n$ itself and it has actually no relation to $x$ or $y$.

the proof that you have knowledge of the private key is the signature.

you're basically asking if the hashed public key(ie. the Bitcoin Address) can be used to verify a signature and the answer is no. The hash destroys the information in the public key.

btw- you can prove ownership of a non-spending bitcoin account by endorsing a plaintext and publishing the signature. The standard Bitcoin wallet has this feature last I checked.


Why are password database breaches bad if cryptographic hashes can't be reversed? If companies such as Facebook store our passwords as hashes, when they are leaked how can this be a threat to the users? I thought of it because nowadays we do not have computational power to break those hashes, so how can a criminal use those hashes against the users?

Users have a habit of choosing passwords badly so that they can be guessed much more easily than cryptographic keys, requiring (say) only a trillion ($10^{12} \approx 2^{40}$) guesses on average instead of a duodecillion ($10^{39} \approx 2^{128}$, or thousand sextillion in the long scale) guesses on average.  Users also have a habit of reusing passwords from site to site, like using the same password for Facebook and Gmail.

Suppose I'm trying to break into your Gmail.  There's only a limited rate at which I can test guesses for your password.  Even if I can narrow your likely passwords down to a trillion possibilities, I can't try more than a few passwords every second at Gmail—even if I had a colossal botnet around the world to avoid IP-based rate limits, and even if I did it in bulk to many targets to avoid account-based rate limits, I'd still be limited by network bandwidth.

But if Facebook's password database gets breached—even if they do everything right like using salts to thwart rainbow tables, using argon2id to raise the computational cost of testing a guess, using OPAQUE to thwart adversaries on the network—then I can try guesses without using the network.  No more rate limits to work around.  No more network bandwidth to worry about.  No more botnet to manage.  I can try guesses offline using my supercomputer cluster tucked away in my evil lair built into the simmering underbelly of a volcano powering my machinations with geothermal heat while sipping at my martini and cackling evilly.

And once I have confirmed a guess for your Facebook password I can try it at Gmail.

There are some mistakes that Facebook could do to make it worse:

Facebook could fail to salt their password hashes uniquely per user.

Then I can search for one of many passwords given their hashes even faster using multi-target attacks like rainbow tables[1] in parallel[2]; if the cost to find one password given its hash is $C$, the cost to find the first of $t$ passwords given their hashes is $C/t$, and the time to find them can be as little as $C/tp$, as long as my volcano supercomputer lair is parallelized $p \geq t^2$ ways.
Facebook could fail to use a costly password hash like argon2id, and instead use MD5.

Then the offline computational cost to test a single guess is as cheap as computing MD5, which costs a few hundred cycles on a typical CPU and negligible memory, in contrast to argon2id which can be scaled to cost billions of cycles and gigabytes of RAM and multiple CPUs in parallel according to the legitimate user's available resources.  This lowers the cost $C$ to find one password and the cost $C/t$ to find the first of $t$ passwords.

In practice, Facebook probably doesn't offload the password hash to the user's computer, so they probably won't use argon2id with billions of cycles of CPU time and gigabytes of RAM and multiple CPUs in parallel, but they will probably use something more expensive to compute than MD5.
Facebook could use a hash that fails to have preimage resistance.

This one is a stretch because essentially no major hash function with advertised preimage resistance has ever been broken[3] (archived).  But if Facebook—for some inexplicable reason—used 2-pass Snefru to hash passwords, then in principle there may be a shortcut to finding a password given its hash more cheaply than just trying passwords until one works[4].
Facebook could just accidentally log their passwords in cleartext.

Well, this one actually happened[5], but Facebook swears that the logs were visible only inside Facebook and that nobody breached Facebook and that nobody inside Facebook would ever dream of abusing insider information like that[6] (archived 2019-06-19), and disclosed it on a night of big news of a long-awaited drama in United States national politics[7].

Note that while it may not pose a threat to the user currently, due to hash functions being computational infeasible to invert. This may not be the case in the future. For example if quantum computers are used and an attacker has your SHA256 hashes and you have not changed your password. It’s better that the attacker has the least amount of information as possible.

If you don’t need to expose it, it would be wise not to.


Can cryptography be used to hide routing information from the router? If Alice wants to talk to Bob and she has to involve a third party system run by Carol to establish, and possibly maintain, communications, then Carol knows that Alice and Bob communicated with each other.

Chuck sneaks into Carol's exchange, and now knows that Alice and Bob are talking to each other.

Carol decides to start a new exchange with new technology, with the primary purpose of never knowing who is talking to who, and she needs to figure out how to do this.

If Carol runs an exchange that is unlimited communications (meaning no per-transaction billing) then she has no business need to know who talked to who, or for how long, as long as both ends are authenticated to her servers.

So the question is:

Is there a way for Carol to design her new network/exchange/endpoints so that her equipment can route and connect two individuals on that service without knowing who is talking to who?

Obviously the service would need to be handling a lot of traffic, and the traffic would need small random delays so you couldn't simply watch the time that Alice puts in a request to the time another request is output and assume that's her outgoing connection.

But I still don't see a way to handle the actual routing and call connection in a way that prevents anyone from seeing who is communicating to whom.

I'm wondering if there's some cryptographic principle or method that might help with this.  So far all my attempts result in one point in the process where both the sender and recipient are known.

The solution is called onion routing; the gist of it is that there are a number of anonymising servers; when Alice wants to send a message to Bob, she picks a random route through a number of the servers; she then repeatedly encrypts the message for each hop, and sends the encrypted message (which states only the first hop in the clear) to the first server.

The first server then decrypts the message, which reveals the second hop.  It then sends the message to the second hop (batching it with a number of other messages, so someone cannot correlate incoming and outgoing messages).

The second server, again, decrypts the message, which reveals the third hop; and then batch-forwards it to the third hop.

This continues until we get to the last server, which decrypts the message, which reveals the actual destination (Bob) it then batch-forwards it to B0b.

Bob then decrypts the message, this reveals the message that Alice originally sent.

There are a number of subtle points; these points are well studied in the literature.

Now, because of all the above 'batch-forwarding', this doesn't work for real-time communication; for messages that don't mind some unpredictable delay, it's workable.

Once they are practical, you may use , homomorphic encryption too ! Since it allows computations over encrypted data. the routes can be encrypted but still the traffic can be routed


How to design a secure challange-response authentication protocol? I am implementing a custom challenge-response protocol to authenticate a client to a server. Mutual authentication is not required, i.e. the server doesn't need to be authenticated to the client.

The protocol works over TCP. Client and server are in a LAN (not over the internet). There is only one server and only one client. The authentication is designed as follows:

$S \rightarrow C : N$

$C \rightarrow S : \{N\}_K$

Where the server $S$ creates a 128-bit random number and sends it as nonce $N$ to the client $C$. The client encrypts the nonce with AES-192 with the pre-shared key $K$ and sends it as response to the server. Then the server decrypts the message and checks the nonce.

Questions:

Is this protocol design secure?
What would be the advantage to use HMAC (or any other MAC) instead of AES encryption?
Did I miss something?

Is this protocol design secure?

See below.

  What would be the advantage to use HMAC (or any other MAC) instead of AES encryption?

HMAC was originally proposed as a construct that turns a Merkle-Damgaard hash function based on compression functions built from block ciphers, into a message authentication code. Although there's no decryption in HMAC, you can actually easily replace your AES decryption-based authentication with comparing HMAC-signed tags.

  Did I miss something?

What you're doing is essentially an authenticated security transport without confidentiality.

What you're missing is that you didn't authenticate the exchange following the initial authentication - this allows for connection hijacking, arbitrary injection of data packets, and more.

Therefore, you should use HMAC+[hash] or CMAC+[block cipher] to authenticate all of your messages exchanged, and also keep a counter as a state to detect duplicate packets and message replay attackes.

Is this protocol design secure?

This design says that server sends a nonce which the client gladly accepts. How does the client knows that nonce is coming from the expected server?
There is no integrity check performed for the nonce sent by server.

Encryption will only provide the confidentiality. It would be desirable if the data is also added with MAC (such as CMAC) for integrity; this should complete the design and make it more robust.


Best way, how to convert 32-byte Keccak hashes to positive numbers up to maximum? I have 32-byte Keccak hashes and I have some maximum number, for example 500, how to uniformly convert those hashes to pseudo-random positive numbers up to that maximum?
I mean I have for example 100 quite random hashes and I want to distribute them so the result would be something like 80 numbers hit once, 19 twice and 1 hit three times (I guess something like that), somehow uniform distribution.
The maximum can be over 32-bits, so I need to use 64-bit integers.

Some approaches come to my mind:
a) always take first 8 bytes, convert them to 64-bit integer and use modulo 500 on them,
b) sum 1st 8 bytes, 2nd 8 bytes, 3rd 8 bytes and 4th 8 bytes to 64-bit integer and use modulo 500,
c) something better?

I know that modulo is not the best for uniform distribution, because it slightly prefers numbers at the beginning of the range, but I think I google how to overcome that by myself and I think it's not even a big deal.

The other thing I am not sure about is whether all the bits in Keccak hashes are quite uniformly distributed, but I guess they should be. I hope that some bit doesn't favor 0s or 1s so some numbers don't get an advantage during my conversion.

Your "32-byte Keccak hash" doesn't look like a canonical, binary Keccak output, but rather appears to be encoded with some Base64 variant—to me it appears to be the MIME version.  Your comments on the matter confuse me whether that is the case or not; you should check your language or library's documentation.

If it's Base64 then it appears to be encoding a 18 bytes of raw binary output, which is 144 bits.  This is a unusual output size.  I would double check how your software is generating that output, and verify that all of that Base64 string really reflects a 144-bit Keccak output, and that there aren't some constant bytes being prefixed or suffixed to it.  Again, your description and comments are not helpful in this regard.

Taking the modulo is fine in practice if you do it over a large enough input set.
 Appendix B of NIST SP 800-185 contains a recommendation that uses modulo to convert the output of an extendable output or variable length hash function into a near-uniform natural number $0 ≤ n < R$ for arbitrary $R$.  The trick is that they make sure to do it over a hash output that is at least 128 bits longer than the number of bits needed to encode values in the output range:

Compute $k = \lceil\log_2(R)\rceil + 128$, where $\lceil\log_2(R)\rceil$ is the number of whole bits needed to encode $R$ distinct values.  For $R = 500$, this is $k = 9 + 128 = 137$.
Hash your input to an output $Z$ with length of at least $k$ bits.  Since your outputs are at least 144 bits, they meet this requirement.
Convert $Z$ to some "bigint" data type (arbitrary precision integers, check library support in your language; e.g., in Java it's BigInteger).  The bits_to_integer algorithm they detail in the document just parses $Z$ as a binary numeral with least significant bits first, although that later detail is not critical (e.g., Java BigInteger parses them in the opposite order, and that's just fine).
Take $N = \mathit{bits\_to\_integer}(Z) \mod R$ as your result.

The trick that allows them to use modulo is that they're willing to accept a biased distribution if they can guarantee the bias is astronomically small.  That's why they insist on taking a hash output 128 bits longer than the number of bits needed to encode $R$.  Suppose we used $R = 500$ but $k = 9$ (instead of the recommended $k = 137$).  The problem here is that since $2^k = 2^9 = 512$, when you take the modulo, 488 of the values have a probability of $1/512$ but 12 of them have a probability of $2/512$—they're twice as likely as the others.

Now suppose we take $k = 10$ instead, so $2^k = 1,024$.  Now when you take modulo 500, there are 476 values in the range have a probability of $2/1,024$ but 24 of them have probability of $3/1,024$—they're only 50% more likely than the rest.  For $k = 11$, $2^k = 2,048$ so you get 452 values with probability $4/2,048$ and 48 with $5/2,048$ (only 25% more likely), and so on.  By the time you get to $k = 137$ the bias is negligible; footnote 12 of the appendix gives:

$$
|\mathrm{Prob}(N=t) - 1/R| ≤ 2^{-w}
$$

...where $w ≥ \lceil\log_2(R)\rceil + 128$.

Why not use method in the format keeping encryption.
Sorry, it is format-preserving encryption. This is the wiki. https://en.wikipedia.org/wiki/Format-preserving_encryption
Its method can make the probability of each number be the same.


Looking for cryptographic secure hash algorithm(s) that produces identical root hash for differently sliced hash list I have a scenario similar to the one described in Wikipedia: hash list, but with a twist. I'm looking for a cryptographically secure hash function that would create the same root hash for the same file, no matter how the the file is chopped up for the individual hashes in the list.

E.g. case 1: File is divided into 3 parts; the hash list consists of the hashes for the 3 parts; the root-hash is computed from the 3 hashes. case 2: Same file is divided into 2 parts; the hash list consists of the hashes computed for the 2 parts, the root hash is computed from the 2 hashes. Since it is the same file I want the root hash to be the same.

Is this doable (maybe with some restrictions on number and size of file parts)?

[Edit]
Specific use case:
My system stores files for users. Large files are usually sent / stored in smaller chunks (currently I don't control in which way the files are split up into chunks). Each chunk is encrypted beforehand by the client, but accompanied by a hash of the unencrypted content. I now would like to know if two users upload the same file (as this allows me to do some optimization) without having to know the content of the file. So if I could compute a "hash" of the whole file by using the individual chunk hashes I could easily achieve this.

A Hash Tree is meant for that. A binary tree seems fit. I'll restrict the description to something directly derived from SHA-256 (256-bits output, 512-bit hashed per round).

A parameter n>0 is selected, defining a "superblock" size of n*512 bits. Say 8192 bits (1kB, for n=16); n=1 works, but a higher value improves computing efficiency markedly.
The file is padded as in SHA-256, and conceptually organized into m superblocks of that size (the last superblock's size might be shorter, but is mutiple of 512 bits; the padding might be in the last superblock, or span the last two superblocks).
The file is chopped in segments of consecutive superblocks, with the limit of segments on superblock boundaries. Each computation point is assigned a segment which it receives (or generates and pads).
Each computation point separately hash each superblock in its assigned segment, using SHA-256 less padding. Each superblock requires n hash rounds (except the last which may require less). Most of the rounds are performed here (exactly as many as for SHA-256 of the whole file), in a distributed manner.

All the hashes obtained at step 4 form the m leaves on top of a single overall binary tree with a 256-bit hash at each node, and structure independent of how the file was chopped. Each of the m-1 non-leaf node of the tree will be the hash, obtained with one round, of the 512 bits in the two nodes linked on its top-left and top-right. The bottom node of the tree will be the final hash. It will be independent on how the file was chopped at step 3, because the computation will be performed according to the same tree regardless of the chopping.

[drawing of tree needed]

All branches in the tree join adjacent levels, except on the right where the j+1th level from the top is skipped when the jth lower-order bit of m-1 is 0.
The computation point responsible for a segment computes the hashes for nodes which have all their leaves assigned to that segment, and must keep the others. This needs precise organization [and is left as an exercise to the reader; my earlier description was flawed].
Each computation point returns its partial result. That will include Ceil(Log2(k+1)) 256-bit hashes at most, for the partial hash of k superblocks. If the communication is centralized, the central point finishes the calculation, re-hashing according to the same binary tree as necessary. With decentralized communication, it is advantageous to aggregate partial results with a peer handling a segment of the file just before or after, which might allow to perform slightly more of the work.

Note: Computations can be interleaved to reduce storage requirements. There is a total of m-1 extra rounds in steps 5 and 6, an overhead of about 1/n, distributed in part.

I have a way, but it's really awful. You can individually hash the combination of each byte's position in the file and the content of that byte, and then XOR all the hashes together.

If you have some control over the block arrangement, you can do a bit better. For example, if the blocks are always at least aligned on 1KB boundaries, you can individually hash each KB using its offset into the file as a HMAC key. Then XOR all the block hashes together. You can accomplish the XORs any way you want, so you can XOR each block and then XOR all the blocks, allowing a block of any size to carry a fixed-length hash value that can easily be combined.

Note that XORing hashes together weakens the security properties of some hashes. I would not recommend this technique if it has to resist a deliberate attack specifically intended to defeat this algorithm. It may take an expert to assure you that the resulting hash algorithm truly is a cryptographically secure hash algorithm


How can I create a block cipher of a reduced size given a fixed length block cipher? I've been reading papers on variable sized block cipher constructions based on fixed-length block ciphers, and they tend to focus on increasing the block size. They either gloss over or speak too generally about decreasing the block size. (Or I'm just not getting it, which is possible)

On the Construction of Variable-Input-Length Ciphers
Efficient Constructions of Variable-Input-Length
Block Ciphers

While these are certainly helpful, I also need a way to encrypt a size much smaller than the usual block ciphers. For example, a credit card has 16 digits, which can be represented in 54 bits. To encrypt a credit card number to another one would require a 54-bit block cipher. (The 54-bits could be brought even lower if you consider that the first and last digits are not random)

Is there a way to do this in such a way that the security isn't brought below the chance of simply guessing the plaintext?

If I understand your problem, I think the best way would be to pad the plaintext bits to 128 bits (8 bytes) with zeros and then use a strong block cipher like AES (Rijndael). Of course, then your ciphertext will be 128 bits instead of the 54 (or whatever) you started with. You can trim these trailing zeros after decryption.  If you want the ciphertext to be the same length, you'll have to use a stream method, but which will not be as strong.


How to construct the blind factors in practice? I'm Implementing a protocol that uses masking techniques (or blinding factors), so we can mask a value $y_0$ as $m_0=y_0 \cdot r_0$ where $y_0 \in \mathbb{Z}_p$ and $r_0 \stackrel {R}\leftarrow \mathbb{Z}_p$ (let $_p$ be a prime number) and the $m_0$ can be unmasked as $m_0\cdot r^{-1}_0=y_0$ at any time.

My Question is: what function do I need to use to get $r_0$ (or $r_i$ in general)?

Can I Use Pseudo-random generators (PRG)? Why?

Blinding technics are well know now to defeat most attacks against SCA.
You need a random number generator (True or Pseudo) to generate unpredictable random $r_i$.
Additionnal precautions against Zero Attacks values can alo be taken.
Try this: $m_0=y_0 \times r_0 \; + \; r_1 \times p \; mod \;(r_2 \times p)$


What does $\langle A, B\rangle$ mean? I'm reading about CL-PKC and in Al-Riyami's FullIndent, I find some notations I must be sure to understand, to well explain it in my report.

  This algorithm takes paramsand $A$'s secret value $x_A$ as input and
  constructs $A$'s public Key $P_A$ like this :

  $$P_A = \langle X_A, Y_A\rangle$$

  With $X_A=x_A P$ and $Y_A = x_A P_0 = x_a s P$

Does $\langle A, B\rangle$ mean the concatenation of $A$ and $B$ ? If yes, why not using the || operator ?

From context, it appears $\langle A,B \rangle$ simply denotes (some value unambiguously encoding) the pair of values $A$ and $B$.

In general, when discussing high-level protocols, no specific encoding for such pairs (or more complex tuples of values) is specified.  It is simply assumed that we can unambiguously store and transmit such structured data somehow, but the specific manner in which this is done is considered an implementation detail.

Of course, an interoperability standard may indeed need to specify such an encoding, especially if such data structures are to be processed by cryptographic primitives that are defined as operating on (bit or byte) strings, with the expectation that independent evaluations of the primitive on the same structure should yield the same canonical output.  Some standard encoding schemes include e.g. csexps or the various ASN.1 encodings, although it's also common for specific interoperability standards to specify their own custom encoding schemes.

Note that, even if $A$ and $B$ are both strings, the pair $\langle A,B \rangle$ can not generally be unambiguously encoded merely by concatenating $A$ and $B$ together, since concatenation may introduce ambiguity when the length of the strings being concatenated is not fixed.  For a simple example, $10 \,||\, 1 = 101 = 1 \,||\, 01$.  That said, if the length of either $A$ or $B$ (or both) is fixed, then $A \,||\, B$ can indeed be a valid unambiguous encoding of $\langle A,B \rangle$.

Triangular or angle-brackets represent inner product in linear algebra but it has nothing to do with the same notation in cryptography. Probably, that's why you're confused about it.

I think, here it's used to show that $P_A$ "is made of" $X_A$ and $Y_A$. The reason I think so is that, there's such usage of angular brackets:

$params= \langle  G1, G2, e, n, P, P0, H1, H2 \rangle$


Berlekamp Massey Algorithm I am trying to solve the BM algorithm to find the shortest LFSR and the feedback polynomial but i keep getting stuck. Is there anybody who could solve any binary code so the steps could be little clear. I had seen the algorithm on Wikepedia but too many letters without any implemented examples are very confusing for me. I would be very grateful if someone could explain the steps with actual numbers. Any numerical example would work.


Can I dynamically calculate an appropriate number of iterations for PBKDF2 based on the system time, rather than using a fixed value? Could you choose the number of PBKDF2 iterations based upon the system time?

I've heard a few people recommend that the number of iterations for PBKDF2 should be doubled every two years (starting with the recommended 1000 iterations in the year 2000 when PKCS #5 was released).

Theoretically at least, you could determine the ideal iterations through an equation based upon the current time. Perhaps something like:

year = <current time in years>
exponent = (year - 2000) / 2
iterations = 1000 x (2 ^ exponent)

Which would give a value of about 115,196 iterations at the time of writing.

Assuming that:

The system clock can be trusted.
The number of iterations is stored with the hash, so that hash verification is still possible.
Safeguards are in place to stop the system attempting to hash with a ludicrous number of iterations.
You continue to monitor the actual time taken to hash passwords on your specific hardware.
You regularly upgrade hardware to keep up with the increasing performance requirements.
You choose an appropriate underlying hash algorithm.

Would such a system be safe and practical?

Of course you can - but as to whether or not it's a practical or advisable idea, I don't think so.  It's not really prudent to implement crypto systems/protocols and assume that they'll be fine in 10 years.

Cryptography is a dynamic field that changes rapidly; algorithms get broken, hardware improves, governments try to undermine the field, and attacks only ever become more sophisticated.  The only way to ensure the security of your system is to stay abreast of what's happening in the crypto/security world, and to adjust your system/protocol accordingly.  For example, despite the recommendation of doubling PBKDF2 rounds periodically, many people in the community now recommend a memory-hard PBKDF like Scrypt instead, making PBKDF2 more or less redundant (although not quite, as it's used internally in Scrypt, and in systems where memory is not available).

Your proposal does have an upside though: a vast majority of security/crypto protocols get implemented and forgotten about.  Look at the linked-in fiasco for example - at the time of designing the system, the architect may have (however erroneously) thought that a saltless sha1 hash of the user's password would be sufficient security.  These days, the idea of a prominent website doing this is unthinkable (hopefully).  So in this sense, your proposal does at least attempt to stay up-to-date, which in lieu of a static system, is better than nothing.  However, I think that continuous scrutiny and a more "hands on" approach is preferable.

Your idea and algorithm look plausible to me. The round number increase according to Moore's Law. Twice the performance every two years is a conservative but good estimation. By the way you should add a comment to the code that explains the rational. Future developers will be very grateful.

You should keep in mind that every extra round makes it harder to crack passwords but makes it also easier to DDoS your service. After all PBKDF2 consumes lots of CPU resources. scrypt is even more problematic. It's designed to require more memory, too.

Almost 120k rounds are a bit excessive, though. I'm using a library that suggests 64k rounds for PBKDF2-SHA-1 and 12k rounds for PBKDF2-SHA512. These days I would start with SHA256 or SHA512 as pseudo-random function. You need fewer rounds for the same CPU time and the key space is large (32 or 64 bytes instead of 20).

Further more I like to suggest two modifications to your code.

1) Instead of a fix and linear growth you could measure the performance of your current hardware. At startup your applications measure the run time of the key derivation function and increase the round count by 5,000 (or so) until you reach a good value. clock_gettime(CLOCK_PROCESS_CPUTIME_ID, res) gives you good resolution. Of course you need to make sure that the round count is within a sane margin.

2) When an user logs into your site, compare her password hash's round count with the current round count. If the value is lower than upgrade the password information with an increased round count. After all it's the only time you have access to the unhashed password.