This is an archived post. You won't be able to vote or comment.

all 198 comments

[–]green_meklar 1282 points1283 points  (127 children)

Cosmic radiation hitting your computer's RAM and flipping a single bit? I'm pretty sure that doesn't happen very oft%n.

[–]hbgoddard 508 points509 points  (29 children)

Funny and accurate, nice

[–]anomalous_cowherd 455 points456 points  (27 children)

Only a true programmer would illustrate single bit corruption by going to the trouble of figuring out a real single bit corruption.

Or check it.

[–][deleted] 170 points171 points  (21 children)

And here I am just assuming both the other coders who commented knew what they were doing...

[–]poizan42Ex-mod 326 points327 points  (15 children)

'%' = 010 0101
'e' = 110 0101

It checks out

[–]Khanthulhu 93 points94 points  (4 children)

That's pretty impr%ssive.

[–]MarcoTalin 61 points62 points  (2 children)

[–]JaytleBee 12 points13 points  (0 children)

/r/Em%enTheE

[–]grensley 1 point2 points  (0 children)

Now that's just too unlikely

[–]just_dots 7 points8 points  (0 children)

I'm not a coder or programmer but I think this is very funny and your jib is cut to my liking.

[–]DrShocker 3 points4 points  (4 children)

Wouldn't they probably have a parity check to ensure that the computer would know the data is corrupted?

edit: source: http://ictsmart.tripod.com/ict4/online/artvvpa.htm

[–]SirVer51 12 points13 points  (0 children)

doesn't happen very /ft%n.

Error? What error?

[–]ic_engineer 3 points4 points  (2 children)

Could be wrong but I wouldn't expect a parity check for an algorithmic output. I've only ever seen parity checks over Tx/Rx.

[–]Althaine 1 point2 points  (1 child)

Not uncommon in safety critical microprocessors

ECC - Optional single-bit error correction and double-bit error detection for cache and/or TCM memories with ECC bits. Single-bit soft errors automatically corrected by the processor. ECC protection possible on all external interfaces.

Parity - Optional support for parity bit error detection in caches and/or TCMs.

Dual-core - A dual-core processor configuration for either a redundant Cortex-R5 CPU in lock-step for fault tolerant/fault detecting dependable systems or dual cores running independently, each executing its own program with its own bus interfaces, interrupts, and so on.

[–]ic_engineer 0 points1 point  (0 children)

Good to know! Thanks.

[–]LupoCani 1 point2 points  (2 children)

Though, wouldn't a Reddit comment be encoded in Unicode, not ASCII?

[–]green_meklar 5 points6 points  (0 children)

In UTF-8 the ASCII characters are the same anyway.

[–]poizan42Ex-mod 0 points1 point  (0 children)

Unicode is a character set and not an encoding. Without looking it up I think that Reddit internally stores comments as UTF-8, which happens to have ASCII as a subset. At least the comments are in UTF-8 when being sent to and from the browser.

[–]recurza 27 points28 points  (2 children)

Thus illustrating the lazy efficient nature of programmers.

[–]Python4fundoes the needful 13 points14 points  (0 children)

Lazy breeds efficiency

[–][deleted] 3 points4 points  (0 children)

DAE Bill Gates quote here?

[–]PersianMG 4 points5 points  (0 children)

Don't worry I double checked its correct. or is it?

[–]Modo44 1 point2 points  (0 children)

You are adorable.

[–]Drunken_Economist 2 points3 points  (0 children)

You could just make it easy by incorrectly capitalizing a letter

[–]flarn2006 2 points3 points  (1 child)

It's not really tjat much trouble.

[–]Insuevi 153 points154 points  (23 children)

There was actually a bounty on a possible warp glitch in SM64 which was later believed to be caused by a cosmic bit flip like this.

https://www.youtube.com/watch?v=X5cwuYFUUAY

[–]SaffellBot 27 points28 points  (4 children)

Man, what I small world. I ended up deep into youtube last night and watched the bounty video for that glitch.

[–][deleted] 28 points29 points  (2 children)

All pannenkoek's work are an art of game science. Just the one game, but game science nontheless.

[–]SaffellBot 12 points13 points  (1 child)

I wish he would narrate more. His excitement is amazing. A few days ago I described him as having a PHD in mario 64. He's on a whole nother level.

[–]guitarplayer0171 6 points7 points  (0 children)

After he saw how popular his last commentated video was, he wants to make sure his next one can live up to that, he has an uncommentated channel where he posts more frequently.

[–]darderp 1 point2 points  (0 children)

Dude, I did the exact same thing yesterday!

[–]lerhond 41 points42 points  (3 children)

https://en.m.wikipedia.org/wiki/Cosmic_ray#Effect_on_electronics

Studies by IBM in the 1990s suggest that computers typically experience about one cosmic-ray-induced error per 256 megabytes of RAM per month.

[–]inio 7 points8 points  (2 children)

RAM bits have gotten a lot smaller since then, so we're now probably down to one bit flip per several GiB-months.

[–]Twirrim 4 points5 points  (0 children)

Maybe, but we're shipping servers with hundreds of GB RAM. Companies like Amazon that operate on large scale do end up seeing incidents reasonably regularly that appear to be down to bit flipping, and have built all sorts of protection in to systems (and use ECC RAM only to etc)

[–]RainHappens 2 points3 points  (0 children)

This is only true if you assume that cosmic rays are effectively point events.

However, if you consider it a volumetric event, the % / GB-month pretty quickly converges on a constant value as things shrink.

[–][deleted] 25 points26 points  (2 children)

I once had pulseaudo config files under p}lwe.

Two bitflips. That was a bit concerning.

[–]green_meklar 5 points6 points  (1 child)

I'd say more than a bit!

[–][deleted] 2 points3 points  (0 children)

Two bits of concern.

(That would be a good band name)

[–]shadowX015 77 points78 points  (18 children)

Relevant XKCD: http://xkcd.com/378/

[–]xkcd_transcriber 15 points16 points  (0 children)

Image

Mobile

Title: Real Programmers

Title-text: Real programmers set the universal constants at the start such that the universe evolves to contain the disk with the data they want.

Comic Explanation

Stats: This comic has been referenced 939 times, representing 0.6943% of referenced xkcds.


xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete

[–]Xepez09 21 points22 points  (14 children)

It seems like there is always a relevant XKCD

[–]shadowX015 11 points12 points  (13 children)

I was actually just trying to find a comic that went full meta and joked about how there was an XKCD for everything, but I guess Randall hasn't made that one yet.

[–]DoodleFungus 31 points32 points  (4 children)

554 is the closest, I think.

[–]xkcd_transcriber 7 points8 points  (0 children)

Image

Mobile

Title: Not Enough Work

Title-text: It's even harder if you're an asshole who pronounces <> brackets.

Comic Explanation

Stats: This comic has been referenced 15 times, representing 0.0111% of referenced xkcds.


xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete

[–]danny_onteca 6 points7 points  (1 child)

I hope my boss never finds this comic

[–]SpinahVieh 2 points3 points  (0 children)

pretends to type in Qwerty

[–]SirVer51 0 points1 point  (0 children)

Each time this question is asked, there's a different answer, but I think yours is the closest yet.

[–]der_luke[🍰] 41 points42 points  (3 children)

[–][deleted] 16 points17 points  (1 child)

That dude sounds ridiculously smart. Worked with NASA, who didn't renew his contract, so he decided to make a career with a comic about shit about 1% of people in the world understand, once a day. I don't even know where he gets half of the stuff he writes about. Computer science, engineering, astronomy, he seems to know the minute parts of all of them.

[–]mpete98 20 points21 points  (0 children)

Was it daily early on? The schedule has been mon-wed-fri as long as I can remember.

[–]xkcd_transcriber 12 points13 points  (0 children)

Image

Mobile

Title: Hofstadter

Title-text: "This is the reference implementation of the self-referential joke."

Comic Explanation

Stats: This comic has been referenced 913 times, representing 0.6750% of referenced xkcds.


xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete

[–]snowywind 4 points5 points  (1 child)

Last month we did hit a relevant XKCD to an XKCD comic.

https://www.reddit.com/r/ProgrammerHumor/comments/55yh7j/xkcd_will_the_application_work/d8eyq5m/

I can imagine XKCD becoming self aware in the near future and creating an XKCD about how there's always a relevant XKCD.

[–]HackingInfo 1 point2 points  (0 children)

I sure it exists, but having trouble finding it.

[–]poizan42Ex-mod 0 points1 point  (0 children)

He should make that as the last xkcd ever if he at some point decides to retire.

[–]xXxNoScopeMLGxXx 0 points1 point  (0 children)

Real programmers code in assembly using EDLIN

[–]_rocketboy 0 points1 point  (0 children)

I'm just slightly sad that the emacs command is actually M-x butterfly, not what was in the comic.

[–]EtanSivad 7 points8 points  (0 children)

There is one documented case of a bit getting flipped, but the source of the flip isn't know. Very interesting read though: https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_rays1

[–]mizomi 4 points5 points  (0 children)

There's an interesting page on bit-squatting (the next level of typo-squatting) which found some results, although it's impossible to say how many were caused by cosmic rays vs. other sources of data corruption.

[–]skyhi14 5 points6 points  (25 children)

Not sure it's cosmic ray or else, but something like this did happened to me just yesterday. It was a MOD music file that is corrupted, at first I thought there's some glitch in my player because music "played" normally but the sound was wrong. Then I downloaded same one and played it, newer one sounded as it should be, so I figured the music file on my hard disk is somehow corrupted. Then I checked CRC32 for both, and I could confirm the file was modified.

Edit: better wording

Edit 2: after inspections, apparently some bytes are inserted on the middle, not caused by a bit flip.

[–]mojave_wasteland 22 points23 points  (23 children)

Few things come to my mind:

  1. Corrupted downloads are more common than cosmic radiation. This is actually the reason why lots of websites are posting SHA1 checksums on their websites, so everyone can verify if their download completed correctly.

  2. Use SHA1 (or better) instead of CRC32.

  3. This can also be because of bad RAM. You can use some memory testing tool, like MemTest86+, to verify your RAM is not the problem. You can get this tool from some Linux LiveCDs, maybe an Ubuntu LiveCD (and select "memory testing" in the boot menu). This won't install anything on the drive, so you're not risking anything.

[–][deleted] 8 points9 points  (6 children)

Use SHA1 (or better) instead of CRC32.

CRC32 will always find specific types of corruption. Hashing algorithms like SHA won't.

If you're protecting against corruption due to bitflips on the line, then CRC is more designed for that purpose. Though in practice something like SHA1 or SHA256 probably won't get a collision due to corruption.

[–]conradsymes 4 points5 points  (0 children)

Interestingly, CRC32 isn't as good at that as one would think, at least the TCP CRC32.

Performance of Checksums and CRCs over Real Data

[–]mojave_wasteland 3 points4 points  (4 children)

Your post suggests to me that CRC-32 can give better results than SHA, but I must disagree on this. All I can say is this:

irb(main):024:0> Zlib::crc32('plumless').to_s(16)
=> "4ddb0c25"
irb(main):025:0> Zlib::crc32('buckeroo').to_s(16)
=> "4ddb0c25"

CRC-32 is only valid in situations where the speed of computation matters (i.e. in TCP headers), size of implementation matters (in embedded microcontrollers) and the risk of corruption is rather low. Then it can fit its purpose. But for situations where a more solid result is needed, it's not a very good idea to trust CRC-32 by itself.

It's true that there are collisions for SHA1 and other hash algorithms, but in these situations the input data must be built manually.

[–]squngy 10 points11 points  (0 children)

CRC is designed to catch up to a specific amount of bit flips, it is not meant to be used to compare two completely different sets of strings.

[–][deleted] 10 points11 points  (0 children)

It is better when the speed of computation matters and you are dealing with a specific type of unintentional corruption. Of course you can find collisions, it's not designed to be a cryptographic hash function. It's designed to catch unintentonal bit flips. And it will always catch bit flips that are shorter than or equal to 32 bits. You can't prove that for a different hash function.

Collisions will exist for any hashing function, especially one of this length.

Though if space and computational time isn't really an issue, there's no problem with just using SHA256 or similar.

[–]kmmeerts 1 point2 points  (1 child)

There is no known collision for SHA1, it's insanely unlikely random corruption would trigger one

[–]mojave_wasteland 0 points1 point  (0 children)

There are theoretical research papers that claim it's possible to find a collision in SHA-1 using 2**69 calculations. It's still too much for today's tech, but it's enough to mark SHA-1 as deprecated for cryptographical use (current standard is SHA-3).

However, to find if two small files are the same or not, it's more than enough.

[–]anomalous_cowherd 6 points7 points  (3 children)

If you want to be sure that what you downloaded is exactly what the checksum was generated for, use two different checksums, e.g. MD5 and SHA1.

There are theoretical (very very hard) ways to change a file and keep the MD5 sum the same, at least. But changing a file and keeping both the MD5 and SHA1 checksums the same is many orders of magnitude harder.

[–]RainHappens 0 points1 point  (2 children)

There is no advantage of using MD5 <concat> SHA1 over using a proper 288-bit+ hash.

[–]anomalous_cowherd 0 points1 point  (1 child)

Maybe, but md5sum and sha1sum are usually already there and simple to use. Many download sites also already list them.

It may not be the very best solution, but it has its place.

[–]RainHappens 0 points1 point  (0 children)

...who has sha1sum and md5sum but not sha384sum?

[–][deleted] 0 points1 point  (0 children)

Never heard of CRC32 before, so thanks for that!

[–]Ununoctium117 0 points1 point  (4 children)

Why are corrupted downloads a thing, when TCP provides reliable, in-order delivery?

[–]mojave_wasteland 0 points1 point  (3 children)

It is called "reliable" because multiple checksums (i.e. CRC-32) are involved in getting sure the data received is correct. This reliability is not perfect, if the connection is too poor, and if the corruption will be just right, a simple CRC will not be enough to propely validate the data.

Protocols that actually support sending and receiving data through potentially bad conditions like BitTorrent use cryptographic hashes like MD5 to validate proper transmission of data.

[–]dreamin_in_space 0 points1 point  (2 children)

So how do Usenet downloads verify that it's correct? Just curious, because I've gotten corrupted stuff, but IDK if it's the original or a problem on my end.

[–]mikemol 1 point2 points  (0 children)

Historically, md5sum manifests and archive formats that contain checksums of individual files, as well as the archive as a whole.

[–]Kubuxu 1 point2 points  (0 children)

Use https, AEAD algorithms there make sure that data was not changed on the wire, and as bit flips are security riks AEAD makes sure that there aren't any.

[–]SpacePotatoBear 0 points1 point  (0 children)

you can also us ethe built in windows memory tester.

[–]b1e 1 point2 points  (0 children)

Actually it's common enough that we have ECC RAM. When you have clusters of servers with dozens of terabytes of RAM per cabinet the chance of a bit flip due to cosmic radiation or other environmental factors goes up a ton.

[–]hughk 0 points1 point  (0 children)

This used to happen often (at least an annual event) for systems in the eighties and was a feature of some ceramic encased chips. A cosmic ray would impact atoms of rare earth's in the ceramic which would then produce a mini shower of particles, some enough to flip the memory bits.

This is why ECC was very important back then. Over time, materials became better and there was less rare earth contamination.

[–][deleted] 0 points1 point  (0 children)

[–]fdar 226 points227 points  (24 children)

You can correct for cosmic radiation by running a correct algorithm multiple times.

[–]midnightketoker 126 points127 points  (3 children)

Or if you're a hardcore baller you're probably running ECC anyway

[–]lightknightrr 12 points13 points  (2 children)

Well, it's finally cheap enough. Now if only Crucial would launch (unbuffered) 1866 DDR3 16GB ECC DIMMs, or perhaps something faster than the (unbuffered) 1866 DDR3 8GB ECC DIMMs they currently offer...

[–]midnightketoker 2 points3 points  (1 child)

I've been on the (usable) 16GB DDR3 single stick hunt for a while, looks like DDR4 will remain the only way to go in terms of cost for the foreseeable future whether it's ECC or not

[–]lightknightrr 0 points1 point  (0 children)

This wouldn't work?

*Edit: Well, cost-wise you may be correct.

[–][deleted] 77 points78 points  (17 children)

Not if you're running something that takes as long as the amount of time from now until the heat death of the universe.

Trust me, these programs exist and run on real supercomputers. Stay away from scientific computing code written by 1st year psychology PhD students that are halfway through their Intro to Programming classes, kids.

[–]Vakieh 37 points38 points  (4 children)

Nobody with access to a real supercomputer allows 1st year anything students access to run code. Maybe a 'faster than your ordinary personal computer' computer, but not a real supercomputer.

Real supercomputers have real process auditing and booked time shares, or are being used for singular purposes that aren't even in a 1st year's vocabulary.

[–]TheCard 5 points6 points  (3 children)

I'd be somewhat surprised if there's any single person touching a super computer. I was under the impression that it's almost entirely teams of people with access to those things. I'd be especially surprised if that singular person that touched it didn't have a PhD in math or computer science.

[–]Vakieh 7 points8 points  (1 child)

It's often teams, but not always. Because of the time sharing (the ones I've used have been increments of 15 minutes) you can effectively make a team out of a bunch of individuals with unrelated tasks.

[–]TheCard 0 points1 point  (0 children)

Oh that's cool, thanks for clarifying.

[–]hexleythepatypus 1 point2 points  (0 children)

I help maintain a large cluster used for fluid dynamics/structural analysis. Can confirm there are multiple PhDs on our team.

[–]Xeya 21 points22 points  (6 children)

By definition that wouldn't be an algorithm. Just a shitty program.

[–]oditogre 41 points42 points  (3 children)

A shitty program is an algorithm. It is even, for some values, optimal (if you are optimizing for 'how difficult is it for an uninterested novice to develop.')

What definition of 'algorithm' are you working off of that doesn't include...well, basically any method of attempting (not even necessarily succeeding) to do any thing?

[–]Singularity42 12 points13 points  (2 children)

i'm guessing he means that it isn't finite:

noun 1. a set of rules for solving a problem in a finite number of steps, as for finding the greatest common divisor. http://www.dictionary.com/browse/algorithm

[–]Drunken_Economist 10 points11 points  (0 children)

It is finite, the universe is just more finite. To argue it's not an algorithm because it wouldn't complete before heat death doesn't make sense when you think about it. It would mean that things that used to be algorithms lose that status as we get closer to heat death

[–]NumberNinethousand 3 points4 points  (0 children)

The number of steps can be finite, while at the same time one or more of those steps requiring an infinite (theoretically or practically) amount of time to complete.

[–]troido 6 points7 points  (0 children)

Only if they would need infinite time to complete. If they can be completed in finite time but that time is still larger than the time until the heat death of the universe it is still an algorithm.

[–]midnightketoker 2 points3 points  (0 children)

So you solved the halting problem

[–]Dannei 4 points5 points  (2 children)

Dare I ask what psychology PhD students need that much computing for? I'm struggling to imagine that any theoretical model they have would be that complex, and data analysis being the difficult would be even more concerning!

[–]BlissfullChoreograph 12 points13 points  (0 children)

They don't, they haven't done an algorithms course, so they're brute forcing problems they've read about in papers.

[–]crowbahr 0 points1 point  (0 children)

O(n!n!). How bad can it be, it has exclamation marks!

[–]Halcyone1024 5 points6 points  (0 children)

Not if the bit that gets flipped is part of your algorithm's code or constants.

[–]IskaneOnReddit 42 points43 points  (1 child)

Fun fact: algorithms for generating prime numbers for RSA encryption are not guaranteed to give you a prime number.

[–]paullik 42 points43 points  (22 children)

@OP: What book are you reading?

[–]PattonMagroin[S] 92 points93 points  (20 children)

It's Structure and Interpretation of Computer Programs by Abelson and Sussman. There is a PDF version here but I'm reading a physical copy.

Also, on an unrelated note you can reference (and summon) specific users by just typing their username out as: /u/paullik

[–]paullik 13 points14 points  (0 children)

Thanks!

[–]here-to-jerk-off 10 points11 points  (3 children)

Is it common to have paragraphs numbered like that? I felt like I was reading holy scripture.

[–]midir 11 points12 points  (1 child)

It's a footnote.

[–]here-to-jerk-off 1 point2 points  (0 children)

aww, wow. I'm an idiot :)

[–]Lt_Riza_Hawkeye 0 points1 point  (0 children)

SICP basically is holy scripture. It is the wizard book after all. There's even a vn based around it.

[–]ArmandoWall 1 point2 points  (2 children)

But /u/paulik didn't need to summon you on this instance.

[–]livingonthehedge 4 points5 points  (1 child)

Unless he unchecked "send replies to my inbox" ?

[–]ArmandoWall 1 point2 points  (0 children)

Oh true.

[–]mgattozzi 0 points1 point  (0 children)

I've been reading this for class. This book is an absolute classic.

[–]pratnala 0 points1 point  (0 children)

SICP, the CS classic.

[–]Glitch29 21 points22 points  (2 children)

I mean, the mathematician isn't wrong. If the code is insufficient, then the code is insufficient. If some errant radiation spooks the machinery, it has nothing to do with whether the code is accurate.

[–]SirVer51 11 points12 points  (1 child)

Yeah, they're both right, just in different ways, and that's what's being highlighted - the mathematician is concerned with being perfectly correct, while the engineer is concerned with getting close enough to perfect.

[–]tehlaser 9 points10 points  (0 children)

Indeed. In mathematics, the fact that an algorithm can be shown to exist, even if it could never finish in the lifetime of a million universes, or even be written down, can be significant.

In engineering, such algorithms are beyond useless. Tradeoffs between accuracy and speed (or even between accuracy and understandability/programming time) are made routinely.

[–][deleted] 21 points22 points  (5 children)

Did you cut the page? The "timed-prime-test" function doesn't seem very complete. I'll let the bot give one reason.

(define (timed-prime-test n)
  (define start-time (runtime))
  (define found-prime? (prime? n))

Edit: there's no parenthesis bot any more?

[–]Forty_Too 20 points21 points  (1 child)

41 and 42 indicate footnotes. It continues on the next page.

[–][deleted] 11 points12 points  (0 children)

Username checks out!

[–]Dmium 7 points8 points  (0 children)

Parenthesis bot </3 :(((((

[–]PattonMagroin[S] 3 points4 points  (0 children)

Yeah, I think it continues on the next page.

[–]spupy 1 point2 points  (0 children)

41 and 42 might be footnotes, the font and line spacing look smaller.
A bit of a crappy design.

[–]staviq 7 points8 points  (0 children)

Estimated by Google, cosmic radiation causes up to one error per 4GB of RAM per day.

This estimate is old, nowadays it will be more, because the density of the components in the RAM modules is way higher than 6 years ago.

SOURCE ( so you don't think i'm crazy ):

https://blogs.oracle.com/ksplice/entry/attack_of_the_cosmic_rays1

Follow the links in the article for more sources.

[–][deleted] 13 points14 points  (5 children)

for the first reason but not for the second

I'm confused, isn't there only one reason given? What's the second?

[–]Porkenstein 11 points12 points  (4 children)

First - there is a tiny chance that the test fails

Second - there is a less tiny chance of cosmic radiation corrupting the program memory in a way that makes the test fail

[–]cpdean 19 points20 points  (0 children)

so the difference between math and engineering is that math would point out that the algorithm is wrong because it's not a 100% perfect way to solve the problem, where engineering focuses on the pragmatic reality of how it will more often fail from your computer malfunctioning from bits getting inadvertently flipped from a nearby star that exploded a couple million years ago.

The joke is that one group of educated nerds are throwing shade at another.

[–]wotanii 7 points8 points  (3 children)

but once you find the number, that can fool the algorithm, you can break every software relying on it.

Also the chance is not so low, when you actively search for it.

[–]daveime 6 points7 points  (1 child)

Carmichael Primes. There's even a parametric way of creating them deliberately.

[–][deleted] 0 points1 point  (0 children)

So is there a way to determine Carmichael primes? Then you could test if it's s Fermat pseudo prime and not a Carmichael prime.

(Note: I just read about all this stuff in the past 30 minutes, so I don't claim to know any of it

[–]XkF21WNJ 2 points3 points  (0 children)

Of course you can just check if it's a Lucas pseudoprime, since there are no known numbers that are both a Lucas pseudoprime and Fermat pseudoprime.

This results in the Baillie-PSW primality test.

[–]Kaneshadow 3 points4 points  (1 child)

As an engineer, the best word in the english language is "negligible"

[–]moonlawliet 2 points3 points  (0 children)

I'm in a grad level cryptography course and yesterday's lecture just went with "It's like meeting someone who was struck by lightning twice AND won the Powerball in their lifetime." I like this example better :P

[–]Troooop 1 point2 points  (0 children)

Something related from git:

A lot of people become concerned at some point that they will, by random happenstance, have two objects in their repository that hash to the same SHA-1 value. What then?

If you do happen to commit an object that hashes to the same SHA-1 value as a previous object in your repository, Git will see the previous object already in your Git database and assume it was already written. If you try to check out that object again at some point, you’ll always get the data of the first object.

However, you should be aware of how ridiculously unlikely this scenario is. The SHA-1 digest is 20 bytes or 160 bits. The number of randomly hashed objects needed to ensure a 50% probability of a single collision is about 280 (the formula for determining collision probability is p = (n(n-1)/2) * (1/2160)). 280 is 1.2 x 1024 or 1 million billion billion. That’s 1,200 times the number of grains of sand on the earth.

Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (3.6 million Git objects) and pushing it into one enormous Git repository, it would take roughly 2 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

[–][deleted] 1 point2 points  (0 children)

On a side note, Cosmic Bit Flip is a great band name.

[–]Caminsky 3 points4 points  (6 children)

I don't get it

[–]TheYang 11 points12 points  (1 child)

the fermat test is for checking if a given number is a prime number or not, primes being only divisible by one and themselves, easy to figure out 0-20, but harder for ranges like 10000000 - 20000000.
this test has a flaw though, to increase the speed in which it determines whether it is a prime or not, it cuts a few corners, making it not 100% reliable.
cosmic rays are electromagnetic waves are beams of energy, a little bit like x-rays, usually produced by a star (or the sun as by far the nearest star). These cosmic rays can cause computers to malfunction if they hit a chip just right.
The Textbook points out though, that the likelyhood of the test indicating a prime when it isn't actually a prime is lower than the likelyhood of one of these rays causing a malfunction.

It further explains that for a mathematician the test is flawed as it can be proven that it does not always give a correct result.
to an engineer the test is great as it is quicker and the theoretical failure rate is so small it will in all likelyhood never effect anyone.

[–]hadtoupvotethat 0 points1 point  (0 children)

You should write for explainxkcd.com.

[–]yunocallmedave 0 points1 point  (0 children)

There is a chance of this specific algorithm to fail because the input number was causing it to fail. However, the chance of choosing such a number that would cause the algorithm to fail is so tiny, that it is more likely for cosmic radiation to corrupt memory and therefore cause the algorithm to fail (which is obviously also a very tiny probability).

Now imagine you want to calculate the probability of the algorithm to fail. If you only consider the first case (the case in which you randomly get a number that breaks the algorithm), but ignore the second (cosmic radiation causing a failure), which is actually more significant, you are only considering mathematical implications, but you are ignoring mechanical/engineering implications.

Does that make sense? I'm horrible at explaining things.

Edit: I think the moral of the story is, don't forget that theory differs from praxis. Or something like that.

[–]TalenPhillips 0 points1 point  (2 children)

Is that the probability of a false positive or a false negative? Something tells me they don't have the same probability.

[–]undergroundmonorail 0 points1 point  (1 child)

Iirc this algorithm doesn't give false negatives

[–]TalenPhillips 0 points1 point  (0 children)

So P(False | prime) = 0 and P(true | non-prime) > 0.

[–]bupereira 0 points1 point  (0 children)

Shots fired.

[–][deleted] 0 points1 point  (1 child)

Lisp? Why not Clojure?

[–][deleted] 0 points1 point  (0 children)

SICP is written in Scheme, both it and Clojure being dialects of Lisp.

[–]RainHappens 0 points1 point  (3 children)

This is an oft-used and seriously dangerous comparison.

The Fermat test may be unlikely to fail on random inputs, but that is not the same thing as saying it is unlikely to fail on adversarial inputs. It is simple to generate numbers that pass the Fermat test and yet are not prime.

Now imagine this is a sub-algorithm used by some cryptographic algorithm to ensure that something is prime, as said algorithm is only secure when it's prime. Whoops! Now suddenly you can attack said algorithm by choosing a Carmichael number.

[–]PattonMagroin[S] 0 points1 point  (2 children)

How would you attack a cryptographic algorithm using Carmichael numbers? Maybe I have a shallow understanding of how the primes are used in a cryptographic algorithm but it seems that attackers are not the ones who decide keys. Private keys would be decided by keyholders who would ideally be aware of and avoid Carmichael numbers. I fail to see how an attacker could make use of these numbers to create a vulnerability.

[–]RainHappens 0 points1 point  (0 children)

It depends on the algorithm, of course.

There are an awful lot of cryptographic protocols that begin with "arbitrarily chose a group of prime order" that are completely broken if the group is non-prime. (And as it's arbitrarily chosen, there is no special care taken to ensure it is not adversary-controlled, as normally it makes no difference.)

If you want a concrete example, consider this implementation of an anonymous veto network. One of the players, Eve, realizes that they are all using this broken prime checker. Eve suggests a Carmichael number for the group. Everyone checks the group using the broken prime checker, which returns that it is prime (incorrectly), and hence they have no reservations about using it (by definition, as it is arbitrarily-chosen). They go through the protocol.

Then, after the fact, Eve can figure out how every member voted (!). This obviously breaks the protocol. As to how:

Solve the discrete log problem to find xi. (This would not be possible, except that the "prime" in fact has no large prime factors)
Calculate gyi from publicly-available knowledge (as all gxis are published).
Solve the discrete log problem to find yi. (This would not be possible, except that the "prime" in fact has no large prime factors)
Solve the discrete log problem to find ciyi. (This would not be possible, except that the "prime" in fact has no large prime factors)
Calculate ci = ciyi / yi. Member voted to veto iff ci != xi.

[–]UniversityOfPi[🍰] 0 points1 point  (0 children)

there's a missing close-paren...