00:00:02 -!- danieljabailey has quit (Quit: ZNC 1.6.4+deb1 - http://znc.in).
00:00:19 -!- danieljabailey has joined.
00:01:01 -!- ATMunn has quit (Client Quit).
00:01:15 -!- ATMunn_ has changed nick to ATMunn.
00:01:23 -!- ATMunn has quit (Client Quit).
00:01:39 -!- ATMunn has joined.
00:09:02 -!- ATMunn has quit (Quit: lol rip).
00:09:12 -!- ATMunn has joined.
00:11:38 -!- ATMunn has quit (Client Quit).
00:11:48 -!- ATMunn has joined.
00:27:19 -!- ATMunn has quit (Quit: lol rip).
00:27:29 -!- ATMunn has joined.
00:39:45 -!- imode has joined.
00:45:53 -!- boily has quit (Quit: ISOCELES CHICKEN).
00:48:12 <doesthiswork> So today I learned that all esoteric languages are actually dialects of Tamil
01:04:53 <imode> dialects of box box box box?
01:06:07 <HackEgo> [U+0BAE TAMIL LETTER MA] [U+0BBF TAMIL VOWEL SIGN I]
01:06:35 <HackEgo> [U+0BB4 TAMIL LETTER LLLA] [U+0BCD TAMIL SIGN VIRAMA]
01:18:17 -!- jaboja has quit (Ping timeout: 252 seconds).
01:27:39 -!- LKoen has quit (Remote host closed the connection).
01:40:32 -!- jaboja has joined.
01:55:08 -!- ski has quit (Ping timeout: 240 seconds).
02:25:31 -!- jaboja has quit (Remote host closed the connection).
02:40:30 -!- oerjan has joined.
03:31:33 -!- Melvar` has joined.
03:32:52 -!- Melvar has quit (Ping timeout: 260 seconds).
03:36:14 <zzo38> If you have a indexed colour picture where each pixel is stored as the index of that colour XOR the index of the colour of the pixel above, and then with RLE, is there a better way to figure out the optimal order of the palette than just by trying each one (which is going to be a lot of possibilities)?
03:48:28 -!- augur has joined.
03:51:57 -!- FreeFull has quit (Ping timeout: 240 seconds).
04:00:35 -!- Sgeo has joined.
04:03:27 -!- Sgeo_ has quit (Ping timeout: 240 seconds).
04:18:14 <\oren\> http://store.steampowered.com/app/643270 good game
04:24:35 -!- Slereah__ has quit (Ping timeout: 240 seconds).
04:46:22 -!- augur has quit (Remote host closed the connection).
05:06:43 <HackEgo> [wiki] [[Tables]] N https://esolangs.org/w/index.php?oldid=53208 * HereToAnnoy * (+1012) created idea
05:09:25 <HackEgo> [wiki] [[User:HereToAnnoy]] M https://esolangs.org/w/index.php?diff=53209&oldid=53207 * HereToAnnoy * (+69) tables
05:19:47 -!- Lymia has quit (Read error: Connection reset by peer).
05:28:47 -!- LKoen has joined.
05:28:48 -!- doesthiswork has quit (Quit: Leaving.).
05:30:22 -!- augur has joined.
05:33:01 -!- LKoen has quit (Ping timeout: 240 seconds).
05:35:35 -!- Lymia has joined.
05:49:36 -!- tswett has quit (Ping timeout: 258 seconds).
05:52:42 -!- tswett has joined.
05:54:15 -!- FreeFull has joined.
05:59:25 -!- Sgeo has quit (Read error: Connection reset by peer).
06:01:51 -!- Melvar` has changed nick to Melvar.
06:03:25 -!- idris-bot has joined.
06:04:09 -!- Sgeo has joined.
06:23:46 -!- sleffy has quit (Ping timeout: 255 seconds).
06:35:04 -!- tswett has quit (Ping timeout: 252 seconds).
07:00:13 -!- imode has quit (Ping timeout: 255 seconds).
07:02:22 -!- FreeFull has quit.
07:24:27 -!- lynn has quit (Ping timeout: 255 seconds).
07:24:53 -!- incomprehensibly has quit (Ping timeout: 255 seconds).
07:25:34 -!- dingbat has quit (Ping timeout: 264 seconds).
07:26:41 -!- dingbat has joined.
07:26:42 -!- incomprehensibly has joined.
07:26:57 -!- HackEgo has quit (Ping timeout: 240 seconds).
07:26:59 -!- lynn has joined.
07:27:13 -!- HackEgo has joined.
07:27:27 -!- Cthulhux has quit (Ping timeout: 240 seconds).
07:29:22 -!- Cthulhux has joined.
07:59:19 -!- Remavas has joined.
08:12:49 -!- augur has quit (Quit: Leaving...).
08:27:54 -!- LKoen has joined.
08:37:05 -!- tromp has quit (Ping timeout: 240 seconds).
09:26:25 -!- oerjan has quit (Quit: Nite).
11:12:06 -!- tromp has joined.
11:34:48 -!- boily has joined.
11:47:53 -!- AnotherTest has joined.
12:26:19 -!- boily has quit (Quit: MIGRAINE CHICKEN).
12:46:59 -!- Remavas has quit (Ping timeout: 246 seconds).
13:09:31 -!- ais523 has joined.
13:36:52 <ais523> whoops, just looked at the sun by mistake, I'm not used to the sky being like this
13:38:43 <ais523> luckily it's very dim in this weather
13:43:55 <lambdabot> EGLL 161220Z AUTO 20016G28KT 9999 NCD 21/15 Q1014
13:44:42 <lambdabot> KSFO 161156Z 00000KT 10SM CLR 14/06 A3011 RMK AO2 SLP195 T01390061 10189 20133 58002
13:46:34 <lambdabot> EGBB 161220Z 18012G22KT 9999 SCT024 19/15 Q1010
13:46:54 <ais523> they're predicting 40mph winds here in Birmingham for a few hours as the edge of the extratropical storm passes
13:47:11 <fizzie> I don't think London's going to see much of that.
13:47:34 <lambdabot> KOAK 161153Z 00000KT 10SM FEW012 11/07 A3011 RMK AO2 SLP196 T01060067 10178 20089 56004
13:47:38 <ais523> fizzie: right, you're further south
13:48:06 <ais523> whereas further west and north they'll get much more of the brunt of the storm
13:48:07 <shachaf> fizzie: The local weather issue here was air quality, not temperature.
13:48:24 <shachaf> Well, that and the fires, a little further north.
13:48:43 <shachaf> But even here the air quality index was worse than Beijing.
13:49:28 <ais523> apparently the reason the sun's so dim at the moment is that the hurricane picked up a subset of the sahara desert (the subset in question is small compared to the sahara desert but large in an absolute sense)
13:50:17 <shachaf> Is it a measurable subset?
13:50:53 <ais523> probably yes in the mathematical sense and no in the practical sense
13:57:49 -!- AnotherTest has quit (Ping timeout: 252 seconds).
13:58:20 <ais523> otherwise it wouldn't have much of an impact on the sun's color
13:58:21 <shachaf> I don't think people would describe a null subset as "large in an absolute sense"
13:58:46 <ais523> that said, the sky here in Birmingham is weird at the moment; blue and normal in one direction, bizarrely yellow in another
13:59:12 <ais523> it's less disconcerting than when it was solid yellow, because at least there's some normality somewhere, but it's still disturbing
13:59:15 <shachaf> So did people come up with any esoteric financial instruments yet?
13:59:27 -!- Remavas has joined.
13:59:42 <lambdabot> *** "exoteric" wn "WordNet (r) 3.0 (2006)"
13:59:42 <lambdabot> adj 1: suitable for the general public; "writings of an exoteric
14:00:30 -!- doesthiswork has joined.
14:00:32 <shachaf> That would be a good word.
14:01:01 <ais523> shachaf: many existing financial instruments are weird enough that it's hard to know how an esoinstrument would be different
14:01:27 <shachaf> Well, usually they exist to accomplish some purpose.
14:01:39 <shachaf> Though I suppose sometimes the purpose is obfuscation.
14:01:53 <shachaf> What sort of weird instruments do you have in mind?
14:09:01 <ais523> I'm not an expert on them, I've just seen other people discuss them (which means that I can hardly remember any details like names)
14:12:33 -!- Sgeo has quit (Read error: Connection reset by peer).
14:19:43 <ais523> hmm, for testing this program I'm writing at work it'd be useful to have a collision in bits 32-64 of an SHA-256 hash; is that a small enough range to practically brute force, and if so, what algorithm should I use?
14:22:36 <shachaf> A 32-bit collision? Are there any other constraints?
14:24:23 <ais523> constraints on the forms of the string I'm colliding
14:24:31 <ais523> ideally, known prefix + known suffix and alphabetical characters in between
14:24:38 <shachaf> Seems like brute force would be easy enough?
14:24:41 <ais523> but I assume that if I'm bruteforcing this the form of the strings doesn't really matter
14:24:52 <b_jonas> yeah, sounds like brute force should work
14:25:21 <shachaf> You could do a clever thing but I doubt it's worth the trouble.
14:25:21 <b_jonas> and the form of strings shouldn't matter, unless it's such that they're hard to generate or there are too few of them, because those bits of SHA-256 are random
14:25:32 <shachaf> What prefix and suffix do you want?
14:25:39 <b_jonas> shachaf: you can't do a clever thing, because SHA-256 is a good digest
14:25:48 <ais523> I guess I use a hash table to store an index from hashes to strings, then keep hashing strings until I find a collision
14:26:00 <ais523> that should be O(2**16) by the birthday paradox, right?
14:26:14 <shachaf> b_jonas: I meant the birthday thing.
14:26:27 <ais523> (except that big-O notation doesn't work like that)
14:26:45 <b_jonas> a moment, I'll try a one-liner with perl and Digest
14:26:51 <shachaf> Not all that clever. I guess 32 bits is enough that it's worth it.
14:27:15 <ais523> shachaf: I'm not 100% sure on the form of the prefix and suffix offhand
14:30:08 <ais523> once I have an algorithm, though, I can work it out
14:30:42 <ais523> hmm, if it's fast enough (and 64K seems fast enough), I could put it in the testsuite so that it finds a new collision in case changes to the details of hashing cause the old one to stop working
14:32:25 <b_jonas> `perl -e use Digest::SHA q(sha256); for $x (q(a)..q(zzzzz)) { $s=qq(GET /$x HTTP/1.1); $d=substr(sha256($s),4,4); if (exists$d{$d}) { printf qq(collision: %s (%s) (%s)\n), unpack(q(H*),$d), $s, $d{$s}; exit 0; } $d{$d}=$s; } die qq(none found);
14:32:27 <HackEgo> collision: 14243f9b (GET /brqn HTTP/1.1) ()
14:32:42 <b_jonas> `perl -e use Digest::SHA q(sha256); for $x (q(a)..q(zzzzz)) { $s=qq(GET /$x HTTP/1.1); $d=substr(sha256($s),4,4); if (exists$d{$d}) { printf qq(collision: %s (%s) (%s)\n), unpack(q(H*),$d), $s, $d{$d}; exit 0; } $d{$d}=$s; } die qq(none found);
14:32:43 <HackEgo> collision: 14243f9b (GET /brqn HTTP/1.1) (GET /adwd HTTP/1.1)
14:33:39 <ais523> does `perl not handle single quotes? or are you just being overcautious with your character set?
14:33:47 <ais523> that certainly seems to run fast enough, at least
14:34:12 <ais523> at this rate it might be worth going for a collision in bits 0-64, which is /also/ a special case but much less likely to happen nonmaliciously
14:34:14 <b_jonas> ais523: I'm using q() to enter one-liners on command-line in windows. single quotes would work too, but I don't like that because that doesn't work on posix shell.
14:34:39 <ais523> Windows uses double quotes to escape, I think
14:34:45 <ais523> ah right, so the single quotes go through literally
14:35:25 <b_jonas> 64-bit collision is still possible to brute force without GPU or parallelism or anything fancy like that, but too slow for HackEgo, I think.
14:35:32 <b_jonas> It would need 2**32 tries.
14:35:51 <ais523> that's a scale that's very sensitive to the complexity of the operations you're performing
14:36:13 <b_jonas> `perl -e use Digest::SHA q(sha256); for $x (q(a)..q(zzzzzz)) { $s=qq(GET /$x HTTP/1.1); $d=substr(sha256($s),2,6); if (exists$d{$d}) { printf qq(collision: %s (%s) (%s)\n), unpack(q(H*),$d), $s, $d{$d}; exit 0; } $d{$d}=$s; } die qq(none found);
14:36:30 <b_jonas> 48 bits of collision might already be too much for HackEgo
14:36:32 <shachaf> It would need slightly more than that, right?
14:36:45 <shachaf> I remember that 1.2 * sqrt(n) was a better approximation.
14:36:47 <b_jonas> shachaf: sure, that's just order of magnitude
14:37:07 <shachaf> 1.2 * sqrt(n) was only for a 50% chance
14:38:30 <ais523> let's see: with n values tested, you have n(n+1)/2 possible collisions; and if you repeatedly roll independent 1/x chances, the number of tries you need for a 50% chance of success IIRC approximates as n*ln(2)
14:38:38 <HackEgo> Undefined subroutine &main::ln called at -e line 1.
14:38:47 <ais523> right, that looks like the right number
14:38:58 <ais523> we can approximate n(n+1) as n² pretty easily
14:39:32 <ais523> so on this approximation it's more like 1.4
14:40:55 <shachaf> I was at a lecture where someone derived it once but I don't remember the details now.
14:40:59 <shachaf> I should go to sleep, it's almost 7.
14:41:30 <ais523> shachaf: US west coast?
14:41:51 <b_jonas> it's not hard to derive it
14:41:52 <ais523> reently there's been enough news coming from the US (and I know enough Americans online) that I added a couple of commonly used US timezones to the clock on this laptop
14:42:08 <ais523> right now it's UTC, London, Washington DC, and Los Angeles
14:44:45 <shachaf> b_jonas: If you're doing these attacks on a larger scale you can also be clever and use less memory.
14:44:47 <b_jonas> I just subtract 6 hours for east coast or 9 hours for west coast. It's not always accurate because of DST stuff, but good enough approximation when I don't want to look up the exact timezones for a location on timeanddate.com
14:44:53 <b_jonas> subtract form the local time that is
14:45:16 <b_jonas> shachaf: and more parallelism too
14:45:33 <b_jonas> which isn't obvious because you still need a hash table or something
14:45:34 <HackEgo> /home/hackbot/hackbot.hg/multibot_cmds/lib/limits: line 5: exec: ctcp: not found
14:45:50 <b_jonas> I'm in the Paris time zone
14:46:14 <ais523> right, I'd figured that out mathematically when ctcp wasn't helping
14:46:33 <b_jonas> we argued on this channel what that timezone is best called, when I said I call it Europe/Paris because it's the biggest city in this timezone, and other people argued it might not be so
14:46:37 <ais523> I wasn't sure if Hungary was far enough east to be in +2 in winter and +3 in summer (rather than +1 in winter and +2 in summer, like Paris)
14:46:57 <b_jonas> No, it switches to that at Romania
14:49:26 <b_jonas> those are about the only places that use that timezone
14:49:57 -!- AnotherTest has joined.
14:50:45 <b_jonas> Ok, actually the three Baltic states are using it too, and possibly Ukraine
14:51:56 <b_jonas> That's actually a lot of places I guess.
14:54:28 <b_jonas> Anyway, I really recommend timeanddate.com for this stuff, when you want more than just guesstimates in your head. It's a well-made site, and the nice part is that the maintainer reacts to my emails.
14:56:11 <ais523> oh, hmm, looks like the prefix and suffix I need is actually just the null string
14:56:14 <ais523> well, that makes things a lot simpler
14:57:14 <ais523> wait, no, there's a salt
14:57:18 <b_jonas> `perl -e use Digest::SHA q(sha256); for $x (q(a)..q(zzzzz)) { $s=$x; $d=substr(sha256($s),4,4); if (exists$d{$d}) { printf qq(collision: %s (%s) (%s)\n), unpack(q(H*),$d), $s, $d{$d}; exit 0; } $d{$d}=$s; } die qq(none found);
14:57:19 <HackEgo> collision: 1a7d5bb0 (bloh) (hlx)
14:57:47 <ais523> or should be, I'm not sure this code is actually using it
14:58:32 <ais523> good thing I looked at that bit of the code!
15:14:25 <ais523> b_jonas: 40-bit collision: cthex, bdllm
15:14:41 <ais523> going significantly beyond this seems unviable in Perl, it uses too much memory
15:14:50 <ais523> I might try switching to Rust
15:14:59 <ais523> and/or borrowing a more powerful computer from the university
15:22:10 <ais523> "Usually, SHA-256 operates on integers with 32 bits (u32). This implementation uses one double (f64) for each bit of each integer, thereby allowing to use 8 fuzzy input bits for each input byte." ← looks like crates.io has some fairly esoteric libraries…
15:22:50 -!- imode has joined.
15:24:18 * ais523 has an idea, and does a web search for "hqwj ever"
15:25:40 <ais523> there is one relevant result but it doesn't contain a generalisation to 64 bits
15:26:05 <ais523> I typed it correctly first time in the search box
15:26:25 <ais523> it is fairly problematic for this that "ever" is a real word :-(
15:27:07 <ais523> anyway, thinking about this, a > 2**32 attempt birthday collision is likely to use more memory than this computer has unless the algorithm is very optimized wrt memory use
15:28:02 <ais523> I wonder if using a database for this would make sense?
15:29:39 <shachaf> But it seems people have algorithms that don't require you to store every input and hash.
15:30:16 <ais523> an obvious improvement in terms of memory usage is to just store the hash, then once you have the second input, go back to the start and brute force a preimage
15:30:22 <ais523> you found it once already so you can find it again
15:30:34 <shachaf> Now that I know why "Pollard's rho algorithm" is called that I think the name is pretty silly.
15:33:07 <int-e> The rainbow table trick should also be applicable (iterate the hash, but only remember those values whose lower k bits are 0, for some chosen k)
15:34:21 <ais523> not in this case, unless we convert the input to be alphabetical between the iterations
15:34:38 <ais523> which seems like it might be fairly slow? it's a clever trick, though
15:34:55 <shachaf> Convert the input to be alphabeticaal?
15:35:00 <ais523> come to think of it, you could actually do this in constant memory
15:35:08 <ais523> via the tortoise-and-hare algorithm for finding a cycle in a linked list
15:35:52 <ais523> the idea is that you repeatedly do the following: truncated-hash the input, convert the truncated hash into a new input of the required form
15:36:09 <ais523> that gives you a chain of truncated hashes which has to repeat eventually (because there are only finitely many possibilities for the truncated hash)
15:36:31 <int-e> ais523: you can even swap the order of the two operations for smaller (probably) intermediate results
15:36:32 <shachaf> That's where the name "rho" comes from. Because a linked list with a cycle in it looks like ρ
15:36:37 <ais523> then you use a cycle detection algorithm (possible in O(1) memory) to find the cycle, and at that point, working "backwards" from the point of the cycle gives you a collision
15:36:55 <ais523> shachaf: that's ridiculous :-P
15:40:50 <shachaf> That's hard to parallelize, though.
15:41:06 <shachaf> But apparently people have more tricks for that.
15:41:12 <int-e> no, it's trivial, just start from n random values
15:41:17 <ais523> wait, I'm not sure this works; you can detect the cycle in O(1) memory but you don't learn the point at which the cycle joins the main sequence
15:42:38 <ais523> which is what you'd need to nkow
15:44:29 <ais523> I guess you need extra values; once you find a collision do another full loop of the cycle to work out how large it is, and track what distance you've gone to work out where you are on the cycle, letting you work out the point it converges
15:44:36 <ais523> then just start from the start and stop at the appropriate point
15:47:28 <int-e> ais523: you can do it if you remember the starting value; the starting value, the tortoise, and the hare will be evenly spaced when the cycle is detected, so just iterate from the starting value and the tortoise synchronously until they become equal. Though perhaps there are cheaper ways of doing it.
15:48:07 <shachaf> I'm not thinking very well right now. I should go to sleep.
15:48:13 <ais523> oh yes, I think that's what my approach would simplify to if I actually did the maths?
15:48:18 <shachaf> But here's a paper discussing it: http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf
15:49:19 <int-e> shachaf: my guess is that the speedup from starting with n random points is almost perfect (as an estimate, (n+1)/2 with n threads)
15:49:57 <int-e> (And by speedup I mean expected speedup, since everything here is probabilistic.)
15:50:58 <shachaf> Yes, it's a different version that I was thinking of, which uses that rainbow trick.
15:51:37 <ais523> sha256(015e2c85)=45faea71c83c8f73bbee1d07c4b2c3428b0c1b537aa964dd5492cb936d268184
15:51:39 <shachaf> But it's not that tricky there either.
15:51:44 <ais523> sha256(da90efdd)=45faea71f8e5a5698d74dacf7a7cfeaf7e1d771d14f51cc064a2778b836e0051
15:51:54 <ais523> looks like this algo works for the small (32-bit) test case
15:52:09 <ais523> `` perl -MDigest::SHA=sha256 -E 'sub i{unpack"H*",substr sha256(shift),0,4}$t=$h="a";do{$h=i(i($h));$t=i($t)}while($h ne $t);$h="a";say $t;do{$lh=$h;$lt=$t;$h=i($h);$t=i($t)}while($h ne $t);say $lh;say $lt;say $h;say $t'
15:52:12 <HackEgo> 6a71fd18 \ da90efdd \ 015e2c85 \ 45faea71 \ 45faea71
15:52:23 <int-e> but I seem to be wrong, since the paper says that the speedup is only O(sqrt(n))
15:53:22 <shachaf> Were you expecting better than O(sqrt(n))?
15:53:40 <shachaf> Oh, you mean for parallelizing.
15:54:01 <int-e> I guess my analogy is flawed
15:56:39 <ais523> huh, I just found a collision on a 48-bit prefix, and it only took marginally over twice as long as on a 40-bit prefix
15:56:43 <ais523> is that just an utter fluke?
15:57:14 <ais523> 0005a3be7429 against b0390e13d757, for those people who are interested
15:57:54 <shachaf> Are you measuring time or number of hashes?
15:58:04 <ais523> but I wouldn't expect startup cost to be significant
15:58:11 <ais523> ~15 seconds compared to ~30 seconds
15:59:09 <ais523> I assume so, it's about a 1% chance I think
15:59:22 <ais523> those happen occasionally but it's still surprising when they do
16:01:03 <ais523> the times should differ by a factor of 256
16:01:07 <ais523> they actually differed by a factor of 2
16:01:14 <ais523> so the result is a factor of 100 away from what's expected
16:02:34 <shachaf> My thinking must be jumbled right now.
16:02:43 <ais523> it's me who's confused
16:02:46 <shachaf> I guess I'll go to sleep. It's already light out. :-(
16:03:02 <shachaf> So more like a 12% chance. Less surprising.
16:06:03 -!- sleffy has joined.
16:06:47 <shachaf> This distinguished point trick is pretty good.
16:19:13 <int-e> that is the rainbow table trick
16:22:36 -!- ais523 has quit (Quit: quit).
16:23:51 <b_jonas> The bun-alert syntax is back!
16:24:31 <HackEgo> olist 1102: shachaf oerjan Sgeo FireFly boily nortti b_jonas
16:24:33 <b_jonas> `perl -e use Digest::SHA q(sha256); for $x (q(a)..q(zzzzz)) { $s=$x; $d=substr(sha256($s),0,4); if (exists$d{$d}) { printf qq(collision: %s (%s) (%s)\n), unpack(q(H*),$d), $s, $d{$d}; exit 0; } $d{$d}=$s; } die qq(none found);
16:24:35 <HackEgo> collision: 63212655 (hgwj) (ever)
16:25:01 <b_jonas> `perl -e use Digest::SHA q(sha256); for $x (q(a)..q(zzzz), q(A)..q(ZZZZ)) { $s=$x; $d=substr(sha256($s),0,4); if (exists$d{$d}) { printf qq(collision: %s (%s) (%s)\n), unpack(q(H*),$d), $s, $d{$d}; } $d{$d}=$s; } die qq(all done);
16:25:31 <HackEgo> all done at -e line 1. \ collision: 63212655 (hgwj) (ever) \ collision: 14202469 (ioaw) (ehks) \ collision: 5e6655a3 (isvc) (gfub) \ collision: 62bd0444 (jcgu) (ifoz) \ collision: dbdda724 (jyen) (ifph) \ collision: 3fbea896 (keer) (bmeq) \ collision: 2932fabe (mcdt) (akcg) \ collision: ee6816e2 (mlgl) (dmyo) \ collision: 82952ecc (nmbm) (apqi) \ c
16:25:58 <b_jonas> "<ais523> an obvious improvement in terms of memory usage is to just store the hash, then
16:26:48 <b_jonas> ais523: how exactly does an eventual repetition give you a collision?
16:28:19 <b_jonas> but the problem with an iterative algorithm like that is that it's not parallelizable. whereas with a hash table, you can probably parallelize it to 32 threads without too much of a loss.
16:28:39 <b_jonas> and you get a quadratic gain from using 32 threads and a shared hash table.
16:29:49 <b_jonas> so that would be like 256 times faster than one thread
16:30:00 <b_jonas> but 16 threads might be more realistic
16:33:48 -!- imode has quit (Ping timeout: 240 seconds).
16:41:59 <int-e> clearly the math is wrong. otherwise you'd get a speedup from interleaving 32 such threads on a single processor...
16:45:30 <int-e> (In this approach, the number of samples you need in order to find a collision is basically unchanged by the parallelization; the only speedup you get is from generating those samples faster. You'll also consume memory much faster, which is why the distinguished point trick is so brilliant, because it saves memory essentially for free.)
16:57:10 <b_jonas> int-e: hm... yes, you're right
16:58:25 <b_jonas> and sure, you're consume memory faster, but eventually you'll need essentially the same amount of memory for single-threaded than multi-threaded
17:10:46 -!- FreeFull has joined.
17:19:19 -!- atrapado_ has joined.
17:22:04 -!- zseri has joined.
17:50:01 <shachaf> `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:14] for x in ["ccf506fc58ee23", "843c7fa058d321"]]'
17:50:01 <HackEgo> ['a522d3c3f644a5', 'a522d3c3f644a5']
17:51:12 <shachaf> Someone else can do 64 bits, I guess.
18:15:23 <shachaf> Taneb is here to do 64 bits?
18:23:27 -!- jaboja has joined.
18:29:42 -!- LKoen_ has joined.
18:31:10 -!- LKoen has quit (Ping timeout: 252 seconds).
18:38:12 -!- LKoen_ has quit (Remote host closed the connection).
18:38:45 -!- Phantom_Hoover has joined.
18:40:21 <b_jonas> shachaf: I could be wrong here, but I figure it's more efficient to store the original value (or a truncation of it) in the hash table and recompute the full digest each time two hash table entries are at the same place, than to store the digest and try to search again for the originla string.
18:40:38 <b_jonas> But this is from a mental calculation that could be wrong.
18:42:09 <b_jonas> For searchging for a 64-bit collision, I'd try to get time on a machine with 32 gigabytes of RAM (which isn't too rare these days), allocate a hash table of 30 gigabytes size or something, with 2**33 entries and 4 bytes of the input in each entry.
18:42:32 <b_jonas> Preferably a machine with fast RAM.
18:43:21 <b_jonas> And ideally compute digest quickly with GPU or something, so you get the digests as fast as you can access the main RAM.
18:43:36 <b_jonas> But just multiple cpu threads might be fast enough for that.
18:49:49 <shachaf> What? Why do all that instead of using the distinguished point trick?
18:53:16 <b_jonas> shachaf: what's the "distinguished point trick"?
18:55:34 <shachaf> You repeatedly feed the output of the hash back into itself until you get a "distinguished" hash (e.g. where the first 16 bits are 0). Then you just store the distinguished hashes and which hashes led to them.
18:56:04 <shachaf> If two hashes end up at the same distinguished hash, you go through the chain and find where they connect.
18:56:24 <shachaf> I'm not explaining it very well but you can read the paper I linked to above.
18:56:30 <shachaf> I should sleep but now it's too late to sleep.
18:56:40 <shachaf> But if I don't sleep I'll regret it. And if I do sleep I'll regret it.
18:56:49 <b_jonas> how well does that parallelize?
18:57:13 <shachaf> The paper I linked is about parallelizing it.
18:57:27 <shachaf> I guess it works pretty well if you use a central store for the distinguished points, and your chains are long enough.
18:57:49 <b_jonas> http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf is this the paper?
18:58:13 <b_jonas> this trick always sounds like black magic
18:59:04 <shachaf> What's black about this magic?
18:59:32 <shachaf> Just look at the diagram, it's pretty simple when it's pointed out.
18:59:53 <shachaf> You don't even need to feed the output of the hash back into the hash, I guess.
19:00:29 <shachaf> Or maybe you do, I don't know.
19:01:37 <b_jonas> I'm looking at https://pdaian.com/blog/collision-finding-the-maxwell-way/ now
19:01:51 <b_jonas> I'm trying to understand the trick now
19:04:00 <shachaf> Though it's hardly his way, it's an old trick.
19:04:08 <b_jonas> I don't understand how you find the first entry of the sequence that collides
19:04:26 <b_jonas> you can find one repetition in the sequence easily, but that's not enoguh
19:05:00 <shachaf> Once you have two short chains that end up at the same distinguished point, you can just scan through them.
19:05:22 <b_jonas> you store milestones to break the sequence to shorter part, and use the milestones to find the approxmiate first collision
19:05:51 <b_jonas> and then recompute and store the elements in the segments where the first collision must be
19:06:20 <b_jonas> which needs only on the order of magnitude of 2**16 entries, not 2**32, for a 2**64 collision, although there's a higher constant factor
19:06:39 <b_jonas> this way you never run out of memory
19:08:20 <b_jonas> as in, you don't actually use 2**16 times less memory, only like 2**12 times less or something
19:08:52 <b_jonas> you could do with fewer milestones
19:09:02 <b_jonas> then you actually need even less than 2**16 entries
19:09:10 <b_jonas> you do need 2**16 milestones
19:10:26 <b_jonas> interesting, thank you for telling about this rho trick
19:10:47 <b_jonas> I had heard of it about prime factoring, but I don't think I realized it's useful for crypto collision finding like this
19:12:49 -!- jaboja has quit (Ping timeout: 248 seconds).
19:23:32 -!- Cthulhux has quit (Changing host).
19:23:32 -!- Cthulhux has joined.
19:31:11 <\oren\> BFS is supposedly going to SSTO for testing
19:31:24 -!- LKoen has joined.
19:33:16 <zzo38> I made another container format, which is GLOGG container, similar to Ogg but I avoided what I considered are the problems with it, without making it so much more complicated like many other formats are.
19:35:49 <zzo38> One problem with Ogg seems how you might not be able to avoid losing data when mixing or separating streams, and how programs might not be able to do this at all if any streams are unrecognized; GLOGG includes the necessary information in "control pages" to allow them to be separated and combined even if some of them are unrecognized.
19:36:59 <zzo38> (Another thing the control page does is to identify the codec by given a UUID, as well as support alternate streams (for languages and such), and relations between streams.)
19:37:07 -!- Remavas-Hex has joined.
19:38:16 -!- Remavas has quit (Ping timeout: 252 seconds).
19:38:29 <zzo38> (Also, the checksum has been reduced to 16-bits in order to reduce the amount of overhead.)
19:38:49 -!- Remavas-Hex has quit (Read error: Connection reset by peer).
19:39:06 -!- Remavas-Hex has joined.
19:46:32 -!- Remavas-Hex has quit (Read error: Connection reset by peer).
19:46:50 -!- Remavas-Hex has joined.
19:59:45 -!- sleffy has quit (Ping timeout: 248 seconds).
20:11:05 -!- zseri_ has joined.
20:12:29 -!- Remavas-3 has joined.
20:14:34 -!- zseri has quit (Ping timeout: 252 seconds).
20:16:02 -!- Remavas-Hex has quit (Ping timeout: 246 seconds).
20:31:03 <zzo38> What you think of this, please?
20:52:53 -!- SigmundYx has joined.
21:01:39 <shachaf> `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:16] for x in ["5fc2544f27bc209e", "aeaefd69151cba80"]]'
21:01:40 <HackEgo> ['6eeafe59946b43c3', '6eeafe59946b43c3']
21:12:13 -!- zseri_ has quit (Quit: Leaving).
21:14:31 -!- LKoen has quit (Remote host closed the connection).
21:27:53 -!- sleffy has joined.
21:53:16 -!- imode has joined.
22:18:36 -!- atrapado_ has quit (Quit: Leaving).
22:48:24 -!- jaboja has joined.
22:54:39 -!- boily has joined.
23:00:08 <shachaf> @tell ais523 `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:16] for x in ["5fc2544f27bc209e", "aeaefd69151cba80"]]'
23:02:53 -!- SigmundYx has quit (Remote host closed the connection).
23:07:05 <HackEgo> 1/2:html//HTML is short for "hope this mess loads". \ arabic//.scihpylgoreiH sa drah sa ton hguoht ,troppus stnof ekam ot drah yrev si taht egaugnal citimes lartnec a si cibarA \ obvious//Obvious, adj.: A postulate used to prove a wide variety of theorems too arduous to prove by other means. In American Sign Language, it is denoted by a vigor
23:07:16 -!- AnotherTest has quit (Ping timeout: 255 seconds).
23:09:04 <HackEgo> 2/2:ous waving of the hands. \ sgdq//SGDQ is Summer Games Done Quick, an annual video games speedrunning event for charity ever summer, see http://gamesdonequick.com and https://gamesdonequick.com/tracker/events/ \ restaurant//A restaurant is a type of transactional resource-distributing system powered by lazy evaluation.
23:13:19 -!- Remavas-3 has quit (Ping timeout: 248 seconds).
23:23:25 -!- Sgeo has joined.
23:45:20 -!- boily has quit (Quit: COUNTING CHICKEN).
23:51:39 -!- oerjan has joined.
23:56:49 -!- hppavilion[1] has joined.
23:58:25 -!- sleffy has quit (Ping timeout: 252 seconds).
23:59:45 <imode> babble: I wonder what kinds of binary trees you could generate from repeatedly factoring a given number.