[17:45:23] 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] 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] 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] I do have an unlimited amount of these number sets. [17:48:45] if that matters at all heh [18:05:30] * BuSyAnToS (n=31749@81-208-83-253.fastres.net) Quit [18:06:04] I'm not sure we'd even suspect some "malicious use" with the limited information you've provided. [18:06:34] can you provide (via a pastebin) some samples of these sets? [18:06:56] Sure one second, I'll gather about 50. [18:07:29] 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] 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] 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] http://pastebin.ca/V0UYFmVa | password = bagels [18:09:46] do you suspect that those letters and numbers are a specific encoding? like base64? [18:10:08] Probably not. [18:10:18] if no, find the alphabet, convert it to binary as tight as possible and then try to compress the result [18:10:36] if you can compress it, there's probably an easy algorithm behind it [18:10:39] "as tight as possible" ? [18:11:53] 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] then save this number in binary, finally try to compress it [18:12:34] Almost looks like the quartic formula that you wrote there. [18:12:36] if compression succeeds for many samples, there is a good chance that an easy algorithm is behind it [18:13:02] it's polynomial, not a formula [18:13:23] Right, but meh.. looked different for a moment. [18:14:12] 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] this results in the number 24779946 [18:15:23] Seems to be a 36 character alphabet [18:16:00] whatever, save the resulting number in binary and try to compress it [18:16:10] btw, a few characters won't be enough [18:16:26] you'll need kilobytes or even megabytes [18:20:23] Okay so... [18:20:29] 12 characters per set. [18:20:38] A few thousand sets would work? [18:22:50] use as many as you can [18:23:34] Alright. [18:24:11] Thanks for the help, as usual :) [18:25:10] 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] samples [18:28:14] * teralaser (n=teralase@unaffiliated/teralaser) Quit [18:40:30] 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] Just making sure, as it seems that's what you meant [18:41:52] yes, but 12 numbers are not enough [18:42:12] the result (!) should be a few kilobytes in size [18:42:31] otherwise the compression ratio is meaningless [18:43:47] I'm confused now... [18:45:19] are you sure you've got a 36 characters alphabet? [18:45:44] The characters used are A-Z 0-9 [18:46:03] Unless we're mixing something up here, that's what you mean by alphabet right? [18:46:32] xxxxxxxxxxxx should be a string containing the characters A-Z 0-9 which is the alphabet, right? [18:46:50] then do the following instead: [18:47:24] take as many samples as you can, build a long string from them, where all whitespace is removed [18:47:39] i.e. you end up with something like NG378GNUSEG3HOS39ASF… [18:48:00] A concatenation of an arbitrary amount of samples. [18:48:01] Right.. [18:48:05] yes [18:48:15] collect as many samples as possible for this [18:48:23] Okay, and do what with this long string? [18:48:28] up to megabytes, if you can [18:48:39] then compress the resulting string using bzip2 or 7zip [18:49:30] 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] Why 64.624% ? [18:51:14] 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] if, however, you need less bits per byte, then the characters are not completely random [18:52:15] 5.1699 / 8 ≈ 0.64624 [18:52:41] I keep seeing this black box in your messages :P [18:52:48] hehe [18:52:52] that's basic information theory [18:53:07] about the entropy contained in a message [18:53:12] I see. [18:54:51] 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] 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] 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] ("has full entropy") [18:57:33] 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] So out of all the samples I currently have ( 119 at the moment ) the alphabet is 31 characters [19:50:07] 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] That's the set out of these samples. [19:53:48] Heh, apparently a team of students at a university are already trying to come up with the algorithm. [19:53:54] Should I even bother trying myself? [19:54:51] why not? but statistical methods like the one i suggested won't work with such a small number of samples [19:55:18] Right, that's why I'm trying to find more. [19:55:29] what about those samples? do they have any sequence? or are the samples unrelated to each other? [19:56:01] They seem completely random, aside from the fact that they are always the same length. [19:57:01] uhm… better formulation: you gave samples from 1 to 100… does the ordering have any meaning? [19:57:48] They are separate entities, not related to eachother at all. [19:58:05] I thought you were talking about the characters in the samples having relation earlier :P [19:58:24] nope [19:58:54] 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] Hm? [19:59:43] 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] 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] I see. [20:01:07] is it hard to get more samples? [20:01:47] They are limited, but many are available on the internet it seems. [20:02:23] 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] 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] well, what's their origin? [20:05:22] or is that unknown? [20:06:46] Origin, like who generates them in the first place? [20:06:58] yes [20:08:05] 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] 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] 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] Although, solving for the missing.. may be possibly easier than coming up with the algorithm as a whole... [20:11:34] so you find them on bottles, and you gain something by knowing valid codes? [20:11:50] and once codes are "used", they aren't valid anymore? [20:11:54] Correct. [20:12:16] But it's unlikely that they are randomly generated and stored in a database. [20:12:27] It's more so likely that they are generated from an algorithm, printed, then used ones are stored. [20:12:37] 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] Wouldn't that require a ridiculous amount of storage? [20:13:07] 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] depends on how many codes they give out [20:14:11] The codes are printed on every bottled Coca-Cola product and on the inside of every pack of consumables. [20:14:29] then the database isn't going to use a single gigabyte [20:14:42] Hm? [20:14:48] It's world-wide, not just by state. [20:14:57] in the ideal case, for 1000000 codes your database would need only 7754888 bytes [20:15:14] 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] Alright, now say... a billion people consume 180 bottles per month. [20:16:23] what's the english billion? 10^9 ? [20:16:33] Yes. [20:17:11] no problem… realistically that's still only 12 * 10^9 bytes, i.e. less than a terabyte [20:17:24] a home computer could do it [20:17:35] 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] It would take over a minute to look it up, no? [20:18:39] no, we've got binary trees [20:19:18] So.. it's possible to return a result within a second? Considering a net latency of 120ms. [20:19:22] it would take comparisons in average, i.e. a few microseconds on decent servers [20:19:29] Well then. [20:19:35] Hm. [20:19:37] it would take about 33 comparisons in average, i.e. a few microseconds on decent servers [20:19:40] typo, sorry [20:20:19] and that's the unoptimized case… depending on how they generate the codes, the database could be optimized even further [20:20:33] So it's possible to fill in the blanks on the partial codes I have, but it would take a while? [20:21:16] 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] 36^3 possibilites, assuming a 36 characters alphabet [20:23:36] So if they aren't using a secure random number generator, what does this mean for me? [20:23:42] Earlier you mentioned that. [20:24:06] there are lots of possibilities of what makes up a `valid' code [20:25:48] 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] What about looking at each part of the code having a meaning [20:27:10] 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] See what I mean by the that? Not sure how well I explained that. [20:27:29] 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] well, that would be very easy [20:28:12] Would it be possible to discover such a method with only 119 samples? [20:28:12] you could detect such a pattern easily using classic cryptanalysis [20:28:51] possible to discover, impossible to verify… you'll need access to a validity oracle [20:29:31] A validity oracle being something that can say "Valid" or "Invalid" with 100% accuracy? [20:29:37] yes [20:29:46] i.e. you'll need to ask the coca cola company [20:30:03] Right, their website has such a thing.. but I'm sure they wouldn't like the high volume of requests. [20:30:32] nope, most of the analysis work is done offline… you only need to query it occassionally [20:30:49] first try some statistical tests, even the most trivial ones [20:31:09] like comparing character occurence ratios, maybe with regard to their positions [20:31:33] I'll give that a shot. [20:31:45] or try to find `vertical' alphabets… i.e. which characters occur at position two in each sample? [20:32:03] Right. I was considering that as well. [20:32:04] etc. [20:32:07] be creative [20:33:15] Alright then, AFK a bit.. going to think over a bunch of ways to look at codes and analyze them. [20:33:32] but all that is equivalent to or a specialization of the compression method, for which 119 samples are a bit few [20:34:37] nevertheless try it out… it gives good hints [20:36:04] 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] if you end up with less than 800 bytes, likely your compression program has found patterns in the codes [21:28:58] ~1398 bytes total, for 100 samples, 14 characters each [21:29:12] 12 + a newline [21:29:45] Drops down to 1039 bytes using LZMA compression [21:30:46] 796 bytes using BZip2 [21:31:07] That's the newline though, I'm guessing... [21:33:06] 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] Out of 119 samples. [21:33:42] So like, column 1 only has , and that rule is applied to 119 samples. [21:33:45] etc [21:37:33] unlikely, if the codes are random [21:38:34] btw, for the compression experiment, you should remove all redundant information [21:38:38] 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] Okay so... one giant line. [23:57:06] 2562 bytes ( LMZA ) 1737 bytes [23:57:44] 2562 bytes ( BZip2 ) 1567 bytes [23:58:30] 2562 bytes ( Deflate ) 1615 bytes [23:58:58] 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] 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] and what does this mean? [02:11:57] Is that line supposed to continue on from something, leading to something? [02:13:07] In response to: [01:44:50] Moose: Well, that's a lot tighter than most binary data. [02:13:24] Lemme pastebin the recent conversation.