< 1508112002 0 :danieljabailey!~danieljab@cpc75709-york6-2-0-cust725.7-1.cable.virginm.net QUIT :Quit: ZNC 1.6.4+deb1 - http://znc.in
< 1508112019 0 :danieljabailey!~danieljab@cpc75709-york6-2-0-cust725.7-1.cable.virginm.net JOIN :#esoteric
< 1508112061 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 QUIT :Client Quit
< 1508112075 0 :ATMunn_!?@? NICK :ATMunn
< 1508112083 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 QUIT :Client Quit
< 1508112099 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 JOIN :#esoteric
< 1508112542 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 QUIT :Quit: lol rip
< 1508112552 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 JOIN :#esoteric
< 1508112698 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 QUIT :Client Quit
< 1508112708 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 JOIN :#esoteric
< 1508113639 0 :ATMunn!~ATMunn@unaffiliated/atmunn26 QUIT :Quit: lol rip
< 1508113649 0 :ATMunn!ATMunn@unaffiliated/atmunn26 JOIN :#esoteric
< 1508113733 0 :doesthiswork!~Adium@207.55.82.87 PRIVMSG #esoteric :maybe they could be outfix operators
< 1508113897 0 :quintopia!~quintopia@unaffiliated/quintopia PRIVMSG #esoteric :helloily
< 1508114385 0 :imode!~imode@unaffiliated/imode JOIN :#esoteric
< 1508114738 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net PRIVMSG #esoteric :QUINTHELLOPIA!
< 1508114753 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net QUIT :Quit: ISOCELES CHICKEN
< 1508114892 0 :doesthiswork!~Adium@207.55.82.87 PRIVMSG #esoteric :So today I learned that all esoteric languages are actually dialects of Tamil
< 1508114937 0 :doesthiswork!~Adium@207.55.82.87 PRIVMSG #esoteric :woops I mean dialects of தமிழ்
< 1508115893 0 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :dialects of box box box box?
< 1508115944 0 :doesthiswork!~Adium@207.55.82.87 PRIVMSG #esoteric :`unidecode த
< 1508115945 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :[U+0BA4 TAMIL LETTER TA]
< 1508115967 0 :doesthiswork!~Adium@207.55.82.87 PRIVMSG #esoteric :`unidecode மி
< 1508115967 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :[U+0BAE TAMIL LETTER MA] [U+0BBF TAMIL VOWEL SIGN I]
< 1508115994 0 :doesthiswork!~Adium@207.55.82.87 PRIVMSG #esoteric :`unidecode ழ்
< 1508115995 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :[U+0BB4 TAMIL LETTER LLLA] [U+0BCD TAMIL SIGN VIRAMA]
< 1508116697 0 :jaboja!~jaboja@jaboja.pl QUIT :Ping timeout: 252 seconds
< 1508117259 0 :LKoen!~LKoen@2a01:e35:2eed:a430:6082:3d35:4496:6a2b QUIT :Remote host closed the connection
< 1508118032 0 :jaboja!~jaboja@jaboja.pl JOIN :#esoteric
< 1508118908 0 :ski!~ski@remote11.chalmers.se QUIT :Ping timeout: 240 seconds
< 1508120731 0 :jaboja!~jaboja@jaboja.pl QUIT :Remote host closed the connection
< 1508121630 0 :oerjan!~oerjan@hagbart.nvg.ntnu.no JOIN :#esoteric
< 1508124693 0 :Melvar`!~melvar@dslb-088-064-057-072.088.064.pools.vodafone-ip.de JOIN :#esoteric
< 1508124772 0 :Melvar!~melvar@dslb-088-065-239-254.088.065.pools.vodafone-ip.de QUIT :Ping timeout: 260 seconds
< 1508124974 0 :zzo38!~zzo38@24-207-56-48.eastlink.ca PRIVMSG #esoteric :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)?
< 1508125708 0 :augur!~augur@104-13-209-43.lightspeed.sntcca.sbcglobal.net JOIN :#esoteric
< 1508125917 0 :FreeFull!~freefull@defocus/sausage-lover QUIT :Ping timeout: 240 seconds
< 1508126435 0 :Sgeo!~Sgeo@ool-18b98627.dyn.optonline.net JOIN :#esoteric
< 1508126607 0 :Sgeo_!~Sgeo@ool-18b98627.dyn.optonline.net QUIT :Ping timeout: 240 seconds
< 1508127494 0 :\oren\!~oren@ec2-52-2-213-98.compute-1.amazonaws.com PRIVMSG #esoteric :http://store.steampowered.com/app/643270 good game
< 1508127875 0 :Slereah__!~Slereah@ALille-651-1-160-135.w90-1.abo.wanadoo.fr QUIT :Ping timeout: 240 seconds
< 1508129182 0 :augur!~augur@104-13-209-43.lightspeed.sntcca.sbcglobal.net QUIT :Remote host closed the connection
< 1508130403 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :[wiki] 14[[07Tables14]]4 N10 02https://esolangs.org/w/index.php?oldid=53208 5* 03HereToAnnoy 5* (+1012) 10created idea
< 1508130565 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :[wiki] 14[[07User:HereToAnnoy14]]4 M10 02https://esolangs.org/w/index.php?diff=53209&oldid=53207 5* 03HereToAnnoy 5* (+69) 10tables
< 1508131187 0 :Lymia!lymia@magical.girl.lyrical.lymia.moe QUIT :Read error: Connection reset by peer
< 1508131727 0 :LKoen!~LKoen@vbo91-1-82-238-218-67.fbx.proxad.net JOIN :#esoteric
< 1508131728 0 :doesthiswork!~Adium@207.55.82.87 QUIT :Quit: Leaving.
< 1508131822 0 :augur!~augur@noisebridge130.static.monkeybrains.net JOIN :#esoteric
< 1508131981 0 :LKoen!~LKoen@vbo91-1-82-238-218-67.fbx.proxad.net QUIT :Ping timeout: 240 seconds
< 1508132135 0 :Lymia!lymia@magical.girl.lyrical.lymia.moe JOIN :#esoteric
< 1508132976 0 :tswett!~tswett@unaffiliated/tswett QUIT :Ping timeout: 258 seconds
< 1508133162 0 :tswett!~tswett@unaffiliated/tswett JOIN :#esoteric
< 1508133255 0 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric
< 1508133565 0 :Sgeo!~Sgeo@ool-18b98627.dyn.optonline.net QUIT :Read error: Connection reset by peer
< 1508133711 0 :Melvar`!?@? NICK :Melvar
< 1508133805 0 :idris-bot!~idris-bot@dslb-088-064-057-072.088.064.pools.vodafone-ip.de JOIN :#esoteric
< 1508133849 0 :Sgeo!~Sgeo@ool-18b98627.dyn.optonline.net JOIN :#esoteric
< 1508135026 0 :sleffy!~sleffy@c-24-7-67-0.hsd1.ca.comcast.net QUIT :Ping timeout: 255 seconds
< 1508135704 0 :tswett!~tswett@unaffiliated/tswett QUIT :Ping timeout: 252 seconds
< 1508137213 0 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 255 seconds
< 1508137342 0 :FreeFull!~freefull@defocus/sausage-lover QUIT :
< 1508138667 0 :lynn!sid154965@gateway/web/irccloud.com/x-gqazesvfygkncqbj QUIT :Ping timeout: 255 seconds
< 1508138693 0 :incomprehensibly!sid3405@gateway/web/irccloud.com/x-indvoolkbgstbbtb QUIT :Ping timeout: 255 seconds
< 1508138734 0 :dingbat!uid70835@gateway/web/irccloud.com/x-kbmhjyzvuksmuopw QUIT :Ping timeout: 264 seconds
< 1508138801 0 :dingbat!uid70835@gateway/web/irccloud.com/x-hsltenertbbomjpw JOIN :#esoteric
< 1508138802 0 :incomprehensibly!sid3405@gateway/web/irccloud.com/x-uiwkxeehbvqlbegf JOIN :#esoteric
< 1508138817 0 :HackEgo!~HackEgo@162.248.166.242 QUIT :Ping timeout: 240 seconds
< 1508138819 0 :lynn!sid154965@gateway/web/irccloud.com/x-allbexztktvtrwjy JOIN :#esoteric
< 1508138833 0 :HackEgo!~HackEgo@162.248.166.242 JOIN :#esoteric
< 1508138847 0 :Cthulhux!cthulhu@piratenpartei/ni/tux QUIT :Ping timeout: 240 seconds
< 1508138962 0 :Cthulhux!cthulhu@rosaelefanten.org JOIN :#esoteric
< 1508140759 0 :Remavas!~Remavas@unaffiliated/remavas JOIN :#esoteric
< 1508141569 0 :augur!~augur@noisebridge130.static.monkeybrains.net QUIT :Quit: Leaving...
< 1508142474 0 :LKoen!~LKoen@2a01:e35:2eed:a430:b4a3:26f8:3955:a3ca JOIN :#esoteric
< 1508143025 0 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net QUIT :Ping timeout: 240 seconds
< 1508145985 0 :oerjan!~oerjan@hagbart.nvg.ntnu.no QUIT :Quit: Nite
< 1508152326 0 :tromp!~tromp@ip-217-103-3-94.ip.prioritytelecom.net JOIN :#esoteric
< 1508153688 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net JOIN :#esoteric
< 1508154473 0 :AnotherTest!~turingcom@d51A46C74.access.telenet.be JOIN :#esoteric
< 1508156779 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net QUIT :Quit: MIGRAINE CHICKEN
< 1508158019 0 :Remavas!~Remavas@unaffiliated/remavas QUIT :Ping timeout: 246 seconds
< 1508159371 0 :ais523!~ais523@unaffiliated/ais523 JOIN :#esoteric
< 1508161012 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :whoops, just looked at the sun by mistake, I'm not used to the sky being like this
< 1508161123 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :luckily it's very dim in this weather
< 1508161435 0 :fizzie!?@? PRIVMSG #esoteric :@metar EGLL
< 1508161435 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :EGLL 161220Z AUTO 20016G28KT 9999 NCD 21/15 Q1014
< 1508161443 0 :fizzie!?@? PRIVMSG #esoteric :So warm.
< 1508161482 0 :fizzie!?@? PRIVMSG #esoteric :@metar KSFO
< 1508161482 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :KSFO 161156Z 00000KT 10SM CLR 14/06 A3011 RMK AO2 SLP195 T01390061 10189 20133 58002
< 1508161491 0 :fizzie!?@? PRIVMSG #esoteric :tables, turned
< 1508161503 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :hi all
< 1508161594 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :@metar EGBB
< 1508161594 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :EGBB 161220Z 18012G22KT 9999 SCT024 19/15 Q1010
< 1508161614 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :they're predicting 40mph winds here in Birmingham for a few hours as the edge of the extratropical storm passes
< 1508161631 0 :fizzie!?@? PRIVMSG #esoteric :I don't think London's going to see much of that.
< 1508161653 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :@metar KOAK
< 1508161654 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :KOAK 161153Z 00000KT 10SM FEW012 11/07 A3011 RMK AO2 SLP196 T01060067 10178 20089 56004
< 1508161658 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :fizzie: right, you're further south
< 1508161686 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :whereas further west and north they'll get much more of the brunt of the storm
< 1508161687 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :fizzie: The local weather issue here was air quality, not temperature.
< 1508161704 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Well, that and the fires, a little further north.
< 1508161723 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But even here the air quality index was worse than Beijing.
< 1508161768 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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)
< 1508161817 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Is it a measurable subset?
< 1508161853 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :probably yes in the mathematical sense and no in the practical sense
< 1508162245 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :Is it a null subset?
< 1508162269 0 :AnotherTest!~turingcom@d51A46C74.access.telenet.be QUIT :Ping timeout: 252 seconds
< 1508162291 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :b_jonas: no
< 1508162300 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :otherwise it wouldn't have much of an impact on the sun's color
< 1508162301 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I don't think people would describe a null subset as "large in an absolute sense"
< 1508162326 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that said, the sky here in Birmingham is weird at the moment; blue and normal in one direction, bizarrely yellow in another
< 1508162352 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :it's less disconcerting than when it was solid yellow, because at least there's some normality somewhere, but it's still disturbing
< 1508162355 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :So did people come up with any esoteric financial instruments yet?
< 1508162360 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`grWp exo
< 1508162367 0 :Remavas!~Remavas@unaffiliated/remavas JOIN :#esoteric
< 1508162368 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :No output.
< 1508162380 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :@wn exoteric
< 1508162382 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :*** "exoteric" wn "WordNet (r) 3.0 (2006)"
< 1508162382 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :exoteric
< 1508162382 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric : adj 1: suitable for the general public; "writings of an exoteric
< 1508162382 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric : nature" [ant: {esoteric}]
< 1508162384 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :@wn esotic
< 1508162385 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :No match for "esotic".
< 1508162430 0 :doesthiswork!~Adium@207.55.82.87 JOIN :#esoteric
< 1508162432 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :That would be a good word.
< 1508162461 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :shachaf: many existing financial instruments are weird enough that it's hard to know how an esoinstrument would be different
< 1508162487 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Well, usually they exist to accomplish some purpose.
< 1508162499 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Though I suppose sometimes the purpose is obfuscation.
< 1508162513 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :What sort of weird instruments do you have in mind?
< 1508162941 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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)
< 1508163153 0 :Sgeo!~Sgeo@ool-18b98627.dyn.optonline.net QUIT :Read error: Connection reset by peer
< 1508163583 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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?
< 1508163588 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :er, 32-63
< 1508163756 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :A 32-bit collision? Are there any other constraints?
< 1508163863 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :constraints on the forms of the string I'm colliding
< 1508163871 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :ideally, known prefix + known suffix and alphabetical characters in between
< 1508163878 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Seems like brute force would be easy enough?
< 1508163881 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but I assume that if I'm bruteforcing this the form of the strings doesn't really matter
< 1508163892 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :yeah, sounds like brute force should work
< 1508163921 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :You could do a clever thing but I doubt it's worth the trouble.
< 1508163921 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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
< 1508163932 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :What prefix and suffix do you want?
< 1508163939 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :shachaf: you can't do a clever thing, because SHA-256 is a good digest
< 1508163948 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I guess I use a hash table to store an index from hashes to strings, then keep hashing strings until I find a collision
< 1508163959 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :ais523: that, yes
< 1508163960 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that should be O(2**16) by the birthday paradox, right?
< 1508163963 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :yes
< 1508163974 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :b_jonas: I meant the birthday thing.
< 1508163987 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :(except that big-O notation doesn't work like that)
< 1508164005 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :a moment, I'll try a one-liner with perl and Digest
< 1508164011 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Not all that clever. I guess 32 bits is enough that it's worth it.
< 1508164035 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :shachaf: I'm not 100% sure on the form of the prefix and suffix offhand
< 1508164208 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :once I have an algorithm, though, I can work it out
< 1508164242 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508164345 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :`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);
< 1508164347 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :collision: 14243f9b (GET /brqn HTTP/1.1) ()
< 1508164351 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :hmm no
< 1508164362 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :`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);
< 1508164363 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :collision: 14243f9b (GET /brqn HTTP/1.1) (GET /adwd HTTP/1.1)
< 1508164366 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :like that
< 1508164370 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :ais523: ^
< 1508164419 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :does `perl not handle single quotes? or are you just being overcautious with your character set?
< 1508164427 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that certainly seems to run fast enough, at least
< 1508164452 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508164454 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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.
< 1508164479 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :Windows uses double quotes to escape, I think
< 1508164485 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :ah right, so the single quotes go through literally
< 1508164525 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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.
< 1508164532 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :It would need 2**32 tries.
< 1508164538 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :right
< 1508164551 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that's a scale that's very sensitive to the complexity of the operations you're performing
< 1508164556 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :yep
< 1508164573 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :`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);
< 1508164590 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :48 bits of collision might already be too much for HackEgo
< 1508164592 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :It would need slightly more than that, right?
< 1508164605 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I remember that 1.2 * sqrt(n) was a better approximation.
< 1508164607 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :shachaf: sure, that's just order of magnitude
< 1508164612 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :and it's random anyway
< 1508164621 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Er, right.
< 1508164627 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :1.2 * sqrt(n) was only for a 50% chance
< 1508164710 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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)
< 1508164717 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :`perl -E say ln(2)
< 1508164718 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :Undefined subroutine &main::ln called at -e line 1.
< 1508164720 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :`perl -E say log(2)
< 1508164721 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :0.693147180559945
< 1508164727 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :right, that looks like the right number
< 1508164738 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :we can approximate n(n+1) as n² pretty easily
< 1508164756 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so n²×2÷ln(2)
< 1508164760 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :`perl -E say log(2)*2
< 1508164761 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :1.38629436111989
< 1508164772 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so on this approximation it's more like 1.4
< 1508164855 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I was at a lecture where someone derived it once but I don't remember the details now.
< 1508164859 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I should go to sleep, it's almost 7.
< 1508164890 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :shachaf: US west coast?
< 1508164911 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :it's not hard to derive it
< 1508164912 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508164928 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :right now it's UTC, London, Washington DC, and Los Angeles
< 1508165031 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes.
< 1508165085 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :b_jonas: If you're doing these attacks on a larger scale you can also be clever and use less memory.
< 1508165087 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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
< 1508165093 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :subtract form the local time that is
< 1508165116 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :shachaf: and more parallelism too
< 1508165133 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :which isn't obvious because you still need a hash table or something
< 1508165133 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :`ctcp b_jonas time
< 1508165134 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :/home/hackbot/hackbot.hg/multibot_cmds/lib/limits: line 5: exec: ctcp: not found
< 1508165137 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :err
< 1508165150 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I'm in the Paris time zone
< 1508165174 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :right, I'd figured that out mathematically when ctcp wasn't helping
< 1508165193 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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
< 1508165197 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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)
< 1508165217 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :No, it switches to that at Romania
< 1508165316 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :and Greece and Bulgaria
< 1508165340 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :oh, and Finland too
< 1508165343 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I always forget that
< 1508165366 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :those are about the only places that use that timezone
< 1508165397 0 :AnotherTest!~turingcom@ptr-82l26zcfapjo07eqrsv.18120a2.ip6.access.telenet.be JOIN :#esoteric
< 1508165445 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :Ok, actually the three Baltic states are using it too, and possibly Ukraine
< 1508165516 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :That's actually a lot of places I guess.
< 1508165668 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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.
< 1508165771 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oh, hmm, looks like the prefix and suffix I need is actually just the null string
< 1508165774 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :well, that makes things a lot simpler
< 1508165834 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :wait, no, there's a salt
< 1508165838 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :`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);
< 1508165839 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :collision: 1a7d5bb0 (bloh) (hlx)
< 1508165867 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :or should be, I'm not sure this code is actually using it
< 1508165912 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :good thing I looked at that bit of the code!
< 1508166865 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :b_jonas: 40-bit collision: cthex, bdllm
< 1508166881 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :going significantly beyond this seems unviable in Perl, it uses too much memory
< 1508166890 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I might try switching to Rust
< 1508166899 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :and/or borrowing a more powerful computer from the university
< 1508167330 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :"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…
< 1508167370 0 :imode!~imode@unaffiliated/imode JOIN :#esoteric
< 1508167458 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :ACTION has an idea, and does a web search for "hqwj ever"
< 1508167540 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :there is one relevant result but it doesn't contain a generalisation to 64 bits
< 1508167553 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :* "hgwj ever"
< 1508167565 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I typed it correctly first time in the search box
< 1508167585 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :it is fairly problematic for this that "ever" is a real word :-(
< 1508167601 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Or a better algorithm?
< 1508167627 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508167682 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I wonder if using a database for this would make sense?
< 1508167779 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But it seems people have algorithms that don't require you to store every input and hash.
< 1508167795 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :right
< 1508167816 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508167822 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :you found it once already so you can find it again
< 1508167834 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Now that I know why "Pollard's rho algorithm" is called that I think the name is pretty silly.
< 1508167987 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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)
< 1508168061 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :not in this case, unless we convert the input to be alphabetical between the iterations
< 1508168078 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :which seems like it might be fairly slow? it's a clever trick, though
< 1508168095 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Convert the input to be alphabeticaal?
< 1508168100 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :come to think of it, you could actually do this in constant memory
< 1508168108 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :via the tortoise-and-hare algorithm for finding a cycle in a linked list
< 1508168152 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508168169 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :that gives you a chain of truncated hashes which has to repeat eventually (because there are only finitely many possibilities for the truncated hash)
< 1508168191 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :ais523: you can even swap the order of the two operations for smaller (probably) intermediate results
< 1508168192 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :That's where the name "rho" comes from. Because a linked list with a cycle in it looks like ρ
< 1508168197 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508168215 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :shachaf: that's ridiculous :-P
< 1508168224 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I agree.
< 1508168272 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :it's very visual
< 1508168450 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :That's hard to parallelize, though.
< 1508168466 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But apparently people have more tricks for that.
< 1508168472 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :no, it's trivial, just start from n random values
< 1508168477 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508168558 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :which is what you'd need to nkow
< 1508168559 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :*know
< 1508168669 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508168676 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :then just start from the start and stop at the appropriate point
< 1508168848 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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.
< 1508168887 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I'm not thinking very well right now. I should go to sleep.
< 1508168893 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oh yes, I think that's what my approach would simplify to if I actually did the maths?
< 1508168895 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :shachaf: do it
< 1508168898 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But here's a paper discussing it: http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf
< 1508168959 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :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)
< 1508168997 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(And by speedup I mean expected speedup, since everything here is probabilistic.)
< 1508169058 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes, it's a different version that I was thinking of, which uses that rainbow trick.
< 1508169097 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :sha256(015e2c85)=45faea71c83c8f73bbee1d07c4b2c3428b0c1b537aa964dd5492cb936d268184
< 1508169099 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But it's not that tricky there either.
< 1508169104 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :sha256(da90efdd)=45faea71f8e5a5698d74dacf7a7cfeaf7e1d771d14f51cc064a2778b836e0051
< 1508169114 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :looks like this algo works for the small (32-bit) test case
< 1508169129 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :`` 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'
< 1508169132 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :6a71fd18 \ da90efdd \ 015e2c85 \ 45faea71 \ 45faea71
< 1508169143 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :but I seem to be wrong, since the paper says that the speedup is only O(sqrt(n))
< 1508169202 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Were you expecting better than O(sqrt(n))?
< 1508169220 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Oh, you mean for parallelizing.
< 1508169241 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :I guess my analogy is flawed
< 1508169399 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :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
< 1508169403 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :is that just an utter fluke?
< 1508169434 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :0005a3be7429 against b0390e13d757, for those people who are interested
< 1508169474 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Are you measuring time or number of hashes?
< 1508169478 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :realtime
< 1508169484 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :but I wouldn't expect startup cost to be significant
< 1508169491 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :~15 seconds compared to ~30 seconds
< 1508169529 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :luck?
< 1508169549 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :I assume so, it's about a 1% chance I think
< 1508169562 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :those happen occasionally but it's still surprising when they do
< 1508169632 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Why only 1%?
< 1508169663 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :the times should differ by a factor of 256
< 1508169667 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :they actually differed by a factor of 2
< 1508169674 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :so the result is a factor of 100 away from what's expected
< 1508169737 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Not a factor of 16?
< 1508169754 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :My thinking must be jumbled right now.
< 1508169760 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :oh right, of course
< 1508169763 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :it's me who's confused
< 1508169766 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I guess I'll go to sleep. It's already light out. :-(
< 1508169767 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Ah.
< 1508169782 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :So more like a 12% chance. Less surprising.
< 1508169789 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But I should still sleep.
< 1508169963 0 :sleffy!~sleffy@c-24-7-67-0.hsd1.ca.comcast.net JOIN :#esoteric
< 1508170007 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :This distinguished point trick is pretty good.
< 1508170030 0 :ais523!~ais523@unaffiliated/ais523 PRIVMSG #esoteric :go to bed!
< 1508170753 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :that is the rainbow table trick
< 1508170784 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes.
< 1508170956 0 :ais523!~ais523@unaffiliated/ais523 QUIT :Quit: quit
< 1508171031 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :The bun-alert syntax is back!
< 1508171070 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`olist 1102
< 1508171071 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :olist 1102: shachaf oerjan Sgeo FireFly boily nortti b_jonas
< 1508171073 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :`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);
< 1508171075 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :collision: 63212655 (hgwj) (ever)
< 1508171078 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :ah
< 1508171101 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :`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);
< 1508171131 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :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
< 1508171158 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :" an obvious improvement in terms of memory usage is to just store the hash, then
< 1508171208 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :ais523: how exactly does an eventual repetition give you a collision?
< 1508171225 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :ah
< 1508171299 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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.
< 1508171319 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :and you get a quadratic gain from using 32 threads and a shared hash table.
< 1508171389 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :so that would be like 256 times faster than one thread
< 1508171392 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :no wait
< 1508171395 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :1024 times faster
< 1508171400 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :but 16 threads might be more realistic
< 1508171628 0 :imode!~imode@unaffiliated/imode QUIT :Ping timeout: 240 seconds
< 1508172119 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :clearly the math is wrong. otherwise you'd get a speedup from interleaving 32 such threads on a single processor...
< 1508172330 0 :int-e!~noone@int-e.eu PRIVMSG #esoteric :(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.)
< 1508173030 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :int-e: hm... yes, you're right
< 1508173052 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :so only 32 such threads
< 1508173105 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :and sure, you're consume memory faster, but eventually you'll need essentially the same amount of memory for single-threaded than multi-threaded
< 1508173351 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :only linear speedup then
< 1508173360 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :still should be worth
< 1508173846 0 :FreeFull!~freefull@defocus/sausage-lover JOIN :#esoteric
< 1508174359 0 :atrapado_!~atrapado@unaffiliated/atrapado JOIN :#esoteric
< 1508174524 0 :zseri!~zseri@i5E86D268.versanet.de JOIN :#esoteric
< 1508176201 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:14] for x in ["ccf506fc58ee23", "843c7fa058d321"]]'
< 1508176201 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :['a522d3c3f644a5', 'a522d3c3f644a5']
< 1508176272 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Someone else can do 64 bits, I guess.
< 1508177642 0 :Taneb!~Taneb@runciman.hacksoc.org PRIVMSG #esoteric :ACTION hello
< 1508177723 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Taneb is here to do 64 bits?
< 1508177930 0 :Taneb!~Taneb@runciman.hacksoc.org PRIVMSG #esoteric :I don't think so
< 1508178207 0 :jaboja!~jaboja@jaboja.pl JOIN :#esoteric
< 1508178582 0 :LKoen_!~LKoen@vbo91-1-82-238-218-67.fbx.proxad.net JOIN :#esoteric
< 1508178670 0 :LKoen!~LKoen@2a01:e35:2eed:a430:b4a3:26f8:3955:a3ca QUIT :Ping timeout: 252 seconds
< 1508179092 0 :LKoen_!~LKoen@vbo91-1-82-238-218-67.fbx.proxad.net QUIT :Remote host closed the connection
< 1508179125 0 :Phantom_Hoover!~phantomho@unaffiliated/phantom-hoover JOIN :#esoteric
< 1508179221 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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.
< 1508179238 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :But this is from a mental calculation that could be wrong.
< 1508179329 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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.
< 1508179352 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :Preferably a machine with fast RAM.
< 1508179401 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :And ideally compute digest quickly with GPU or something, so you get the digests as fast as you can access the main RAM.
< 1508179416 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :But just multiple cpu threads might be fast enough for that.
< 1508179789 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :What? Why do all that instead of using the distinguished point trick?
< 1508179996 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :shachaf: what's the "distinguished point trick"?
< 1508180134 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :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.
< 1508180164 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :If two hashes end up at the same distinguished hash, you go through the chain and find where they connect.
< 1508180178 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :shachaf: hmm
< 1508180184 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I'm not explaining it very well but you can read the paper I linked to above.
< 1508180190 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I should sleep but now it's too late to sleep.
< 1508180200 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :But if I don't sleep I'll regret it. And if I do sleep I'll regret it.
< 1508180209 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :how well does that parallelize?
< 1508180230 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :might work I guess
< 1508180233 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :The paper I linked is about parallelizing it.
< 1508180247 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :I guess it works pretty well if you use a central store for the distinguished points, and your chains are long enough.
< 1508180269 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :http://people.scs.carleton.ca/~paulv/papers/JoC97.pdf is this the paper?
< 1508180275 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Yes.
< 1508180286 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :let me see
< 1508180293 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :this trick always sounds like black magic
< 1508180344 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :What's black about this magic?
< 1508180372 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Just look at the diagram, it's pretty simple when it's pointed out.
< 1508180393 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :You don't even need to feed the output of the hash back into the hash, I guess.
< 1508180429 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Or maybe you do, I don't know.
< 1508180497 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I'm looking at https://pdaian.com/blog/collision-finding-the-maxwell-way/ now
< 1508180511 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I'm trying to understand the trick now
< 1508180579 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :whoa, I know that Maxwell
< 1508180640 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Though it's hardly his way, it's an old trick.
< 1508180648 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I don't understand how you find the first entry of the sequence that collides
< 1508180666 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :you can find one repetition in the sequence easily, but that's not enoguh
< 1508180677 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :oh, I see!
< 1508180700 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Once you have two short chains that end up at the same distinguished point, you can just scan through them.
< 1508180722 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :you store milestones to break the sequence to shorter part, and use the milestones to find the approxmiate first collision
< 1508180751 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :and then recompute and store the elements in the segments where the first collision must be
< 1508180771 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Right.
< 1508180780 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :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
< 1508180783 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :nice
< 1508180799 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :this way you never run out of memory
< 1508180808 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :nice trick
< 1508180811 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :Higher constant factor?
< 1508180900 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :as in, you don't actually use 2**16 times less memory, only like 2**12 times less or something
< 1508180925 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :hmm wait
< 1508180932 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :you could do with fewer milestones
< 1508180933 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :sorry
< 1508180942 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :then you actually need even less than 2**16 entries
< 1508180945 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :no wait
< 1508180950 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :you do need 2**16 milestones
< 1508180952 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I'm confused
< 1508181026 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :interesting, thank you for telling about this rho trick
< 1508181047 0 :b_jonas!~x@russell2.math.bme.hu PRIVMSG #esoteric :I had heard of it about prime factoring, but I don't think I realized it's useful for crypto collision finding like this
< 1508181169 0 :jaboja!~jaboja@jaboja.pl QUIT :Ping timeout: 248 seconds
< 1508181812 0 :Cthulhux!cthulhu@rosaelefanten.org QUIT :Changing host
< 1508181812 0 :Cthulhux!cthulhu@piratenpartei/ni/tux JOIN :#esoteric
< 1508182238 0 :\oren\!~oren@ec2-52-2-213-98.compute-1.amazonaws.com PRIVMSG #esoteric :yo guys hav u herd?
< 1508182271 0 :\oren\!~oren@ec2-52-2-213-98.compute-1.amazonaws.com PRIVMSG #esoteric :BFS is supposedly going to SSTO for testing
< 1508182284 0 :LKoen!~LKoen@2a01:e35:2eed:a430:9409:5791:18ec:23bf JOIN :#esoteric
< 1508182396 0 :zzo38!~zzo38@24-207-56-48.eastlink.ca PRIVMSG #esoteric :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.
< 1508182549 0 :zzo38!~zzo38@24-207-56-48.eastlink.ca PRIVMSG #esoteric :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.
< 1508182619 0 :zzo38!~zzo38@24-207-56-48.eastlink.ca PRIVMSG #esoteric :(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.)
< 1508182627 0 :Remavas-Hex!~Remavas@unaffiliated/remavas JOIN :#esoteric
< 1508182696 0 :Remavas!~Remavas@unaffiliated/remavas QUIT :Ping timeout: 252 seconds
< 1508182709 0 :zzo38!~zzo38@24-207-56-48.eastlink.ca PRIVMSG #esoteric :(Also, the checksum has been reduced to 16-bits in order to reduce the amount of overhead.)
< 1508182729 0 :Remavas-Hex!~Remavas@unaffiliated/remavas QUIT :Read error: Connection reset by peer
< 1508182746 0 :Remavas-Hex!~Remavas@unaffiliated/remavas JOIN :#esoteric
< 1508183192 0 :Remavas-Hex!~Remavas@unaffiliated/remavas QUIT :Read error: Connection reset by peer
< 1508183210 0 :Remavas-Hex!~Remavas@unaffiliated/remavas JOIN :#esoteric
< 1508183985 0 :sleffy!~sleffy@c-24-7-67-0.hsd1.ca.comcast.net QUIT :Ping timeout: 248 seconds
< 1508184665 0 :zseri_!~zseri@i5E86D092.versanet.de JOIN :#esoteric
< 1508184749 0 :Remavas-3!~Remavas@unaffiliated/remavas JOIN :#esoteric
< 1508184874 0 :zseri!~zseri@i5E86D268.versanet.de QUIT :Ping timeout: 252 seconds
< 1508184962 0 :Remavas-Hex!~Remavas@unaffiliated/remavas QUIT :Ping timeout: 246 seconds
< 1508185863 0 :zzo38!~zzo38@24-207-56-48.eastlink.ca PRIVMSG #esoteric :What you think of this, please?
< 1508187173 0 :SigmundYx!~quassel@196.185.75.98 JOIN :#esoteric
< 1508187699 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :`` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:16] for x in ["5fc2544f27bc209e", "aeaefd69151cba80"]]'
< 1508187700 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :['6eeafe59946b43c3', '6eeafe59946b43c3']
< 1508188333 0 :zseri_!~zseri@i5E86D092.versanet.de QUIT :Quit: Leaving
< 1508188471 0 :LKoen!~LKoen@2a01:e35:2eed:a430:9409:5791:18ec:23bf QUIT :Remote host closed the connection
< 1508189273 0 :sleffy!~sleffy@173-8-158-238-SFBA.hfc.comcastbusiness.net JOIN :#esoteric
< 1508190796 0 :imode!~imode@unaffiliated/imode JOIN :#esoteric
< 1508192316 0 :atrapado_!~atrapado@unaffiliated/atrapado QUIT :Quit: Leaving
< 1508194104 0 :jaboja!~jaboja@jaboja.pl JOIN :#esoteric
< 1508194479 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net JOIN :#esoteric
< 1508194549 0 :quintopia!~quintopia@unaffiliated/quintopia PRIVMSG #esoteric :coily
< 1508194744 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net PRIVMSG #esoteric :QUINTHELLOPIA!
< 1508194808 0 :shachaf!~shachaf@unaffiliated/shachaf PRIVMSG #esoteric :@tell ais523 `` python -c 'import hashlib; print [hashlib.sha256(x).hexdigest()[0:16] for x in ["5fc2544f27bc209e", "aeaefd69151cba80"]]'
< 1508194808 0 :lambdabot!~lambdabot@haskell/bot/lambdabot PRIVMSG #esoteric :Consider it noted.
< 1508194973 0 :SigmundYx!~quassel@196.185.75.98 QUIT :Remote host closed the connection
< 1508195219 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net PRIVMSG #esoteric :`5 w
< 1508195225 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :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
< 1508195236 0 :AnotherTest!~turingcom@ptr-82l26zcfapjo07eqrsv.18120a2.ip6.access.telenet.be QUIT :Ping timeout: 255 seconds
< 1508195343 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net PRIVMSG #esoteric :`n
< 1508195344 0 :HackEgo!~HackEgo@162.248.166.242 PRIVMSG #esoteric :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.
< 1508195599 0 :Remavas-3!~Remavas@unaffiliated/remavas QUIT :Ping timeout: 248 seconds
< 1508196205 0 :Sgeo!~Sgeo@ool-18b98627.dyn.optonline.net JOIN :#esoteric
< 1508197520 0 :boily!~alexandre@cable-192.222.236.157.electronicbox.net QUIT :Quit: COUNTING CHICKEN
< 1508197899 0 :oerjan!~oerjan@hagbart.nvg.ntnu.no JOIN :#esoteric
< 1508198209 0 :hppavilion[1]!~dosgmowdo@93-231-58-66.gci.net JOIN :#esoteric
< 1508198305 0 :sleffy!~sleffy@173-8-158-238-SFBA.hfc.comcastbusiness.net QUIT :Ping timeout: 252 seconds
< 1508198385 0 :imode!~imode@unaffiliated/imode PRIVMSG #esoteric :babble: I wonder what kinds of binary trees you could generate from repeatedly factoring a given number.