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:28:53 maybe they could be outfix operators 00:31:37 helloily 00:39:45 -!- imode has joined. 00:45:38 QUINTHELLOPIA! 00:45:53 -!- boily has quit (Quit: ISOCELES CHICKEN). 00:48:12 So today I learned that all esoteric languages are actually dialects of Tamil 00:48:57 woops I mean dialects of தமிழ் 01:04:53 dialects of box box box box? 01:05:44 `unidecode த 01:05:45 ​[U+0BA4 TAMIL LETTER TA] 01:06:07 `unidecode மி 01:06:07 ​[U+0BAE TAMIL LETTER MA] [U+0BBF TAMIL VOWEL SIGN I] 01:06:34 `unidecode ழ் 01:06:35 ​[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 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 [wiki] [[Tables]] N https://esolangs.org/w/index.php?oldid=53208 * HereToAnnoy * (+1012) created idea 05:09:25 [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 whoops, just looked at the sun by mistake, I'm not used to the sky being like this 13:38:43 luckily it's very dim in this weather 13:43:55 @metar EGLL 13:43:55 EGLL 161220Z AUTO 20016G28KT 9999 NCD 21/15 Q1014 13:44:03 So warm. 13:44:42 @metar KSFO 13:44:42 KSFO 161156Z 00000KT 10SM CLR 14/06 A3011 RMK AO2 SLP195 T01390061 10189 20133 58002 13:44:51 tables, turned 13:45:03 hi all 13:46:34 @metar EGBB 13:46:34 EGBB 161220Z 18012G22KT 9999 SCT024 19/15 Q1010 13:46:54 they're predicting 40mph winds here in Birmingham for a few hours as the edge of the extratropical storm passes 13:47:11 I don't think London's going to see much of that. 13:47:33 @metar KOAK 13:47:34 KOAK 161153Z 00000KT 10SM FEW012 11/07 A3011 RMK AO2 SLP196 T01060067 10178 20089 56004 13:47:38 fizzie: right, you're further south 13:48:06 whereas further west and north they'll get much more of the brunt of the storm 13:48:07 fizzie: The local weather issue here was air quality, not temperature. 13:48:24 Well, that and the fires, a little further north. 13:48:43 But even here the air quality index was worse than Beijing. 13:49:28 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 Is it a measurable subset? 13:50:53 probably yes in the mathematical sense and no in the practical sense 13:57:25 Is it a null subset? 13:57:49 -!- AnotherTest has quit (Ping timeout: 252 seconds). 13:58:11 b_jonas: no 13:58:20 otherwise it wouldn't have much of an impact on the sun's color 13:58:21 I don't think people would describe a null subset as "large in an absolute sense" 13:58:46 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 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 So did people come up with any esoteric financial instruments yet? 13:59:20 `grWp exo 13:59:27 -!- Remavas has joined. 13:59:28 No output. 13:59:40 @wn exoteric 13:59:42 *** "exoteric" wn "WordNet (r) 3.0 (2006)" 13:59:42 exoteric 13:59:42 adj 1: suitable for the general public; "writings of an exoteric 13:59:42 nature" [ant: {esoteric}] 13:59:44 @wn esotic 13:59:45 No match for "esotic". 14:00:30 -!- doesthiswork has joined. 14:00:32 That would be a good word. 14:01:01 shachaf: many existing financial instruments are weird enough that it's hard to know how an esoinstrument would be different 14:01:27 Well, usually they exist to accomplish some purpose. 14:01:39 Though I suppose sometimes the purpose is obfuscation. 14:01:53 What sort of weird instruments do you have in mind? 14:09:01 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 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:19:48 er, 32-63 14:22:36 A 32-bit collision? Are there any other constraints? 14:24:23 constraints on the forms of the string I'm colliding 14:24:31 ideally, known prefix + known suffix and alphabetical characters in between 14:24:38 Seems like brute force would be easy enough? 14:24:41 but I assume that if I'm bruteforcing this the form of the strings doesn't really matter 14:24:52 yeah, sounds like brute force should work 14:25:21 You could do a clever thing but I doubt it's worth the trouble. 14:25:21 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 What prefix and suffix do you want? 14:25:39 shachaf: you can't do a clever thing, because SHA-256 is a good digest 14:25:48 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:25:59 ais523: that, yes 14:26:00 that should be O(2**16) by the birthday paradox, right? 14:26:03 yes 14:26:14 b_jonas: I meant the birthday thing. 14:26:27 (except that big-O notation doesn't work like that) 14:26:45 a moment, I'll try a one-liner with perl and Digest 14:26:51 Not all that clever. I guess 32 bits is enough that it's worth it. 14:27:15 shachaf: I'm not 100% sure on the form of the prefix and suffix offhand 14:30:08 once I have an algorithm, though, I can work it out 14:30:42 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 `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 collision: 14243f9b (GET /brqn HTTP/1.1) () 14:32:31 hmm no 14:32:42 `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 collision: 14243f9b (GET /brqn HTTP/1.1) (GET /adwd HTTP/1.1) 14:32:46 like that 14:32:50 ais523: ^ 14:33:39 does `perl not handle single quotes? or are you just being overcautious with your character set? 14:33:47 that certainly seems to run fast enough, at least 14:34:12 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 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 Windows uses double quotes to escape, I think 14:34:45 ah right, so the single quotes go through literally 14:35:25 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 It would need 2**32 tries. 14:35:38 right 14:35:51 that's a scale that's very sensitive to the complexity of the operations you're performing 14:35:56 yep 14:36:13 `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 48 bits of collision might already be too much for HackEgo 14:36:32 It would need slightly more than that, right? 14:36:45 I remember that 1.2 * sqrt(n) was a better approximation. 14:36:47 shachaf: sure, that's just order of magnitude 14:36:52 and it's random anyway 14:37:01 Er, right. 14:37:07 1.2 * sqrt(n) was only for a 50% chance 14:38:30 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:37 `perl -E say ln(2) 14:38:38 Undefined subroutine &main::ln called at -e line 1. 14:38:40 `perl -E say log(2) 14:38:41 0.693147180559945 14:38:47 right, that looks like the right number 14:38:58 we can approximate n(n+1) as n² pretty easily 14:39:16 so n²×2÷ln(2) 14:39:20 `perl -E say log(2)*2 14:39:21 1.38629436111989 14:39:32 so on this approximation it's more like 1.4 14:40:55 I was at a lecture where someone derived it once but I don't remember the details now. 14:40:59 I should go to sleep, it's almost 7. 14:41:30 shachaf: US west coast? 14:41:51 it's not hard to derive it 14:41:52 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 right now it's UTC, London, Washington DC, and Los Angeles 14:43:51 Yes. 14:44:45 b_jonas: If you're doing these attacks on a larger scale you can also be clever and use less memory. 14:44:47 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 subtract form the local time that is 14:45:16 shachaf: and more parallelism too 14:45:33 which isn't obvious because you still need a hash table or something 14:45:33 `ctcp b_jonas time 14:45:34 ​/home/hackbot/hackbot.hg/multibot_cmds/lib/limits: line 5: exec: ctcp: not found 14:45:37 err 14:45:50 I'm in the Paris time zone 14:46:14 right, I'd figured that out mathematically when ctcp wasn't helping 14:46:33 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 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 No, it switches to that at Romania 14:48:36 and Greece and Bulgaria 14:49:00 oh, and Finland too 14:49:03 I always forget that 14:49:26 those are about the only places that use that timezone 14:49:57 -!- AnotherTest has joined. 14:50:45 Ok, actually the three Baltic states are using it too, and possibly Ukraine 14:51:56 That's actually a lot of places I guess. 14:54:28 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 oh, hmm, looks like the prefix and suffix I need is actually just the null string 14:56:14 well, that makes things a lot simpler 14:57:14 wait, no, there's a salt 14:57:18 `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 collision: 1a7d5bb0 (bloh) (hlx) 14:57:47 or should be, I'm not sure this code is actually using it 14:58:32 good thing I looked at that bit of the code! 15:14:25 b_jonas: 40-bit collision: cthex, bdllm 15:14:41 going significantly beyond this seems unviable in Perl, it uses too much memory 15:14:50 I might try switching to Rust 15:14:59 and/or borrowing a more powerful computer from the university 15:22:10 "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 there is one relevant result but it doesn't contain a generalisation to 64 bits 15:25:53 * "hgwj ever" 15:26:05 I typed it correctly first time in the search box 15:26:25 it is fairly problematic for this that "ever" is a real word :-( 15:26:41 Or a better algorithm? 15:27:07 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 I wonder if using a database for this would make sense? 15:29:39 But it seems people have algorithms that don't require you to store every input and hash. 15:29:55 right 15:30:16 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 you found it once already so you can find it again 15:30:34 Now that I know why "Pollard's rho algorithm" is called that I think the name is pretty silly. 15:33:07 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 not in this case, unless we convert the input to be alphabetical between the iterations 15:34:38 which seems like it might be fairly slow? it's a clever trick, though 15:34:55 Convert the input to be alphabeticaal? 15:35:00 come to think of it, you could actually do this in constant memory 15:35:08 via the tortoise-and-hare algorithm for finding a cycle in a linked list 15:35:52 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 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 ais523: you can even swap the order of the two operations for smaller (probably) intermediate results 15:36:32 That's where the name "rho" comes from. Because a linked list with a cycle in it looks like ρ 15:36:37 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 shachaf: that's ridiculous :-P 15:37:04 I agree. 15:37:52 it's very visual 15:40:50 That's hard to parallelize, though. 15:41:06 But apparently people have more tricks for that. 15:41:12 no, it's trivial, just start from n random values 15:41:17 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 which is what you'd need to nkow 15:42:39 *know 15:44:29 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 then just start from the start and stop at the appropriate point 15:47:28 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 I'm not thinking very well right now. I should go to sleep. 15:48:13 oh yes, I think that's what my approach would simplify to if I actually did the maths? 15:48:15 shachaf: do it 15:48:18 But here's a paper discussing it: http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf 15:49:19 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 (And by speedup I mean expected speedup, since everything here is probabilistic.) 15:50:58 Yes, it's a different version that I was thinking of, which uses that rainbow trick. 15:51:37 sha256(015e2c85)=45faea71c83c8f73bbee1d07c4b2c3428b0c1b537aa964dd5492cb936d268184 15:51:39 But it's not that tricky there either. 15:51:44 sha256(da90efdd)=45faea71f8e5a5698d74dacf7a7cfeaf7e1d771d14f51cc064a2778b836e0051 15:51:54 looks like this algo works for the small (32-bit) test case 15:52:09 `` 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 6a71fd18 \ da90efdd \ 015e2c85 \ 45faea71 \ 45faea71 15:52:23 but I seem to be wrong, since the paper says that the speedup is only O(sqrt(n)) 15:53:22 Were you expecting better than O(sqrt(n))? 15:53:40 Oh, you mean for parallelizing. 15:54:01 I guess my analogy is flawed 15:56:39 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 is that just an utter fluke? 15:57:14 0005a3be7429 against b0390e13d757, for those people who are interested 15:57:54 Are you measuring time or number of hashes? 15:57:58 realtime 15:58:04 but I wouldn't expect startup cost to be significant 15:58:11 ~15 seconds compared to ~30 seconds 15:58:49 luck? 15:59:09 I assume so, it's about a 1% chance I think 15:59:22 those happen occasionally but it's still surprising when they do 16:00:32 Why only 1%? 16:01:03 the times should differ by a factor of 256 16:01:07 they actually differed by a factor of 2 16:01:14 so the result is a factor of 100 away from what's expected 16:02:17 Not a factor of 16? 16:02:34 My thinking must be jumbled right now. 16:02:40 oh right, of course 16:02:43 it's me who's confused 16:02:46 I guess I'll go to sleep. It's already light out. :-( 16:02:47 Ah. 16:03:02 So more like a 12% chance. Less surprising. 16:03:09 But I should still sleep. 16:06:03 -!- sleffy has joined. 16:06:47 This distinguished point trick is pretty good. 16:07:10 go to bed! 16:19:13 that is the rainbow table trick 16:19:44 Yes. 16:22:36 -!- ais523 has quit (Quit: quit). 16:23:51 The bun-alert syntax is back! 16:24:30 `olist 1102 16:24:31 olist 1102: shachaf oerjan Sgeo FireFly boily nortti b_jonas 16:24:33 `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 collision: 63212655 (hgwj) (ever) 16:24:38 ah 16:25:01 `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 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 " an obvious improvement in terms of memory usage is to just store the hash, then 16:26:48 ais523: how exactly does an eventual repetition give you a collision? 16:27:05 ah 16:28:19 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 and you get a quadratic gain from using 32 threads and a shared hash table. 16:29:49 so that would be like 256 times faster than one thread 16:29:52 no wait 16:29:55 1024 times faster 16:30:00 but 16 threads might be more realistic 16:33:48 -!- imode has quit (Ping timeout: 240 seconds). 16:41:59 clearly the math is wrong. otherwise you'd get a speedup from interleaving 32 such threads on a single processor... 16:45:30 (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 int-e: hm... yes, you're right 16:57:32 so only 32 such threads 16:58:25 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:02:31 only linear speedup then 17:02:40 still should be worth 17:10:46 -!- FreeFull has joined. 17:19:19 -!- atrapado_ has joined. 17:22:04 -!- zseri has joined. 17:50:01 `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:14] for x in ["ccf506fc58ee23", "843c7fa058d321"]]' 17:50:01 ​['a522d3c3f644a5', 'a522d3c3f644a5'] 17:51:12 Someone else can do 64 bits, I guess. 18:14:02 * Taneb hello 18:15:23 Taneb is here to do 64 bits? 18:18:50 I don't think so 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 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 But this is from a mental calculation that could be wrong. 18:42:09 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 Preferably a machine with fast RAM. 18:43:21 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 But just multiple cpu threads might be fast enough for that. 18:49:49 What? Why do all that instead of using the distinguished point trick? 18:53:16 shachaf: what's the "distinguished point trick"? 18:55:34 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 If two hashes end up at the same distinguished hash, you go through the chain and find where they connect. 18:56:18 shachaf: hmm 18:56:24 I'm not explaining it very well but you can read the paper I linked to above. 18:56:30 I should sleep but now it's too late to sleep. 18:56:40 But if I don't sleep I'll regret it. And if I do sleep I'll regret it. 18:56:49 how well does that parallelize? 18:57:10 might work I guess 18:57:13 The paper I linked is about parallelizing it. 18:57:27 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 http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf is this the paper? 18:57:55 Yes. 18:58:06 let me see 18:58:13 this trick always sounds like black magic 18:59:04 What's black about this magic? 18:59:32 Just look at the diagram, it's pretty simple when it's pointed out. 18:59:53 You don't even need to feed the output of the hash back into the hash, I guess. 19:00:29 Or maybe you do, I don't know. 19:01:37 I'm looking at https://pdaian.com/blog/collision-finding-the-maxwell-way/ now 19:01:51 I'm trying to understand the trick now 19:02:59 whoa, I know that Maxwell 19:04:00 Though it's hardly his way, it's an old trick. 19:04:08 I don't understand how you find the first entry of the sequence that collides 19:04:26 you can find one repetition in the sequence easily, but that's not enoguh 19:04:37 oh, I see! 19:05:00 Once you have two short chains that end up at the same distinguished point, you can just scan through them. 19:05:22 you store milestones to break the sequence to shorter part, and use the milestones to find the approxmiate first collision 19:05:51 and then recompute and store the elements in the segments where the first collision must be 19:06:11 Right. 19:06:20 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:23 nice 19:06:39 this way you never run out of memory 19:06:48 nice trick 19:06:51 Higher constant factor? 19:08:20 as in, you don't actually use 2**16 times less memory, only like 2**12 times less or something 19:08:45 hmm wait 19:08:52 you could do with fewer milestones 19:08:53 sorry 19:09:02 then you actually need even less than 2**16 entries 19:09:05 no wait 19:09:10 you do need 2**16 milestones 19:09:12 I'm confused 19:10:26 interesting, thank you for telling about this rho trick 19:10:47 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:30:38 <\oren\> yo guys hav u herd? 19:31:11 <\oren\> BFS is supposedly going to SSTO for testing 19:31:24 -!- LKoen has joined. 19:33:16 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 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 (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 (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 What you think of this, please? 20:52:53 -!- SigmundYx has joined. 21:01:39 `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:16] for x in ["5fc2544f27bc209e", "aeaefd69151cba80"]]' 21:01:40 ​['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. 22:55:49 coily 22:59:04 QUINTHELLOPIA! 23:00:08 @tell ais523 `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:16] for x in ["5fc2544f27bc209e", "aeaefd69151cba80"]]' 23:00:08 Consider it noted. 23:02:53 -!- SigmundYx has quit (Remote host closed the connection). 23:06:59 `5 w 23:07:05 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:03 `n 23:09:04 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 babble: I wonder what kinds of binary trees you could generate from repeatedly factoring a given number.