21 Replies Latest reply on Jul 14, 2011 3:09 PM by -==cfSearching==-

    Calculating combinations of a key

    ACS LLC Level 1

      I want to protect accounds by introducing a key, and I need to calculate the potential combinations

      so that I am happy with the amount of potential combinations.

       

      I will use numbers 0-9 and characters A to Z .. so 36 characters in each column.

       

      Example: 65TG9

       

      Does anybody know where I might find an online calculator that I can use to check the number of combinations?

       

      I need to let it know there are 36 characters, and then test the length of the string to get it up to a big enough number. I'm just trying to stop overkill, no point having a huge UUID if I don't need it

       

      Thanks

       

      Mark

        • 1. Re: Calculating combinations of a key
          Owain North Level 4

          Surely it's just 26 (letters in alphabet) multiplied by 26 again 35 times, ie 3.34E49?

           

          Unless I've misunderstood. Or my maths is crap.

          • 2. Re: Calculating combinations of a key
            ACS LLC Level 1

            I'm not so sure

             

            Let's go with an easy example

             

            Let's say I have a combination lock that has 1 and 2 on the barrel, and I have two barrels

             

            that would give a potential

             

            1 - 1

            1 - 2

            2 - 1

            2 - 2

             

            So 4 combinations. If I add an extra barrel

             

            1,1,1

            1,1,2

            1,2,1

            1,2,2

            2,1,1

            2,1,2

            2,2,1

            2,2,2

             

            So 8 possible combinations, unless I messed that up

             

            so 2 with 2 = 4

            2 with 3 = 8

             

            ummm

             

            I think there is a formula that involves a triangle LOL.. I was not listening in school that day.. something about having to minus 1 for every row

             

            Maybe it involves "to the power of - minus something or other"

             

            There must be an online calculator somewhere!

             

            Mark

            • 3. Re: Calculating combinations of a key
              Dan Bracuk Level 5

              Regarding " no point having a huge UUID if I don't need it"

               

              They aren't that big, and they are available.

              • 4. Re: Calculating combinations of a key
                ACS LLC Level 1

                Hi Dan,

                 

                I just don't think I need it. I'm planning on a large amount of users, and each one will need a record. This will be publically available, so I don't want to use actual CF generated UUID's because they are too similar when they come from the same server, so if you have one, you're halfway there on another one.

                 

                What I'm going to do is seed and make my own random string, and match that with the UID of the user, so the UID and string would have to match, that way it won' matter if in some bizzare situation it randomly creates two identical strings, because the UID's would not match you'd need both

                 

                I want to guage the number of combinations based on a much smaller string.

                 

                36 characters (0-9 and A-Z) and maybe just 8 or 10 characters. I have a feeling that would give me millions of combo's which would work and cut down the storage requirements at the same time

                 

                Thanks

                 

                Mark

                • 5. Re: Calculating combinations of a key
                  Adam Cameron. Level 5
                  This will be publically available, so I don't want to use actual CF generated UUID's because they are too similar when they come from the same server, so if you have one, you're halfway there on another one.

                   

                  Oh dear.  UUIDs are called UUIDs for a reason.  Universally Unique... errr... IDs.  But the key part is "universally unique".  And really?  They are.

                   

                  To suggest that a person could possibly intuit one UUID based on another UUID from the same server is... um... "ill-informed" shall I say.

                   

                  There are UUID algorithms that use the server's MAC address as a part of the result (hence the similarity you're seeing on a given server), but the rest of it is based on (for example) the clock ticks in 100s of nanoseconds, a random component, and a sequence number in case there's a crazy situation in which the same random number is resolved in the same 100 nanosecond period.  So very very very (and continue the "verys" for a while) unlikely to repeat.  And also bear in mind that UUIDs are absolutely *not* random (universally unique != random), so there's a strong guarantee of non-randomness there.

                   

                  Contrast this with your idea of a ten-character base-36 random number as a key. At any given moment there's a chance that one number will the the same as the previous number (or another already-used number), and the maximum combinations are 3656158440062976 (statistically: not many).  Compared to the odds of two UUIDs matching being 3.4x10^38.  And that's all UUIDs ever generated.  On all computers.  Ever.  Over 20 orders of magnitude less likely to be reused that your idea.  Even if you remove the random element and just use a sequence (which would be more unique than doing it randomly).

                   

                  As far as storage concerns go... a UUID is a 128-bit number.  16 bytes.  You could store 65000 of them in one MB.  Remember those: megabytes?  It's what we had before gigabytes, just before we went to terabytes. I think 1MB is 1/2000th of the storage my fairly mundane laptop's video card has.  Storage is never a concern when it comes to primary keys.

                   

                  So... yeah... using a UUID is much better.

                   

                  However... UUIDs are unwieldy @ 32 hexadecimal characters long.  If one needs to give one's users an ID that they can remember (but really?  No-one bothers, they just copy and paste) then perhaps take the current time stamp to the millisecond (eg: yyyymmddhhnnsslll), then convert it to base-36 for brevity.  The IDs will be sequential, but not really guessable (given the granularity of the base ID).

                   

                  But whatever you do:

                  1) don't use random numbers;

                  2) don't reinvent the - industry-established, tried-and-true - wheel.

                   

                  --

                  Adam

                  • 6. Re: Calculating combinations of a key
                    ACS LLC Level 1

                    Hey Adam

                     

                    Thanks for the long explaination

                     

                    I do understand how the UUID's work and why UUID's have some parameters that are shared on the same server, but aside from storage, which as you point out is not going to be off the scale, there is also another reason that I have to make these codes as short as I can while still maintaining a suitable amount of storage.

                     

                    It's not really a problem if one record happens to end up with the same code as another, because a hacker would also need to know the UID of the user.

                     

                    User UID:3  -- Key: ABCD12345

                    User UID:5  -- Key: GTFHY6TRE

                    ...

                    ...

                    User UID: 100000 -- Key ABCD12345

                     

                    Even if two users have the same key the hacker needs to hit every uid with their guess at the key, I'm not sure if that poses much of a security issue. I guess thinking about it, it does have a slight risk, if there is a guarantee that the key is always unique then there is no way they could try the above

                     

                    umm

                     

                    Mark

                    • 7. Re: Calculating combinations of a key
                      -==cfSearching==- Level 4

                      I think there is a formula that involves a triangle LOL..

                       

                      Ooh. Math flashbacks ...

                      http://mathforum.org/dr.math/faq/faq.pascal.triangle.html

                      • 8. Re: Calculating combinations of a key
                        insuractive Level 3

                        Its been a while since my last math class, but I'm pretty sure that the equation for testing the possible permutations here would be:

                         

                        (# of unique characters in the set)^(# of positions)

                         

                        e.g.

                        2 characters with 2 positions = 2^2 = 4

                        2 characters with 3 positions = 2^3 = 8

                         

                        with 36 characters, you can go a long way with only a few positions.  quick suggestion though - the times that we've implemented this sort of random character string generator, its always a good idea to leave out certain... shall we say... naughty... letters out of the mix to prevent any user from being assigned a randomly generated obscene key.

                         

                        Now THAT is probably a fairly fun math probelm to solve right there.

                         

                        Obviously not an issue if you are using the key as part of an encrypted/encoded token that no one will ever see but the server.

                        • 9. Re: Calculating combinations of a key
                          insuractive Level 3

                          Also (and I'm sure there's probably a really obvious answer for this) - why not just encrypt the user ID using the plethora of strong encryption options available in CF?

                          • 10. Re: Calculating combinations of a key
                            -==cfSearching==- Level 4

                            Its been a while since my last math class, but I'm pretty

                            sure that the equation for testing the possible permutations

                            here would be:

                             

                            (# of unique characters in the set)^(# of positions)

                             

                            It also depends on how you define "permutation". I do not remember all the distinctions. But there are different formulas depending on whether the order is significant, items can be repeated, etcetera.

                            • 11. Re: Calculating combinations of a key
                              ACS LLC Level 1

                              ahh you are right, I forgot about bad words .. I did remove some letters in a previous site that required this

                               

                              I think the F should probably go for a start!

                              • 12. Re: Calculating combinations of a key
                                -==cfSearching==- Level 4

                                Someone on stackoverflow mentioned Crockford's Base32 excludes the letter U for that reason. I wonder if that covers all bases

                                 

                                http://en.wikipedia.org/wiki/Base32#Crockford.27s_Base32

                                • 13. Re: Calculating combinations of a key
                                  ACS LLC Level 1

                                  well let''s say that you have 0 to 9 and A to Z (although I might take out some letters as above to stop bad words)

                                   

                                  Now that's 10 numbers and 26 characters, so this could be thought of as a combination lock.with a total of 36 "characters" on each barrel

                                   

                                  Now the question is how many rows on the barrel. . so let's say for this argument, 35 of them, so a typical code might look like this

                                   

                                  XAKBSLYWEHCUSSKBUHOOABYTVULHMKNCPBI

                                   

                                  I need to figure out based on the 36 characters in each location, 35 character string, how to formulate the number of permitations or combinations, I know.. I know there's a difference, I believe it's permitations right as order does not matter.

                                   

                                  I don't mind if we randomly happen to create the same code which is highly unlikely but not impossible,because I will also append their UID in the system, so it'll be a combo of UID and KEY, so even if somebody has the same key it won't matter because both must match. If I really wanted to go mental I could throw in a UUID to ensure full uniqeness but that would be overkill

                                   

                                  Mark

                                  • 14. Re: Calculating combinations of a key
                                    ACS LLC Level 1

                                    I put it to the test. letter U will work well

                                     

                                    Any idea how to EASILY omit the letter U from here --> There must be a fancy way in CF

                                     

                                    <CFSET loginkey = "">


                                    <CFLOOP INDEX="random1" FROM="1" TO="35"><CFSET loginkey = loginkey & #chr(RandRange(65,90,"SHA1PRNG"))#>

                                    </CFLOOP>

                                    • 15. Re: Calculating combinations of a key
                                      insuractive Level 3

                                      With a 36 character set and 35 positions to play with, as long as you don't care what order the characters come in you have 2.95x10^54 different combinations.  But again, I'm wondering if this istn't over kill.  Couldn't you just append a checksum to the ID, encrypt the whole thing and use that as the key instead of trying to generate your own token system?

                                      • 16. Re: Calculating combinations of a key
                                        ACS LLC Level 1

                                        could you post example code? I'm not sure how to do that


                                        • 17. Re: Calculating combinations of a key
                                          -==cfSearching==- Level 4

                                          Now the question is how many rows on the barrel. .

                                           

                                          If you want to do the math, the cheezy link I posted earlier should have the different formulas. Maybe even online calculations. But using a UUID, or something built in, makes more sense to me.

                                           

                                          Message was edited by: -==cfSearching==-

                                          • 18. Re: Calculating combinations of a key
                                            ACS LLC Level 1

                                            this will be posted inside a URL, so it is visible. if it was an internal identifier I would have just gone with UUID, but I don't like the UUID because although it's guaranteed to be unique, it takes a lot of parameters from the server that make many of the characters the same so many can be stripped of.so although it has a huge combination, if you remove the characters that are typically the same it's a lot less than me making me own

                                            • 19. Re: Calculating combinations of a key
                                              insuractive Level 3

                                              Something like this (assuming your IDs are numeric):

                                               

                                              <!--- build a checksum that defines a set relationship between the original value and the value that is encoded. That way you can decode the encrypted value and/or check your work later --->

                                              <cfset sUnencryptedValue = "#myID#,#(myID + 999 MOD 11)#>

                                               

                                              <!--- Generate secret key to use to encrypt/decrypt.  Typically you would store this somewhere if you ever need to decrypt this value --->

                                              <cfset sKey = GenerateSecretKey("DESEDE")>

                                               

                                              <cfset sMyEncryptedString = Encrypt(sUnencryptedValue, sKey, "DESEDE", "Hex")>

                                               

                                              At the end of which you have a unique value, encrypted using Triple DES (feel free to chose a different algorithm) that is encoded as a hexidecimal string so you know its URL safe.  Alternatively, you could use Base64 or UUEncode.

                                               

                                              As long as your checksum calculation is sufficently complex and you are careful with your key generation and your encryption choice, there is no reasonable expectation that your token/key generation will be compromised.  Unless, of course, that the encryption scheme itself has been cracked.  However, either way, its probably more secure than a security-through-obfuscation solution you are trying to come up with here.

                                               

                                              Message was edited by: insuractive

                                              • 20. Re: Calculating combinations of a key
                                                ACS LLC Level 1

                                                ummm.. that looks rather complicated!!!! I think I like my way! ;-)

                                                • 21. Re: Calculating combinations of a key
                                                  -==cfSearching==- Level 4

                                                  All I meant was, I would not reinvent the wheel. I am responding via email. So I cannot see the whole thread, but IIRC there were a few alternatives suggested ?  ie I would use one of those, rather than trying to roll my own ..