[17:45:23] <Moose> Alright.. so I've got a question, or possibly a bunch of them.. depending on how this discussion goes if at all.
[17:46:13] <Moose> I've got these sets of letters and numbers.. somehow they are validated.. 12 numbers and letters.. they don't specifically add up to anything..
[17:46:46] <Moose> Any idea on how I can figure out the algorithm used to generate them? This isn't for any malicious use I assure you, although it does sound like it :P
[17:48:38] <Moose> I do have an unlimited amount of these number sets.
[17:48:45] <Moose> if that matters at all heh
[18:05:30] * BuSyAnToS (n=31749@81-208-83-253.fastres.net) Quit
[18:06:04] <delinka> I'm not sure we'd even suspect some "malicious use" with the limited information you've provided.
[18:06:34] <delinka> can you provide (via a pastebin) some samples of these sets?
[18:06:56] <Moose> Sure one second, I'll gather about 50.
[18:07:29] <Moose> Well, you could suspect malicious use if you knew what they were for.. that's the thing. Although I have a legitimate use for the algorithm.
[18:08:10] <mm_freak> Moose: what's the origin of these letters and numbers? some sort of solid black box? i.e., a function, which you don't have insight into?
[18:08:40] <Moose> Yeah, as far as I know.. I can't find any information on the algorithm.
[18:08:48] -> *delinka* http://pastebin.ca/V0UYFmVa | password = bagels
[18:09:41] <Moose> http://pastebin.ca/V0UYFmVa | password = bagels
[18:09:46] <mm_freak> do you suspect that those letters and numbers are a specific encoding? like base64?
[18:10:08] <Moose> Probably not.
[18:10:18] <mm_freak> if no, find the alphabet, convert it to binary as tight as possible and then try to compress the result
[18:10:36] <mm_freak> if you can compress it, there's probably an easy algorithm behind it
[18:10:39] <Moose> "as tight as possible" ?
[18:11:53] <mm_freak> yes, if the alphabet contains 62 characters, you can encode a string of those characters as a number: a + bx + cx² + dx³ + …, where x = 62
[18:12:14] <mm_freak> then save this number in binary, finally try to compress it
[18:12:34] <Moose> Almost looks like the quartic formula that you wrote there.
[18:12:36] <mm_freak> if compression succeeds for many samples, there is a good chance that an easy algorithm is behind it
[18:13:02] <mm_freak> it's polynomial, not a formula
[18:13:23] <Moose> Right, but meh.. looked different for a moment.
[18:14:12] <mm_freak> like, if you got an alphabet of 12 characters, and you got a string 6, 11, 2, 0, 7, 3, 8, then encode it like: 6 + 11*12 + 2*12^2 + 7*12^4 + 3*12^5 + 8*12^6
[18:14:30] <mm_freak> this results in the number 24779946
[18:15:23] <Moose> Seems to be a 36 character alphabet
[18:16:00] <mm_freak> whatever, save the resulting number in binary and try to compress it
[18:16:10] <mm_freak> btw, a few characters won't be enough
[18:16:26] <mm_freak> you'll need kilobytes or even megabytes
[18:20:23] <Moose> Okay so...
[18:20:29] <Moose> 12 characters per set.
[18:20:38] <Moose> A few thousand sets would work?
[18:22:50] <mm_freak> use as many as you can
[18:23:34] <Moose> Alright.
[18:24:11] <Moose> Thanks for the help, as usual :)
[18:25:10] <mm_freak> well… likely my hints won't help much… it would be much easier, if you could tell us more about the origin of those sampels
[18:25:13] <mm_freak> samples
[18:28:14] * teralaser (n=teralase@unaffiliated/teralaser) Quit
[18:40:30] <Moose> So using the equation you gave me mm_freak, for 12 numbers with a 36 character alphabet.. I'll have a + bx + cx^2 + ... and it'll end up going to the power of 11?
[18:40:50] <Moose> Just making sure, as it seems that's what you meant
[18:41:52] <mm_freak> yes, but 12 numbers are not enough
[18:42:12] <mm_freak> the result (!) should be a few kilobytes in size
[18:42:31] <mm_freak> otherwise the compression ratio is meaningless
[18:43:47] <Moose> I'm confused now...
[18:45:19] <mm_freak> are you sure you've got a 36 characters alphabet?
[18:45:44] <Moose> The characters used are A-Z 0-9
[18:46:03] <Moose> Unless we're mixing something up here, that's what you mean by alphabet right?
[18:46:32] <Moose> xxxxxxxxxxxx should be a string containing the characters A-Z 0-9 which is the alphabet, right?
[18:46:50] <mm_freak> then do the following instead:
[18:47:24] <mm_freak> take as many samples as you can, build a long string from them, where all whitespace is removed
[18:47:39] <mm_freak> i.e. you end up with something like NG378GNUSEG3HOS39ASF…
[18:48:00] <Moose> A concatenation of an arbitrary amount of samples.
[18:48:01] <Moose> Right..
[18:48:05] <mm_freak> yes
[18:48:15] <mm_freak> collect as many samples as possible for this
[18:48:23] <Moose> Okay, and do what with this long string?
[18:48:28] <mm_freak> up to megabytes, if you can
[18:48:39] <mm_freak> then compress the resulting string using bzip2 or 7zip
[18:49:30] <mm_freak> if the result uses less than about 64.624% of the space, then chances are good that there is an easy function behind it
[18:49:52] <Moose> Why 64.624% ?
[18:51:14] <mm_freak> because you need about 5.1699 bits (ln 36 / ln 2) to encode 36 different characters… assuming, the characters are random, you really need that many bits… i.e. you need 5.1699 / 8 of the space used by random full bytes
[18:51:45] <mm_freak> if, however, you need less bits per byte, then the characters are not completely random
[18:52:15] <mm_freak> 5.1699 / 8 ≈ 0.64624
[18:52:41] <Moose> I keep seeing this black box in your messages :P
[18:52:48] <mm_freak> hehe
[18:52:52] <mm_freak> that's basic information theory
[18:53:07] <mm_freak> about the entropy contained in a message
[18:53:12] <Moose> I see.
[18:54:51] <mm_freak> the best generic compression you can achieve for a message with an alphabet of N characters is ln(N) / ln(2) / 8
[18:55:36] <mm_freak> the compression could be better, but that's the average to expect… and that's why you need as many samples as possible to get a meaningful result
[18:56:37] <mm_freak> the generic compression is the worst case compression, i.e. if you do not have any further information about the message, i.e. if the message is random
[18:56:54] <mm_freak> ("has full entropy")
[18:57:33] <mm_freak> what i suggested above (the polynomial method) is equivalent to this one
[19:42:00] * Alpha (n=Alpha@unaffiliated/savant) Quit
[19:43:30] * Alpha (n=Alpha@cpe-76-167-196-164.socal.res.rr.com) has joined ##crypto
[19:49:51] <Moose> So out of all the samples I currently have ( 119 at the moment ) the alphabet is 31 characters
[19:50:07] <Moose> 0 1 4 5 6 7 9 A B C F G H I J K L M N O P R S T U V W X Y Z
[19:50:11] <Moose> That's the set out of these samples.
[19:53:48] <Moose> Heh, apparently a team of students at a university are already trying to come up with the algorithm.
[19:53:54] <Moose> Should I even bother trying myself?
[19:54:51] <mm_freak> why not? but statistical methods like the one i suggested won't work with such a small number of samples
[19:55:18] <Moose> Right, that's why I'm trying to find more.
[19:55:29] <mm_freak> what about those samples? do they have any sequence? or are the samples unrelated to each other?
[19:56:01] <Moose> They seem completely random, aside from the fact that they are always the same length.
[19:57:01] <mm_freak> uhm… better formulation: you gave samples from 1 to 100… does the ordering have any meaning?
[19:57:48] <Moose> They are separate entities, not related to eachother at all.
[19:58:05] <Moose> I thought you were talking about the characters in the samples having relation earlier :P
[19:58:24] <mm_freak> nope
[19:58:54] <mm_freak> but well… it's unlikely that in a set of 119 samples, each 12 characters long, any character from the alphabet doesn't appear
[19:58:58] * Protogenes (n=Protogen@pD95DE872.dip.t-dialin.net) has joined ##crypto
[19:59:14] <Moose> Hm?
[19:59:43] <Moose> So you mean, that it's likely the entire english alphabet is used as well as the numbers 0 - 9? or that it's unlikely for that to be the case out of 119 samples?
[20:00:16] <mm_freak> you said, out of 119 samples, only 31 characters appear… that would be pretty unlikely, if the alphabet really had 36 characters
[20:00:50] <Moose> I see.
[20:01:07] <mm_freak> is it hard to get more samples?
[20:01:47] <Moose> They are limited, but many are available on the internet it seems.
[20:02:23] <Moose> I could also possibly request samples from the university that is doing the same.. although they might not want to just hand them out.
[20:02:55] <Moose> They have no value, aside from they can provide more information.
[20:03:33] * comperr (n=tracking@unaffiliated/comperr) Quit (Remote closed the connection)
[20:03:55] * comperr (n=tracking@unaffiliated/comperr) has joined ##crypto
[20:05:15] <mm_freak> well, what's their origin?
[20:05:22] <mm_freak> or is that unknown?
[20:06:46] <Moose> Origin, like who generates them in the first place?
[20:06:58] <mm_freak> yes
[20:08:05] <Moose> The Coca-Cola bottling company. They are point codes for their prize system. The reason I'm needing to generate my own.. is because I've got somewhere around 200 unreadable ones that have 3 - 5 missing numbers. With the algorithm, I could figure out what they should be.
[20:09:40] <Moose> Now, this is why I've been hesitant to give out the origin. A lot of people look at it all awkward like and say it's a bad idea and that I'm just trying to get free stuff.
[20:10:41] <Moose> Anyways, used ones are available online, this is where I've obtained some.. and others I've already redeemed points for, etc.
[20:11:14] <Moose> Although, solving for the missing.. may be possibly easier than coming up with the algorithm as a whole...
[20:11:34] <mm_freak> so you find them on bottles, and you gain something by knowing valid codes?
[20:11:50] <mm_freak> and once codes are "used", they aren't valid anymore?
[20:11:54] <Moose> Correct.
[20:12:16] <Moose> But it's unlikely that they are randomly generated and stored in a database.
[20:12:27] <Moose> It's more so likely that they are generated from an algorithm, printed, then used ones are stored.
[20:12:37] <mm_freak> most likely there is no algorithm behind them… most likely they get generated at random and saved in a database… used ones are removed from it
[20:12:51] <Moose> Wouldn't that require a ridiculous amount of storage?
[20:13:07] <mm_freak> but if, among a set of 119 samples, only 31 characters appear, chances are that the PRNG they use is not secure
[20:13:18] <mm_freak> depends on how many codes they give out
[20:14:11] <Moose> The codes are printed on every bottled Coca-Cola product and on the inside of every pack of consumables.
[20:14:29] <mm_freak> then the database isn't going to use a single gigabyte
[20:14:42] <Moose> Hm?
[20:14:48] <Moose> It's world-wide, not just by state.
[20:14:57] <mm_freak> in the ideal case, for 1000000 codes your database would need only 7754888 bytes
[20:15:14] <mm_freak> that's less than 8 megabyte
[20:15:40] * Protogenes|DND (n=Protogen@pD95DF526.dip.t-dialin.net) Quit (Read error: 110 (Connection timed out))
[20:15:51] <Moose> Alright, now say... a billion people consume 180 bottles per month.
[20:16:23] <mm_freak> what's the english billion? 10^9 ?
[20:16:33] <Moose> Yes.
[20:17:11] <mm_freak> no problem… realistically that's still only 12 * 10^9 bytes, i.e. less than a terabyte
[20:17:24] <mm_freak> a home computer could do it
[20:17:35] <Moose> Okay, now the lookup time?
[20:17:35] * martman (n=martman@cpe-74-71-208-185.twcny.res.rr.com) has left ##crypto ("Leaving")
[20:17:49] <Moose> It would take over a minute to look it up, no?
[20:18:39] <mm_freak> no, we've got binary trees
[20:19:18] <Moose> So.. it's possible to return a result within a second? Considering a net latency of 120ms.
[20:19:22] <mm_freak> it would take comparisons in average, i.e. a few microseconds on decent servers
[20:19:29] <Moose> Well then.
[20:19:35] <Moose> Hm.
[20:19:37] <mm_freak> it would take about 33 comparisons in average, i.e. a few microseconds on decent servers
[20:19:40] <mm_freak> typo, sorry
[20:20:19] <mm_freak> and that's the unoptimized case… depending on how they generate the codes, the database could be optimized even further
[20:20:33] <Moose> So it's possible to fill in the blanks on the partial codes I have, but it would take a while?
[20:21:16] <Moose> Order being taken in to consideration obviously, having 12 spaces that can be filled, and only 9 of them filled properly. That's a lot of possibilities.
[20:22:27] <mm_freak> 36^3 possibilites, assuming a 36 characters alphabet
[20:23:36] <Moose> So if they aren't using a secure random number generator, what does this mean for me?
[20:23:42] <Moose> Earlier you mentioned that.
[20:24:06] <mm_freak> there are lots of possibilities of what makes up a `valid' code
[20:25:48] <mm_freak> in the case of a large database, you're lost and stuck with bruteforce or with attacking their PRNG, which you don't even know
[20:26:44] <Moose> What about looking at each part of the code having a meaning
[20:27:10] <Moose> Maybe, there are specific characters used at specific indices in the string, and not all characters in the set are valid for different positions.
[20:27:28] <Moose> See what I mean by the that? Not sure how well I explained that.
[20:27:29] <mm_freak> in the case of a truth function, it's the opposite… the database doesn't store valid codes, but invalid codes instead, and a code is valid, if it passes the truth function _and_ is _not_ contained in the database
[20:27:47] <mm_freak> well, that would be very easy
[20:28:12] <Moose> Would it be possible to discover such a method with only 119 samples?
[20:28:12] <mm_freak> you could detect such a pattern easily using classic cryptanalysis
[20:28:51] <mm_freak> possible to discover, impossible to verify… you'll need access to a validity oracle
[20:29:31] <Moose> A validity oracle being something that can say "Valid" or "Invalid" with 100% accuracy?
[20:29:37] <mm_freak> yes
[20:29:46] <mm_freak> i.e. you'll need to ask the coca cola company
[20:30:03] <Moose> Right, their website has such a thing.. but I'm sure they wouldn't like the high volume of requests.
[20:30:32] <mm_freak> nope, most of the analysis work is done offline… you only need to query it occassionally
[20:30:49] <mm_freak> first try some statistical tests, even the most trivial ones
[20:31:09] <mm_freak> like comparing character occurence ratios, maybe with regard to their positions
[20:31:33] <Moose> I'll give that a shot.
[20:31:45] <mm_freak> or try to find `vertical' alphabets… i.e. which characters occur at position two in each sample?
[20:32:03] <Moose> Right. I was considering that as well.
[20:32:04] <mm_freak> etc.
[20:32:07] <mm_freak> be creative
[20:33:15] <Moose> Alright then, AFK a bit.. going to think over a bunch of ways to look at codes and analyze them.
[20:33:32] <mm_freak> but all that is equivalent to or a specialization of the compression method, for which 119 samples are a bit few
[20:34:37] <mm_freak> nevertheless try it out… it gives good hints
[20:36:04] <mm_freak> 119 samples, that's 1428 bytes… theoretically they compress to 922 bytes in average, if they're random and the compression function is perfect
[20:36:56] * Alpha (n=Alpha@unaffiliated/savant) Quit (Connection timed out)
[20:36:58] <mm_freak> if you end up with less than 800 bytes, likely your compression program has found patterns in the codes
[21:28:58] <Moose> ~1398 bytes total, for 100 samples, 14 characters each
[21:29:12] <Moose> 12 + a newline
[21:29:45] <Moose> Drops down to 1039 bytes using LZMA compression
[21:30:46] <Moose> 796 bytes using BZip2
[21:31:07] <Moose> That's the newline though, I'm guessing...
[21:33:06] <Moose> Anyways.. mm_freak: how likely is it that only 7/31 characters can appear in column 1, 14/31 in 2, 12/31 in 3?
[21:33:18] <Moose> Out of 119 samples.
[21:33:42] <Moose> So like, column 1 only has <insert 14 characters here>, and that rule is applied to 119 samples.
[21:33:45] <Moose> etc
[21:37:33] <mm_freak> unlikely, if the codes are random
[21:38:34] <mm_freak> btw, for the compression experiment, you should remove all redundant information
[21:38:38] <mm_freak> including newlines and spaces
[22:13:51] * lemald (n=lemald@h0030ab08ad51.hsd1.ma.comcast.net) Quit ("leaving")
[22:20:13] * Rhamphoryncus (n=rhamph@S010600146c3c91a1.ed.shawcable.net) has joined ##crypto
[22:25:49] * Alpha (n=Alpha@unaffiliated/savant) has joined ##crypto
[22:26:18] * Alpha (n=Alpha@unaffiliated/savant) Quit (Remote closed the connection)
[22:26:52] * aia (n=aia@unaffiliated/aia) has joined ##crypto
[22:30:19] * aia (n=aia@unaffiliated/aia) Quit (Client Quit)
[23:56:50] <Moose> Okay so... one giant line.
[23:57:06] <Moose> 2562 bytes ( LMZA ) 1737 bytes
[23:57:44] <Moose> 2562 bytes ( BZip2 ) 1567 bytes
[23:58:30] <Moose> 2562 bytes ( Deflate ) 1615 bytes
[23:58:58] <Moose> Seems like there aren't many patterns :P
[00:10:28] * Protogenes (n=Protogen@pD95DE872.dip.t-dialin.net) Quit (Read error: 104 (Connection reset by peer))
[00:11:11] * Protogenes (n=Protogen@pD95DE872.dip.t-dialin.net) has joined ##crypto
[00:11:15] * Protogenes is now known as Protogenes|DND
[00:24:10] * brendonw (n=brendonw@66.159.221.21) has joined ##crypto
[00:29:02] * Rhamphoryncus (n=rhamph@unaffiliated/rhamphoryncus) Quit ("Valid HTML! http://validator.w3.org/ | Support ISO 8601! http://www.cl.cam.ac.uk/~mgk25/iso-time.html")
[00:38:14] * aref (n=aref@234.80-203-92.nextgentel.com) has joined ##crypto
[00:49:11] * Protogenes|DND is now known as Protogenes
[00:55:33] * Alpha_ (n=Alpha@cpe-76-167-196-164.socal.res.rr.com) has joined ##crypto
[00:57:23] * Alpha_ is now known as Alpha
[01:44:50] <intgr> Moose: Well, that's a lot tighter than most binary data.
[01:46:40] * Jafet (n=Owner@42.7.111.218.kmr02-home.tm.net.my) has joined ##crypto
[02:06:26] <Moose> and what does this mean?
[02:11:57] <Jafet> Is that line supposed to continue on from something, leading to something?
[02:13:07] <Moose> In response to: [01:44:50] <intgr> Moose: Well, that's a lot tighter than most binary data.
[02:13:24] <Moose> Lemme pastebin the recent conversation.