Talk:Cryptographic nonce

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Cryptography / Computer science  (Rated Start-class, High-importance)
WikiProject icon This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the quality scale.
 High  This article has been rated as High-importance on the importance scale.
Taskforce icon
This article is supported by WikiProject Computer science (marked as High-importance).
 
WikiProject Numismatics / Cryptocurrency  (Rated Start-class, Low-importance)
WikiProject icon This article is within the scope of WikiProject Numismatics, a collaborative effort to improve the coverage of Numismatics articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Start-Class article Start  This article has been rated as Start-Class on the project's quality scale.
 Low  This article has been rated as Low-importance on the project's importance scale.
Taskforce icon
This article is supported by the Cryptocurrency task force (marked as Low-importance).
 

Diagram[edit]

Typical client-server communication during a nonce-based authentication process.
The above diagram, including a cnonce

I propose this diagram as an illustration. Any comments?--Cameltrader 11:36, 24 March 2007 (UTC)

It looks nice, but if you look at digest access authentication the client should also use its own nonce to calculate the hash (and pass it to the server) – please see section 4.9 of RFC 2617. Thanks.  — Lee J Haywood 13:01, 24 March 2007 (UTC)
Right, it says they've put the cnonce there, so that the client can have its own influence on the hash, and so that it be infeasible for a man in the middle to precompute anything and forge the real nonce. The cnonce must be omitted if the server doesn't send a qop directive (see page 11 in the RFC), and the nonce is still a nonce. Besides, HTTP digest access authentication is just an example in this article and it is not the only protocol where nonces are used; for instance, Yahoo! do such a trick in JavaScript for their web-based e-mail service without a client nonce. My diagram demonstrates the simplest form, so I think it is not appropriate to complicate it by tightly following the HTTP digest auth spec. Cheers. --Cameltrader 16:54, 24 March 2007 (UTC)
Hmm, that's interesting – I don't see why anyone would want to omit the client nonce when it's so useful. Your diagram is fine, I was just suggesting a possible improvement. As an aside, I've just implemented my own AJAX variant of digest access authentication, which doesn't needlessly pass back the server nonce (which can be tied to the user name for single sessions). Also once the first authentication is successful, my system agrees a new nonce between the client and server without actually passing it across (it's a hash that includes a new random number that is returned by the server), which is easy because both sides already know what the password hash is, etc. I think this emulates the 'auth-int' qop. Thanks.  — Lee J Haywood 18:04, 24 March 2007 (UTC)
I agree that the cnonce adds another obstacle to an eavesdropper, this is also a good point to include in the article, if we can attribute it properly. The following is obvious from the RFC, but let me think it over again: if someone can intercept the traffic, she can substitute the nonce returned (2nd arrow) with a "special" one, and when the "login" request (3rd arrow) comes in, she must be able to restore the password from the h(nonce + password). Normally, this cannot happen immediately, so the real nonce will expire, and the eavesdropper will have to do some cracking for homework, to obtain the raw password. If there had been a cnonce involved, the eavesdropper wouldn't have had control over the hash addend, and couldn't use any precomputed tables, such as a precomputed dictionary attack (rainbow or whatever) for the "special" nonce. The cnonce just makes life a bit harder for the eavesdropper, but without it the protocol is still hard enough.
I'd also like to point out that I've left out details such as the fact that the password may be salted (this invalidates the dictionary attack) and hashed separately, or that nonces should expire after a certain period.
It would be interesting if someone can provide information about other protocols or application designs where nonces are used, but cnonces aren't. --Cameltrader 11:33, 25 March 2007 (UTC)
I think that I'm right in thinking that digest access authentication forces the server to store the MD5 hash of the user, realm and password (or just the password itself, on a weak system)? I've updated the article to indicate that a salt cannot be applied to individual passwords, as you've suggested above, for that scheme. I think you're right that a salt is better than a client nonce, but hadn't contemplated it until you mentioned it.  — Lee J Haywood 15:23, 25 March 2007 (UTC)
Let's wait for a third opinion. The question is: should we add a client nonce (cnonce) to the diagram? --Cameltrader 16:51, 25 March 2007 (UTC)

Here comes the third opinion (mine that is):

First of all when I teach/explain crypto I usually use the names "client-IV" and "server-IV" or if you will "client-nonce" and "server-nonce". Since that is clearer than just "nonce" and "cnonce".

Secondly, the client-nonce is usually necessary if you want the server to securely identify itself to the client. Since both the client and the server want to know that the other party is not an imposter.

But I think we should start with a simple example. A full example is probably too big for beginner eyes. So we should probably start out with the simplest example and then perhaps have a second image with a more complex example. What I suggest as the simplest example is similar to the first image that Cameltrader suggested:

CLIENT                              SERVER

                                <-  Nonce
Username                   ->
Hash( nonce + username 
  + password )             ->
                                <-  Login ok or failed

Note that since several users might have chosen the same password the username should normally be included in the hash to create the unique combination "username+password".

Now for a big example:

Nonce-two-way.svg
CLIENT                                SERVER

Client-nonce                 ->
Username                     ->
                                  <-  Server-nonce
                                  <-  Servername
Hash( client-nonce 
  + server-nonce + username 
  + password + servername )  ->
                                  <-  Hash( server-nonce 
                                        + client-nonce + username                             
                                        + password + servername )

Note that the server puts the two nonces in another order than the client does to make the two hashes different. Or more common: Both can initiate the hash with some label that is unique to the direction of communication.

The two IVs/nonces are also often used as part of the shared secret that is used for encrypting and MACing the communication. This is for instance done in TLS/SSL. Again then the client nonce is needed so the client can be sure it talks with the right server and not a replay of the server.

Another well known motivation is that in case one of the two nodes has a weak or compromised random number generator it is good if both provide a nonce/IV thus ensuring more randomness in the shared secret. This is especially true if the nonce is not a random nonce but instead is a simple counter since counters might be reused by accident. (Running from a restored backup is the classic example.) Or if the nonce is based on time. Since it is often easy to trick a node into using the wrong time.

--David Göthberg 16:36, 8 April 2007 (UTC)

I notice that the password itself is being used as part of the hash, which implies that the server holds the actual password rather than, say, a hash of it – but perhaps that doesn't matter in a simple example? Also, the motivation for including the user name in the hash is clear for the first example, but less so for the second? Thanks.  — Lee J Haywood 07:18, 9 April 2007 (UTC)
I agree with Lee, the client should return hash(nonce + cnonce + hash(password)). 1111mol (talk) — Preceding undated comment added 11:21, 29 March 2015 (UTC)
About the first example: yes, there may be two users with the same password, but they are expected to obtain different nonces from the server. Inclusion of the username in the hash is alright, except that it doesn't stir in any additional different-ness. This is what I considered when I drew the diagram, I may be wrong.
David, as far as I got it, you propose that we include both examples? The current amount of text is disproportionate to two pictures, unfortunately, but we can put them and expect more prose, anyway... Your second example looks great, I'll try to SVG-ize that later as well. It seems not to be vulnerable to the precomputation attack we discussed above with Lee. I'm not sure about the usefulness of hashing the username and the servername, though. If a real-world protocol uses the same sequence of messages, we can mention that in the picture's description.
Btw, I'd prefer not to call nonces IV-s because it's a bit confusing, but you can judge better.
--Cameltrader 19:22, 10 April 2007 (UTC)

Removed from article[edit]

The word derives from nonce. The n represents an arbitrary number that, for security reasons, will only be used once.[citation needed]

I removed this because it is uncited, I've never seen such a derivation elsewhere, and because the regular English word nonce exactly matches the cryptographic usage, making any other etymology highly suspect. Arvindn 02:38, 25 March 2007 (UTC)

There seems to be a good etymology here... [1].  — Lee J Haywood 09:12, 25 March 2007 (UTC)

How do you prononounce this?[edit]

Do you say "NONce", so it sounds like the word ON, or do you say "n(w)ONCE", like the word ONCE? 198.49.180.40 (talk) 20:35, 21 November 2007 (UTC)

The first -- It's an 800-year-old word. The backformation given as the etymology is now in the very first sentence, but it doesn't make it remotely correct. I've had my fill of correcting such idiocy in Wikipedia, so I'm just going to let it stand. 76.14.60.75 (talk) 03:33, 12 January 2008 (UTC)
Listen here. 46.116.86.242 (talk) 19:43, 7 August 2012 (UTC)

Bitcoin PoW[edit]

The statement regarding Bitcoin's proof-of-work system is not entirely correct. The difficulty factor changes dynamically to prevent an increase or decrease in time taken to find a block[1], not in the amount of bitcoins actually rewarded. The reward for solving a block is halved every 210,000 blocks[2] regardless of how long those blocks take to mine, so coin generation is block sensitive, not time sensitive. Even the difficulty re-target itself is block sensitive, rather than time sensitive, occurring every 2016 blocks[3]. The target is to generate one block every 10 minutes[4] so if, at re-target, it is found that blocks have been generated faster than one per 10 minutes, difficulty increases. Conversely if block generation has taken too long the difficulty will decrease. The confusion is understandable since coins are awarded every time a block is found, so varying the time between blocks will vary the coin generation rate overall, but the specific mechanism mentioned here is used to control block time and the language of the article does not accurately reflect that.

Also, when referring to the project or the application, the word "Bitcoin" is a proper noun and should be capitalized. When referring to some quantity of the currency, it is typically accepted to use the lowercase "bitcoin" or "bitcoins."[5]

I therefore recommend that we change this:

Similarly, the bitcoin block-chain hashing algorithm can be tuned to an arbitrary difficulty by changing the required minimum/maximum value of the hash so that the number of bitcoins awarded for new blocks does not increase linearly with increased network computation power as new users join. This is likewise achieved by forcing bitcoin miners to add nonce values to the value being hashed to change the hash algorithm output. Because cryptographic hash algorithms cannot easily be predicted based on their inputs, this makes the act of blockchain hashing and the possibility of being awarded bitcoins something of a lottery, where the first "miner" to find a nonce that delivers a desirable hash is awarded valuable bitcoins.

To something like this:

Similarly, the Bitcoin block-chain hashing algorithm can be tuned to an arbitrary difficulty by changing the acceptable value range of the hash so that the time between new blocks does not decrease with increased network computation power as new miners join. This is likewise achieved by forcing Bitcoin miners to add nonce values to the value being hashed to change the hash algorithm's output. Because the outputs of cryptographic hash algorithms cannot easily be predicted based on their inputs, this makes the act of blockchain hashing and the possibility of being awarded bitcoins something of a lottery, where the first miner to find a nonce that delivers a desirable hash is awarded bitcoins and the odds of winning that lottery increase or decrease dynamically to maintain a steady block rate.

Opinions?

Enmaku (talk) 18:20, 10 December 2012 (UTC)

References

  1. ^ "Difficulty". The Bitcoin Wiki. Retrieved 10 December 2012. 
  2. ^ "Blocks". The Bitcoin Wiki. Retrieved 10 December 2012. 
  3. ^ "Difficulty - How often does the difficulty change". The Bitcoin Wiki. Retrieved 10 December 2012. 
  4. ^ "Blocks - What is the maximum number of blocks?". The Bitcoin Wiki. Retrieved 10 December 2012. 
  5. ^ "How do we capitalize Bitcoin (or BitCoin or bitcoin)?". The Bitcoin StackExchange. Retrieved 10 December 2012. 

Citations Lacking[edit]

This article is almost entirely missing relevant citations, and contains much unsourced material, so I've added the refimprove tag. I may work on the article over time, but feel free to make changes.

131.204.254.100 (talk) 00:20, 21 November 2013 (UTC)

Requested move 8 January 2015[edit]

The following is a closed discussion of a requested move. Please do not modify it. Subsequent comments should be made in a new section on the talk page. Editors desiring to contest the closing decision should consider a move review. No further edits should be made to this section.

The result of the move request was: Not moved. EdJohnston (talk) 00:20, 16 January 2015 (UTC)



Cryptographic nonceCryptographic N-Once – Please place your rationale for the proposed move here.

  • N as in number
  • once as in one time
  • N-once.

70.79.133.180 (talk) 23:17, 8 January 2015 (UTC)

  • Oppose. "Nonce" is the term actually used for this concept in English. "N-once" is rare and seems to be based on a misunderstanding (the term actually derives from "...for the nonce"). 209.211.131.181 (talk) 05:11, 9 January 2015 (UTC)
  • Oppose. "Nonce" is the the most common term used for this concept from the several crypto-related books that I've read in relation to my day job. —seav (talk) 15:05, 11 January 2015 (UTC)
  • Oppose per the above.  — SMcCandlish ¢ ≽ʌⱷ҅ʌ≼  10:28, 15 January 2015 (UTC)

The above discussion is preserved as an archive of a requested move. Please do not modify it. Subsequent comments should be made in a new section on this talk page or in a move review. No further edits should be made to this section.